แนะนำ Pushdown Automata
โครงสร้างพื้นฐานของ PDA
ระบบอัตโนมัติแบบเลื่อนลงเป็นวิธีการใช้ไวยากรณ์ที่ไม่มีบริบทในลักษณะเดียวกับที่เราออกแบบ DFA สำหรับไวยากรณ์ปกติ DFA สามารถจำข้อมูลจำนวน จำกัด ได้ แต่ PDA สามารถจำข้อมูลได้ไม่ จำกัด จำนวน
โดยทั่วไปแล้วระบบอัตโนมัติแบบเลื่อนลงคือ -
"Finite state machine" + "a stack"
ระบบอัตโนมัติแบบเลื่อนลงมีสามองค์ประกอบ -
- เทปป้อนข้อมูล
- ชุดควบคุมและ
- กองที่มีขนาดไม่สิ้นสุด
หัวสแต็กจะสแกนสัญลักษณ์ด้านบนของสแตก
สแต็กทำสองการดำเนินการ -
Push - เพิ่มสัญลักษณ์ใหม่ที่ด้านบน
Pop - สัญลักษณ์ด้านบนจะถูกอ่านและลบออก
PDA อาจอ่านสัญลักษณ์อินพุตหรือไม่ก็ได้ แต่ต้องอ่านด้านบนสุดของสแตกในทุกการเปลี่ยนแปลง
PDA สามารถอธิบายได้อย่างเป็นทางการว่าเป็น 7-tuple (Q, ∑, S, δ, q 0 , I, F) -
Q คือจำนวนรัฐที่ จำกัด
∑ เป็นตัวอักษรสำหรับป้อนข้อมูล
S คือสัญลักษณ์สแต็ก
δ คือฟังก์ชันการเปลี่ยน: Q × (∑ ∪ {ε}) × S × Q × S *
q0คือสถานะเริ่มต้น (q 0 ∈ Q)
I คือสัญลักษณ์สแต็กบนสุดเริ่มต้น (I ∈ S)
F คือชุดของสถานะการยอมรับ (F ∈ Q)
แผนภาพต่อไปนี้แสดงการเปลี่ยนแปลงใน PDA จากสถานะ q 1เป็นสถานะ q 2โดยระบุว่า a, b → c -
ซึ่งหมายความว่าในสถานะ q1หากเราพบสตริงอินพุต ‘a’ และสัญลักษณ์ด้านบนของสแต็กคือ ‘b’แล้วเราก็ป๊อป ‘b’ผลักดัน ‘c’ ที่ด้านบนของสแต็กและย้ายไปที่สถานะ q2.
คำศัพท์ที่เกี่ยวข้องกับ PDA
คำอธิบายทันที
คำอธิบายทันที (ID) ของ PDA จะแสดงด้วย triplet (q, w, s) โดยที่
q คือรัฐ
w เป็นอินพุตที่ไม่มีการบริโภค
s คือเนื้อหาสแต็ก
สัญกรณ์ Turnstile
สัญกรณ์ "turnstile" ใช้สำหรับการเชื่อมต่อคู่ของ ID ที่แสดงถึงการเคลื่อนไหวหนึ่งหรือหลายครั้งของ PDA ขั้นตอนการเปลี่ยนแสดงโดยสัญลักษณ์ประตูหมุน "⊢"
พิจารณา PDA (Q, ∑, S, δ, q 0 , I, F) การเปลี่ยนแปลงสามารถแสดงทางคณิตศาสตร์ได้ด้วยสัญกรณ์ turnstile ต่อไปนี้ -
(p, aw, Tβ) ⊢ (q, w, αb)นี่หมายความว่าในขณะที่เปลี่ยนจากสถานะ p เพื่อระบุ qสัญลักษณ์อินพุต ‘a’ ถูกใช้ไปและด้านบนสุดของสแต็ก ‘T’ ถูกแทนที่ด้วยสตริงใหม่ ‘α’.
Note - หากเราต้องการให้ PDA เป็นศูนย์หรือมากกว่านั้นเราต้องใช้สัญลักษณ์ (⊢ *) แทน