✖

อินเตอร์เซกชันของภาษาปรกติ

ให้ภาษาปรกติสองภาษา L1, L2 จะพิสูจน์ว่าอินเตอร์เซกชันของภาษาทั้งสอง L = L1 ∩ L2 เป็นภาษาปรกติด้วย

แนวคิดของการพิสูจน์

มีภาษาปรกติสองภาษา L1 และ L2 และต้องการพิสูจน์ว่าอินเตอร์เซกชัน L1 ∩ L2 เป็นภาษาปรกติ เนื่องจาก L1 และ L2 เป็นภาษาปรกติ จึงมีออโตมาตาจำกัด A1 และ A2 ที่ยอมรับภาษา L1 และ L2 นั่นคือ L(A1) = L1 และ L(A2) = L2 ต่อไปจะสร้างออโตมาตาจำกัด A ที่ยอมรับภาษา L1 ∩ L2 ซึ่งเป็นการพิสูจน์ว่าภาษา L1 ∩ L2 เป็นภาษาปรกติ

สตริงอยู่ในอินเตอร์เซกชันของภาษาถ้าสตริงนั้นอยู่ทั้งในภาษา L1 และในภาษา L2 นั่นคือทั้งออโตมาตา A1 และออโตมาตา A2 ต้องยอมรับสตริงนั้น จะใช้แนวคิดเดียวกับที่ใช้กับยูเนียนของภาษาปรกติทุกประการ เพียงแต่เปลี่ยนเซตของสถานะสิ้นสุด

การเขียนให้เป็นรูปนัย

ให้ออโตมาตาสองตัว

A1=⟨Q1,Σ1,δ1,q0,F1⟩A2=⟨Q2,Σ2,δ2,p0,F2⟩

สร้างออโตมาตา A = ⟨Q, Σ, δ, q, F⟩ ที่ยอมรับภาษา L(A1) ∩ L(A2) โดยที่

  • Q = Q1 × Q2
  • Σ= Σ1 ∩ Σ2
  • q = ⟨q0, p0⟩
  • F = F1 × F2

ฟังก์ชันการเปลี่ยนสถานะ δ เป็นไปตามความสัมพันธ์ต่อไปนี้:

∀q∈Q1,p∈Q2:δ(⟨q,p⟩,a)=⟨δ1(q,a),δ2(p,a)⟩

ตัวอย่าง

ให้ออโตมาตา A1 ต่อไปนี้ยอมรับสตริงทั้งหมดที่มีเลข 1 เป็นจำนวนคู่:

และออโตมาตา A2 ยอมรับสตริงที่มีเลข 0 เป็นจำนวนคี่:

จะสร้างออโตมาตาที่ยอมรับอินเตอร์เซกชันของภาษาทั้งสอง เซตของสถานะของออโตมาตานี้อยู่ในรูป Q = Q1 × Q2 สถานะเริ่มต้นคือสถานะ ⟨q0, p0⟩ และสถานะสิ้นสุดคือ F1 × F2:

ต่อไปเติมการเปลี่ยนสถานะโดยให้ δ(⟨q,p⟩, a) = ⟨δ1(q, a), δ2(p, a)⟩:

เช่น ในออโตมาตานี้ จากสถานะ ⟨q0, p0⟩ มีการเปลี่ยนสถานะสำหรับสัญลักษณ์ 0 ไปที่สถานะ ⟨q0,p1⟩ หมายความว่าออโตมาตา A1 มีการเปลี่ยนสถานะสำหรับสัญลักษณ์ 0 จากสถานะ q0 กลับมาที่สถานะ q0 และออโตมาตา A2 มีการเปลี่ยนสถานะสำหรับสัญลักษณ์ 0 จากสถานะ p0 ไปที่สถานะ p1

ลองทดสอบออโตมาตาได้ ออโตมาตาควรยอมรับสตริงอย่าง 110 หรือ 00000 (มีเลข 1 เป็นจำนวนคู่และมีเลข 0 เป็นจำนวนคี่) แต่ไม่ควรยอมรับสตริงอย่าง 11, 111, 1010

แหล่งอ้างอิง

สารบัญ: สมบัติปิดของภาษาปรกติ, ยูเนียนของภาษาปรกติ, อินเตอร์เซกชันของภาษาปรกติ, ผลต่างของภาษาปรกติ, คอมพลีเมนต์ของภาษาปรกติ, การต่อภาษาปรกติ, ส่วนปิดคลุมของภาษาปรกติ