Theory of Computation (CS-501) Unit 4 Notes

How unit 4 is examined

A PDA is a finite automaton plus a stack, and it accepts exactly the context free languages; PDA design, DPDA versus NPDA and the PDA to CFG conversion carry the marks.

Example of PDA

High weight

Definition. ==A PDA is a 7-tuple $M=(Q,\Sigma,\Gamma,\delta,q_0,Z_0,F)$ with states $Q$, input alphabet $\Sigma$, stack alphabet $\Gamma$, transition $\delta: Q\times(\Sigma\cup\{\epsilon\})\times\Gamma \to$ finite subsets of $Q\times\Gamma^*$, start state $q_0$, initial stack symbol $Z_0$ and final states $F$.==

Key points.

A move $\delta(q,a,X)=(p,\gamma)$ reads $a$, pops $X$, pushes $\gamma$ (leftmost symbol on top) and goes to $p$.
An instantaneous description (ID) is a triple $(q,w,\gamma)$: current state, unread input, stack contents (top at left). The move relation is $(q,aw,X\alpha)\vdash(p,w,\gamma\alpha)$.
Acceptance by final state means $(q_0,w,Z_0)\vdash^*(f,\epsilon,\gamma)$ with $f\in F$; by empty stack means $(q_0,w,Z_0)\vdash^*(p,\epsilon,\epsilon)$. Both give the same class of languages.
Strategy: push while reading the first block, pop while reading the matching block, and let $Z_0$ on top mean the count is exactly balanced.

PDA versus FA.

Basis	FA	PDA
Memory	Finite control only	Finite control plus unbounded stack
Language class	Regular	Context free
Determinism	DFA = NFA in power	DPDA weaker than NPDA
Example	$a^b^$	$a^nb^n$
Use	Lexical analysis	Parsing

Diagram. PDA for $a^nb^n$ drawn as two circles: $q_0$ (start) with a loop labelled $a,Z/AZ$ and $a,A/AA$, an arrow $q_0\to q_1$ labelled $b,A/\epsilon$, and $q_1$ (double circle) with loops $b,A/\epsilon$ and $\epsilon,Z/\epsilon$. Label = input, pop / push; $Z=Z_0$, $A$ marks an a.

State	Input, top	Move
$q_0$	$a,Z$ / $a,A$	stay, push $A$
$q_0$	$b,A$	go to $q_1$, pop
$q_1$	$b,A$	stay, pop
$q_1$	$\epsilon,Z$	pop $Z$, stack empty, accept

Transitions (empty stack, $Z=Z_0$, $\epsilon$ = empty; all checked by simulation).

a^n b^n (n>=1): d(q0,a,Z)=(q0,AZ) d(q0,a,A)=(q0,AA)
  d(q0,b,A)=(q1,e) d(q1,b,A)=(q1,e) d(q1,e,Z)=(q1,e)
(ab)^n (n>=1): d(q0,a,Z)=(q1,AZ) d(q1,b,A)=(q2,e)
  d(q2,a,Z)=(q1,AZ) d(q2,e,Z)=(q2,e)
a^n b^3n: as a^n b^n but a pushes AAA; each b pops one A
a^2n b^n: push A per a; d(q0,b,A)=(q1,e) d(q1,e,A)=(q2,e)
  d(q2,b,A)=(q1,e) d(q2,e,Z)=(q2,e)   (each b pops two A)
a^n b^m a^n: d(q0,a,Z)=(q0,AZ) d(q0,a,A)=(q0,AA)
  d(q0,b,A)=(q1,A) d(q1,b,A)=(q1,A) d(q1,a,A)=(q2,e)
  d(q2,a,A)=(q2,e) d(q2,e,Z)=(q2,e)
ww^R: d(q0,x,Y)=(q0,xY) for x in {a,b}, Y in {a,b,Z}
  d(q0,e,Y)=(q1,Y) (guess middle) d(q1,x,x)=(q1,e) d(q1,e,Z)=(q1,e)

Trace of $abba$ for $ww^R$: $(q_0,abba,Z)\vdash(q_0,bba,aZ)\vdash(q_0,ba,baZ)\vdash(q_1,ba,baZ)\vdash(q_1,a,aZ)\vdash(q_1,\epsilon,Z)\vdash(q_1,\epsilon,\epsilon)$, accepted.

