PadhaikoAll subjects

Pushdown Automata, CFG↔PDA & Context-Sensitive Grammar

Theory of Computation (ENCT 203)

Open in the Padhaiko app

Pushdown 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:

  1. Input Tape: A sequential tape containing the input string, read from left to right by a read-only tape head.
  2. Finite-State Control: A finite set of internal states governed by transition logic.
  3. Pushdown Stack: An infinite auxiliary storage memory accessible strictly at the top element via push and pop operations.
Definition

Formal 7-Tuple Definition of a PDA

A Pushdown Automaton is formally defined as a 7-tuple:

where:

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.

Stack Operations

  1. 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 .
  2. Pop: The top symbol of the stack is removed by replacing it with ().
  3. 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:

The move relation is denoted by :

Language Acceptance Criteria

A PDA can accept an input string through either of two equivalent conventions:

  1. Acceptance by Final State (): The input string is completely read, and the automaton reaches an accepting state , regardless of what remains on the stack:
  1. Acceptance by Empty Stack (): The input string is completely read, and the stack is simultaneously emptied, regardless of the final state reached:
Theorem

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

Example 1

1

Design a Pushdown Automaton for the language:

Design Strategy
  1. In state , for each input , push onto the stack.
  2. When the first arrives, transition to state and pop one from the stack.
  3. In state , continue popping one for each subsequent .
  4. When input is exhausted and the initial stack symbol is exposed, transition via to accepting state .
State Diagram and Machine Verification
PDA for an bnPDA
PDA for a^n b^n b,a/ε a,z0/az0 a,a/aa b,a/ε ε,z0/z0 q0 q1 q2
StateInputPopNext StatePush
→q0az0q0az0
→q0aaq0aa
→q0baq1ε
q1baq1ε
q1εz0q2z0
  • Machine-checked
  • ✓ accepts ab
  • ✓ accepts aabb
  • ✓ accepts aaabbb
  • ✓ rejects ε
  • ✓ rejects a
  • ✓ rejects b
  • ✓ rejects aab
  • ✓ rejects abb
  • ✓ rejects ba
Answer:

The PDA recognizes .

Example 2

2

Design a PDA that accepts the language:

Counting Strategy Using the Stack

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.
Automaton Specification
PDA for Equal Number of a's and b'sPDA
PDA for Equal Number of a's and b's a,z0/az0 b,z0/bz0 a,a/aa b,b/bb a,b/ε b,a/ε ε,z0/z0 q0 q1
StateInputPopNext StatePush
→q0az0q0az0
→q0bz0q0bz0
→q0aaq0aa
→q0bbq0bb
→q0abq0ε
→q0baq0ε
→q0εz0q1z0
  • Machine-checked
  • ✓ accepts ε
  • ✓ accepts ab
  • ✓ accepts ba
  • ✓ accepts aabb
  • ✓ accepts bbaa
  • ✓ accepts abab
  • ✓ rejects a
  • ✓ rejects b
  • ✓ rejects aab
  • ✓ rejects abb
  • ✓ rejects aa
Answer:

The PDA correctly balances equal counts of and in arbitrary order.

Example 3

3

Design a pushdown automaton for the language:

Test your design for the string . [2074 Chaitra]

Design Strategy

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 .
Machine Verification
PDA for an b2nPDA
PDA for a^n b^{2n} a,a/aa a,z0/az0 b,a/a b,a/ε b,a/a ε,z0/z0 q0 q1 q2 q3
StateInputPopNext StatePush
→q0aaq0aa
→q0az0q0az0
→q0baq1a
q1baq2ε
q2baq1a
q2εz0q3z0
  • Machine-checked
  • ✓ accepts abb
  • ✓ accepts aabbbb
  • ✓ rejects ε
  • ✓ rejects ab
  • ✓ rejects a
  • ✓ rejects b
  • ✓ rejects abbb
  • ✓ rejects aabb
Tracing String aabbbb
Answer:

The PDA successfully verifies with 's matching 's.

