✖

ยูเนียนของภาษาปรกติ

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

วิธีที่ใช้ออโตมาตาแบบดีเทอร์มินิสติก

แนวคิด

มีภาษาปรกติสองภาษา L1 และ L2 และต้องการพิสูจน์ว่ายูเนียน L1 ∪ L2 เป็นภาษาปรกติ เนื่องจาก L1 และ L2 เป็นภาษาปรกติ จึงมีออโตมาตาจำกัด A1 และ A2 ที่ยอมรับภาษา L1 และ L2 นั่นคือ L(A1) = L1 และ L(A2) = L2 ต่อไปจะสร้างออโตมาตาจำกัด A ที่ยอมรับภาษา L1 ∪ L2 ซึ่งเป็นการพิสูจน์ว่าภาษา L1 ∪ L2 เป็นภาษาปรกติ

ทำได้อย่างไร มีออโตมาตาจำกัด A1 และ A2 ที่ยอมรับแต่ละภาษาอยู่แล้ว กล่าวได้ว่าสตริง w อยู่ในภาษา L1 ∪ L2 ก็ต่อเมื่อออโตมาตา A1 หรือ A2 อย่างน้อยหนึ่งตัวยอมรับสตริงนั้น

ออโตมาตา A อาจทำงานดังนี้ สำหรับขาเข้า w จะจำลองการคำนวณของออโตมาตา A1 สำหรับขาเข้า w ถ้า A1 ยอมรับสตริง w แล้ว A ก็ยอมรับสตริง w ด้วย ถ้า A1 ปฏิเสธสตริง w แล้ว A จะลองจำลองการคำนวณของ A2 สำหรับขาเข้า w ต่อ ถ้า A2 ยอมรับสตริง w แล้ว A ก็ยอมรับสตริง w ด้วย มิฉะนั้นจะปฏิเสธ

เหลือเพียงเขียนให้เป็นรูปนัยว่าการที่ออโตมาตา A “จำลอง” การคำนวณของออโตมาตาอีกตัวหมายความว่าอย่างไร

การเขียนให้เป็นรูปนัย

มีภาษาปรกติสองภาษา L1 และ L2 ซึ่งออโตมาตาจำกัดต่อไปนี้ยอมรับ

A1=⟨Q1,Σ1,δ1,q1,F1⟩A2=⟨Q2,Σ2,δ2,q2,F2⟩

จะสร้างออโตมาตาจำกัด A = ⟨Q, Σ, δ, q, F⟩ ที่ยอมรับภาษา L = L1 ∪ L2 โดยใช้แนวคิดการจำลองออโตมาตาสองตัว A1, A2 นึกภาพว่าสตริงขาเข้าคือ w = w1w2… wn และตอนนี้จะจำลองการทำงานของออโตมาตา A1 และ A2 สำหรับสตริง w ไปพร้อมกัน รูปแบบเริ่มต้นของออโตมาตา A1 คือ ⟨q1, w1w2… wn⟩ รูปแบบเริ่มต้นของ A2 คือ ⟨q2, w1w2… wn⟩ ในแต่ละออโตมาตาคำนวณหนึ่งขั้น จะได้รูปแบบ ⟨δ1(q1, w1), w2… wn⟩ และ ⟨δ2(q2, w1), w2… wn⟩

จะเห็นว่ารูปแบบทั้งสองต่างกันเฉพาะส่วนประกอบแรก ส่วนประกอบที่สองซึ่งคือส่วนของสตริงที่ยังไม่ได้อ่านเหมือนกันเสมอ ดังนั้นระหว่างการจำลองไม่จำเป็นต้องเก็บรูปแบบสองรูปแบบของออโตมาตาสองตัว แต่ใช้รูปแบบเดียวในรูป ⟨⟨qi, qj⟩, wl… wn⟩ ก็พอ โดยที่ qi ∈ Q1 และ qj ∈ Q2 กล่าวอีกอย่างคือ ออโตมาตา A ที่กำลังสร้างจะมีรูปแบบเริ่มต้น ⟨⟨q1, q2⟩, w⟩ ส่วนแรกของคู่ ⟨q1, q2⟩ แทนสถานะปัจจุบันของออโตมาตา A1 และส่วนที่สองแทนสถานะปัจจุบันของออโตมาตา A2

