ส่วนปิดคลุมของภาษาปรกติ
ให้ภาษาปรกติ L จะพิสูจน์ว่าส่วนปิดคลุมของภาษา L เป็นภาษาปรกติด้วย
ส่วนปิดคลุมของภาษาคืออะไร
ส่วนปิดคลุมของภาษา L (Kleene star) เขียนแทนด้วย L∗ ส่วนปิดคลุมประกอบด้วยสตริงทั้งหมดที่สร้างได้จากการต่อสตริงจำนวนจำกัดจากภาษา L นิยามส่วนปิดคลุมได้เป็น:
โดยที่ ∘ แทนการดำเนินการต่อ ส่วนปิดคลุมมีสตริงว่าง ϵ อยู่ด้วย
ขั้นตอนในรูปนัย
จะทำคล้ายกับกรณีการต่อภาษามาก เพียงแต่แทนที่จะเชื่อมออโตมาตาสองตัวที่ต่างกัน จะเชื่อมออโตมาตาตัวเดียวเข้ากับตัวเอง คือลากการเปลี่ยนสถานะแบบเอปไซลอนจากสถานะสิ้นสุดของออโตมาตาไปยังสถานะเริ่มต้นของออโตมาตา อย่างไรก็ตาม ส่วนปิดคลุมต้องมีสตริงว่างด้วย จะทำอย่างไร อาจทำให้สถานะเริ่มต้นเป็นสถานะสิ้นสุด ออโตมาตาก็จะยอมรับสตริงว่าง แต่ก็อาจยอมรับสตริงอื่นที่ไม่ควรยอมรับด้วย ดังนั้นจะสร้างสถานะเริ่มต้นใหม่แทน แล้วลากการเปลี่ยนสถานะแบบเอปไซลอนจากสถานะเริ่มต้นใหม่นี้ไปยังสถานะเริ่มต้นเดิม
มีภาษาปรกติ L1 และออโตมาตาที่ยอมรับภาษานี้:
สร้างออโตมาตาแบบนอนดีเทอร์มินิสติก A = ⟨Q, Σ, δ, qs, F⟩ โดยที่
- Q = Q1 ∪ {qs}
- Σ= Σ1
- F = F1 ∪ {qs}
นิยามฟังก์ชันการเปลี่ยนสถานะ δ ดังนี้:
ตัวอย่าง
ให้ออโตมาตา A1 ต่อไปนี้ยอมรับสตริง 00 หรือ 11:
ส่วนปิดคลุมของภาษา L(A1) จึงเป็นภาษาของสตริงทั้งหมดที่ประกอบด้วยคู่ 00 และ 11 เช่น 0000, 110011, 11110000 เป็นต้น ออโตมาตาที่ยอมรับส่วนปิดคลุมนี้สร้างได้โดยเพิ่มสถานะเริ่มต้นใหม่ qs ที่มีการเปลี่ยนสถานะแบบเอปไซลอนไปยังสถานะเริ่มต้นเดิม q0 และเพิ่มการเปลี่ยนสถานะแบบเอปไซลอนจากสถานะ q3 และ q4 ไปยังสถานะ q0:
ตรวจสอบได้ว่าออโตมาตานี้ยอมรับสตริง 0000, 110011, 11110000 จริง แต่ไม่ยอมรับ เช่น สตริง 1010
แหล่งอ้างอิง
สารบัญ: สมบัติปิดของภาษาปรกติ, ยูเนียนของภาษาปรกติ, อินเตอร์เซกชันของภาษาปรกติ, ผลต่างของภาษาปรกติ, คอมพลีเมนต์ของภาษาปรกติ, การต่อภาษาปรกติ, ส่วนปิดคลุมของภาษาปรกติ