เราได้รับด้วยภาษา "L" และภารกิจคือการสร้างออโตมาตาแบบเลื่อนลงสำหรับภาษาที่กำหนด ซึ่งอธิบายว่าการเกิดขึ้นของอักขระ 'a' ควรเพิ่มขึ้นเป็นสองเท่าของเวลาที่เกิดขึ้น ของอักขระ 'b' และการเกิดขึ้นของอักขระ 'c' ควรเพิ่มเป็นสี่เท่าของเวลาของ 'd' และการปรากฏของอักขระทั้งหมดควรมีอย่างน้อย 1 ซึ่งสามารถทำให้สตริงเป็น NULL ได้ และออโตมาตาควรยอมรับ พี>
Automata แบบเลื่อนลงคืออะไร
ออโตมาตาแบบกดลงหรือออโตมาตันแบบกดลงหรือพีดีเอเป็นเทคนิคในการใช้ไวยากรณ์ที่ไม่มีบริบทในลักษณะเดียวกับที่เราออกแบบ 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 ยอมรับได้มีรูปแบบ -
-
ค 4n ง n − ccccd, ccccccccdd เป็นต้น จำนวน cs คือ 4 คูณด้วยจำนวน ของดีเอส เมื่อ m เป็น 0 เราจะไม่มี as และ bs กด cs ต่อไปและทันทีที่พบ d แรกจากนั้นให้เปิด 4 c จาก stack หากเราไปถึงจุดสิ้นสุดของสตริงและไม่มี cs แสดงว่าสตริงนั้นได้รับการยอมรับ
-
a 2 นาที ข ม − aab, aaaabb เป็นต้น จำนวนเท่ากับ 2 คูณจำนวน ของ bs. เมื่อ n เป็น 0 เราจะไม่มี cs และ ds กดต่อไปทันทีที่พบ b ตัวแรกจากนั้นให้ป๊อป 2 b จากสแต็ก หากเราไปถึงจุดสิ้นสุดของสตริงและไม่มีค่าใด ๆ แสดงว่าสตริงนั้นได้รับการยอมรับ
-
a 2 นาที ค 4n ง n ข ม − aaccccdb, aaaaccccccccddbb. จำนวนเท่ากับ 2 เท่าของจำนวน ของ bs และ cs เท่ากับ 4 คูณจำนวนของ ds กด as และ cs ต่อไป ทันทีที่พบ d แรก ให้ป๊อป 4 cs หากอยู่ด้านบนแล้วจึงปรากฏขึ้น 2 สำหรับ bs ที่เหลือ หากเราถึงจุดสิ้นสุดและไม่มี a เหลืออยู่ ระบบจะยอมรับสตริงนั้น
-
สตริง NULL ก็เป็นที่ยอมรับเช่นกัน a 0 ค 0 ง 0 b 0 .
มาทำความเข้าใจเครื่องจักรกันเถอะ
-
การเปลี่ยนสถานะ q0 -
-
( a, I/a,I ) − หากด้านบนของสแต็กคือ I และสัญลักษณ์อินพุตปัจจุบันคือ a ให้กด a ไปที่ด้านบนของสแต็กและอยู่ที่ q0 สแต็คกลายเป็น AI…
-
( c, I/c,I ) − หากด้านบนของสแต็กคือ I และสัญลักษณ์อินพุตปัจจุบันคือ c ให้กด c ไปที่ด้านบนของสแต็กและอยู่ที่ q0 Stack กลายเป็น cI...
-
( a, a/a,a ) − หาก top ของ stack เป็น a และสัญลักษณ์อินพุตปัจจุบันเป็น a ด้วย ให้กด a ไปที่ด้านบนของ stack และอยู่ที่ q0 สแต็คกลายเป็น aa.... ดันต่อไปจนกระทั่งถึง c หรือ b.
-
( c, c/c,c ) − หากด้านบนของสแต็กเป็น c และสัญลักษณ์อินพุตปัจจุบันเป็น c ด้วย ให้กด c ที่ด้านบนของสแต็กและอยู่ที่ q0 สแต็คกลายเป็นซีซี.... กด cs ต่อไปจนกว่าจะถึง d.
-
( b, a/e,aa ) - หากด้านบนของสแต็กเป็น a และสัญลักษณ์อินพุตปัจจุบันคือ b ให้ป๊อปอัป 2 จากสแต็กและย้ายไปที่ q3
-
(c, a/c,a ) − หากด้านบนของสแต็กเป็น a และสัญลักษณ์อินพุตปัจจุบันคือ c ให้กด c ไปที่ด้านบนของสแต็กแล้วย้ายไปที่ q1 สแต็คกลายเป็น...
-
( d, c/e,cccc ) − หากด้านบนของสแต็กคือ c และสัญลักษณ์อินพุตปัจจุบันคือ d ให้เปิด 4 ds จากสแต็กแล้วย้ายไปที่ q4
-
( $, I/I, I) - หากด้านบนของสแต็กคือ I และไม่มีอินพุต ให้ไม่ต้องดำเนินการใดๆ และย้ายไปที่ q5 สำหรับสตริง NULL
-
-
การเปลี่ยนสถานะ q1 -
-
( c, c/c,c ) − หากด้านบนของสแต็กคือ c และสัญลักษณ์อินพุตปัจจุบันเป็น c ด้วย ให้กด c ไปที่ด้านบนของสแต็กและอยู่ที่ q1 สแต็คกลายเป็นซีซี.... กด cs ต่อไปจนกว่าจะถึง d.
-
( d, c/e,cccc ) − หากด้านบนของสแต็กคือ c และสัญลักษณ์อินพุตปัจจุบันคือ d ให้ป๊อปอัป 4 ds จากสแต็กแล้วย้ายไปที่ q2
-
-
การเปลี่ยนสถานะ q2 -
-
( d, c/e,cccc ) − หากด้านบนของสแต็กคือ c และสัญลักษณ์อินพุตปัจจุบันคือ d ให้ป๊อปอัป 4 ds จากสแต็กแล้วย้ายไปที่ q2
-
( b, a/e,aa ) - หากด้านบนของสแต็กเป็น a และสัญลักษณ์อินพุตปัจจุบันคือ b ให้ป๊อปอัป 2 จากสแต็กและย้ายไปที่ q3
-
-
การเปลี่ยนสถานะ q3 -
-
( b, a/e,aa ) - หากด้านบนของสแต็กเป็น a และสัญลักษณ์อินพุตปัจจุบันคือ b ให้ป๊อปอัป 2 จากสแต็กและยังคงอยู่ที่ q3
-
( $, I/I, I ) − หากด้านบนของ stack คือ I และไม่มีอินพุต ให้ไม่ต้องดำเนินการใดๆ และย้ายไปที่ q5 สำหรับสตริง NULL
-
-
การเปลี่ยนสถานะ q4 -
-
( d, c/e,cccc ) − หากด้านบนของสแต็กคือ c และสัญลักษณ์อินพุตปัจจุบันคือ d ให้ป๊อปอัป 4 ds จากสแต็กและยังคงอยู่ที่ q4
-
( $, I/I, I ) - หากด้านบนของสแต็กคือ I และไม่มีอินพุต ให้ไม่ต้องดำเนินการใดๆ และย้ายไปที่ q5 สำหรับสตริง NULL
-