จึงเขียนได้ว่าออโตมาตา A ที่กำลังสร้างจะมีเซตของสถานะเท่ากับ Q = Q1 × Q2 ซึ่งเป็นผลคูณคาร์ทีเซียนของสถานะของออโตมาตาสองตัวก่อนหน้า แนวคิดต่อไปคือ ออโตมาตา A มีสถานะเริ่มต้น ⟨q1, q2⟩ และถ้าสำหรับสัญลักษณ์ w1 ออโตมาตา A1 เปลี่ยนไปที่สถานะ qi และสำหรับสัญลักษณ์ w1 เดียวกัน ออโตมาตา A2 เปลี่ยนไปที่สถานะ qj แล้วออโตมาตา A จะเปลี่ยนไปที่สถานะ ⟨qi, qj⟩ สำหรับสัญลักษณ์ w1

เขียนฟังก์ชันการเปลี่ยนสถานะ δ ได้ดังนี้ (ในที่นี้สมมติว่าขณะนี้อยู่ในสถานะ qi และ qj):

δ(⟨qi,qj⟩,w)=⟨δ1(qi,w),δ2(qj,w)⟩

เหลือเพียงรายละเอียดเล็กน้อย สำหรับอักษร Σ= Σ1 ∪ Σ2 สถานะเริ่มต้นคือ q = ⟨q1, q2⟩ และสถานะสิ้นสุดคือทุกคู่ ⟨qi, qj⟩ ที่ qi ∈ F1 หรือ qj ∈ F2

ตัวอย่างประกอบ

ให้ออโตมาตาสองตัว ตัวแรกคือออโตมาตา A1 ซึ่งยอมรับสตริงทั้งหมด (รวมทั้งสตริงว่าง) ที่เลข 0 และ 1 สลับกัน คือสตริงในรูป 01, 0101, 010101, …

ออโตมาตาอีกตัว A2 ยอมรับสตริงที่มีเลข 0 อย่างน้อยหนึ่งตัว:

ยูเนียนของภาษาทั้งสองคือสตริงที่มีเลข 0 หรืออยู่ในรูป 01, 0101, … ต่อไปจะสร้างออโตมาตาจำกัด A = ⟨Q, Σ, δ, q, F⟩ ที่ยอมรับภาษายูเนียนนี้และไม่ยอมรับสตริงอื่น อย่างแรกจะดูว่าสถานะของออโตมาตาใหม่ A มีอะไรบ้าง ซึ่งคือผลคูณคาร์ทีเซียนของสถานะของออโตมาตาตัวแรกและตัวที่สอง:

Q=Q1×Q2={⟨q0,p0⟩,⟨q0,p1⟩,⟨q1,p0⟩,⟨q1,p1⟩,⟨q2,p0⟩,⟨q2,p1⟩}

นี่คือสถานะหกสถานะของออโตมาตา A ซึ่งยอมรับภาษายูเนียน L(A1) ∪ L(A2) ในแผนภาพจะมีลักษณะดังนี้:

ไม่ต้องตกใจที่สถานะประกอบด้วยคู่ของสถานะ ชื่อเช่นนี้ใช้เพียงเพื่อให้เห็นได้ง่ายว่าเกิดอะไรขึ้นในออโตมาตา จะตั้งชื่อสถานะตามปกติเป็น q0, …, q5 ก็ได้ สถานะสิ้นสุดคือสถานะที่มีสถานะ q0 หรือ p1 อยู่ด้วย ซึ่งเป็นสถานะสิ้นสุดของออโตมาตาเดิม สถานะเริ่มต้นคือ ⟨q0, p0⟩

ต่อไปต้องหาการเปลี่ยนสถานะทั้งหมด เขียนตารางดังนี้:

01⟨q0,p0⟩⟨q0,p1⟩⟨q1,p0⟩⟨q1,p1⟩⟨q2,p0⟩⟨q2,p1⟩

แล้วเติมตารางทีละช่อง อย่างแรกหาว่าจากสถานะ ⟨q0, p0⟩ เมื่อขาเข้าเป็น 0 จะเปลี่ยนไปที่ใด หาว่าในออโตมาตา A1 จากสถานะ q0 เมื่อขาเข้าเป็น 0 จะเปลี่ยนไปที่ใด ซึ่งคือสถานะ q1 ในออโตมาตา A2 จาก p0 เมื่อขาเข้าเป็นศูนย์จะเปลี่ยนไปที่สถานะ p1 จึงเขียน ⟨q1, p1⟩ ลงในตาราง:

01⟨q0,p0⟩⟨q1,p1⟩⟨q0,p1⟩⟨q1,p0⟩⟨q1,p1⟩⟨q2,p0⟩⟨q2,p1⟩