Example 4

4

Construct a PDA for the even-length palindrome language:

Non-Deterministic Guessing of the Center

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 .
Automaton Verification
NPDA for wwRPDA
NPDA for ww^R a,a/ε b,b/ε a,z0/az0 b,z0/bz0 a,a/aa b,b/bb a,b/ab b,a/ba ε,z0/z0 ε,a/a ε,b/b ε,z0/z0 q0 q1 q2
StateInputPopNext StatePush
→q0az0q0az0
→q0bz0q0bz0
→q0aaq0aa
→q0bbq0bb
→q0abq0ab
→q0baq0ba
→q0εz0q1z0
→q0εaq1a
→q0εbq1b
q1aaq1ε
q1bbq1ε
q1εz0q2z0
  • Machine-checked
  • ✓ accepts ε
  • ✓ accepts aa
  • ✓ accepts bb
  • ✓ accepts abba
  • ✓ accepts baab
  • ✓ rejects ab
  • ✓ rejects ba
  • ✓ rejects a
  • ✓ rejects b
  • ✓ rejects abb
Answer:

The NPDA accepts all even palindromes through non-deterministic center guessing.

Example 5

5

Design a PDA for the marked palindrome language:

Deterministic Marker Detection

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 Diagram and Verification
DPDA for wcwRPDA
DPDA for wcw^R a,a/ε b,b/ε a,z0/az0 b,z0/bz0 a,a/aa b,b/bb a,b/ab b,a/ba c,z0/z0 c,a/a c,b/b ε,z0/z0 q0 q1 q2
StateInputPopNext StatePush
→q0az0q0az0
→q0bz0q0bz0
→q0aaq0aa
→q0bbq0bb
→q0abq0ab
→q0baq0ba
→q0cz0q1z0
→q0caq1a
→q0cbq1b
q1aaq1ε
q1bbq1ε
q1εz0q2z0
  • Machine-checked
  • ✓ accepts c
  • ✓ accepts aca
  • ✓ accepts bcb
  • ✓ accepts abcba
  • ✓ accepts bacab
  • ✓ rejects ε
  • ✓ rejects ab
  • ✓ rejects acb
  • ✓ rejects abca
Answer:

Because marker unambiguously triggers the popping phase, this language is recognized by a Deterministic PDA (DPDA).

Example 6

6

Design a PDA for the language:

Design Analysis
  • 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.
Automaton Verification
PDA for an bn cmPDA
PDA for a^n b^n c^m c,z0/z0 b,a/ε a,a/aa a,z0/az0 b,a/ε c,z0/z0 ε,z0/z0 q0 q1 q2 q3
StateInputPopNext StatePush
→q0aaq0aa
→q0az0q0az0
→q0baq1ε
q1baq1ε
q1cz0q2z0
q2cz0q2z0
q2εz0q3z0
  • Machine-checked
  • ✓ accepts abc
  • ✓ accepts abcc
  • ✓ accepts aabbc
  • ✓ accepts aabbcc
  • ✓ rejects ε
  • ✓ rejects ab
  • ✓ rejects c
  • ✓ rejects a
  • ✓ rejects aabb
Answer:

The PDA balances and counts on the stack, then verifies trailing 's.

Example 7

7

Design a PDA to accept the language:

Stack Counter Design
  • 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 Diagram and Verification
PDA for am bn c3mPDA
PDA for a^m b^n c^{3m} b,a/a a,z0/az0 a,a/aa b,a/a c,a/a c,a/a c,a/ε c,a/a ε,z0/z0 q0 q1 q2 q3 q4 q5
StateInputPopNext StatePush
→q0az0q0az0
→q0aaq0aa
→q0baq1a
q1baq1a
q1caq2a
q2caq3a
q3caq4ε
q4caq2a
q4εz0q5z0
  • Machine-checked
  • ✓ accepts abccc
  • ✓ accepts abbccc
  • ✓ accepts aabbcccccc
  • ✓ rejects ε
  • ✓ rejects abc
  • ✓ rejects abcc
  • ✓ rejects aabccc
