✖

ผลต่างของภาษาปรกติ

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

แนวคิด

ที่จริงแล้วแทบไม่มีอะไรต้องพิสูจน์ เพราะผลต่างของเซตสองเซตเป็นไปตามความสัมพันธ์ต่อไปนี้:

L1∖L2=L1∩L2′

โดยที่ L2′ คือคอมพลีเมนต์ของภาษา L2 จากบทเรื่องอินเตอร์เซกชันของภาษาปรกติและคอมพลีเมนต์ของภาษาปรกติ ทราบแล้วว่าภาษาปรกติปิดภายใต้การดำเนินการทั้งสองนี้ หมายความว่าสร้างออโตมาตาที่ยอมรับอินเตอร์เซกชันของภาษาและคอมพลีเมนต์ของภาษาได้ จึงใช้ออโตมาตาเหล่านี้สร้างออโตมาตาที่ยอมรับภาษา L1 ∩ L2′ ซึ่งก็คือภาษา L1 ∖ L2 นั่นเอง

ตัวอย่าง

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

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

จะสร้างออโตมาตาที่ยอมรับผลต่างของภาษาทั้งสอง จึงต้องมีออโตมาตา A2′ ซึ่งยอมรับคอมพลีเมนต์ของภาษาของออโตมาตา A2 เพียงสลับสถานะสิ้นสุดกับสถานะที่ไม่ใช่สถานะสิ้นสุด:

ตอนนี้เหลือเพียงสร้างออโตมาตา A ที่ยอมรับอินเตอร์เซกชันของภาษา L(A1) และ L(A2′):

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

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