เมื่อขาเข้าเป็น 1 จะได้ว่า สำหรับออโตมาตา A1 มี δ1(q0, 1) = q2 และสำหรับออโตมาตา A2 มี δ2(p0, 1) = p0 จึงได้สถานะ ⟨q2, p0⟩

01⟨q0,p0⟩⟨q1,p1⟩⟨q2,p0⟩⟨q0,p1⟩⟨q1,p0⟩⟨q1,p1⟩⟨q2,p0⟩⟨q2,p1⟩

เติมส่วนที่เหลือของตาราง:

01⟨q0,p0⟩⟨q1,p1⟩⟨q2,p0⟩⟨q0,p1⟩⟨q1,p1⟩⟨q2,p1⟩⟨q1,p0⟩⟨q2,p1⟩⟨q0,p0⟩⟨q1,p1⟩⟨q2,p1⟩⟨q0,p1⟩⟨q2,p0⟩⟨q2,p1⟩⟨q2,p0⟩⟨q2,p1⟩⟨q2,p1⟩⟨q2,p1⟩

จากตารางนี้ เหลือเพียงวาดส่วนที่เหลือของแผนภาพ

ลองตรวจสอบว่าออโตมาตาทำงานถูกต้อง ลองให้ยอมรับสตริง 0100 ออโตมาตาจะผ่านสถานะตามลำดับดังนี้

⟨q0,p0⟩,⟨q1,p1⟩,⟨q0,p1⟩,⟨q1,p1⟩,⟨q2,p1⟩

เนื่องจากสถานะ ⟨q2, p1⟩ เป็นสถานะสิ้นสุด ออโตมาตา A จึงยอมรับสตริง 0100 ถ้าลองให้ออโตมาตา A1 และ A2 ยอมรับสตริง 0100 จะเป็นอย่างไร ออโตมาตา A1 จะผ่านสถานะตามลำดับดังนี้:

q0,q1,q0,q1,q2

ออโตมาตาจบที่สถานะ q2 ซึ่งไม่ใช่สถานะสิ้นสุด ออโตมาตา A1 จึงไม่ยอมรับสตริงนี้ แล้วออโตมาตา A2 เป็นอย่างไร

p0,p1,p1,p1,p1

สถานะ p1 เป็นสถานะสิ้นสุด ออโตมาตา A2 จึงยอมรับสตริง 0100 สังเกตว่าออโตมาตา A1 และ A2 จบที่สถานะ q2 และ p1 ซึ่งสอดคล้องกับการที่ออโตมาตา A จบที่สถานะ ⟨q2, p1⟩

วิธีที่ใช้ออโตมาตาแบบนอนดีเทอร์มินิสติก

ตัวอย่าง

การที่เซตของภาษาปรกติปิดภายใต้ยูเนียน พิสูจน์ได้ด้วยการสร้างออโตมาตาแบบนอนดีเทอร์มินิสติกเช่นกัน ซึ่งง่ายกว่ามาก

มีภาษาปรกติสองภาษา L1, L2 และต้องการพิสูจน์ว่ายูเนียนของภาษาทั้งสอง L = L1 ∪ L2 เป็นภาษาปรกติด้วย เนื่องจาก L1, L2 เป็นภาษาปรกติ จึงต้องมีออโตมาตา A1, A2 ที่ยอมรับภาษาเหล่านี้ นั่นคือ L(A1) = L1 และ L(A2) = L2 จะใช้ออโตมาตาเหล่านี้สร้างออโตมาตา A ที่ยอมรับภาษา L นั่นคือ L(A) = L

สมมติว่าออโตมาตาจำกัด A1 และ A2 เป็นดังนี้:

และ

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

การเขียนให้เป็นรูปนัย

ให้ออโตมาตาสองตัว A1 = ⟨Q1, Σ, δ1, q1, F1⟩ และ A2 = ⟨Q2, Σ, δ2, q2, F2⟩ จะสร้างออโตมาตา A = ⟨Q, Σ, δ, q0, F⟩ ที่ยอมรับยูเนียนของภาษาที่ออโตมาตาทั้งสองยอมรับ นั่นคือ L(A) = L(A1) ∪ L(A2) โดยที่

  • Q = Q1 ∪ Q2 ∪ {q0}
  • F = F1 ∪ F2

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

δ(q,a)={δ1(q,a)ถ้าq∈Q1δ2(q,a)ถ้าq∈Q2{q1,q2}ถ้าq=q0∧a=ε∅ถ้าq=q0∧a≠ε

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

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