For $w\in(a,b)^2$ (May 2023) the same PDA works; add a counter state if only $|w|=2$ is wanted. For $(ab)^n$ the start state $q_0$ is kept separate so that $\epsilon$ is not accepted.

Answer frame. For a design question open with the 7-tuple and the acceptance mode; state the push/pop strategy in one line; draw the diagram; list $\delta$; trace one short string as IDs; close with "hence $L=N(M)$". For PDA versus FA give the table. For "What is PDA?" give the tuple, ID and the $\vdash$ relation.

Pitfall: Making $\epsilon$ accepted in $(ab)^n$, $n\ge1$, by letting the start state pop $Z_0$; likewise forgetting the $\epsilon,Z_0$ pop that empties the stack.

Asked: [14 marks] (Nov 2019) Design a PDA that accepts $L=\{a^nb^ma^n: m,n>0\}$ Asked: [14 marks] (Nov 2023) Construct the PDA by empty stack: (i) $\{(ab)^n\mid n\ge1\}$, (ii) $\{ww^R\mid w\in(a+b)^*\}$, (iii) $\{a^{2n}b^n\mid n\ge1\}$ Asked: [14 marks] (May 2023) Design a PDA: (i) $a^nb^{3n}, n\ge1$; (ii) $ww^R, w\in(a,b)^2$ Asked: [7 marks] (Dec 2020) State the difference between PDA and FA. Asked: [7 marks] (Jun 2020) What is PDA? Explain instantaneous description of PDA. Asked: [7 marks] (Dec 2025) Design a PDA for $L=\{a^nb^n\mid n\ge1\}$. Asked: [7 marks] (Jun 2025) Construct a PDA for $L=\{ww^R\mid w\in(a+b)\}$ Asked: [6 marks] (Dec 2024) Construct the PDA accepting $\{(ab)^n: n\ge1\}$ by empty stack.

Deterministic and non-deterministic PDA

Definition. A PDA is deterministic (DPDA) if every configuration has at most one move: $|\delta(q,a,X)|+|\delta(q,\epsilon,X)|\le1$; a non-deterministic PDA (NPDA) may have several choices, and accepts if any one sequence of choices accepts.

Key points.

A DPDA never has two moves on the same state, input and stack top, and never lets an $\epsilon$-move compete with an input move.
An NPDA can guess, for example the middle of a palindrome, and it accepts if at least one guess leads to acceptance.
Unlike finite automata, NPDA is strictly more powerful than DPDA, so they are not equivalent.
DPDAs accept the deterministic CFLs (DCFL) such as $a^nb^n$ and $a^mb^nc^n$; NPDAs accept all CFLs.
$\{ww^R\}$ is a CFL but not a DCFL, because a DPDA cannot know where the middle is.
DPDA acceptance by final state is stronger than by empty stack; for an NPDA both are equal.

Basis	DPDA	NPDA
Moves per configuration	At most one	Several
Power	DCFL only	All CFL
Example	$a^nb^n$	$ww^R$
Parsing	Easy, linear time	Needs backtracking
Complement	DCFL closed	CFL not closed

