Push Down Automata Flashcards
(16 cards)
What model of computation recognizes context-free languages?
Pushdown Automata (PDA).
Why can’t finite automata recognize the language aⁿbⁿ?
Because they have no memory to track how many a’s and b’s have been seen.
What feature gives PDAs more power than DFAs?
A stack, which allows them to store and recall information.
What is the key idea for using a PDA to recognize aⁿbⁿ?
Push an ‘a’ for each a read, and pop one for each b read — accept if the stack is empty.
What is the formal definition of a PDA?
A 6-tuple: (Q, Σ, Γ, s, Δ, F), where Q is states, Σ is input alphabet, Γ is stack alphabet, s is start state, Δ is transition relation, and F is accepting states.
What does the PDA transition function Δ contain?
Tuples of the form ((p, a, α), (q, β)) — meaning read a, pop α, move to q, and push β.
What happens if the PDA cannot match the required top stack symbol?
The transition is not valid — the move is blocked.
What is a PDA configuration?
A triple (p, w, γ), representing the current state, input remaining, and stack content.
What does a one-step PDA transition look like?
(p, av, γ) ⊢ (q, v, δ), where a is read, α is popped, β is pushed, and state changes from p to q.
When does a PDA accept a word?
If it reads all input, ends in an accepting state, and the stack is empty.
What language does a PDA that pushes a’s and pops for b’s recognize?
L = { aⁿbⁿ | n ≥ 0 }
How does a PDA recognize aⁿbⁿ using three states?
State 2 pushes a’s, state 3 pops a’s for b’s, accept in state 3 with empty stack.
What does the stack symbol ‘c’ represent in the equal-a-b PDA?
It marks the bottom of the stack — a guard symbol.
What language does a PDA that balances total counts of a’s and b’s (regardless of order) recognize?
L = { w ∈ {a,b}* | #a(w) = #b(w) }
How does a PDA process a word with equal a’s and b’s in arbitrary order?
It pushes opposing symbols and cancels out matching pairs using stack transitions.
What is the major difference between DFAs and PDAs?
DFAs have no memory; PDAs use a stack to track nested or balanced structure.