Answer:

The PDA correctly balances 's against 's across intermediate 's.

Example 8

8

Design a PDA to accept the language:

Sequential Stack Operations

The language consists of two independent matching blocks:

  1. First block: push 's in , pop with 's in until .
  2. Second block: push 's in , pop with 's in until .
  3. Transition to accept state when empty.
Automaton Verification
PDA for an bn cm dmPDA
PDA for a^n b^n c^m d^m d,c/ε c,c/cc b,a/ε a,z0/az0 a,a/aa b,a/ε c,z0/cz0 d,c/ε ε,z0/z0 q0 q1 q2 q3 q4
StateInputPopNext StatePush
→q0az0q0az0
→q0aaq0aa
→q0baq1ε
q1baq1ε
q1cz0q2cz0
q2ccq2cc
q2dcq3ε
q3dcq3ε
q3εz0q4z0
  • Machine-checked
  • ✓ accepts abcd
  • ✓ accepts aabbcd
  • ✓ accepts abccdd
  • ✓ accepts aabbccdd
  • ✓ rejects ε
  • ✓ rejects abc
  • ✓ rejects abd
  • ✓ rejects abbcd
Answer:

The PDA verifies independent consecutive matching blocks sequentially.

Example 9

9

Design a PDA for the language:

Non-Deterministic Branching

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 ().
Automaton Verification
NPDA for ai bj ck with i=j or i=kPDA
NPDA for a^i b^j c^k with i=j or i=k c,a/ε b,a/a c,z0/z0 b,a/ε a,z0/az0 a,a/aa b,a/ε ε,z0/z0 c,z0/z0 ε,z0/z0 ε,z0/z0 ε,z0/z0 b,a/a c,a/ε ε,z0/z0 ε,z0/z0 q0 q1 q2 q3 q4 q5
StateInputPopNext StatePush
→q0az0q0az0
→q0aaq0aa
→q0baq1ε
→q0εz0q1z0
q1baq1ε
q1cz0q2z0
q1εz0q2z0
q2cz0q2z0
q2εz0q3z0
→q0εz0q4z0
→q0baq4a
q4baq4a
q4caq5ε
q4εz0q5z0
q5caq5ε
q5εz0q3z0
  • Machine-checked
  • ✓ accepts ε
  • ✓ accepts ab
  • ✓ accepts abc
  • ✓ accepts aabbc
  • ✓ accepts aabbcc
  • ✓ rejects a
  • ✓ rejects b
  • ✓ rejects aab
  • ✓ rejects abb
Answer:

The NPDA accepts or via non-deterministic branching.


3.8 Equivalence of CFL and PDA: Conversion of CFG to PDA

Theorem

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:

  1. Initialize: Push the start symbol onto the stack.
  2. Variable Expansions: For each production rule , define an -move:
  1. Terminal Matchings: For each terminal , define a terminal consumption move:
Example 10

10

Construct an equivalent Pushdown Automaton for the context-free grammar:

Conversion Rules

Let accept by empty stack:

  1. Initialize stack with start variable :
  1. Non-terminal expansion rules from :
  1. Terminal matching rules:
Automaton Specification (Accept by Empty Stack)
PDA from CFG by Empty StackPDA
PDA from CFG by Empty Stack ε,S/aSa ε,S/bSb ε,S/c a,a/ε b,b/ε c,c/ε ε,z0/S p q
StateInputPopNext StatePush
→pεz0qS
qεSqaSa
qεSqbSb
qεSqc
qaaqε
qbbqε
qccqε
  • Machine-checked
  • ✓ accepts c
  • ✓ accepts aca
  • ✓ accepts bcb
  • ✓ accepts abcba
  • ✓ rejects ε
  • ✓ rejects a
  • ✓ rejects b
  • ✓ rejects ab
  • ✓ rejects ca
Answer:

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

Definition

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:

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

Example 11

11

Design a PDA for the language:

