อินเตอร์เซกชันของภาษาปรกติ
ให้ภาษาปรกติสองภาษา 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 ต้องยอมรับสตริงนั้น จะใช้แนวคิดเดียวกับที่ใช้กับยูเนียนของภาษาปรกติทุกประการ เพียงแต่เปลี่ยนเซตของสถานะสิ้นสุด
การเขียนให้เป็นรูปนัย
ให้ออโตมาตาสองตัว
สร้างออโตมาตา A = ⟨Q, Σ, δ, q, F⟩ ที่ยอมรับภาษา L(A1) ∩ L(A2) โดยที่
- Q = Q1 × Q2
- Σ= Σ1 ∩ Σ2
- q = ⟨q0, p0⟩
- F = F1 × F2
ฟังก์ชันการเปลี่ยนสถานะ δ เป็นไปตามความสัมพันธ์ต่อไปนี้:
ตัวอย่าง
ให้ออโตมาตา 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
แหล่งอ้างอิง
สารบัญ: สมบัติปิดของภาษาปรกติ, ยูเนียนของภาษาปรกติ, อินเตอร์เซกชันของภาษาปรกติ, ผลต่างของภาษาปรกติ, คอมพลีเมนต์ของภาษาปรกติ, การต่อภาษาปรกติ, ส่วนปิดคลุมของภาษาปรกติ