เราได้รับด้วยภาษา "L" และภารกิจคือการสร้างออโตมาตาแบบเลื่อนลงสำหรับภาษาที่กำหนด ซึ่งอธิบายว่าการเกิดขึ้นของ 0 และ 3 จะเท่ากัน และการเกิดขึ้นของ 1 และ 2 จะเท่ากันและการเกิดขึ้นของตัวเลขทั้งหมดควรเป็นอย่างน้อย 1 ซึ่งสามารถทำให้สตริงเป็น 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 ยอมรับได้มีรูปแบบ -
-
0 n 3 น − 03, 0033, 000333 เป็นต้น จำนวน 0s เท่ากับหมายเลข จาก 3 วินาที เมื่อ m เป็น 0 เราจะไม่มี 1 และ 2 กด 0 ไปเรื่อยๆ และทันทีที่พบ 3 ตัวแรก ให้กด 0 หากเราไปถึงจุดสิ้นสุดของสตริงและไม่มี 0s แสดงว่าสตริงนั้นได้รับการยอมรับ
-
1 ม 2 ม − 12, 1122, 111222 เป็นต้น จำนวน 1s เท่ากับจำนวน จาก 2 วินาที เมื่อ n เป็น 0 เราจะไม่มี 0 และ 3 กด 1s ต่อไปและทันทีที่พบ 2 ตัวแรกจากนั้นให้กด 1s หากเราไปถึงจุดสิ้นสุดของสตริงและไม่มี 1s แสดงว่าสตริงนั้นได้รับการยอมรับ
-
0 n 1 ม 2 ม 3 น − 0123, 001233, 011223 เป็นต้น จำนวน 0s เท่ากับหมายเลข ของ 3s และ 1s เท่ากับ 2s กด 0s และ 1s ต่อไป ทันทีที่พบ 2 ตัวแรก ให้ป๊อป 1s หากอยู่ด้านบน จากนั้นจึงปรากฏขึ้น 0s สำหรับ 3s ที่เหลือ หากเราถึงจุดสิ้นสุดและไม่มี 0 เหลือ แสดงว่าสตริงนั้นยอมรับ
-
สตริง NULL ก็เป็นที่ยอมรับเช่นกัน 0 0 1 0 2 0 3 0 .
มาทำความเข้าใจเครื่องจักรกันเถอะ
-
การเปลี่ยนสถานะ q0 -
-
( 0, I/0,I ) − หากด้านบนของสแต็กคือ I และสัญลักษณ์อินพุตปัจจุบันคือ 0 ให้กด 0 ไปที่ด้านบนของสแต็กและอยู่ที่ q0 สแต็คกลายเป็น 0I...
-
( 0, 0/0,0 ) − หากด้านบนของสแต็กเป็น 0 และสัญลักษณ์อินพุตปัจจุบันเป็น 0 ด้วย ให้กด 0 ไปที่ด้านบนของสแต็กและอยู่ที่ q0 สแต็คกลายเป็น 00.... กด 0s ต่อไปจนกว่าจะถึง 1 หรือ 3
-
( 1, 0/1,0 ) − หากด้านบนของสแต็กเป็น 0 และสัญลักษณ์อินพุตปัจจุบันคือ 1 ให้กด 1 ไปที่ด้านบนของสแต็กแล้วย้ายไปที่ q1 สแต็คกลายเป็น 10...
-
( 1, I/1,I ) − หากด้านบนของสแต็กคือ I และสัญลักษณ์อินพุตปัจจุบันคือ 1 ให้กด 1 และย้ายไปที่ q5
-
( 3, 0/e ) − หากด้านบนของสแต็กเป็น 0 และสัญลักษณ์อินพุตปัจจุบันคือ 3 ให้กด 0 แล้วย้ายไปที่ q3
-
( $, I/I ) - หากด้านบนของสแต็กคือ I และไม่มีอินพุต ไม่ต้องทำอะไรและย้ายไปที่ q4 สำหรับสตริง NULL
-
-
การเปลี่ยนสถานะ q1 -
-
( 1, 1/11 ) - หากด้านบนของสแต็กคือ 1 และสัญลักษณ์อินพุตปัจจุบันเป็น 1 ด้วย ให้กด 1 ไปที่ด้านบนของสแต็กและอยู่ที่ q1 สแต็คกลายเป็น 11... กด 1 วินาทีต่อไปจนกว่าจะถึง 2
-
( 2, 1/e ) − หากด้านบนของสแต็กคือ 1 และสัญลักษณ์อินพุตปัจจุบันคือ 2 ให้กด 1 แล้วย้ายไปที่ q2
-
-
การเปลี่ยนสถานะ q2 -
-
(2, 1/e ) − หากด้านบนของสแต็กคือ 1 และสัญลักษณ์อินพุตปัจจุบันคือ 2 ให้ป๊อปอัป 1 และยังคงอยู่ที่ q2
-
( 3, 0/e ) − หากด้านบนของสแต็กเป็น 0 และสัญลักษณ์อินพุตปัจจุบันคือ 3 ให้กด 0 แล้วย้ายไปที่ q3
-
-
การเปลี่ยนสถานะ q3 -
-
( 3, 0/e ) − หากด้านบนของสแต็กเป็น 0 และสัญลักษณ์อินพุตปัจจุบันคือ 3 ให้กด 1 และยังคงอยู่ที่ q3
-
( $, I/I ) - หากด้านบนของสแต็กคือ I และไม่มีอินพุต ไม่ต้องทำอะไรและย้ายไปที่ q4 สำหรับสตริง NULL
-
-
การเปลี่ยนสถานะ q5 -
-
( 1, 1/1,1 ) − หากด้านบนของสแต็กคือ 1 และสัญลักษณ์อินพุตปัจจุบันเป็น 1 ด้วย ให้กด 1 ไปที่ด้านบนของสแต็กและอยู่ที่ q5 สแต็คกลายเป็น 11... กด 1 วินาทีต่อไปจนกว่าจะถึง 2
-
( 2, 1/e ) − หากด้านบนของสแต็กคือ 1 และสัญลักษณ์อินพุตปัจจุบันคือ 2 ให้กด 1 แล้วย้ายไปที่ q6
-
-
การเปลี่ยนสถานะ q6 -
-
(2, 1/e ) − หากด้านบนของสแต็กคือ 1 และสัญลักษณ์อินพุตปัจจุบันคือ 2 ให้ป๊อปอัป 1 และยังคงอยู่ที่ q6
-
( $, I/I ) - หากด้านบนของ stack คือ I และไม่มีอินพุต ไม่ต้องทำอะไรและย้ายไปที่ q4 สำหรับสตริง NULL
-