and trace the string . Also draw its derivation parse tree. [2082 Kartik]

State Machine Design
  • : 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 ).
Automaton Verification
PDA for am bn (m >= n)PDA
PDA for a^m b^n (m >= n) b,a/ε a,z0/az0 a,a/aa b,a/ε ε,z0/z0 ε,a/a q1 q2 q3
StateInputPopNext StatePush
→q1az0q1az0
→q1aaq1aa
→q1baq2ε
q2baq2ε
q2εz0q3z0
q2εaq3a
  • Machine-checked
  • ✓ accepts ab
  • ✓ accepts aab
  • ✓ accepts aaabb
  • ✓ accepts aaaaabbb
  • ✓ rejects ε
  • ✓ rejects a
  • ✓ rejects b
  • ✓ rejects abb
  • ✓ rejects aabbb
Trace for aaaaabbb (m=5, n=3)
Answer:

The string is accepted with surplus remaining on the stack.

Example 12

12

Design a PDA to accept:

Check your design for the string . [2081 Bhadra]

Counting Scheme

Push all 's in . Pop 's with 's in , then continue popping 's with 's in . Accept in when stack top is .

Automaton Verification
PDA for ai bj ck (i = j + k)PDA
PDA for a^i b^j c^k (i = j + k) c,a/ε b,a/ε a,a/aa a,z0/az0 b,a/ε c,a/ε ε,z0/z0 q0 q1 q2 q3 q4
StateInputPopNext StatePush
→q0az0q1az0
q1aaq1aa
q1baq2ε
q2baq2ε
q2caq3ε
q3caq3ε
q3εz0q4z0
  • Machine-checked
  • ✓ accepts aabc
  • ✓ accepts aaabcc
  • ✓ accepts aaabbc
  • ✓ rejects ε
  • ✓ rejects abc
  • ✓ rejects a
  • ✓ rejects b
  • ✓ rejects c
  • ✓ rejects aabb
Trace for aaabcc (i=3, j=1, k=2)
Answer:

The string is accepted via matched popping.

Example 13

13

Design a PDA for . Test your design for the string . [2076 Ashwin]

Design Analysis

For every pair of 's read, push one onto the stack. For every three 's read, pop one from the stack.

Automaton Verification
PDA for a2n b3nPDA
PDA for a^{2n} b^{3n} ε,z0/z0 a,z0/z0 a,a/aa a,z0/az0 a,a/a b,a/a b,a/a b,a/ε ε,z0/z0 q0 qf q1 q2 q3 q4
StateInputPopNext StatePush
→q0εz0qfz0
→q0az0q1z0
q1aaq2aa
q1az0q2az0
q2aaq1a
q2baq3a
q3baq4a
q4baq2ε
q2εz0qfz0
  • Machine-checked
  • ✓ accepts ε
  • ✓ accepts aabbb
  • ✓ accepts aaaabbbbbb
  • ✓ rejects ab
  • ✓ rejects aab
  • ✓ rejects aabb
  • ✓ rejects abbb
Trace for aabbb
Answer:

The design verifies and accepts ().

Example 14

14

Design a PDA which accepts all strings of . [2075 Chaitra]

Nested Pushdown Operation

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 .

Automaton Verification
PDA for an bm cm dnPDA
PDA for a^n b^m c^m d^n d,a/ε c,b/ε b,b/bb a,a/aa a,z0/az0 b,a/ba c,b/ε d,a/ε ε,z0/z0 q0 q1 q2 q3 q4
StateInputPopNext StatePush
→q0aaq0aa
→q0az0q0az0
→q0baq1ba
q1bbq1bb
q1cbq2ε
q2cbq2ε
q2daq3ε
q3daq3ε
q3εz0q4z0
  • Machine-checked
  • ✓ accepts abcd
  • ✓ accepts aabbccdd
  • ✓ accepts abbccd
  • ✓ rejects ε
  • ✓ rejects ab
  • ✓ rejects abc
  • ✓ rejects abbcdd
