✖

การต่อภาษาปรกติ

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

การต่อภาษาคืออะไร

การต่อสตริงสองสตริง “010” และ “1111” จะได้สตริง “0101111” การต่อภาษาจึงให้ภาษาใหม่ ซึ่งสร้างโดยนำสตริงทุกสตริงจากภาษาหนึ่งมาต่อกับสตริงทุกสตริงจากอีกภาษาหนึ่ง การต่อสตริงสองสตริงและการต่อภาษาสองภาษาเขียนแทนด้วยวงกลมเล็ก ∘ จากนั้นนิยามการต่อภาษา L1 และ L2 ได้ดังนี้:

L1∘L2={a∘b|a∈L1,b∈L2}

แนวคิดของการพิสูจน์

มีภาษาปรกติสองภาษา L1, L2 และออโตมาตาสองตัวที่ยอมรับภาษาเหล่านี้:

A1=⟨Q1,Σ1,δ1,q0,F1⟩A2=⟨Q2,Σ2,δ2,p0,F2⟩

จะสร้างออโตมาตาแบบนอนดีเทอร์มินิสติก 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 เช่นกัน ในออโตมาตานี้จำลองได้ทั้งสองแบบ ออโตมาตาอาจเดินตามเส้นทางนี้:

q0→0q1→0q1→εp0→0p1→1p2

ในเส้นทางนี้ออโตมาตาจะ “ยอมรับ” ส่วน 00 ของสตริงก่อน แล้วจึงยอมรับส่วน 01 หรืออาจเดินตามเส้นทางนี้:

q0→0q1→εp0→0p0→0p1→1p2

ซึ่งออโตมาตาจะ “ยอมรับ” ส่วน 0 ของสตริงก่อน แล้วจึงยอมรับส่วน 001 แน่นอนว่าทั้งสองกรณีไปถึงสถานะสิ้นสุด p2

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

กล่าวอีกครั้ง: มีภาษาปรกติสองภาษา L1, L2 และออโตมาตาสองตัวที่ยอมรับภาษาเหล่านี้:

A1=⟨Q1,Σ1,δ1,q0,F1⟩A2=⟨Q2,Σ2,δ2,p0,F2⟩

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

  • Q = Q1 ∪ Q2 (สมมติด้วยว่า Q1 ∩ Q2 = ∅)
  • Σ= Σ1 ∪ Σ2
  • q = q0
  • F = F2

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

δ(q,a)={δ1(q,a)ถ้าq∈Q1∧q∉F1δ1(q,a)ถ้าq∈F1∧a≠εδ1(q,a)∪{p0}ถ้าq∈F1∧a=εδ2(q,a)ถ้าq∈Q2

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

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