การต่อภาษาปรกติ
ให้ภาษาปรกติสองภาษา L1, L2 จะพิสูจน์ว่าการต่อภาษาทั้งสอง (concatenation) L = L1 ∘ L2 เป็นภาษาปรกติด้วย
การต่อภาษาคืออะไร
การต่อสตริงสองสตริง “010” และ “1111” จะได้สตริง “0101111” การต่อภาษาจึงให้ภาษาใหม่ ซึ่งสร้างโดยนำสตริงทุกสตริงจากภาษาหนึ่งมาต่อกับสตริงทุกสตริงจากอีกภาษาหนึ่ง การต่อสตริงสองสตริงและการต่อภาษาสองภาษาเขียนแทนด้วยวงกลมเล็ก ∘ จากนั้นนิยามการต่อภาษา L1 และ L2 ได้ดังนี้:
แนวคิดของการพิสูจน์
มีภาษาปรกติสองภาษา L1, L2 และออโตมาตาสองตัวที่ยอมรับภาษาเหล่านี้:
จะสร้างออโตมาตาแบบนอนดีเทอร์มินิสติก A = ⟨Q, Σ, δ, q, F⟩ ที่ “มีออโตมาตาทั้งสอง A1 และ A2 อยู่ภายใน” แนวคิดหลักคือ เริ่มให้ออโตมาตา A1 อ่านสตริง และเมื่อออโตมาตา A1 ไปถึงสถานะสิ้นสุด ก็ลองให้ออโตมาตา A2 ยอมรับส่วนที่เหลือของสตริง ถ้าออโตมาตานี้ยอมรับส่วนนั้นของสตริงด้วย ออโตมาตา A ก็ยอมรับสตริงนั้น
ตัวอย่าง
ให้ออโตมาตา A1 ต่อไปนี้ยอมรับสตริงไม่ว่างที่ประกอบด้วยเลข 0 เท่านั้น และสตริงที่ขึ้นต้นด้วยเลข 1 แล้วตามด้วยเลข 0 เท่านั้น (1, 10, 100, …):
และให้ออโตมาตา A2 ต่อไปนี้ยอมรับสตริงที่ลงท้ายด้วย 01:
เชื่อมออโตมาตาทั้งสองโดยเพิ่มการเปลี่ยนสถานะแบบเอปไซลอนจากทุกสถานะสิ้นสุดของออโตมาตา A1 ไปยังสถานะเริ่มต้นของออโตมาตา A2 แล้วเปลี่ยนสถานะสิ้นสุดของ A1 ให้เป็นสถานะธรรมดา สถานะเริ่มต้นของออโตมาตาใหม่ทั้งตัวคือสถานะเริ่มต้นของออโตมาตา A1:
ออโตมาตาจะทำงานอย่างไร เริ่มจำลองการทำงานของออโตมาตา A1 ถ้าเปลี่ยนไปที่สถานะที่เคยเป็นสถานะสิ้นสุด q1 หรือ q2 ก็รู้ว่าออโตมาตา A1 ยอมรับส่วนหนึ่งของสตริงนี้ เพื่อให้สตริงทั้งสตริงอยู่ในภาษา L1 ∘ L2 ส่วนที่เหลือของสตริงต้องเป็นที่ยอมรับของออโตมาตาตัวที่สอง A2 ด้วย ด้วยเหตุนี้จากทุกสถานะที่เคยเป็นสถานะสิ้นสุดจึงมีการเปลี่ยนสถานะแบบเอปไซลอนไปยังสถานะเริ่มต้นเดิมของออโตมาตา A2
ยกตัวอย่างสตริง 0001 สตริงนี้อยู่ในการต่อภาษาทั้งสอง เพราะเกิดได้จากการต่อสตริง 00 ∘ 01 แต่ก็เกิดได้จากการต่อสตริง 0 ∘ 001 เช่นกัน ในออโตมาตานี้จำลองได้ทั้งสองแบบ ออโตมาตาอาจเดินตามเส้นทางนี้:
ในเส้นทางนี้ออโตมาตาจะ “ยอมรับ” ส่วน 00 ของสตริงก่อน แล้วจึงยอมรับส่วน 01 หรืออาจเดินตามเส้นทางนี้:
ซึ่งออโตมาตาจะ “ยอมรับ” ส่วน 0 ของสตริงก่อน แล้วจึงยอมรับส่วน 001 แน่นอนว่าทั้งสองกรณีไปถึงสถานะสิ้นสุด p2
ขั้นตอนในรูปนัย
กล่าวอีกครั้ง: มีภาษาปรกติสองภาษา L1, L2 และออโตมาตาสองตัวที่ยอมรับภาษาเหล่านี้:
สร้างออโตมาตาแบบนอนดีเทอร์มินิสติก A = ⟨Q, Σ, δ, q, F⟩ โดยที่
- Q = Q1 ∪ Q2 (สมมติด้วยว่า Q1 ∩ Q2 = ∅)
- Σ= Σ1 ∪ Σ2
- q = q0
- F = F2
สร้างฟังก์ชันการเปลี่ยนสถานะ δ ทีละกรณี:
แหล่งอ้างอิง
สารบัญ: สมบัติปิดของภาษาปรกติ, ยูเนียนของภาษาปรกติ, อินเตอร์เซกชันของภาษาปรกติ, ผลต่างของภาษาปรกติ, คอมพลีเมนต์ของภาษาปรกติ, การต่อภาษาปรกติ, ส่วนปิดคลุมของภาษาปรกติ