⭐ FULL 4 MARKS EXAMPLE — 1 (DFA)
Q. Construct a DFA for strings ending with 01 over {0,1}.
Step 1: Definition of DFA
A DFA is a 5-tuple (Q, Σ, δ, q₀, F)
Where
Q = set of states
Σ = input alphabet
Δ = transition function
Q₀ = start state
F = set of final states
Step 2: Identify conditions
String must end with 01.
So DFA must “remember” last two symbols.
Step 3: State Meaning
Q0 → No specific pattern seen yet
Q1 → last symbol was 0
Q2 → last two symbols are 01 (ACCEPT state)
Step 4: Transition Table
Current State
Input 0
Input 1
Q0
Q1
Q0
Q1
Q1
Q2
Q2
Q1
Q0
Step 5: Final DFA
Q = {q0, q1, q2}
Σ = {0, 1}
Q₀ = q0
F = {q2}
Δ = above table
Step 6: Explanation
If the machine reaches q1, it means the last input seen is 0.
If the next input is 1, we move to q2 which indicates the final string ends
with 01.
Any extra symbols after q2 will move it out of q2 unless the last two remain
01.
Thus q2 correctly represents strings ending with 01.
✔ This answer = full 4 marks.
⭐ FULL 4 MARKS EXAMPLE — 2 (NFA → DFA)
Q. Convert the following NFA to DFA.
NFA:
A ─0→ B
A ─1→ A
B ─1→ B
Final state: B
Step 1: ε-closures
(There are no ε moves, so closures are same)
Ε(A) = {A}
Ε(B) = {B}
Step 2: Create DFA States using subset construction
Start state = {A}
Possible subsets:
{A}, {B}, {A,B}, ∅
Step 3: Find transitions
For {A}:
On 0 → {B}
On 1 → {A}
For {B}:
On 0 → ∅
On 1 → {B}
For {A,B}:
On 0 → {B}
On 1 → {A,B}
Step 4: DFA Transition Table
DFA State
{A}
{B}
{A}
{B}
∅
{B}
{A,B}
{B}
{A,B}
∅
Step 5: Final DFA
Qᴰ = { {A}, {B}, {A,B}, ∅ }
Start = {A}
Final = any state containing B → {B}, {A,B}
Step 6: Explanation
In DFA, each state represents all possible NFA states reachable at a time.
Since B is final, any DFA state containing B becomes final.
3) Construct DFA — Example 2
Q. Construct a DFA for strings over {0,1} having an even number of 0’s.
Step 1: Purpose
We must accept strings in which the total count of symbol 0 is even (0,2,4,
…). 1 does not affect parity.
Step 2: State meanings
� — so far seen an even number of 0’s (start, accept)
� — so far seen an odd number of 0’s (non-accept)
Step 3: 5-tuple
� where
�, �
�, �
Step 4: Transition table
Current State
Input 0
Input 1
�
Step 5: Explanation
On reading a 0 the machine toggles between even and odd states; reading 1
leaves parity unchanged. Start state � is accepting because zero 0’s is even.
This DFA accepts exactly those strings with an even number of 0’s.
✔ Full 4 marks.
4) NFA → DFA — Example 2 (with ε-closure)
Q. Convert the NFA below into an equivalent DFA.
NFA: states �, start �, final �.
Transitions:
Step 1: ε-closures
Ε-closure(p) = {p,q}
Ε-closure(q) = {q}
Ε-closure® = {r}
Step 2: DFA start state
Start = ε-closure(p) = {p,q}
Step 3: Compute moves and closures
From {p,q}:
On 0: move({p,q},0) = move(p,0) ∪ move(q,0) = ∅ ∪ {q} = {q} → ε-
closure({q}) = {q}
On 1: move({p,q},1) = move(p,1) ∪ move(q,1) = ∅ ∪ {r} = {r} → ε-
closure({r}) = {r}
From {q}:
On 0: {q} → {q}
On 1: {r}
From {r}:
On 0: ∅
On 1: {r}
Include ∅ as dead state.
Step 4: DFA transition table
DFA State
{p,q}
{q}
{r}
{q}
{q}
{r}
{r}
{r}
∅
Step 5: Final states
Any DFA state containing NFA final state r is final → {r} and any other that
contains r (none else here).
Step 6: Explanation
Subset construction with ε-closures yields DFA states as sets of NFA states.
The DFA accepts same language as NFA because it simulates all possible NFA
computations deterministically.
✔ Full 4 marks.
5) Regular Expression → FA — Example 1
Q. Construct a finite automaton for the regular expression �.
Step 1: Understand the expression
Strings are any prefix (0 or 1 repeated), followed by 0 then 1. So machine
needs to recognize the final two-symbol pattern 01.
Step 2: Choose minimal DFA states (remember last up to 2 symbols)
�: start — no relevant suffix yet (or generic prefix)
�: last symbol seen is 0
�: last two symbols are 01 (accept)
Step 3: Transition table (same as earlier DFA for ending with 01)
State
Q0
Q1
Q0
Q1
Q1
Q2
Q2
Q1
Q0
Start �, Final �.
Step 4: Explanation
Any prefix loop returns to �. Seeing 0 moves to �; if next symbol is 1, we
reach � and accept. This DFA accepts exactly �.
✔ Full 4 marks (give 5-tuple + table + 1-line justification).
6) Regular Expression → FA — Example 2
Q. Construct an NFA for � and indicate how to convert to DFA (brief).
Step 1: Build small NFAs for 01 and 10
NFA for 01: �
NFA for 10: �
Step 2: Union and Kleene star (Thompson construction)
New start � with ε to starts of both blocks.
The two block accepts connect by ε to new accept �.
For Kleene star, add ε from � back to � and ε from � to � (to accept ε).
Step 3: NFA description (states representative)
States: S, s1, a, f1, s2, b, f2, F with ε arcs S→s1, S→s2; f1→F, f2→F; F→S; S→F.
Step 4: Convert to DFA (brief)
Apply subset construction: compute ε-closures of S and reachable sets on
inputs 0 and 1 to form DFA states. Final DFA states are those containing any
NFA accept state.
Step 5: Explanation
This NFA accepts sequences of blocks 01 or 10 repeated. Thompson’s
method gives a direct NFA; subset construction produces an equivalent DFA if
required.
✔ Full 4 marks: draw small diagram in exam + brief note on subset
conversion.
7) CFG → CNF — Example 1
Q. Convert the grammar below to Chomsky Normal Form (CNF):
�.
Step 1: Identify terminals and long productions
All productions are short but use terminals in right-hand sides where
nonterminal form required.
Step 2: Introduce terminal nonterminals
Create � and �.
Step 3: Replace terminals in productions where necessary
� (replace a by �)
� (replace b by �)
� (already a single terminal via Y)
Step 4: Final CNF productions
�, �
Step 5: Explanation
All productions are now of the form � or �, so the grammar is in CNF.
✔ Full 4 marks.
8) CFG → CNF — Example 2 (unit & ε removal sketched)
Q. Convert grammar to CNF:
(Exam requires sketching removal steps and listing final CNF – show main
steps concisely.)
Step 1: Eliminate ε-production
S is nullable. Replace occurrences of S in productions to add alternatives
where S may be empty:
� generates � after removing nullable S.
Keep � and if needed add � (if B nullable — here B not nullable so keep �
only). Also keep ε only for start if allowed; CNF allows S→ε only if S nullable
originally.
Step 2: Remove unit productions
Find unit chains: � and �. Replace � by bodies of B and S (after their
expansion) to eliminate units.
After substitution and simplification (short list of resulting alternatives),
assume we get productions without unit rules and without ε except possibly
S→ε.
Step 3: Introduce terminal nonterminals and binarize long RHS
Introduce �, �. Break long RHS into binary forms. For example, if we have
production like � convert via new nonterminals: let � then �, etc.
Step 4: Final (example) CNF form (representative after steps)
� (if S nullable)
� (after expansion)
Step 5: Explanation
The key steps: remove ε, remove unit productions, introduce terminals as
single nonterminals, and break long RHS into binary rules. The final result
(listed) conforms to CNF
9) PDA — Example 1 (accept by empty stack): �
Q. Construct a PDA that accepts � by empty stack.
Step 1: Idea
Push one stack symbol for every a read; for every b pop one symbol. Accept
when input exhausted and only bottom marker remains (or by final state
after emptying stack).
Step 2: States and stack symbol
States: � (push state), � (pop state), � (accept). Stack symbols: used
symbol �, bottom marker �.
Step 3: δ rules (informal standard notation)
� — on first a push A over bottom Z.
� — for each a push another A.
� — on first b pop and go to popping state.
� — pop one A for each b.
� — when stack back to Z and no input, go to accept.
Step 4: Explanation
Push stage reads all as and pushes A for each. On reading first b, the PDA
switches to popping stage and pops one A per b. If numbers match, stack
returns to bottom marker Z when input ends and PDA moves to accept. This
PDA accepts exactly �.
✔ Full 4 marks.
10) PDA — Example 2 (aⁿ bⁿ cᵐ)
Q. Construct a PDA for �.
Step 1: Idea
Use push/pop for matching a and b (like previous). After finishing bs,
transition to a state that ignores any number of c (does not touch stack).
Accept by final state.
Step 2: States and stack symbol
States: � (push a’s), � (pop b’s), � (read c’s / final). Stack symbol A,
bottom Z.
Step 3: δ rules
� — push for each a.
� — on first b start popping.
� — continue popping for b.
� — after popping all A’s and encountering c, move to �.
� — loop on c without stack effect (or accept by final state that loops on c).
� — allow zero c’s and accept (move to q2 directly when stack is Z).
Step 4: Explanation
A’s are pushed, b’s pop those pushes ensuring equal count. After stack is
empty, any number of c’s are accepted by moving to state � which ignores
c’s. This accepts �.
11) Turing Machine — Example 1 (even number of 1’s)
Q. Design a TM that accepts strings over {0,1} having even number of 1s.
Step 1: Idea
Scan from left to right, toggling parity state on each 1. On blank check parity
and accept/reject.
Step 2: States
�: even parity so far (start)
�: odd parity so far
�, �
Step 3: Transition function (δ lines)
� — ignore 0, move right
� — on 1 switch to odd
� — ignore 0 in odd state
� — on 1 flip back to even
On blank (⊔): � and �
Step 4: Explanation
The TM scans the tape once, toggling between � (even) and � (odd) when it
sees 1. At the end, if in even state it accepts; if in odd state it rejects. This
recognizes strings with even number of 1 s.
12) Turing Machine — Example 2 (replace every 0 by 1 and halt)
Q. Design a TM that replaces every 0 on the tape by 1, leaves 1 as is, and
halts.
Step 1: Idea
Single-pass overwrite: for each symbol, write new symbol and move right; on
blank halt.
Step 2: States
� start/processing, � accept (halt).
Step 3: Transition function (δ lines)
� — overwrite 0 by 1, move right
� — keep 1, move right
� — on blank, halt and accept
Step 4: Explanation
The TM scans right replacing each 0 encountered by 1. When it reaches the
blank symbol at the end of input, it transitions to accept and halts. The tape
then contains the same string except all 0’s have become 1’s