สร้างออโตมาตาแบบเลื่อนลงสำหรับ L ={0(n+m)1m2n | m, n =0} ใน C++

เราได้รับด้วยภาษา "L" และภารกิจคือการสร้างออโตมาตาแบบเลื่อนลงสำหรับภาษาที่กำหนด ซึ่งอธิบายว่าการเกิดขึ้นของ 0 จะเป็นการเพิ่มการเกิดขึ้นของ 1 และ 2 และการเกิดขึ้นของ 1 และ 2 จะเป็นอย่างน้อยหนึ่งรายการซึ่งสามารถทำให้สตริงเป็น NULL ได้และออโตมาตาควรยอมรับได้

Automata แบบเลื่อนลงคืออะไร

ออโตมาตาแบบกดลงหรือออโตมาตันแบบกดลงหรือ PDA เป็นเทคนิคในการใช้ไวยากรณ์ที่ไม่มีบริบทในลักษณะเดียวกับที่เราออกแบบ Deterministic Finite Automaton หรือ DFA สำหรับไวยากรณ์ปกติ DFA สามารถดำเนินการกับข้อมูลที่มีจำกัด แต่ PDA สามารถดำเนินการกับข้อมูลที่ไม่สิ้นสุดได้ เราสามารถเข้าใจกลไกการกดลงเป็นการรวมกันของ "finite statemachine" และ "stack"

หุ่นยนต์กดลงมีสามองค์ประกอบ -

• เทปใส่ข้อมูล

• หน่วยควบคุม และ

• สแต็คที่มีขนาดอนันต์

PDA สามารถอธิบายอย่างเป็นทางการว่า 7−tuple (Q, Ʃ, S, δ, q0, I, F) -

• Q คือจำนวนที่จำกัดของสถานะ

• Ʃ เป็นตัวอักษรอินพุต

• S คือสัญลักษณ์สแต็ก

• δ คือฟังก์ชันการเปลี่ยนภาพ:Q × (Ʃ υ {ε}) × S × Q × S*

• q0 คือสถานะเริ่มต้น (q0 ε Q)

• I คือสัญลักษณ์บนสแต็กเริ่มต้น (I ε S)

• F คือชุดของสถานะการยอมรับ (F ε Q)

มาสร้าง Automata แบบเลื่อนลงสำหรับภาษาที่กำหนด −

สตริงที่ PDA ยอมรับได้มีรูปแบบ -

• 1. 0 ⁿ 2 ^น :02, 0022, 000222 เป็นต้น จำนวน 0s เท่ากับจำนวน จาก 2 วินาที เมื่อ m เป็น 0 เราจะไม่มี 1s กด 0 ไปเรื่อยๆ และทันทีที่พบ 2 ตัวแรก ให้กด 0 หากเราไปถึงจุดสิ้นสุดของสตริงและไม่มี 0s แสดงว่าสตริงนั้นได้รับการยอมรับ

• 0 ^ม 1 ^ม :01, 0011, 000111 เป็นต้น จำนวน 0s เท่ากับจำนวน จาก 1 วินาที เมื่อ n เป็น 0 เราจะไม่มี 2s กด 0 ต่อไปและทันทีที่พบ 1 แรกจากนั้นให้กด 0 หากเราไปถึงจุดสิ้นสุดของสตริงและไม่มี 0s แสดงว่าสตริงนั้นได้รับการยอมรับ

• 0 ^n+m 1 ^ม 2 ^น :0012, 000112, 000122 เป็นต้น จำนวน 0 วินาที เท่ากับผลรวมของหมายเลข ของ 1s และ 2s กด 0 ต่อไปและเมื่อพบ 1 แรกจากนั้นให้กด 0 เหล่านั้นจนกว่าจะไม่มี 1s เหลืออยู่ จากนั้นให้กด 0s อีกครั้งและเมื่อพบ 2 ตัวแรกจากนั้นให้กด 0 เหล่านั้นจนกว่าจะไม่มี 2s เหลืออยู่ สตริงจะได้รับการยอมรับ

• สตริง NULL ก็เป็นที่ยอมรับเช่นกัน 0 ⁰ 1 ⁰ 2 ⁰

มาทำความเข้าใจเครื่องจักรกันเถอะ

• การเปลี่ยนสถานะ q0 :

  • 0, I/0I ) − หากด้านบนของสแต็กคือ I และสัญลักษณ์อินพุตปัจจุบันคือ 0 ให้กด 0 ไปที่ด้านบนของสแต็กและอยู่ที่ q0 สแต็คกลายเป็น 0I...

  • ( 0, 0/00 ) − หากด้านบนของสแต็กเป็น 0 และสัญลักษณ์อินพุตปัจจุบันเป็น 0 ด้วย ให้กด 0 ไปที่ด้านบนของสแต็กและอยู่ที่ q0 กองซ้อนกลายเป็น 00.... กด 0 ต่อไปจนกว่าจะถึง 1 หรือ 2 ถัดไป

  • (1, 0/$ ) - หากด้านบนของสแต็กเป็น 0 และสัญลักษณ์อินพุตปัจจุบันคือ 1 ให้กด 0 แล้วย้ายไปที่ q1

  • (2, 0/$ ) - หากด้านบนของสแต็กเป็น 0 และสัญลักษณ์อินพุตปัจจุบันคือ 2 ให้กด 0 แล้วย้ายไปที่ q2

  • ( $, I/I ) - หากด้านบนของ stack คือ I และไม่มีอินพุต ไม่ต้องทำอะไรและย้ายไปที่ qf สำหรับสตริง NULL

• การเปลี่ยนสถานะ q1 -

  • (1, 0/$ ) - หากด้านบนของสแต็กเป็น 0 และสัญลักษณ์อินพุตปัจจุบันคือ 1 ให้กด 0 ไปที่และอยู่ที่ q1

  • ( $, I/I ) - หากด้านบนของ stack คือ I และไม่มีอินพุต ไม่ต้องทำอะไรและย้ายไปที่ qf

  • (2, 0/$ ) - หากด้านบนของสแต็กเป็น 0 และสัญลักษณ์อินพุตปัจจุบันคือ 2 ให้กด 0 แล้วย้ายไปที่ q2

• การเปลี่ยนสถานะ q2 -

  • (2, 0/$ ) - หากด้านบนของสแต็กเป็น 0 และสัญลักษณ์อินพุตปัจจุบันคือ 2 ให้ป๊อปอัป 0 และยังคงอยู่ที่ q2

  • ($, I/I ) - หากด้านบนของสแต็กคือ I และไม่มีอินพุต ไม่ต้องทำอะไรและย้ายไปที่ qf