Pushdown Automata, CFG↔PDA & Context-Sensitive Grammar
Open in the Padhaiko appPushdown Automata, CFG↔PDA and Context-Sensitive Grammar
Finite automata lack the memory needed to recognize context-free languages requiring unbounded counting or symmetric matching, such as or . A Pushdown Automaton (PDA) extends the finite-state machine by incorporating an unbounded, last-in-first-out (LIFO) stack memory. PDAs serve as the operational, machine-based counterpart to context-free grammars. Beyond CFLs lie the Context-Sensitive Grammars (CSGs) and languages, recognized by linear-bounded automata.
3.7 Introduction to Pushdown Automata (PDA)
A Pushdown Automaton consists of three cooperative components:
- Input Tape: A sequential tape containing the input string, read from left to right by a read-only tape head.
- Finite-State Control: A finite set of internal states governed by transition logic.
- Pushdown Stack: An infinite auxiliary storage memory accessible strictly at the top element via push and pop operations.
Formal 7-Tuple Definition of a PDA
A Pushdown Automaton is formally defined as a 7-tuple:
where:
- is a finite set of states.
- is a finite input alphabet.
- is a finite stack alphabet.
- is the transition function mapping:
Given current state , input symbol , and current stack top , returns a finite set of pairs where is the next state and replaces on top of the stack.
- is the initial start state.
- is the initial start symbol present on the stack.
- is the set of accepting (final) states.
Stack Operations
- Push: A new symbol or sequence of symbols is pushed onto the stack. If is popped and replaced by , symbol is pushed on top of .
- Pop: The top symbol of the stack is removed by replacing it with ().
- No-operation (Skip): The top symbol remains unchanged on the stack ().
Instantaneous Description (ID)
The configuration of a PDA at any discrete moment is captured by an Instantaneous Description (ID) written as a 3-tuple:
where:
- is the current state.
- is the remaining unconsumed input string.
- is the complete current content of the stack, with the leftmost symbol representing the top of the stack.
The move relation is denoted by :
Language Acceptance Criteria
A PDA can accept an input string through either of two equivalent conventions:
- Acceptance by Final State (): The input string is completely read, and the automaton reaches an accepting state , regardless of what remains on the stack:
- Acceptance by Empty Stack (): The input string is completely read, and the stack is simultaneously emptied, regardless of the final state reached:
Equivalence of Acceptance Criteria
For every PDA that accepts by final state, there exists an equivalent PDA that accepts by empty stack such that , and conversely.
Worked Out Examples: Designing Pushdown Automata
1
Design a Pushdown Automaton for the language:
- In state , for each input , push onto the stack.
- When the first arrives, transition to state and pop one from the stack.
- In state , continue popping one for each subsequent .
- When input is exhausted and the initial stack symbol is exposed, transition via to accepting state .
| State | Input | Pop | Next State | Push |
|---|---|---|---|---|
| →q0 | a | z0 | q0 | az0 |
| →q0 | a | a | q0 | aa |
| →q0 | b | a | q1 | ε |
| q1 | b | a | q1 | ε |
| q1 | ε | z0 | q2 | z0 |
- Machine-checked
- ✓ accepts ab
- ✓ accepts aabb
- ✓ accepts aaabbb
- ✓ rejects ε
- ✓ rejects a
- ✓ rejects b
- ✓ rejects aab
- ✓ rejects abb
- ✓ rejects ba
The PDA recognizes .
2
Design a PDA that accepts the language:
The stack maintains the surplus of one symbol over the other:
- If the stack holds , push the incoming symbol ( or ).
- If incoming symbol matches stack top, push it (accumulating surplus).
- If incoming symbol differs from stack top, pop it (canceling an opposite pair).
- Transition to accept state when the stack returns to at string end.
| State | Input | Pop | Next State | Push |
|---|---|---|---|---|
| →q0 | a | z0 | q0 | az0 |
| →q0 | b | z0 | q0 | bz0 |
| →q0 | a | a | q0 | aa |
| →q0 | b | b | q0 | bb |
| →q0 | a | b | q0 | ε |
| →q0 | b | a | q0 | ε |
| →q0 | ε | z0 | q1 | z0 |
- Machine-checked
- ✓ accepts ε
- ✓ accepts ab
- ✓ accepts ba
- ✓ accepts aabb
- ✓ accepts bbaa
- ✓ accepts abab
- ✓ rejects a
- ✓ rejects b
- ✓ rejects aab
- ✓ rejects abb
- ✓ rejects aa
The PDA correctly balances equal counts of and in arbitrary order.
3
Design a pushdown automaton for the language:
Test your design for the string . [2074 Chaitra]
Every input is pushed onto the stack. Each stacked must match two 's:
- State : read all 's and push them onto the stack.
- On reading , enter an alternating two-state loop ():
- on (first , no pop).
- on (second , pop ).
- on (next , no pop).
- When stack is emptied to , transition to accepting state .
| State | Input | Pop | Next State | Push |
|---|---|---|---|---|
| →q0 | a | a | q0 | aa |
| →q0 | a | z0 | q0 | az0 |
| →q0 | b | a | q1 | a |
| q1 | b | a | q2 | ε |
| q2 | b | a | q1 | a |
| q2 | ε | z0 | q3 | z0 |
- Machine-checked
- ✓ accepts abb
- ✓ accepts aabbbb
- ✓ rejects ε
- ✓ rejects ab
- ✓ rejects a
- ✓ rejects b
- ✓ rejects abbb
- ✓ rejects aabb
The PDA successfully verifies with 's matching 's.
4
Construct a PDA for the even-length palindrome language:
Because no special delimiter marks the center of the palindrome , the automaton must non-deterministically guess when the first half ends and the reversed half begins:
- In state , read and push every input symbol ( or ).
- Non-deterministically branch via an -transition from to , guessing the center.
- In state , match each remaining input symbol against the stack top and pop.
- Accept in state when stack returns to .
| State | Input | Pop | Next State | Push |
|---|---|---|---|---|
| →q0 | a | z0 | q0 | az0 |
| →q0 | b | z0 | q0 | bz0 |
| →q0 | a | a | q0 | aa |
| →q0 | b | b | q0 | bb |
| →q0 | a | b | q0 | ab |
| →q0 | b | a | q0 | ba |
| →q0 | ε | z0 | q1 | z0 |
| →q0 | ε | a | q1 | a |
| →q0 | ε | b | q1 | b |
| q1 | a | a | q1 | ε |
| q1 | b | b | q1 | ε |
| q1 | ε | z0 | q2 | z0 |
- Machine-checked
- ✓ accepts ε
- ✓ accepts aa
- ✓ accepts bb
- ✓ accepts abba
- ✓ accepts baab
- ✓ rejects ab
- ✓ rejects ba
- ✓ rejects a
- ✓ rejects b
- ✓ rejects abb
The NPDA accepts all even palindromes through non-deterministic center guessing.
5
Design a PDA for the marked palindrome language:
Unlike , the center symbol serves as an explicit delimiter:
- In state , push all symbols before .
- On reading , transition to without altering the stack.
- In state , match incoming symbols against stack top and pop.
- Transition to accept state on empty stack .
| State | Input | Pop | Next State | Push |
|---|---|---|---|---|
| →q0 | a | z0 | q0 | az0 |
| →q0 | b | z0 | q0 | bz0 |
| →q0 | a | a | q0 | aa |
| →q0 | b | b | q0 | bb |
| →q0 | a | b | q0 | ab |
| →q0 | b | a | q0 | ba |
| →q0 | c | z0 | q1 | z0 |
| →q0 | c | a | q1 | a |
| →q0 | c | b | q1 | b |
| q1 | a | a | q1 | ε |
| q1 | b | b | q1 | ε |
| q1 | ε | z0 | q2 | z0 |
- Machine-checked
- ✓ accepts c
- ✓ accepts aca
- ✓ accepts bcb
- ✓ accepts abcba
- ✓ accepts bacab
- ✓ rejects ε
- ✓ rejects ab
- ✓ rejects acb
- ✓ rejects abca
Because marker unambiguously triggers the popping phase, this language is recognized by a Deterministic PDA (DPDA).
6
Design a PDA for the language:
- Read and push 's in state .
- For each , pop an in state .
- Upon seeing in , read one or more 's in state without modifying the stack.
- Transition to accept state upon input completion.
| State | Input | Pop | Next State | Push |
|---|---|---|---|---|
| →q0 | a | a | q0 | aa |
| →q0 | a | z0 | q0 | az0 |
| →q0 | b | a | q1 | ε |
| q1 | b | a | q1 | ε |
| q1 | c | z0 | q2 | z0 |
| q2 | c | z0 | q2 | z0 |
| q2 | ε | z0 | q3 | z0 |
- Machine-checked
- ✓ accepts abc
- ✓ accepts abcc
- ✓ accepts aabbc
- ✓ accepts aabbcc
- ✓ rejects ε
- ✓ rejects ab
- ✓ rejects c
- ✓ rejects a
- ✓ rejects aabb
The PDA balances and counts on the stack, then verifies trailing 's.
7
Design a PDA to accept the language:
- In state , push an for every read.
- In state , read 's without changing the stack.
- For each on the stack, consume three 's using a 3-cycle ().
- The third pops an . Accept in state when stack reaches .
| State | Input | Pop | Next State | Push |
|---|---|---|---|---|
| →q0 | a | z0 | q0 | az0 |
| →q0 | a | a | q0 | aa |
| →q0 | b | a | q1 | a |
| q1 | b | a | q1 | a |
| q1 | c | a | q2 | a |
| q2 | c | a | q3 | a |
| q3 | c | a | q4 | ε |
| q4 | c | a | q2 | a |
| q4 | ε | z0 | q5 | z0 |
- Machine-checked
- ✓ accepts abccc
- ✓ accepts abbccc
- ✓ accepts aabbcccccc
- ✓ rejects ε
- ✓ rejects abc
- ✓ rejects abcc
- ✓ rejects aabccc
The PDA correctly balances 's against 's across intermediate 's.
8
Design a PDA to accept the language:
The language consists of two independent matching blocks:
- First block: push 's in , pop with 's in until .
- Second block: push 's in , pop with 's in until .
- Transition to accept state when empty.
| State | Input | Pop | Next State | Push |
|---|---|---|---|---|
| →q0 | a | z0 | q0 | az0 |
| →q0 | a | a | q0 | aa |
| →q0 | b | a | q1 | ε |
| q1 | b | a | q1 | ε |
| q1 | c | z0 | q2 | cz0 |
| q2 | c | c | q2 | cc |
| q2 | d | c | q3 | ε |
| q3 | d | c | q3 | ε |
| q3 | ε | z0 | q4 | z0 |
- Machine-checked
- ✓ accepts abcd
- ✓ accepts aabbcd
- ✓ accepts abccdd
- ✓ accepts aabbccdd
- ✓ rejects ε
- ✓ rejects abc
- ✓ rejects abd
- ✓ rejects abbcd
The PDA verifies independent consecutive matching blocks sequentially.
9
Design a PDA for the language:
The PDA non-deterministically chooses which equality to test:
- Branch 1 (): matches 's with 's (), ignoring 's.
- Branch 2 (): ignores 's and matches 's with 's ().
| State | Input | Pop | Next State | Push |
|---|---|---|---|---|
| →q0 | a | z0 | q0 | az0 |
| →q0 | a | a | q0 | aa |
| →q0 | b | a | q1 | ε |
| →q0 | ε | z0 | q1 | z0 |
| q1 | b | a | q1 | ε |
| q1 | c | z0 | q2 | z0 |
| q1 | ε | z0 | q2 | z0 |
| q2 | c | z0 | q2 | z0 |
| q2 | ε | z0 | q3 | z0 |
| →q0 | ε | z0 | q4 | z0 |
| →q0 | b | a | q4 | a |
| q4 | b | a | q4 | a |
| q4 | c | a | q5 | ε |
| q4 | ε | z0 | q5 | z0 |
| q5 | c | a | q5 | ε |
| q5 | ε | z0 | q3 | z0 |
- Machine-checked
- ✓ accepts ε
- ✓ accepts ab
- ✓ accepts abc
- ✓ accepts aabbc
- ✓ accepts aabbcc
- ✓ rejects a
- ✓ rejects b
- ✓ rejects aab
- ✓ rejects abb
The NPDA accepts or via non-deterministic branching.
3.8 Equivalence of CFL and PDA: Conversion of CFG to PDA
Equivalence of CFLs and PDAs
A language is context-free if and only if there exists a Pushdown Automaton such that (acceptance by empty stack) or (acceptance by final state).
Construction Algorithm (CFG to Empty-Stack PDA):
Given context-free grammar , construct a 1-state (or 2-state) PDA accepting by empty stack:
- Initialize: Push the start symbol onto the stack.
- Variable Expansions: For each production rule , define an -move:
- Terminal Matchings: For each terminal , define a terminal consumption move:
10
Construct an equivalent Pushdown Automaton for the context-free grammar:
Let accept by empty stack:
- Initialize stack with start variable :
- Non-terminal expansion rules from :
- Terminal matching rules:
| State | Input | Pop | Next State | Push |
|---|---|---|---|---|
| →p | ε | z0 | q | S |
| q | ε | S | q | aSa |
| q | ε | S | q | bSb |
| q | ε | S | q | c |
| q | a | a | q | ε |
| q | b | b | q | ε |
| q | c | c | q | ε |
- Machine-checked
- ✓ accepts c
- ✓ accepts aca
- ✓ accepts bcb
- ✓ accepts abcba
- ✓ rejects ε
- ✓ rejects a
- ✓ rejects b
- ✓ rejects ab
- ✓ rejects ca
The resulting PDA accepts the language of the CFG by empty stack through top-down simulation.
3.9 Context-Sensitive Grammar (CSG) and Linear Bounded Automata
Context-Sensitive Grammar (CSG) and Language (CSL)
A Context-Sensitive Grammar (Type 1 in the Chomsky Hierarchy) is a 4-tuple where every production rule has the form:
where:
- is a non-terminal variable.
- represent the left and right contexts.
- is a non-empty string of terminals and non-terminals.
Equivalently, every rule satisfies the non-contracting condition:
A language generated by a CSG is called a Context-Sensitive Language (CSL). Classic examples include:
Linear Bounded Automaton (LBA)
The computational machine model that recognizes Context-Sensitive Languages is the Linear Bounded Automaton (LBA)—a non-deterministic Turing Machine whose tape head cannot move beyond the portion of tape originally occupied by the input string (delimited by left and right end-markers and ).
Solutions to Examination Questions: PDA Design & Tracing
11
Design a PDA for the language:
and trace the string . Also draw its derivation parse tree. [2082 Kartik]
- : push 's onto the stack.
- : pop an for each .
- Because , surplus 's may remain on the stack after all 's are read.
- : accept if the stack has (when ) or surplus 's (when ).
| State | Input | Pop | Next State | Push |
|---|---|---|---|---|
| →q1 | a | z0 | q1 | az0 |
| →q1 | a | a | q1 | aa |
| →q1 | b | a | q2 | ε |
| q2 | b | a | q2 | ε |
| q2 | ε | z0 | q3 | z0 |
| q2 | ε | a | q3 | a |
- Machine-checked
- ✓ accepts ab
- ✓ accepts aab
- ✓ accepts aaabb
- ✓ accepts aaaaabbb
- ✓ rejects ε
- ✓ rejects a
- ✓ rejects b
- ✓ rejects abb
- ✓ rejects aabbb
The string is accepted with surplus remaining on the stack.
12
Design a PDA to accept:
Check your design for the string . [2081 Bhadra]
Push all 's in . Pop 's with 's in , then continue popping 's with 's in . Accept in when stack top is .
| State | Input | Pop | Next State | Push |
|---|---|---|---|---|
| →q0 | a | z0 | q1 | az0 |
| q1 | a | a | q1 | aa |
| q1 | b | a | q2 | ε |
| q2 | b | a | q2 | ε |
| q2 | c | a | q3 | ε |
| q3 | c | a | q3 | ε |
| q3 | ε | z0 | q4 | z0 |
- Machine-checked
- ✓ accepts aabc
- ✓ accepts aaabcc
- ✓ accepts aaabbc
- ✓ rejects ε
- ✓ rejects abc
- ✓ rejects a
- ✓ rejects b
- ✓ rejects c
- ✓ rejects aabb
The string is accepted via matched popping.
13
Design a PDA for . Test your design for the string . [2076 Ashwin]
For every pair of 's read, push one onto the stack. For every three 's read, pop one from the stack.
| State | Input | Pop | Next State | Push |
|---|---|---|---|---|
| →q0 | ε | z0 | qf | z0 |
| →q0 | a | z0 | q1 | z0 |
| q1 | a | a | q2 | aa |
| q1 | a | z0 | q2 | az0 |
| q2 | a | a | q1 | a |
| q2 | b | a | q3 | a |
| q3 | b | a | q4 | a |
| q4 | b | a | q2 | ε |
| q2 | ε | z0 | qf | z0 |
- Machine-checked
- ✓ accepts ε
- ✓ accepts aabbb
- ✓ accepts aaaabbbbbb
- ✓ rejects ab
- ✓ rejects aab
- ✓ rejects aabb
- ✓ rejects abbb
The design verifies and accepts ().
14
Design a PDA which accepts all strings of . [2075 Chaitra]
Push 's in . On reading , push 's in . Pop 's with 's in . When 's are exhausted, pop 's with 's in . Accept in on .
| State | Input | Pop | Next State | Push |
|---|---|---|---|---|
| →q0 | a | a | q0 | aa |
| →q0 | a | z0 | q0 | az0 |
| →q0 | b | a | q1 | ba |
| q1 | b | b | q1 | bb |
| q1 | c | b | q2 | ε |
| q2 | c | b | q2 | ε |
| q2 | d | a | q3 | ε |
| q3 | d | a | q3 | ε |
| q3 | ε | z0 | q4 | z0 |
- Machine-checked
- ✓ accepts abcd
- ✓ accepts aabbccdd
- ✓ accepts abbccd
- ✓ rejects ε
- ✓ rejects ab
- ✓ rejects abc
- ✓ rejects abbcdd
The nested stack structure handles in LIFO order.
15
Design a pushdown automaton which accepts . [2075 Ashwin]
Push 's in . Read 's without changing stack in . For each on stack, consume two 's (). Accept in when is reached.
| State | Input | Pop | Next State | Push |
|---|---|---|---|---|
| →q0 | a | z0 | q0 | az0 |
| →q0 | a | a | q0 | aa |
| →q0 | b | a | q1 | a |
| q1 | b | a | q1 | a |
| q1 | c | a | q2 | a |
| q2 | c | a | q3 | ε |
| q3 | c | a | q2 | a |
| q3 | ε | z0 | q4 | z0 |
- Machine-checked
- ✓ accepts abcc
- ✓ accepts abbcc
- ✓ accepts aabcccc
- ✓ rejects ε
- ✓ rejects abc
- ✓ rejects abccc
- ✓ rejects aabbcc
The PDA correctly balances 's against 's across 's.
16
Design a PDA that accepts and check it for the string . [2074 Ashwin]
- Push 's in .
- The first transitions without popping , consuming the extra .
- For each on stack, consume two 's: on first , on second (pops ).
- If more 's remain, on next .
- Transition on accepts.
| State | Input | Pop | Next State | Push |
|---|---|---|---|---|
| →q0 | a | z0 | q0 | az0 |
| →q0 | a | a | q0 | aa |
| →q0 | b | a | q1 | a |
| q1 | b | a | q2 | a |
| q2 | b | a | q3 | ε |
| q3 | b | a | q2 | a |
| q3 | ε | z0 | q4 | z0 |
- Machine-checked
- ✓ accepts abbb
- ✓ accepts aabbbbb
- ✓ accepts aaabbbbbbb
- ✓ rejects ε
- ✓ rejects ab
- ✓ rejects abb
- ✓ rejects abbbb
- ✓ rejects aabbbb
The string is accepted.
17
Design a PDA that accepts strings having the total number of 's equal to the sum of 's and 's ( where ). Test your design for the string . [2073 Chaitra]
Push 's in . Pop with 's in . Continue popping with 's in . Accept in when is reached.
| State | Input | Pop | Next State | Push |
|---|---|---|---|---|
| →q0 | a | a | q0 | aa |
| →q0 | a | z0 | q0 | az0 |
| →q0 | b | a | q1 | ε |
| q1 | b | a | q1 | ε |
| q1 | c | a | q2 | ε |
| q2 | c | a | q2 | ε |
| q2 | ε | z0 | q3 | z0 |
- Machine-checked
- ✓ accepts aabc
- ✓ accepts aaaabbcc
- ✓ rejects ε
- ✓ rejects abc
- ✓ rejects a
- ✓ rejects b
- ✓ rejects c
The design verifies through continuous popping of stacked 's.
18
Construct a PDA which accepts . Verify your design by taking as an example. [2073 Shrawan]
The 's are split into (matching 's) and (matching 's):
- In : push 's.
- First 's pop 's until .
- Subsequent 's in push 's onto the stack.
- In : 's pop 's. Accept in on .
| State | Input | Pop | Next State | Push |
|---|---|---|---|---|
| →q0 | a | a | q0 | aa |
| →q0 | a | z0 | q0 | az0 |
| →q0 | b | a | q1 | ε |
| q1 | b | b | q1 | bb |
| q1 | b | z0 | q1 | bz0 |
| q1 | b | a | q1 | ε |
| q1 | c | b | q2 | ε |
| q2 | c | b | q2 | ε |
| q2 | ε | z0 | q3 | z0 |
- Machine-checked
- ✓ accepts abbc
- ✓ accepts abbbcc
- ✓ accepts aabbbbcc
- ✓ rejects ε
- ✓ rejects abc
- ✓ rejects abb
- ✓ rejects aabbc
The string is accepted.
19
Design a PDA that accepts and check the string . [2072 Chaitra]
Read three 's through a cycle , pushing exactly one per triple:
- : push .
- : read without push.
- : read without push.
Each in pops one . Accept in on .
| State | Input | Pop | Next State | Push |
|---|---|---|---|---|
| →q0 | a | z0 | q1 | az0 |
| →q0 | a | a | q1 | aa |
| q1 | a | a | q2 | a |
| q2 | a | a | q0 | a |
| →q0 | b | a | q3 | ε |
| q3 | b | a | q3 | ε |
| q3 | ε | z0 | q4 | z0 |
- Machine-checked
- ✓ accepts aaab
- ✓ accepts aaaaaabb
- ✓ rejects ε
- ✓ rejects a
- ✓ rejects b
- ✓ rejects aab
- ✓ rejects aaabb
The PDA verifies with exactly 2 's stacked for 6 input 's.
20
Design a pushdown automaton to accept . Show how it accepts the string . [2072 Kartik]
Push all input symbols in . Non-deterministically guess center via -transition to . Pop matching symbols in . Accept in when stack is .
| State | Input | Pop | Next State | Push |
|---|---|---|---|---|
| →q0 | b | z0 | q0 | bz0 |
| →q0 | a | z0 | q0 | az0 |
| →q0 | a | b | q0 | ab |
| →q0 | b | a | q0 | ba |
| →q0 | a | a | q0 | aa |
| →q0 | b | b | q0 | bb |
| →q0 | ε | b | q1 | b |
| →q0 | ε | a | q1 | a |
| q1 | b | b | q1 | ε |
| q1 | a | a | q1 | ε |
| q1 | ε | z0 | q2 | z0 |
- Machine-checked
- ✓ accepts aa
- ✓ accepts bb
- ✓ accepts abba
- ✓ accepts baab
- ✓ accepts abbbba
- ✓ rejects ab
- ✓ rejects ba
- ✓ rejects a
- ✓ rejects b
- ✓ rejects abb
The string is successfully verified.
Exercise Set: Pushdown Automata & Operations
Exercise Questions: Pushdown Automata
Define the block diagram of a Pushdown Automaton (PDA). [2081 Bhadra]
Block Diagram Structure and Components: A Pushdown Automaton (PDA) is a computational model consisting of a finite-state control augmented with an auxiliary unbounded pushdown store (stack) operating under Last-In, First-Out (LIFO) discipline.
+-------------------------------------------------------------+
| Input Tape: [ a ] [ a ] [ b ] [ b ] [ # ] ... |
+-------------------------------------------------------------+
|
| (Read-only head, advances right)
v
+-----------------------+
| Finite State Control |
| State q ∈ Q |
+-----------------------+
^
| (Read / Pop / Push at stack top)
v
+-------------------------------------------------------------+
| Pushdown Stack: [ a ] [ a ] [ z0 ] (LIFO, unbounded) |
+-------------------------------------------------------------+
The three structural units operate as follows:
- Input Tape and Read Head: Holds the input string over alphabet , terminated by an end marker. The head is read-only and moves strictly from left to right; on an -transition, the head remains stationary.
- Finite State Control: A finite-state sequential logic unit storing the active state and executing state changes determined by the transition function .
- Pushdown Stack: A linear, unbounded storage medium containing symbols from stack alphabet . Access is strictly confined to the topmost cell (top-of-stack). The bottom of the stack is initially marked by .
Formal 7-Tuple Definition: Formally, a Pushdown Automaton is defined as a 7-tuple:
where:
- is a finite set of internal states.
- is a finite input alphabet.
- is a finite stack alphabet.
- is the transition function mapping:
- is the initial start state.
- is the initial stack start symbol.
- is the set of final (accepting) states.
Role of Stack in Context-Free Language Recognition: Finite automata possess only finite memory ( states), making it impossible to count an arbitrary number of symbols (such as remembering in ). The pushdown stack provides unbounded memory:
- Pushing a symbol onto the stack records each occurrence of an incoming symbol.
- Popping matches and balances those occurrences against subsequent symbols.
This push/pop mechanism grants the PDA the exact computational capability required to accept all context-free languages.
A Pushdown Automaton consists of:
- An input tape with cells containing symbols from and an end-of-string marker.
- A finite-state control with state transitions governed by .
- A read-only input head that advances sequentially left to right.
- An unbounded pushdown stack storing symbols from alphabet , accessed via a LIFO top-of-stack pointer.
Describe the operation of pushdown automata. [2080 Baishakh, 2079 Baishakh]
Single-Step Transition Dynamics: At each clock step, the PDA inspects its current state , the current input symbol , and the current top-of-stack symbol . If , the machine performs three simultaneous actions:
- State Change: Updates the control state from to .
- Input Consumption: If , consumes symbol and advances the input head one cell right. If , no input symbol is read and the head does not advance (-transition).
- Stack Operation: Pops top symbol and pushes string onto the stack:
- Push: If , symbol is pushed on top of .
- Pop: If , symbol is removed (stack height decreases by 1).
- No-op / Replace: If , stack remains unchanged; if , is replaced by .
Instantaneous Descriptions (ID) and Computations: The global configuration of a PDA at any instant is captured by an Instantaneous Description (ID) written as a triple:
where is the current state, is the remaining unread input string, and is the complete stack content from top to bottom (the leftmost symbol of is at the top of the stack).
A single move between configurations is denoted by the turnstile relation :
The reflexive and transitive closure is denoted by .
Acceptance Criteria: Final State vs Empty Stack: A PDA accepts input strings via two standard conventions:
- Acceptance by Final State:
- Acceptance by Empty Stack (Null Stack):
Concrete Machine Verification: The following PDA accepts by final state:
| State | Input | Pop | Next State | Push |
|---|---|---|---|---|
| →q0 | a | z0 | q0 | az0 |
| →q0 | a | a | q0 | aa |
| →q0 | b | a | q1 | ε |
| q1 | b | a | q1 | ε |
| q1 | ε | z0 | q2 | z0 |
- Machine-checked
- ✓ accepts ab
- ✓ accepts aabb
- ✓ accepts aaabbb
- ✓ rejects ε
- ✓ rejects a
- ✓ rejects b
- ✓ rejects aab
Trace on :
Since input is consumed and the PDA halts in accepting state , is accepted.
At each step, based on the current finite state, the current input symbol (or ), and the top symbol of the stack, the PDA performs three coordinated actions:
- Transitions to a next finite state.
- Advances the input head (unless an -move was taken).
- Replaces the current top stack symbol with a string of stack symbols (pushing new symbols, popping by writing , or leaving it unchanged).