Diagram. DPDA for $a^mb^nc^n$ (final-state acceptance, $F=\{q_0,q_3\}$): $q_0$ loops on $a,Z/Z$ (a's ignored) and goes to $q_1$ on $b,Z/BZ$; $q_1$ loops on $b,B/BB$ and goes to $q_2$ on $c,B/\epsilon$; $q_2$ loops on $c,B/\epsilon$ and goes to $q_3$ on $\epsilon,Z/Z$.

NPDA for $0^{n+1}1^{2n}$ (printed "$n\ge m$"; $m$ is undefined, so take $m=0$). The first 0 pushes nothing and each later 0 pushes two symbols:

d(q0,0,Z)=(q1,Z)  d(q1,0,Z)=(q1,AAZ)  d(q1,0,A)=(q1,AAA)
d(q1,1,A)=(q2,e)  d(q2,1,A)=(q2,e)  d(q2,e,Z)=(q2,e)  d(q1,e,Z)=(q1,e) for n=0

Check: $0011$ pushes $AA$, two 1s pop them, then $Z$ is popped.

DPDA for $a^mb^nc^n$: $\delta(q_0,a,Z)=(q_0,Z)$, $\delta(q_0,b,Z)=(q_1,BZ)$, $\delta(q_1,b,B)=(q_1,BB)$, $\delta(q_1,c,B)=(q_2,\epsilon)$, $\delta(q_2,c,B)=(q_2,\epsilon)$, $\delta(q_2,\epsilon,Z)=(q_3,Z)$.

Answer frame. Open with the two definitions; give the table; example: $a^nb^n$ (DPDA) and $ww^R$ (NPDA with the $\epsilon$ guess); close "NPDA is strictly more powerful, DPDA $\subsetneq$ NPDA". For "equivalent or not?" state not equivalent in the first line and prove by $ww^R$. For design questions draw the diagram and list $\delta$.

Asked: [7 marks] (May 2023, Dec 2024, Dec 2025) Explain DPDA and NPDA with a suitable example. Explain pushdown automata and deterministic and non-deterministic PDAs. Asked: [7 marks] (Nov 2022) Construct an NPDA for $L=\{0^{n+1}1^{2n}\mid n\ge m\}$ over $\{0,1\}$. Asked: [7 marks] (Nov 2022) Give a DPDA that accepts $\{a^mb^nc^n\mid m,n\ge0\}$. Asked: [7 marks] (Dec 2024) Are NPDA and DPDA equivalent or not? Illustrate with an example.

Conversion of PDA into CFG and vice versa

Definition. A language is context free if and only if some PDA accepts it, so every CFG can be converted to an NPDA and every PDA to a CFG.

CFG to PDA (steps).

Step 1: Take one state q; stack alphabet = variables and terminals; Z0 at the bottom.
Step 2: Push the start symbol: d(q,e,Z)=(q,SZ).
Step 3: For each production A -> alpha add d(q,e,A)=(q,alpha).
Step 4: For each terminal a add d(q,a,a)=(q,e).
Step 5: Accept by empty stack: d(q,e,Z)=(q,e).

Example ($S\to aBB\mid cDD,\ B\to cD\mid aS,\ D\to dD\mid d$). Productions give $\delta(q,\epsilon,S)=\{(q,aBB),(q,cDD)\}$, $\delta(q,\epsilon,B)=\{(q,cD),(q,aS)\}$, $\delta(q,\epsilon,D)=\{(q,dD),(q,d)\}$, plus $\delta(q,t,t)=(q,\epsilon)$ for $t=a,c,d$. Input $acdcd$ (leftmost $S\Rightarrow aBB\Rightarrow acDB\Rightarrow acdB\Rightarrow acdcD\Rightarrow acdcd$): the stack goes $S\to aBB\to BB$ (match a) $\to cDB\to DB$ (match c) $\to dB\to B\to cD\to D\to d\to\epsilon$; accepted. The second grammar ($S\to aABB\mid aAA,\ A\to aBB\mid a,\ B\to bBB\mid A$) uses the same recipe; $aaa$ is accepted by $S\Rightarrow aAA\Rightarrow aaA\Rightarrow aaa$.

PDA to CFG (steps, empty-stack PDA).

Step 1: Variables are triples [p,X,q]: from state p, popping X, the PDA ends in q.
Step 2: Start rules: S -> [q0,Z0,p] for every state p.
Step 3: If d(p,a,X) has (r,e): add [p,X,r] -> a.
Step 4: If d(p,a,X) has (r,Y1...Yk): add [p,X,s_k] -> a[r,Y1,s1][s1,Y2,s2]...[s_(k-1),Yk,s_k] for all s1..sk.
Step 5: Delete useless variables and productions.

Correctness idea: $[p,X,q]\Rightarrow^* w$ exactly when the PDA can go from $p$ to $q$ reading $w$ and removing $X$ from the stack.

Example (PDA of $a^nb^n$ above). $S\to[q_0,Z,q_1]\to a[q_0,A,q_1][q_1,Z,q_1]$, $[q_0,A,q_1]\to a[q_0,A,q_1][q_1,A,q_1]\mid b$, $[q_1,A,q_1]\to b$, $[q_1,Z,q_1]\to\epsilon$. Rename to $S\to aQ,\ Q\to aQR\mid b,\ R\to b$; then $S\Rightarrow aQ\Rightarrow aaQR\Rightarrow aabR\Rightarrow aabb$.

Diagram. The CFG-to-NPDA machine is one circle $q$ with two kinds of loop: $\epsilon,A/\alpha$ (expand a variable) and $a,a/\epsilon$ (match a terminal against the input).

Answer frame. For PDA to CFG open with "PDA and CFG are equivalent", state the triple, give the four rule types (start, pop, push, state change), close with the correctness idea. For a NPDA diagram (Nov 2022) write each arrow as (state, input, pop) to (state, push), apply Step 4 to each, then drop useless triples. For CFG to NPDA give the five steps and trace one string.

Pitfall: Pushing the right side reversed. The leftmost symbol of $\alpha$ must end on top of the stack.

Asked: [7 marks] (Nov 2022, Nov 2023) Give an NPDA that simulates the grammar $S\to aBB\mid cDD,\ B\to cD\mid aS,\ D\to dD\mid d$. Also: for $S\to aABB/aAA,\ A\to aBB/a,\ B\to bBB/A$ construct the PDA. Asked: [7 marks] (Nov 2022) Construct the corresponding CFG for the following NPDA. Asked: [7 marks] (Jun 2025) Describe the conversion from PDA to CFG using the standard algorithm.

CFG equivalent to PDA

Definition. The class of languages accepted by PDAs equals the class of context free languages.

Given a CFG, the single-state NPDA that expands variables and matches terminals accepts the same language, so CFL $\subseteq$ PDA languages.
Given a PDA, the triple grammar $[p,X,q]$ generates the same language, so PDA languages $\subseteq$ CFL.
The equivalence holds for NPDAs only, since DPDAs give the smaller class DCFL.
Final-state and empty-stack acceptance are interconvertible.

Petrinet model

Definition. A Petri net is a bipartite directed graph of places and transitions, with tokens in places, used to model concurrent and distributed systems.

Formally it is $(P,T,F,M_0)$: places $P$, transitions $T$, arcs $F\subseteq(P\times T)\cup(T\times P)$ and initial marking $M_0$.
A transition is enabled when every input place holds a token.
Firing removes one token from each input place and adds one to each output place.
It models parallelism, synchronisation and resource sharing, which a PDA cannot express.

Last-minute revision

PDA = $(Q,\Sigma,\Gamma,\delta,q_0,Z_0,F)$; $\delta$ gives finite subsets of $Q\times\Gamma^*$.
ID = $(q,w,\gamma)$; $\vdash$ is one move; $\vdash^*$ is zero or more.
Push on the first block, pop on the second; the last $\epsilon,Z_0$ move empties the stack.
$a^nb^{3n}$: push three symbols per a; $a^{2n}b^n$: pop two per b.
$ww^R$ needs an $\epsilon$ guess of the middle, so it is an NPDA and not a DPDA.
DPDA $\subsetneq$ NPDA; NPDA = CFL, DPDA = DCFL.
FA has no stack (regular); PDA has one stack (context free).
CFG to PDA: one state, expand variables, match terminals.
PDA to CFG: variables $[p,X,q]$, start $S\to[q_0,Z_0,p]$.
Petri net: places, transitions, tokens; firing moves tokens.

Memory hooks

Push-Pop-Zero: push, pop, then $Z_0$ off.
Two a's per b means pop twice; three b's per a means push three times.
A palindrome has no signposted middle, so the machine must guess it.
Triple $[p,X,q]$: "from p, remove X, land in q".
CFG to PDA: "expand on top, match on input".

Coverage checklist

example of PDA: Nov 2019 $a^nb^ma^n$, Nov 2023, May 2023, Dec 2020 PDA vs FA, Jun 2020 ID, Dec 2025, Jun 2025, Dec 2024
deterministic and non-deterministic PDA: DPDA/NPDA (May 2023, Dec 2024, Dec 2025), Nov 2022 NPDA, Nov 2022 DPDA, Dec 2024 equivalence
conversion of PDA into context free grammar and vice versa: Nov 2022 NPDA to CFG, Nov 2022 and Nov 2023 CFG to NPDA, Jun 2025
CFG equivalent to PDA: no past questions
Petrinet model: no past questions

Account

Theory of Computation (CS-501) - Unit 4 Short Notes