Answer:

The nested stack structure handles in LIFO order.

Example 15

15

Design a pushdown automaton which accepts . [2075 Ashwin]

State Transitions

Push 's in . Read 's without changing stack in . For each on stack, consume two 's (). Accept in when is reached.

Automaton Verification
PDA for an bm c2nPDA
PDA for a^n b^m c^{2n} b,a/a a,z0/az0 a,a/aa b,a/a c,a/a c,a/ε c,a/a ε,z0/z0 q0 q1 q2 q3 q4
StateInputPopNext StatePush
→q0az0q0az0
→q0aaq0aa
→q0baq1a
q1baq1a
q1caq2a
q2caq3ε
q3caq2a
q3εz0q4z0
  • Machine-checked
  • ✓ accepts abcc
  • ✓ accepts abbcc
  • ✓ accepts aabcccc
  • ✓ rejects ε
  • ✓ rejects abc
  • ✓ rejects abccc
  • ✓ rejects aabbcc
Answer:

The PDA correctly balances 's against 's across 's.

Example 16

16

Design a PDA that accepts and check it for the string . [2074 Ashwin]

Alternating Cycle Logic
  • 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.
Automaton Verification
PDA for an b2n+1PDA
PDA for a^n b^{2n+1} a,z0/az0 a,a/aa b,a/a b,a/a b,a/ε b,a/a ε,z0/z0 q0 q1 q2 q3 q4
StateInputPopNext StatePush
→q0az0q0az0
→q0aaq0aa
→q0baq1a
q1baq2a
q2baq3ε
q3baq2a
q3εz0q4z0
  • Machine-checked
  • ✓ accepts abbb
  • ✓ accepts aabbbbb
  • ✓ accepts aaabbbbbbb
  • ✓ rejects ε
  • ✓ rejects ab
  • ✓ rejects abb
  • ✓ rejects abbbb
  • ✓ rejects aabbbb
Trace for aabbbbb
Answer:

The string is accepted.

Example 17

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]

Pushdown Matching Strategy

Push 's in . Pop with 's in . Continue popping with 's in . Accept in when is reached.

Automaton Verification
PDA for ai bj ck with i = j + kPDA
PDA for a^i b^j c^k with i = j + k c,a/ε b,a/ε a,a/aa a,z0/az0 b,a/ε c,a/ε ε,z0/z0 q0 q1 q2 q3
StateInputPopNext StatePush
→q0aaq0aa
→q0az0q0az0
→q0baq1ε
q1baq1ε
q1caq2ε
q2caq2ε
q2εz0q3z0
  • Machine-checked
  • ✓ accepts aabc
  • ✓ accepts aaaabbcc
  • ✓ rejects ε
  • ✓ rejects abc
  • ✓ rejects a
  • ✓ rejects b
  • ✓ rejects c
Trace for aaaabbcc (i=4, j=2, k=2)
Answer:

The design verifies through continuous popping of stacked 's.

Example 18

18

Construct a PDA which accepts . Verify your design by taking as an example. [2073 Shrawan]

Two-Phase Matching

