home

หน้าแรก
 Computer >> คอมพิวเตอร์ >  >> การเขียนโปรแกรม >> C++

สร้างออโตมาตา Pushdown สำหรับ L ={0m1(n+m)2n | m,n =0} ใน C++

เราได้รับด้วยภาษา "L" และภารกิจคือการสร้างออโตมาตาแบบเลื่อนลงสำหรับภาษาที่กำหนด ซึ่งอธิบายว่าการเกิดขึ้นของ 1 จะเป็นการเพิ่มการเกิดขึ้นของ 0 และ 2 และการเกิดขึ้นของ 0 และ 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 แบบเลื่อนลงสำหรับภาษาที่กำหนด −

สร้างออโตมาตา Pushdown สำหรับ L ={0m1(n+m)2n | m,n =0} ใน C++

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

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

  • 1 น 2 น − 12, 1122, 111222 เป็นต้น จำนวน 1s เท่ากับจำนวน จาก 2 วินาที เมื่อ m เป็น 0 เราจะไม่มี 0 กด 1s ต่อไปและทันทีที่พบ 2 ตัวแรกจากนั้นให้กด 1s หากเราไปถึงจุดสิ้นสุดของสตริงและไม่มี 1s แสดงว่าสตริงนั้นได้รับการยอมรับ

  • 0 n 1 m+n 2 ม − 0112, 001112, 001112 เป็นต้น จำนวน 1 วินาที เท่ากับผลรวมของหมายเลข ของ 0s และ 2s กด 0 ต่อไปทันทีที่พบ 1 ตัวแรก จากนั้นให้กด 0 จนกว่าจะไม่มี 0 เหลืออยู่ ตอนนี้กด 1s อีกครั้งจนกว่าจะพบ 2 ตัวแรก จากนั้นสำหรับแต่ละ 2 เริ่ม popping 1s จนกว่าเราจะเหลือไม่มี 1s หากเราถึงจุดสิ้นสุดและไม่เหลือ 1 แสดงว่าสตริงนั้นได้รับการยอมรับ

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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