✖

ส่วนปิดคลุมของภาษาปรกติ

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

ส่วนปิดคลุมของภาษาคืออะไร

ส่วนปิดคลุมของภาษา L (Kleene star) เขียนแทนด้วย L∗ ส่วนปิดคลุมประกอบด้วยสตริงทั้งหมดที่สร้างได้จากการต่อสตริงจำนวนจำกัดจากภาษา L นิยามส่วนปิดคลุมได้เป็น:

L∗={a1∘a2∘⋯∘an|ai∈L,n∈N0}

โดยที่ ∘ แทนการดำเนินการต่อ ส่วนปิดคลุมมีสตริงว่าง ϵ อยู่ด้วย

ขั้นตอนในรูปนัย

จะทำคล้ายกับกรณีการต่อภาษามาก เพียงแต่แทนที่จะเชื่อมออโตมาตาสองตัวที่ต่างกัน จะเชื่อมออโตมาตาตัวเดียวเข้ากับตัวเอง คือลากการเปลี่ยนสถานะแบบเอปไซลอนจากสถานะสิ้นสุดของออโตมาตาไปยังสถานะเริ่มต้นของออโตมาตา อย่างไรก็ตาม ส่วนปิดคลุมต้องมีสตริงว่างด้วย จะทำอย่างไร อาจทำให้สถานะเริ่มต้นเป็นสถานะสิ้นสุด ออโตมาตาก็จะยอมรับสตริงว่าง แต่ก็อาจยอมรับสตริงอื่นที่ไม่ควรยอมรับด้วย ดังนั้นจะสร้างสถานะเริ่มต้นใหม่แทน แล้วลากการเปลี่ยนสถานะแบบเอปไซลอนจากสถานะเริ่มต้นใหม่นี้ไปยังสถานะเริ่มต้นเดิม

มีภาษาปรกติ L1 และออโตมาตาที่ยอมรับภาษานี้:

A1=⟨Q1,Σ1,δ1,q0,F1⟩

สร้างออโตมาตาแบบนอนดีเทอร์มินิสติก A = ⟨Q, Σ, δ, qs, F⟩ โดยที่

  • Q = Q1 ∪ {qs}
  • Σ= Σ1
  • F = F1 ∪ {qs}

นิยามฟังก์ชันการเปลี่ยนสถานะ δ ดังนี้:

δ(q,a)={δ1(q,a)ถ้าq∈Q1∧q∉F1δ1(q,a)ถ้าq∈F1∧a≠ϵδ1(q,a)∪{q0}ถ้าq∈F1∧a=ϵ{q0}ถ้าq=qs∧a=ϵ∅ถ้าq=qs∧a≠ϵ

ตัวอย่าง

ให้ออโตมาตา A1 ต่อไปนี้ยอมรับสตริง 00 หรือ 11:

ส่วนปิดคลุมของภาษา L(A1) จึงเป็นภาษาของสตริงทั้งหมดที่ประกอบด้วยคู่ 00 และ 11 เช่น 0000, 110011, 11110000 เป็นต้น ออโตมาตาที่ยอมรับส่วนปิดคลุมนี้สร้างได้โดยเพิ่มสถานะเริ่มต้นใหม่ qs ที่มีการเปลี่ยนสถานะแบบเอปไซลอนไปยังสถานะเริ่มต้นเดิม q0 และเพิ่มการเปลี่ยนสถานะแบบเอปไซลอนจากสถานะ q3 และ q4 ไปยังสถานะ q0:

ตรวจสอบได้ว่าออโตมาตานี้ยอมรับสตริง 0000, 110011, 11110000 จริง แต่ไม่ยอมรับ เช่น สตริง 1010

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

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