The 's are split into (matching 's) and (matching 's):

  1. In : push 's.
  2. First 's pop 's until .
  3. Subsequent 's in push 's onto the stack.
  4. In : 's pop 's. Accept in on .
Automaton Verification
PDA for an bn+m cmPDA
PDA for a^n b^{n+m} c^m c,b/ε b,b/bb b,z0/bz0 b,a/ε a,a/aa a,z0/az0 b,a/ε c,b/ε ε,z0/z0 q0 q1 q2 q3
StateInputPopNext StatePush
→q0aaq0aa
→q0az0q0az0
→q0baq1ε
q1bbq1bb
q1bz0q1bz0
q1baq1ε
q1cbq2ε
q2cbq2ε
q2εz0q3z0
  • Machine-checked
  • ✓ accepts abbc
  • ✓ accepts abbbcc
  • ✓ accepts aabbbbcc
  • ✓ rejects ε
  • ✓ rejects abc
  • ✓ rejects abb
  • ✓ rejects aabbc
Trace for abbbcc (n=1, m=2)
Answer:

The string is accepted.

Example 19

19

Design a PDA that accepts and check the string . [2072 Chaitra]

Counting 3a's to 1b

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 .

Automaton Verification
PDA for a3n bnPDA
PDA for a^{3n} b^n b,a/ε a,z0/az0 a,a/aa a,a/a a,a/a b,a/ε ε,z0/z0 q0 q1 q2 q3 q4
StateInputPopNext StatePush
→q0az0q1az0
→q0aaq1aa
q1aaq2a
q2aaq0a
→q0baq3ε
q3baq3ε
q3εz0q4z0
  • Machine-checked
  • ✓ accepts aaab
  • ✓ accepts aaaaaabb
  • ✓ rejects ε
  • ✓ rejects a
  • ✓ rejects b
  • ✓ rejects aab
  • ✓ rejects aaabb
Trace for aaaaaabb (n=2)
Answer:

The PDA verifies with exactly 2 's stacked for 6 input 's.

Example 20

20

Design a pushdown automaton to accept . Show how it accepts the string . [2072 Kartik]

Non-Deterministic Model

Push all input symbols in . Non-deterministically guess center via -transition to . Pop matching symbols in . Accept in when stack is .

Automaton Verification
NPDA for wwR String TracePDA
NPDA for ww^R String Trace b,b/ε a,a/ε b,z0/bz0 a,z0/az0 a,b/ab b,a/ba a,a/aa b,b/bb ε,b/b ε,a/a ε,z0/z0 q0 q1 q2
StateInputPopNext StatePush
→q0bz0q0bz0
→q0az0q0az0
→q0abq0ab
→q0baq0ba
→q0aaq0aa
→q0bbq0bb
→q0εbq1b
→q0εaq1a
q1bbq1ε
q1aaq1ε
q1εz0q2z0
  • Machine-checked
  • ✓ accepts aa
  • ✓ accepts bb
  • ✓ accepts abba
  • ✓ accepts baab
  • ✓ accepts abbbba
  • ✓ rejects ab
  • ✓ rejects ba
  • ✓ rejects a
  • ✓ rejects b
  • ✓ rejects abb
Trace for abbbba (w = abb)
Answer:

The string is successfully verified.


Exercise Set: Pushdown Automata & Operations

Exercise Questions: Pushdown Automata

Question 1

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:

  1. 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.
  2. Finite State Control: A finite-state sequential logic unit storing the active state and executing state changes determined by the transition function .
  3. 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.

Answer:

A Pushdown Automaton consists of:

  1. An input tape with cells containing symbols from and an end-of-string marker.
  2. A finite-state control with state transitions governed by .
  3. A read-only input head that advances sequentially left to right.
  4. An unbounded pushdown stack storing symbols from alphabet , accessed via a LIFO top-of-stack pointer.
Question 2

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:

  1. State Change: Updates the control state from to .
  2. 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).
  3. 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:

  1. Acceptance by Final State:
  1. Acceptance by Empty Stack (Null Stack):

Concrete Machine Verification: The following PDA accepts by final state:

PDA Operation Example: Balanced a and b SequencePDA
PDA Operation Example: Balanced a and b Sequence b,a/ε a,z0/az0 a,a/aa b,a/ε ε,z0/z0 q0 q1 q2
StateInputPopNext StatePush
→q0az0q0az0
→q0aaq0aa
→q0baq1ε
q1baq1ε
q1εz0q2z0
  • 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.

Answer:

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:

  1. Transitions to a next finite state.
  2. Advances the input head (unless an -move was taken).
  3. Replaces the current top stack symbol with a string of stack symbols (pushing new symbols, popping by writing , or leaving it unchanged).

Past exam questions for Theory of Computation

← CFL Closure, Pumping Lemma & Decision AlgorithmsTuring Machines: Representation, Moves & Computing →