Pushdown Automata Acceptance
มีสองวิธีในการกำหนดการยอมรับ PDA
การยอมรับสถานะขั้นสุดท้าย
ในสถานะสุดท้ายที่ยอมรับได้ PDA จะยอมรับสตริงเมื่อหลังจากอ่านสตริงทั้งหมดแล้ว PDA จะอยู่ในสถานะสุดท้าย จากสถานะเริ่มต้นเราสามารถทำการเคลื่อนไหวที่ลงเอยในสถานะสุดท้ายด้วยค่าสแต็กใดก็ได้ ค่าสแต็กไม่เกี่ยวข้องตราบเท่าที่เราอยู่ในสถานะสุดท้าย
สำหรับ PDA (Q, ∑, S, δ, q 0 , I, F) ภาษาที่ยอมรับโดยชุดของสถานะสุดท้าย F คือ -
L (PDA) = {w | (q 0 , w, I) ⊢ * (q, ε, x), q ∈ F}
สำหรับสตริงสแต็กอินพุตใด ๆ x.
การยอมรับกองซ้อนว่าง
ที่นี่ PDA ยอมรับสตริงเมื่อหลังจากอ่านสตริงทั้งหมดแล้ว PDA ได้ล้างสแต็ก
สำหรับ PDA (Q, ∑, S, δ, q 0 , I, F) ภาษาที่สแตกว่างยอมรับคือ -
L (PDA) = {w | (q 0 , w, I) ⊢ * (q, ε, ε), q ∈ Q}
ตัวอย่าง
สร้าง PDA ที่ยอมรับ L = {0n 1n | n ≥ 0}
วิธีการแก้
ภาษานี้ยอมรับ L = {ε, 01, 0011, 000111, ............................. }
ในตัวอย่างนี้จำนวน ‘a’ และ ‘b’ ต้องเหมือนกัน
เริ่มแรกเราใส่สัญลักษณ์พิเศษ ‘$’ ลงในกองว่าง
จากนั้นก็อยู่ที่สถานะ q2ถ้าเราพบอินพุต 0 และด้านบนเป็น Null เราจะกด 0 เข้าไปในสแต็ก ซึ่งอาจทำซ้ำ และถ้าเราพบอินพุต 1 และด้านบนเป็น 0 เราจะแสดงค่า 0 นี้
จากนั้นก็อยู่ที่สถานะ q3หากเราพบอินพุต 1 และด้านบนเป็น 0 เราจะแสดงค่านี้เป็น 0 ซึ่งอาจวนซ้ำ และถ้าเราพบอินพุต 1 และด้านบนเป็น 0 เราจะแสดงองค์ประกอบบนสุด
หากสัญลักษณ์พิเศษ '$' จะพบที่ด้านบนของสแต็คก็จะโผล่ออกมาและในที่สุดมันก็จะไปยอมรับรัฐ Q 4
ตัวอย่าง
สร้าง PDA ที่ยอมรับ L = {ww R | w = (a + b) *}
Solution
เริ่มแรกเราใส่สัญลักษณ์พิเศษ '$' ลงในกองว่าง ในสถานะq2, wกำลังอ่าน อยู่ในสถานะq3แต่ละ 0 หรือ 1 จะปรากฏขึ้นเมื่อตรงกับอินพุต หากมีการป้อนข้อมูลอื่นใด PDA จะเข้าสู่สถานะตาย เมื่อเราไปถึงสัญลักษณ์พิเศษ '$' เราจะไปที่สถานะยอมรับq4.