✖

คอมพลีเมนต์ของภาษาปรกติ

ให้ภาษาปรกติ L จะพิสูจน์ว่าคอมพลีเมนต์ของภาษา L เป็นภาษาปรกติด้วย

คอมพลีเมนต์คืออะไร

คอมพลีเมนต์ของภาษา L คือสตริงทั้งหมดที่ไม่อยู่ในภาษา L คอมพลีเมนต์เขียนแทนด้วย L' นั่นคือ สำหรับอักษร Σ จะได้ว่า:

L′={w∈Σ∗|w∉L}

เช่น สำหรับภาษาของสตริงที่มีสัญลักษณ์ 1 อย่างน้อยหนึ่งตัว คอมพลีเมนต์คือภาษาของสตริงที่ไม่มีสัญลักษณ์ 1 เลยสักตัว

ขั้นตอน

ขั้นตอนง่ายมาก ให้ภาษาปรกติ L และออโตมาตาที่สมบูรณ์แบบดีเทอร์มินิสติก A = ⟨Q, Σ, δ, q0, F⟩ ที่ยอมรับภาษานี้ (ออโตมาตาจำกัดทุกตัวแปลงเป็นออโตมาตาเช่นนี้ได้) ออโตมาตา A' ที่ยอมรับ L' สร้างได้โดยสลับสถานะสิ้นสุดกับสถานะที่ไม่ใช่สถานะสิ้นสุด: A' = ⟨Q, Σ, δ, q0, Q ∖ F⟩ แค่นั้นก็เสร็จ

ตัวอย่าง

ให้ออโตมาตาเป็นดังนี้:

ออโตมาตาที่ยอมรับคอมพลีเมนต์ของภาษาจะมีลักษณะดังนี้:

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

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