Skip to content
JNTUK · B.Tech study libraryFree access · No sign-up
JNTUK · R23 · CSE · Semester 3-1

Formal Languages and Automata Theory exam preparation.

Practice questions for every unit in the style of the R23 end exam, a model answer for each, and a one-page revision summary. Built on the official syllabus units.

  • Practice questions in the exam's style
  • Drafted with AI and checked by a second AI pass. Doubtful points were verified against public sources. Report a mistake
Units
5
Questions
60
2-mark
30
10-mark
30
Checked on

Exam guide

Paper pattern

Semester-end theory paper, 70 marks, from the JNTUK B.Tech R23 Regulations, end-examination pattern for theory subjects.

  1. Question 1 · 20 marksTen compulsory short-answer questions of 2 marks each (two from every unit).
  2. Questions 2 to 6 · 50 marksFive either/or questions of 10 marks each, one per unit. You answer one of the two in each.
  • The semester-end examination carries 70 marks; internal assessment carries 30.
  • Mid-semester examinations are separate: a 20-minute objective paper (10 marks) and a 90-minute subjective paper with three either/or questions of 10 marks (condensed to 15 marks).
  • The regulations text does not state the length of the end examination. Use the duration printed on your hall ticket or question paper.

Read the R23 regulations (PDF) ↗

How to split your time

This plan assumes a 3-hour paper. If yours is different, keep the same proportions. Marks per minute stay roughly even across Question 1 and the 10-mark answers.

  1. 10 minRead the paper and choose one option in each either/or question
  2. 30 minQuestion 1: ten short answers (about 3 minutes each)
  3. 130 minQuestions 2 to 6: one 10-mark answer per unit (about 26 minutes each)
  4. 10 minFinal check of numbering, calculations and diagrams

Study tips for Formal Languages and Automata Theory

  • Practise drawing DFA, NFA and PDA transition diagrams neatly with a clearly marked start state, double-circled final states and labelled arrows, then trace three or four sample strings through each machine to confirm it accepts and rejects exactly what the language requires.
  • Work through NFA-to-DFA subset construction and DFA minimization step by step on paper, writing the full transition table at every stage so you can catch missing or unreachable states before drawing the final diagram.
  • For context-free grammars, practise writing leftmost and rightmost derivations alongside the matching parse tree, and rehearse simplification and conversion to Chomsky and Greibach normal forms in a fixed order: remove null productions, then unit productions, then useless symbols.
  • Pumping lemma template: assume the language is regular (or context-free) with pumping length p, choose a string w in L with |w| ≥ p, written in terms of p, then prove that every allowed split fails: each xyz with |xy| ≤ p, |y| ≥ 1, or each uvwxy with |vwx| ≤ p, |vx| ≥ 1, leaves the language when pumped for some i ≥ 0.
  • Design Turing machines as a short transition table plus a one-line description of what each state does, then trace one accepted and one rejected input to check the machine.
Unit 1

Finite Automata

Syllabus: Need for automata theory and its central concepts; Finite automata and transition systems; Acceptance of a string; DFA and design of DFAs; NFA and design of NFAs; Equivalence of DFA and NFA; Conversion of NFA into DFA; Finite automata with epsilon-transitions; Minimisation of finite automata; Finite automata with output: Mealy and Moore machines; Applications and limitations of finite automata

One-page revision summary

  • Automata theory gives a mathematical model of computation and underlies compilers, digital circuit design and computability theory.
  • An alphabet is a finite non-empty set of symbols; Σ* is the set of all strings over Σ including ε, and a language is any subset of Σ*.
  • A transition system is a labelled directed graph with initial and final states; it accepts a string if some path from an initial state to a final state spells that string.
  • A string w is accepted by a DFA when δ^(q0, w) ∈ F, where δ^ extends δ to strings one symbol at a time.
  • An NFA accepts w when at least one computation path ends in a final state, that is, when δ^(q0, w) ∩ F ≠ ∅.
  • A DFA is designed by deciding what finite information about the input must be remembered and giving one state to each possibility.
  • NFAs are designed by guessing, for example looping on the start state and then matching a required suffix.
  • DFA, NFA and ε-NFA all accept exactly the same class of languages, the regular languages.
  • The subset construction turns an n-state NFA into a DFA whose states are subsets of the NFA states, with at most 2^n states.
  • An ε-NFA is converted by starting from ECLOSE(q0) and taking the ε-closure after every move on an input symbol.
  • Minimisation removes unreachable states and then merges equivalent states by repeatedly refining the partition {F, Q−F}.
  • The minimal DFA of a regular language is unique apart from the names of its states.
  • Mealy machines attach outputs to transitions and Moore machines attach outputs to states; each can be converted into the other.
  • Applications of finite automata include lexical analysis, pattern search, protocol checking, vending machines and sequential circuits.
  • Finite automata have only finite memory, so they cannot recognise languages such as {a^n b^n}, balanced parentheses or palindromes.

Learn these by heart

  • DFA M = (Q, Σ, δ, q0, F) with δ: Q × Σ → Q; NFA δ: Q × Σ → 2^Q; ε-NFA δ: Q × (Σ ∪ {ε}) → 2^Q.
  • Extended transition function: δ^(q, ε) = q and δ^(q, wa) = δ(δ^(q, w), a); L(M) = {w | δ^(q0, w) ∈ F}.
  • |Σ^k| = |Σ|^k, Σ* = Σ^0 ∪ Σ^1 ∪ Σ^2 ∪ ..., and Σ+ = Σ* − {ε}.
  • Subset construction: δD(S, a) = union of δN(s, a) over s ∈ S; a subset is final if it contains an NFA final state; the DFA has at most 2^n states.
  • ε-NFA to DFA: the start state is ECLOSE(q0), and δD(S, a) = ECLOSE(union of δ(s, a) over s ∈ S).
  • Minimisation: start with {F, Q−F} and split a group when its states move to different groups on some symbol; stop when no group changes.
  • Mealy: λ: Q × Σ → Δ, giving n outputs; Moore: λ: Q → Δ, giving n+1 outputs; Mealy to Moore needs at most |Q| × |Δ| states.

2-mark questions

1 Define alphabet, string and language with one example each. 2 marks
Model answer

An alphabet Σ is a finite, non-empty set of symbols, for example Σ = {0,1}. A string is a finite sequence of symbols from Σ, such as 0110; the empty string ε has length 0. A language is any subset of Σ*, for example L = {w | w ends with 1}.

2 Give the formal definition of a deterministic finite automaton (DFA). 2 marks
Model answer

A DFA is a 5-tuple M = (Q, Σ, δ, q0, F). Q is a finite set of states and Σ is the input alphabet. δ: Q × Σ → Q is the transition function, which gives exactly one next state for each pair. q0 ∈ Q is the start state and F ⊆ Q is the set of final states.

3 How does an NFA differ from a DFA, and when does an NFA accept a string? 2 marks
Model answer

In an NFA, δ: Q × Σ → 2^Q, so a state may have zero, one or many moves on a symbol. A DFA always has exactly one move. An NFA accepts w if at least one possible path for w ends in a final state, that is, δ^(q0, w) ∩ F ≠ ∅.

4 An ε-NFA has the moves q0 -ε→ q1, q1 -ε→ q2 and q2 -a→ q0. Find ECLOSE(q0) and ECLOSE(q2). 2 marks
Model answer

ECLOSE(q) is the set of states reachable from q using only ε-moves, including q itself. From q0 we reach q1 by ε, and from q1 we reach q2 by ε. So ECLOSE(q0) = {q0, q1, q2}. The move q2 -a→ q0 is not an ε-move, so ECLOSE(q2) = {q2}.

5 Define a Moore machine and state how its output length differs from that of a Mealy machine. 2 marks
Model answer

A Moore machine is a 6-tuple (Q, Σ, Δ, δ, λ, q0) in which the output function λ: Q → Δ depends only on the current state. It emits one output in the start state and one after every input, so an input of length n gives n+1 outputs. A Mealy machine gives exactly n outputs.

6 State two applications and two limitations of finite automata. 2 marks
Model answer

Applications:

  • lexical analysers in compilers
  • text and pattern search, as in editors and grep

Limitations:

  • A finite automaton has only finite memory, so it cannot count without bound. For example, it cannot recognise {a^n b^n | n ≥ 0}.
  • It cannot check balanced parentheses or recognise palindromes.

10-mark questions

1 Explain the need for automata theory and its central concepts (alphabet, strings, powers of an alphabet, Kleene closure, language). Also explain a transition system with a suitable example. 10 marks
Model answer

Automata theory studies abstract computing machines and the problems they can solve. It gives a precise mathematical model of computation. This model is used to design software and hardware and to decide what computers can and cannot do.

Need for automata theory:

  • It models systems that move among a finite number of states, such as digital circuits, vending machines and communication protocols.
  • It is the basis of lexical analysis, pattern matching and parsing in compilers.
  • It helps classify problems as decidable or undecidable, and as tractable or intractable.

Central concepts:

1. Alphabet: a finite, non-empty set of symbols, written Σ. Example: Σ = {0,1}.

2. String: a finite sequence of symbols from Σ. The empty string ε has length 0, and |w| is the length of w. For example, |0110| = 4.

3. Powers of an alphabet: Σ^k is the set of all strings of length k. For Σ = {a,b}, Σ^2 = {aa, ab, ba, bb}. In general |Σ^k| = |Σ|^k, so here |Σ^2| = 2^2 = 4.

4. Kleene closure: Σ* = Σ^0 ∪ Σ^1 ∪ Σ^2 ∪ ... is the set of all strings over Σ, including ε. The positive closure is Σ+ = Σ* − {ε}.

5. Language: any subset L of Σ*. Example: L = {w ∈ {0,1}* | w ends with 1}.

6. Problem: deciding whether a given string w belongs to a language L. This is called the membership question.

Transition system:

A transition system is a finite directed graph. Its vertices are states and its edges are labelled with input symbols (in the general definition, with strings). One or more states are marked initial and one or more are marked final. A string is accepted if some path from an initial state to a final state spells the string when its edge labels are read in order. A finite automaton M = (Q, Σ, δ, q0, F) is a transition system whose edges are given by the transition function δ.

Example: a transition system over {0,1} that accepts the strings ending in 1.

Transition system over {0,1} accepting strings ending in 1Diagram in words: Two circles labelled q0 and q1. An arrow with no source points into q0, marking it as the initial state. q1 is drawn as a double circle, marking it as final. q0 has a self-loop labelled 0. An arrow labelled 1 goes from q0 to q1. q1 has a self-loop labelled 1. An arrow labelled 0 goes from q1 back to q0.q0 (initial)q1 (final)0110
Transition system over {0,1} accepting strings ending in 1

Transition table:

  • q0: on 0 → q0, on 1 → q1
  • q1: on 0 → q0, on 1 → q1

For input 101 the path is q0 -1→ q1 -0→ q0 -1→ q1. It ends in the final state q1, so 101 is accepted.

Conclusion: alphabets, strings and languages are the vocabulary of the subject. Transition systems give a graphical model of machines that read strings and decide membership in a language.

2 Design a DFA over Σ = {0,1} that accepts all strings containing an even number of 0s and an even number of 1s. Give its transition table and diagram, and check the acceptance of the strings 110101 and 1011. 10 marks
Model answer

The automaton only needs to remember two things: whether the number of 0s read so far is even or odd, and whether the number of 1s is even or odd. These give 2 × 2 = 4 combinations, so the DFA needs four states.

Step 1: Define the states.

  • q0: even 0s, even 1s. This is the start state and the only final state.
  • q1: even 0s, odd 1s.
  • q2: odd 0s, even 1s.
  • q3: odd 0s, odd 1s.

Step 2: Decide the moves. Reading 0 flips the parity of the 0s. Reading 1 flips the parity of the 1s.

Step 3: Transition table.

  • q0 (start, final): on 0 → q2, on 1 → q1
  • q1: on 0 → q3, on 1 → q0
  • q2: on 0 → q0, on 1 → q3
  • q3: on 0 → q1, on 1 → q2

So M = ({q0,q1,q2,q3}, {0,1}, δ, q0, {q0}).

DFA for strings with an even number of 0s and an even number of 1sDiagram in words: Four circles placed at the corners of a square. q0 is at the top-left, q1 at the top-right, q2 at the bottom-left and q3 at the bottom-right. q0 is a double circle and has an incoming start arrow. Along the top side, arrows labelled 1 go from q0 to q1 and from q1 to q0. Along the bottom side, arrows labelled 1 go from q2 to q3 and from q3 to q2. Along the left side, arrows labelled 0 go from q0 to q2 and from q2 to q0. Along the right side, arrows labelled 0 go from q1 to q3 and from q3 to q1.startq0 (start,final)q1q2q311110000
DFA for strings with an even number of 0s and an even number of 1s

Step 4: Check acceptance using the extended transition function δ^.

For w = 110101:

  • δ(q0,1) = q1
  • δ(q1,1) = q0
  • δ(q0,0) = q2
  • δ(q2,1) = q3
  • δ(q3,0) = q1
  • δ(q1,1) = q0

So δ^(q0, 110101) = q0 ∈ F, and the string is accepted. As a check, 110101 has two 0s and four 1s, and both counts are even.

For w = 1011:

  • δ(q0,1) = q1
  • δ(q1,0) = q3
  • δ(q3,1) = q2
  • δ(q2,1) = q3

So δ^(q0, 1011) = q3 ∉ F, and the string is rejected. As a check, 1011 has one 0 and three 1s, and both counts are odd.

Conclusion: a DFA is designed by deciding what finite information about the input must be remembered and giving one state to each possibility. A string is accepted exactly when δ^(q0, w) is a final state.

3 Define an NFA. State and justify the equivalence of NFA and DFA. Using the subset construction, convert the NFA below into an equivalent DFA. NFA N = ({p,q,r}, {0,1}, δ, p, {r}) with δ(p,0) = {p,q}, δ(p,1) = {p}, δ(q,0) = ∅, δ(q,1) = {r}, δ(r,0) = δ(r,1) = ∅. 10 marks
Model answer

An NFA is a 5-tuple N = (Q, Σ, δ, q0, F) with δ: Q × Σ → 2^Q. A state may therefore have several moves, or none, on the same symbol. N accepts w if δ^(q0, w) ∩ F ≠ ∅.

Equivalence theorem: for every NFA N there is a DFA D with L(D) = L(N). Every DFA is already an NFA whose move sets are singletons, so the two models recognise the same class of languages.

Justification by subset construction:

  • The states of D are subsets of Q. The start state of D is {q0}.
  • For a subset S and symbol a, δD(S, a) is the union of δN(s, a) over all s in S.
  • A subset is final in D if it contains at least one state of F.
  • By induction on |w|, δD^({q0}, w) = δN^(q0, w). The base case w = ε holds trivially. In the inductive step, both sides take the union of the moves on the last symbol.
  • Hence D accepts w exactly when N does. D has at most 2^n states.

Conversion of the given NFA:

1. Start state A = {p}.

2. From A = {p}: on 0, δ(p,0) = {p,q}, a new state B. On 1, δ(p,1) = {p} = A.

3. From B = {p,q}: on 0, δ(p,0) ∪ δ(q,0) = {p,q} ∪ ∅ = {p,q} = B. On 1, δ(p,1) ∪ δ(q,1) = {p} ∪ {r} = {p,r}, a new state C.

4. From C = {p,r}: on 0, {p,q} ∪ ∅ = B. On 1, {p} ∪ ∅ = A.

5. No new subsets appear, so the construction stops. Only C contains r, so C is the only final state.

DFA transition table:

  • A = {p} (start): on 0 → B, on 1 → A
  • B = {p,q}: on 0 → B, on 1 → C
  • C = {p,r} (final): on 0 → B, on 1 → A
DFA from subset construction on NFA NDiagram in words: Three circles labelled A, B and C. A has a start arrow, and C is a double circle. A has a self-loop labelled 1, and an arrow labelled 0 goes from A to B. B has a self-loop labelled 0, and an arrow labelled 1 goes from B to C. An arrow labelled 0 goes from C to B, and an arrow labelled 1 goes from C to A.A = {p} (start)B = {p,q}C = {p,r}(final)100101
DFA from subset construction on NFA N

Check with w = 1101: A -1→ A -1→ A -0→ B -1→ C. C is final, so 1101 is accepted. It does end in 01.

Conclusion: the resulting DFA has only 3 of the possible 2^3 = 8 subset states. It accepts exactly the strings over {0,1} that end in 01, which is the same language as the NFA.

4 Explain finite automata with ε-transitions and the ε-closure. Convert the ε-NFA below into an equivalent DFA. States q0, q1, q2; start q0; final q2; moves: q0 -a→ q0, q0 -ε→ q1, q1 -b→ q1, q1 -ε→ q2, q2 -c→ q2. 10 marks
Model answer

An ε-NFA is a 5-tuple (Q, Σ, δ, q0, F) with δ: Q × (Σ ∪ {ε}) → 2^Q. An ε-move lets the machine change state without reading any input. The ε-closure ECLOSE(q) is the set of all states reachable from q using ε-moves only, including q itself.

To convert to a DFA we use the subset construction with closures:

  • The start state of the DFA is ECLOSE(q0).
  • δD(S, a) = ECLOSE of the union of δ(s, a) over all s in S.
  • A subset is final if it contains a final state.

Step 1: ε-closures.

  • ECLOSE(q0) = {q0, q1, q2}
  • ECLOSE(q1) = {q1, q2}
  • ECLOSE(q2) = {q2}

Step 2: Start state A = {q0, q1, q2}.

Step 3: Moves from A.

  • On a: δ(q0,a) = {q0}, and q1, q2 have no a-moves. ECLOSE({q0}) = {q0,q1,q2} = A.
  • On b: δ(q1,b) = {q1}. ECLOSE({q1}) = {q1,q2} = B.
  • On c: δ(q2,c) = {q2}. ECLOSE({q2}) = {q2} = C.

Step 4: Moves from B = {q1,q2}.

  • On a: ∅. This is a dead state, called D.
  • On b: ECLOSE({q1}) = B.
  • On c: ECLOSE({q2}) = C.

Step 5: Moves from C = {q2}.

  • On a: ∅ = D.
  • On b: ∅ = D.
  • On c: C.

Step 6: The dead state D = ∅ goes to D on a, b and c.

Step 7: Final states. A, B and C all contain q2, so they are final. D is non-final.

DFA transition table:

  • A (start, final): a → A, b → B, c → C
  • B (final): a → D, b → B, c → C
  • C (final): a → D, b → D, c → C
  • D: a → D, b → D, c → D
DFA obtained from the ε-NFA by subset constructionDiagram in words: Four circles A, B, C and D. A has a start arrow, and A, B and C are double circles. A has a self-loop labelled a, an arrow labelled b to B, and an arrow labelled c to C. B has a self-loop labelled b, an arrow labelled c to C, and an arrow labelled a to D. C has a self-loop labelled c and an arrow labelled a,b to D. D has a self-loop labelled a,b,c.startA (start,final)B (final)C (final)Dabcbcaca,ba,b,c
DFA obtained from the ε-NFA by subset construction

Check with two strings:

  • aabc: A -a→ A -a→ A -b→ B -c→ C. C is final, so the string is accepted.
  • ba: A -b→ B -a→ D. D is not final, so the string is rejected.

Conclusion: the ε-NFA and the DFA both accept a*b*c*. This shows that ε-moves add convenience in design but no extra power.

5 Explain the procedure for minimising a DFA. Minimise the DFA below over {0,1} with start state A and final state E: A: 0→B, 1→C; B: 0→B, 1→D; C: 0→B, 1→C; D: 0→B, 1→E; E: 0→B, 1→C; F: 0→D, 1→E. 10 marks
Model answer

Minimisation produces a DFA with the fewest states that accepts the same language. Two states p and q are equivalent if, for every string w, δ^(p,w) and δ^(q,w) are either both final or both non-final. Equivalent states can be merged.

Procedure (partition refinement):

1. Remove the states that cannot be reached from the start state.

2. Form the first partition P0 with two groups: final states and non-final states.

3. Split a group whenever two of its states move, on some input symbol, into different groups.

4. Repeat until no group splits. Each final group becomes one state of the minimal DFA.

Step 1: Reachability.

From A we reach B and C. From B we reach D, and from D we reach E. No transition enters F, so F is unreachable and is removed. The states left are A, B, C, D and E.

Step 2: P0 = {A, B, C, D}, {E}.

Step 3: Refine {A,B,C,D}.

  • On 0, every state goes to B, which is in the same group.
  • On 1: A → C, B → D and C → C stay in the group, but D → E leaves it.

So D splits off. P1 = {A, B, C}, {D}, {E}.

Step 4: Refine {A,B,C}.

  • On 0, all go to B.
  • On 1: A → C and C → C stay in the group, but B → D goes to {D}.

So B splits off. P2 = {A, C}, {B}, {D}, {E}.

Step 5: Refine {A,C}.

  • On 0, both go to B.
  • On 1, both go to C, which lies in {A,C}.

No split occurs, so P3 = P2 and the partition is stable. A and C are equivalent.

Step 6: Build the minimal DFA. Let X = [A,C].

  • X (start): 0 → B, 1 → X
  • B: 0 → B, 1 → D
  • D: 0 → B, 1 → E
  • E (final): 0 → B, 1 → X
Minimal DFA for strings over {0,1} ending in 011Diagram in words: Four circles X, B, D and E. X has a start arrow, and E is a double circle. X has a self-loop labelled 1 and an arrow labelled 0 to B. B has a self-loop labelled 0 and an arrow labelled 1 to D. D has an arrow labelled 0 back to B and an arrow labelled 1 to E. E has an arrow labelled 0 to B and an arrow labelled 1 to X.X (start)BDE (final)10010101
Minimal DFA for strings over {0,1} ending in 011

Check with w = 1011: X -1→ X -0→ B -1→ D -1→ E. E is final, so the string is accepted.

Conclusion: the original 6-state DFA reduces to 4 states. The minimal DFA accepts all strings over {0,1} that end in 011. The minimal DFA of a regular language is unique apart from the names of its states.

6 Define Mealy and Moore machines and compare them. Convert the Mealy machine below into an equivalent Moore machine and verify it with the input 0101. Mealy machine over input {0,1}, output {0,1}, start state A: A: 0→B/0, 1→A/0; B: 0→B/0, 1→A/1. 10 marks
Model answer

Finite automata with output do not accept or reject strings. Instead, they produce an output string for each input string. There are two models.

Mealy machine: a 6-tuple (Q, Σ, Δ, δ, λ, q0) with output function λ: Q × Σ → Δ. The output is attached to transitions, and an input of length n gives n outputs.

Moore machine: a 6-tuple (Q, Σ, Δ, δ, λ, q0) with λ: Q → Δ. The output is attached to states, and an input of length n gives n+1 outputs, because the start state also emits one.

Comparison:

  • A Mealy machine usually needs fewer states.
  • A Moore machine's output is steadier, because it changes only with the state.
  • The two models are equivalent, apart from the extra first output of a Moore machine.

The given Mealy machine outputs 1 exactly when the substring 01 has just been read.

Conversion procedure:

1. For every state, collect the outputs on its incoming transitions. 2. If a state receives different outputs, split it into one copy per output. 3. Give each copy its output and copy the outgoing transitions.

Step 1: Incoming outputs.

  • Into A: A -1/0→ A and B -1/1→ A. A receives the outputs 0 and 1, so it splits into A0 (output 0) and A1 (output 1).
  • Into B: A -0/0→ B and B -0/0→ B. B receives only output 0, so it stays a single state B with output 0.

Step 2: Moore transitions. A copy of a state has the same next states as the original. A target is chosen by the output of the original Mealy transition.

  • A0, output 0 (start): 0 → B, 1 → A0
  • A1, output 1: 0 → B, 1 → A0
  • B, output 0: 0 → B, 1 → A1

The start state is A0, because the original start state A also receives output 0.

Moore machine equivalent to the given Mealy machineDiagram in words: Three circles labelled A0/0, A1/1 and B/0. A0 has a start arrow and a self-loop labelled 1. An arrow labelled 0 goes from A0 to B. B has a self-loop labelled 0, and an arrow labelled 1 goes from B to A1. From A1, an arrow labelled 0 goes to B and an arrow labelled 1 goes to A0.startA0/0B/0A1/1100101
Moore machine equivalent to the given Mealy machine

Step 3: Verify with 0101.

  • Mealy: A -0/0→ B -1/1→ A -0/0→ B -1/1→ A. The output is 0101.
  • Moore: A0 emits 0. Then A0 -0→ B emits 0, B -1→ A1 emits 1, A1 -0→ B emits 0, and B -1→ A1 emits 1. The output is 00101.

Dropping the initial 0 from the Moore output leaves 0101, which matches the Mealy output.

Conclusion: the Moore machine needs one extra state because A had to be split, but it produces the same response as the Mealy machine. When converting a Mealy machine with n states and m output symbols, at most n × m Moore states are needed.

Unit 2

Regular Expressions and Regular Grammars

Syllabus: Regular expressions and regular sets; Identity rules; Equivalence of two regular expressions; Manipulation of regular expressions; Conversion between finite automata and regular expressions; Pumping lemma for regular sets; Closure properties of regular sets; Grammars and classification of grammars; Chomsky hierarchy; Right-linear and left-linear regular grammars; Equivalence and conversion between regular grammars and finite automata

One-page revision summary

  • A regular expression uses ∅, ε, symbols, union (+), concatenation and star (*), with precedence star > concatenation > union, and the set it denotes is a regular set.
  • Kleene's theorem: a language is denoted by a regular expression if and only if it is accepted by a finite automaton.
  • Identities such as ε + RR* = R*, (R*)* = R*, (P+Q)* = (P*Q*)* and P(QP)* = (PQ)*P, together with the distributive laws and factoring, are used to simplify and manipulate regular expressions.
  • Two regular expressions are equivalent if they denote the same set, which can be tested algebraically with identities or by comparing minimal DFAs.
  • Thompson's construction turns a regular expression into an ε-NFA inductively, and every piece it builds has exactly one start state and one final state.
  • Base cases: for ∅ a start and a final state with no edge, for ε a start and a final joined by an ε-edge, and for a symbol a a start and a final joined by an a-edge.
  • For R1 + R2, a new start state gets ε-edges to the starts of both machines, and both old final states get ε-edges to a new final state.
  • For R1R2, the final state of R1 gets an ε-edge to the start of R2 (or the two are merged), and R1's start and R2's final become the new start and final.
  • For R*, a new start and a new final are added with ε-edges new start → old start, new start → new final, old final → old start and old final → new final.
  • Worked example (a+b)*ab: the union part has states 1 to 6 with 1 –ε→ 2, 1 –ε→ 4, 2 –a→ 3, 4 –b→ 5, 3 –ε→ 6 and 5 –ε→ 6.
  • Starring it adds states 0 and 7 with ε-edges 0→1, 0→7, 6→1 and 6→7, and concatenating ab adds 7 –a→ 8 and 8 –b→ 9, so the ε-NFA has ten states, start 0 and final 9.
  • To convert an FA to a regular expression, write one equation per state and solve them with Arden's theorem, or eliminate states one by one.
  • The pumping lemma is a necessary condition for regularity, so it can only show that a language is not regular.
  • Complement is obtained by swapping final and non-final states of a complete DFA, and intersection by the product construction with final states F1 × F2.
  • A grammar is G = (V, T, P, S), and its language is the set of terminal strings derivable from S.
  • Grammars are classified into types 0 to 3 according to the restrictions on the left and right sides of their productions, and the Chomsky hierarchy regular ⊂ context-free ⊂ context-sensitive ⊂ recursively enumerable matches FA, PDA, LBA and TM respectively.
  • Right-linear and left-linear grammars both generate exactly the regular languages, but mixing both forms in one grammar can give a non-regular language, e.g. S → aA, A → Sb | b generates {a^n b^n | n ≥ 1}.
  • In a right-linear grammar, A → aB becomes the transition A –a→ B, A → a goes to a new final state, and A → ε makes A final.
  • A left-linear grammar is converted to an FA by reversing its productions into a right-linear grammar, building that FA, and reversing the FA.

Learn these by heart

  • Arden's theorem: if ε ∉ P, then R = Q + RP has the unique solution R = QP*.
  • Pumping lemma: if L is regular, ∃ n such that ∀ w ∈ L with |w| ≥ n, w = xyz with |xy| ≤ n, |y| ≥ 1 and xy^i z ∈ L ∀ i ≥ 0.
  • Key identities: ∅R = ∅, εR = R, R + R = R, ε + RR* = R*, (R*)* = R*, (P+Q)* = (P*Q*)*, (PQ)*P = P(QP)*.
  • Thompson pieces: union and star each add two new states and four ε-edges, concatenation adds one ε-edge (or merges two states), and every piece keeps a single start and a single final state.
  • Chomsky types: Type 0 α → β (TM); Type 1 |α| ≤ |β| (LBA); Type 2 A → α (PDA); Type 3 A → aB | a (FA).
  • Grammar–FA mapping: A → aB ⇔ A –a→ B; A → ε ⇔ A is final; for a left-linear grammar, a transition p –a→ q gives q → pa and the start state gets q0 → ε.
  • Regular sets are closed under union, concatenation, star, complement, intersection, difference, reversal, homomorphism and inverse homomorphism.

2-mark questions

1 Define a regular expression and a regular set with an example. 2 marks
Model answer

A regular expression over an alphabet Σ is built from ∅, ε and each symbol a ∈ Σ. It uses union (+), concatenation and Kleene star (*), applied a finite number of times. The language it denotes, L(r), is called a regular set. For example, (0+1)*01 denotes all binary strings ending in 01.

2 State any four identity rules for regular expressions. 2 marks
Model answer

Identity rules are algebraic laws that hold for all regular expressions P, Q and R:

  • ∅ + R = R and ∅R = R∅ = ∅
  • εR = Rε = R
  • R + R = R and (R*)* = R*
  • ε + RR* = R* and (P + Q)* = (P*Q*)*
3 When are two regular expressions equivalent? Show that a(ba)* and (ab)*a are equivalent. 2 marks
Model answer

Two regular expressions are equivalent if they denote the same set.

  • a(ba)* = {a, aba, ababa, …}
  • (ab)*a = {a, aba, ababa, …}

Since a(ba)^k = (ab)^k a for every k ≥ 0, both sets are equal. Hence the two expressions are equivalent, which is the rule P(QP)* = (PQ)*P.

4 State the pumping lemma for regular sets. 2 marks
Model answer

If L is a regular set, there is a constant n such that every w ∈ L with |w| ≥ n can be split as w = xyz, where |xy| ≤ n, |y| ≥ 1 and xy^i z ∈ L for all i ≥ 0. The lemma is used to prove that a language is not regular.

5 List the closure properties of regular sets. 2 marks
Model answer

Regular sets are closed under union, concatenation, Kleene star, complement, intersection, difference, reversal, homomorphism and inverse homomorphism. Applying any of these operations to regular sets always produces a regular set. For example, the complement of a regular set L over Σ, namely Σ* − L, is again regular.

6 Distinguish between right-linear and left-linear grammars with an example each. 2 marks
Model answer

In a right-linear grammar every production is A → xB or A → x (x ∈ T*), so the variable stays at the right end. Example: S → aS | b generates a*b.

In a left-linear grammar every production is A → Bx or A → x. Example: S → Sa | b generates ba*.

Both kinds generate exactly the regular languages.

10-mark questions

1 State the identity rules for regular expressions. Using them prove that b + a*b = a*b, and show that (a*b*)* and (a + b)* are equivalent. How can the equivalence of two regular expressions be tested in general? 10 marks
Model answer

Regular expressions (REs) describe regular sets algebraically. Two REs are equivalent when they denote the same set. Identity rules let us transform one expression into another without changing its language.

Identity rules (P, Q, R are regular expressions):

  • I1: ∅ + R = R + ∅ = R
  • I2: ∅R = R∅ = ∅
  • I3: εR = Rε = R
  • I4: ε* = ε and ∅* = ε
  • I5: R + R = R
  • I6: R*R* = R*
  • I7: RR* = R*R
  • I8: (R*)* = R*
  • I9: ε + RR* = ε + R*R = R*
  • I10: (PQ)*P = P(QP)*
  • I11: (P + Q)* = (P*Q*)* = (P* + Q*)*
  • I12: (P + Q)R = PR + QR and R(P + Q) = RP + RQ

(a) Proof that b + a*b = a*b

Step 1: By I9, a* = ε + aa*, so a*b = (ε + aa*)b.

Step 2: By I12 and I3, (ε + aa*)b = εb + aa*b = b + aa*b.

Step 3: Hence b + a*b = b + (b + aa*b) = (b + b) + aa*b.

Step 4: By I5, b + b = b, so the expression becomes b + aa*b. By Step 2 this equals a*b.

Therefore b + a*b = a*b.

(b) Equivalence of (a*b*)* and (a + b)*

Let L1 = L((a*b*)*) and L2 = L((a + b)*).

Step 1 (L1 ⊆ L2): L2 is the set of all strings over {a, b}. Every string of L1 is made only of a's and b's, so it lies in L2.

Step 2 (L2 ⊆ L1): a = a·ε ∈ a*b* and b = ε·b ∈ a*b*. A string w = c1c2…ck with each ci ∈ {a, b} is therefore a concatenation of k strings of a*b*, so w ∈ (a*b*)*. For k = 0, ε ∈ (a*b*)* as well.

Step 3: Each set contains the other, so L1 = L2, that is, (a*b*)* = (a + b)*. This is identity I11 with P = a and Q = b.

Testing equivalence in general

  • Algebraic method: rewrite one expression into the other using the identities I1 to I12.
  • Automaton method: convert both REs to DFAs and minimise them. Then check that the two minimal DFAs are identical up to renaming of states.
  • To prove non-equivalence, one counterexample string is enough. For instance, abab ∈ (ab)* but abab ∉ a*b*, so (ab)* ≠ a*b*.

Conclusion: Identity rules give a quick algebraic way of simplifying and comparing regular expressions. The set argument or a minimal-DFA comparison confirms equivalence rigorously.

2 State and prove Arden's theorem. Use it to find a regular expression for the DFA with states q1 (start), q2, q3 (final) and transitions δ(q1,a)=q2, δ(q1,b)=q1, δ(q2,a)=q2, δ(q2,b)=q3, δ(q3,a)=q2, δ(q3,b)=q1. 10 marks
Model answer

Arden's theorem converts a finite automaton into a regular expression. We write one equation per state and solve the equations.

Statement: Let P and Q be regular expressions over Σ, where P does not contain ε. Then the equation R = Q + RP has the unique solution R = QP*.

Proof

Step 1 (QP* is a solution): Substitute R = QP*. Then Q + QP*P = Q(ε + P*P) = QP*, using the identity ε + P*P = P*.

Step 2 (expansion): Let R be any solution. Substituting the equation into itself repeatedly gives R = Q + QP + QP² + … + QP^k + RP^(k+1) for every k ≥ 0.

Step 3 (R ⊆ QP*): Take any w ∈ R with |w| = m and choose k = m. Since ε ∉ P, every string of RP^(m+1) has length at least m + 1, so w is not in that term. Hence w ∈ Q(ε + P + … + P^m) ⊆ QP*.

Step 4 (QP* ⊆ R): If w ∈ QP^i, the expansion with k ≥ i shows that w ∈ R. So R = QP*, and the solution is unique.

Example

DFA with start state q1 and final state q3Diagram in words: Three circles q1, q2 and q3. An unlabelled arrow from outside enters q1 (start state), and q3 is double-circled (final state). Arrows: q1 to q1 labelled b (self-loop), q1 to q2 labelled a, q2 to q2 labelled a (self-loop), q2 to q3 labelled b, q3 to q2 labelled a, and q3 to q1 labelled b.startq1q2q3 (final)baabab
DFA with start state q1 and final state q3

Step 1: Write an equation for each state from its incoming arrows, adding ε for the start state. q1 = ε + q1b + q3b q2 = q1a + q2a + q3a q3 = q2b

Step 2: Substitute q3 = q2b into the q2 equation: q2 = q1a + q2a + q2ba = q1a + q2(a + ba). By Arden with Q = q1a and P = a + ba: q2 = q1a(a + ba)*.

Step 3: Substitute into the q1 equation: q1 = ε + q1b + q2bb = ε + q1b + q1a(a + ba)*bb = ε + q1(b + a(a + ba)*bb). By Arden with Q = ε: q1 = (b + a(a + ba)*bb)*.

Step 4: The final state gives the answer: q3 = q2b = (b + a(a + ba)*bb)* a(a + ba)* b

Check: the strings ab, aab, bab and abab are all accepted by the DFA and generated by the expression. The DFA accepts exactly the strings ending in ab, so the result is equivalent to (a + b)*ab.

Conclusion: Arden's theorem turns state equations into a regular expression mechanically. The expression for the final state is the language of the automaton; if there are several final states, their expressions are added.

3 State the pumping lemma for regular sets, explain why it holds, and use it to prove that L = {0^k 1^k | k ≥ 0} is not regular. 10 marks
Model answer

The pumping lemma states a property that every regular language must have. It is mainly used to show, by contradiction, that a given language is not regular.

Statement: If L is a regular set, then there is a constant n, depending only on L, such that every string w ∈ L with |w| ≥ n can be written as w = xyz where

  • |xy| ≤ n,
  • |y| ≥ 1, and
  • xy^i z ∈ L for every i ≥ 0.

Why it holds

Step 1: Let M be a DFA for L with n states.

Step 2: While reading the first n symbols of w, M passes through n + 1 states q0, q1, …, qn. By the pigeonhole principle two of them are equal, say qj = qk with j < k ≤ n.

Step 3: Let x be the first j symbols, y the symbols from position j + 1 to k, and z the rest. Then |xy| = k ≤ n and |y| = k − j ≥ 1.

Step 4: Reading y takes M from qj back to the same state, so y labels a loop. The loop can be skipped (i = 0) or repeated any number of times, and M still ends in the same final state. Hence xy^i z ∈ L.

Pumping lemma: the loop on y in the DFADiagram in words: A start state q0 with an arrow labelled x going to a state p. At p there is a self-loop labelled y. From p an arrow labelled z goes to a double-circled final state f.q0 (start)pf (final,double circle)xyz
Pumping lemma: the loop on y in the DFA

Proof that L = {0^k 1^k | k ≥ 0} is not regular

Step 1: Assume, for contradiction, that L is regular, and let n be its pumping constant.

Step 2: Choose w = 0^n 1^n. Then w ∈ L and |w| = 2n ≥ n.

Step 3: Consider any split w = xyz with |xy| ≤ n and |y| ≥ 1. The first n symbols of w are all 0s, so x and y contain only 0s. Thus x = 0^p, y = 0^q with q ≥ 1, and z = 0^(n−p−q) 1^n.

Step 4: Take i = 0. Then xz = 0^(n−q) 1^n. Since q ≥ 1, the number of 0s (n − q) is less than the number of 1s (n), so xz ∉ L.

Step 5: The lemma requires xy^0 z ∈ L, so this is a contradiction. Hence L is not regular. Taking i = 2 also works, because 0^(n+q) 1^n ∉ L.

Remarks

  • The lemma is only a necessary condition. A language that satisfies it need not be regular, so the lemma can prove non-regularity but never regularity.
  • In such a proof we may choose w and i, but we must handle every possible split into x, y and z.

Conclusion: A finite automaton cannot count an unbounded number of 0s. The pumping lemma turns this intuition into a rigorous proof.

4 Explain the closure properties of regular sets with proofs. Using closure, show that the set of strings over {a, b} with equal numbers of a's and b's is not regular. 10 marks
Model answer

A class of languages is closed under an operation if applying that operation to members of the class always gives a member of the class. Regular sets are closed under many operations. This makes them easy to combine and also helps prove that some languages are not regular.

Let L1 and L2 be regular. Let r1 and r2 be their regular expressions, and let M1 = (Q1, Σ, δ1, q1, F1) and M2 = (Q2, Σ, δ2, q2, F2) be complete DFAs for them.

1. Union, concatenation and Kleene star: r1 + r2, r1r2 and r1* are regular expressions by definition. Hence L1 ∪ L2, L1L2 and L1* are regular. In automaton form, union is built as follows.

Union of regular sets: new start state with ε-arrows to M1 and M2Diagram in words: A new start state s has two ε-arrows, one to the start state of M1 and one to the start state of M2. M1 and M2 are drawn as boxes that keep their own final states, and these are the final states of the new machine.M1M2s (new start)q1 (startof M1)F1 (finalstates)q2 (startof M2)F2 (finalstates)εε
Union of regular sets: new start state with ε-arrows to M1 and M2

2. Complement: Build M' = (Q1, Σ, δ1, q1, Q1 − F1), that is, swap the final and non-final states of the complete DFA M1. M' accepts a string exactly when M1 rejects it, so Σ* − L1 is regular. The DFA must be complete, including any dead state.

3. Intersection: Use the product construction M = (Q1 × Q2, Σ, δ, (q1, q2), F1 × F2) with δ((p, q), a) = (δ1(p, a), δ2(q, a)). M runs both DFAs in parallel and accepts when both accept. Alternatively, by De Morgan's law, L1 ∩ L2 = complement(complement(L1) ∪ complement(L2)).

4. Difference: L1 − L2 = L1 ∩ complement(L2), which is regular by 2 and 3.

5. Reversal: Reverse every arrow of an FA for L1 and make the old start state the only final state. Add a new start state with ε-arrows to all old final states. The result accepts L1^R.

6. Homomorphism: If h maps each symbol to a string, replace each symbol a in r1 by h(a). This gives a regular expression for h(L1).

7. Inverse homomorphism: A DFA for h⁻¹(L1) uses the states of M1 with δ'(q, a) = δ̂1(q, h(a)). Reading a thus simulates reading h(a).

Application: Let L = {w ∈ {a, b}* | w has equal numbers of a's and b's}.

Step 1: Suppose L is regular.

Step 2: a*b* is regular, so by closure under intersection L ∩ a*b* would be regular.

Step 3: But L ∩ a*b* = {a^n b^n | n ≥ 0}, which is not regular by the pumping lemma.

Step 4: This is a contradiction, so L is not regular.

Conclusion: Regular sets are closed under union, concatenation, star, complement, intersection, difference, reversal, homomorphism and inverse homomorphism. Each property is proved by building a regular expression or an automaton for the result.

5 Define right-linear and left-linear grammars. Construct a finite automaton for the right-linear grammar S → 0S | 1A, A → 0A | 1S | ε, and then obtain an equivalent left-linear grammar from the automaton. 10 marks
Model answer

A regular grammar is either right-linear or left-linear. Such grammars generate exactly the languages accepted by finite automata, and conversion in either direction is mechanical.

Definitions

  • Right-linear grammar: every production has the form A → xB or A → x, where A and B are variables and x ∈ T*.
  • Left-linear grammar: every production has the form A → Bx or A → x.

Rules for converting a right-linear grammar to an FA

  • Each variable becomes a state, and the start symbol becomes the start state.
  • A → aB gives the transition A –a→ B.
  • A → a gives A –a→ Fnew, where Fnew is an extra final state.
  • A → ε makes A a final state.
  • A → a1a2…akB with k > 1 is split by adding an intermediate state after each symbol.

Applying the rules to S → 0S | 1A, A → 0A | 1S | ε

Step 1: Create states S (start) and A.

Step 2: S → 0S gives S –0→ S, and S → 1A gives S –1→ A.

Step 3: A → 0A gives A –0→ A, and A → 1S gives A –1→ S.

Step 4: A → ε makes A final.

Finite automaton for S → 0S | 1A, A → 0A | 1S | εDiagram in words: Two states S and A. An arrow from outside enters S (start), and A is double-circled (final). S has a self-loop labelled 0 and an arrow to A labelled 1. A has a self-loop labelled 0 and an arrow back to S labelled 1.startSA (final)0101
Finite automaton for S → 0S | 1A, A → 0A | 1S | ε

This FA is a DFA that changes state on every 1, so it accepts binary strings with an odd number of 1s. Check: S ⇒ 1A ⇒ 10A ⇒ 10 is accepted (one 1). The string 11 ends in S and is rejected.

Rules for converting an FA to a left-linear grammar

Here the variable for a state X generates the strings that lead from the start state to X.

  • For each transition p –a→ q, add q → pa.
  • For the start state q0, add q0 → ε.
  • The start symbol is the variable of the final state. If there are several final states, add a new start symbol Z with Z → each final-state variable.

Applying the rules to the FA

Step 1: S –0→ S gives S → S0.

Step 2: S –1→ A gives A → S1.

Step 3: A –0→ A gives A → A0.

Step 4: A –1→ S gives S → A1.

Step 5: S is the start state, so add S → ε.

Left-linear grammar (start symbol A): A → A0 | S1, S → S0 | A1 | ε.

Verification: A ⇒ A0 ⇒ A00 ⇒ S100 ⇒ S0100 ⇒ 0100. This string has one 1 and is accepted by the FA.

A left-linear grammar can also be converted to an FA another way. Reverse each right side to get a right-linear grammar for L^R, build its FA, and then reverse that FA.

Conclusion: Right-linear grammars, left-linear grammars and finite automata are equivalent descriptions of regular languages.

6 Define a grammar and explain the classification of grammars. Describe the Chomsky hierarchy with an example and the recognising machine for each type. 10 marks
Model answer

A grammar is a finite set of rewriting rules that generates the strings of a language. Chomsky classified grammars into four types according to the form of their productions.

Definition: A grammar is G = (V, T, P, S), where

  • V is a finite set of variables,
  • T is a finite set of terminals with V ∩ T = ∅,
  • P is a finite set of productions α → β in which α contains at least one variable,
  • S ∈ V is the start symbol.

We write α ⇒ β when β is obtained from α by applying one production, and ⇒* for zero or more steps. The language of G is L(G) = {w ∈ T* | S ⇒* w}.

Classification

1. Type 0 (unrestricted grammar): productions α → β with no further restriction. These generate the recursively enumerable languages, recognised by Turing machines.

2. Type 1 (context-sensitive grammar): productions α → β with |α| ≤ |β|. S → ε is allowed only if S does not appear on any right side. These generate the context-sensitive languages, recognised by linear bounded automata. Example for {a^n b^n c^n | n ≥ 1}: S → aSBC | aBC, CB → BC, aB → ab, bB → bb, bC → bc, cC → cc. Derivation for n = 2: S ⇒ aSBC ⇒ aaBCBC ⇒ aaBBCC ⇒ aabBCC ⇒ aabbCC ⇒ aabbcC ⇒ aabbcc.

3. Type 2 (context-free grammar): productions A → α, where A is a single variable and α ∈ (V ∪ T)*. These generate the context-free languages, recognised by pushdown automata. Example: S → aSb | ε generates {a^n b^n | n ≥ 0}.

4. Type 3 (regular grammar): right-linear productions A → aB | a, or left-linear productions A → Ba | a, with ε-productions permitted. These generate the regular languages, recognised by finite automata. Example: S → aS | bS | a generates the strings over {a, b} that end in a.

Chomsky hierarchy

Every type 3 grammar is type 2. Every type 2 grammar without ε-productions is type 1, and every type 1 grammar is type 0. The language families therefore form a chain: Regular ⊂ Context-free ⊂ Context-sensitive ⊂ Recursively enumerable.

Chomsky hierarchy: each class lies inside the nextDiagram in words: Four boxes in a column, each linked to the next by an arrow labelled inside. Type 3 regular languages (FA) lies inside Type 2 context-free languages (PDA), which lies inside Type 1 context-sensitive languages (LBA), which lies inside Type 0 recursively enumerable languages (TM).Type 0: r.e.languages (TM)Type 1: context-sens. (LBA)Type 2: context-free (PDA)Type 3:regular (FA)insideinsideinside
Chomsky hierarchy: each class lies inside the next

Each inclusion is proper:

  • {a^n b^n} is context-free but not regular.
  • {a^n b^n c^n} is context-sensitive but not context-free.
  • Some recursively enumerable languages are not context-sensitive.

Conclusion: Moving down the hierarchy, productions become more restricted, the languages become simpler, and the recognising machines need less memory.

Unit 3

Context-Free Grammars

Syllabus: Formal languages and context-free grammars; Leftmost and rightmost derivations; Parse trees; Ambiguous grammars; Elimination of useless symbols; Elimination of epsilon-productions and unit productions; Chomsky normal form; Greibach normal form; Pumping lemma for context-free languages; Closure properties of context-free languages; Applications of context-free grammars

One-page revision summary

  • A CFG G = (V, T, P, S) has productions A → α with a single variable on the left, and L(G) is the set of terminal strings derivable from S.
  • A leftmost derivation always replaces the leftmost variable and a rightmost derivation the rightmost; each parse tree corresponds to exactly one leftmost and one rightmost derivation.
  • A parse tree has the start symbol at the root, variables at interior nodes and terminals or ε at the leaves; its yield, read left to right, is the derived string.
  • A grammar is ambiguous if some string has two parse trees, or equivalently two leftmost derivations.
  • Some CFLs are inherently ambiguous: every grammar for them is ambiguous.
  • Expression grammars are made unambiguous by using one variable per precedence level (E, T, F) and left recursion for left associativity.
  • A symbol is useful only if it is both generating and reachable; remove non-generating symbols first, then unreachable ones.
  • Nullable variables are found iteratively: A is nullable if A → ε or A → B1...Bk with every Bi nullable.
  • Unit productions A → B are removed by finding all unit pairs (A, B) and copying the non-unit bodies of B to A.
  • Every CFL without ε has a CNF grammar (A → BC | a), obtained after simplification by replacing terminals in long bodies and splitting long bodies.
  • Every CFL without ε has a GNF grammar (A → aα), obtained by variable ordering, substitution and left-recursion removal.
  • The pumping lemma for CFLs splits z into uvwxy and pumps v and x together; it is used to prove that languages such as {a^n b^n c^n} and {ww} are not context-free.
  • CFLs are closed under union, concatenation, Kleene star, reversal, homomorphism, inverse homomorphism and intersection with regular languages.
  • CFLs are not closed under intersection or complement; the standard counterexample intersects {a^n b^n c^m} and {a^m b^n c^n}.
  • In a compiler the lexical analyser turns source text into tokens, which act as the terminals of the CFG, and the parser checks the token sequence against the grammar and builds a parse tree for later semantic analysis and code generation.
  • A grammar fragment S → id = E ; | if ( C ) S | if ( C ) S else S | { L } with L → S L | ε lets a parser recognise assignments, nested if statements and blocks; its two if rules cause the dangling-else ambiguity.
  • Nested structures such as balanced parentheses (B → (B)B | ε), begin–end blocks and matched XML start and end tags need unbounded counting, so they are context-free but not regular, which is why syntax is specified by CFGs rather than regular expressions.
  • Parser generators such as YACC and Bison read CFG productions annotated with semantic actions and automatically produce an LALR(1) parser, while XML DTDs and natural-language phrase-structure rules (S → NP VP) are further CFG-style applications.
  • Every regular language is context-free, because a right-linear grammar is a special case of a CFG.

Learn these by heart

  • CNF: every production is A → BC or A → a; a string of length n is derived in exactly 2n − 1 steps.
  • GNF: every production is A → aα with a ∈ T and α ∈ V*; a string of length n is derived in exactly n steps.
  • Pumping lemma for CFLs: z = uvwxy, |vwx| ≤ n, |vx| ≥ 1, and u v^i w x^i y ∈ L for all i ≥ 0.
  • Simplification order: ε-productions → unit productions → useless symbols (non-generating first, then unreachable).
  • Left-recursion removal: A → Aα | β becomes A → β | βZ and Z → α | αZ.
  • Closed: ∪, concatenation, *, reversal, homomorphism, ∩ with a regular language. Not closed: ∩ and complement.
  • Compiler use: tokens are terminals, the parser derives the token string from S, and the resulting parse tree drives translation; YACC/Bison build LALR(1) parsers from a CFG.

2-mark questions

1 Define a context-free grammar and the language it generates. 2 marks
Model answer

A context-free grammar is a 4-tuple G = (V, T, P, S). V is a finite set of variables, T is a finite set of terminals disjoint from V, P is a finite set of productions of the form A → α with A ∈ V and α ∈ (V ∪ T)*, and S ∈ V is the start symbol. The language of G is L(G) = {w ∈ T* | S ⇒* w}.

2 Distinguish a leftmost derivation from a rightmost derivation with a small example. 2 marks
Model answer

In a leftmost derivation, the leftmost variable of the sentential form is replaced at every step. In a rightmost derivation, the rightmost variable is replaced.

For S → AB, A → a, B → b:

  • Leftmost: S ⇒ AB ⇒ aB ⇒ ab
  • Rightmost: S ⇒ AB ⇒ Ab ⇒ ab

Both derivations correspond to the same parse tree.

3 When is a context-free grammar said to be ambiguous? Give an example. 2 marks
Model answer

A CFG is ambiguous if some string in its language has two or more distinct parse trees. Equivalently, the string has two different leftmost derivations.

Example: S → SS | a. The string aaa can be grouped as (aa)a or as a(aa). This gives two different parse trees, so the grammar is ambiguous.

4 What is a useless symbol in a CFG? Give an example. 2 marks
Model answer

A symbol X is useful if S ⇒* αXβ ⇒* w for some terminal string w; otherwise X is useless. A useful symbol must be both generating (it derives some terminal string) and reachable (it appears in some sentential form derived from S).

Example: in S → a | B, B → bB, the variable B never yields a terminal string, so B is useless.

5 Distinguish Chomsky normal form from Greibach normal form. 2 marks
Model answer

In Chomsky normal form, every production is A → BC or A → a, where A, B, C are variables and a is a terminal.

In Greibach normal form, every production is A → aα, where a is a terminal and α is a string of zero or more variables.

A CNF derivation of a string of length n takes 2n − 1 steps; a GNF derivation takes exactly n steps.

6 Find the nullable variables of the grammar S → AB, A → aA | ε, B → bB | A. 2 marks
Model answer

A variable is nullable if it can derive ε.

  • A → ε, so A is nullable.
  • B → A and A is nullable, so B is nullable.
  • S → AB and both A and B are nullable, so S is nullable.

Nullable set = {A, B, S}. Since the start symbol S is nullable, ε ∈ L(G).

10-mark questions

1 Consider the grammar G: S → XY, X → aXb | ab, Y → cY | c. (a) Describe L(G). (b) Give the leftmost and rightmost derivations of the string aabbccc. (c) Draw the parse tree and explain how both derivations relate to it. 10 marks
Model answer

A context-free grammar generates strings by repeatedly replacing a variable with the body of one of its productions. A leftmost derivation (⇒lm) always expands the leftmost variable. A rightmost derivation (⇒rm) always expands the rightmost variable. Both can be pictured by one parse tree.

Step 1: Language of G.

  • X → aXb | ab generates a^n b^n with n ≥ 1. Each use of X → aXb adds one a on the left and one b on the right, and X → ab ends the recursion.
  • Y → cY | c generates c^m with m ≥ 1.
  • S → XY concatenates the two parts.
  • Therefore L(G) = {a^n b^n c^m | n ≥ 1, m ≥ 1}.

Step 2: Leftmost derivation of aabbccc. S ⇒lm XY ⇒lm aXbY ⇒lm aabbY ⇒lm aabbcY ⇒lm aabbccY ⇒lm aabbccc X is completely expanded before Y is touched, because X is always the leftmost variable.

Step 3: Rightmost derivation of aabbccc. S ⇒rm XY ⇒rm XcY ⇒rm XccY ⇒rm Xccc ⇒rm aXbccc ⇒rm aabbccc Here Y is expanded first, because it is the rightmost variable in every sentential form until it disappears.

Both derivations use the same six production applications: S → XY, X → aXb, X → ab, Y → cY (twice) and Y → c. Only the order differs.

Step 4: Parse tree.

Parse tree of aabbccc in grammar GDiagram in words: The root node S has two children, X on the left and Y on the right. X has three children, left to right: leaf a, an inner node X, leaf b. The inner X has two children: leaf a and leaf b. Y has two children: leaf c and an inner node Y. That inner Y has two children: leaf c and a third node Y. The third Y has a single child, leaf c. Reading the leaves from left to right gives the yield a a b b c c c.SXYaXbabcYcYc
Parse tree of aabbccc in grammar G

Step 5: Relation between the derivations and the tree. A parse tree records which production is used at each interior node but not the order of use.

  • Expanding the tree top-down, always choosing the leftmost unexpanded variable, reproduces the leftmost derivation of Step 2.
  • Always choosing the rightmost unexpanded variable reproduces the rightmost derivation of Step 3.
  • So each parse tree corresponds to exactly one leftmost and exactly one rightmost derivation.

Conclusion: aabbccc ∈ L(G) = {a^n b^n c^m | n, m ≥ 1}. Its leftmost and rightmost derivations differ only in the order of replacement, and both correspond to the single parse tree described above.

2 Show that the grammar E → E + E | E * E | a is ambiguous using the string a + a * a. Construct an equivalent unambiguous grammar and give the unique leftmost derivation of the same string in it. 10 marks
Model answer

A grammar is ambiguous when one string has two different parse trees, or equivalently two different leftmost derivations. Ambiguity matters in compilers, because each parse tree gives a different meaning, here a different order of evaluating + and *.

Step 1: First leftmost derivation (+ at the root). E ⇒ E + E ⇒ a + E ⇒ a + E * E ⇒ a + a * E ⇒ a + a * a

Step 2: Second leftmost derivation (* at the root). E ⇒ E * E ⇒ E + E * E ⇒ a + E * E ⇒ a + a * E ⇒ a + a * a

The two derivations differ at the very first step, so they are different leftmost derivations of the same string.

Step 3: The two parse trees.

Parse trees of a + a * a: two ambiguous trees and the unambiguous treeDiagram in words: Tree 1 has root E with three children: E, +, E. The left child E has one child, leaf a. The right child E has three children: E, *, E, and each of these two E nodes has one child, leaf a. This tree means a + (a * a). Diagram in words: Tree 2 has root E with three children: E, *, E. The left child E has three children: E, +, E, and each of these two E nodes has one child, leaf a. The right child E of the root has one child, leaf a. This tree means (a + a) * a. Diagram in words: The root E has children E, +, T. The left E has child T, which has child F, which has child leaf a.Tree 1: a + (a * a)Tree 2: (a + a) * aUnambiguous tree (E, T, F)E → E + EE → aE → E * EE → aE → aE → E * EE → E + EE → aE → aE → aE → E + TE ⇒ T ⇒ F ⇒ aT → T * FT ⇒ F ⇒ aF → aleft Eright Eleft Eright Eleft Eright Eleft Eright EETTF
Parse trees of a + a * a: two ambiguous trees and the unambiguous tree

Both trees have yield a + a * a, so the grammar is ambiguous.

Step 4: Removing the ambiguity. Introduce one variable for each precedence level and make the recursion left-sided so that both operators associate to the left: E → E + T | T T → T * F | F F → a In this grammar:

  • * can only appear below a T, so * binds more tightly than +.
  • Left recursion forces a + a + a to be grouped as (a + a) + a.
  • The language is unchanged: it is still all strings a op a op ... a with op ∈ {+, *}.

Step 5: Unique leftmost derivation of a + a * a. E ⇒ E + T ⇒ T + T ⇒ F + T ⇒ a + T ⇒ a + T * F ⇒ a + F * F ⇒ a + a * F ⇒ a + a * a At every step only one production can lead to the target string, so this derivation is the only leftmost derivation.

Conclusion: The original grammar is ambiguous because a + a * a has two parse trees. The layered grammar E, T, F generates the same language, gives * higher precedence than +, and assigns every string exactly one parse tree. This is the main application of context-free grammars in compilers: a parser for a programming language uses a layered grammar of this kind so that every expression has one parse tree, and that tree fixes the order of evaluation.

3 Simplify the grammar S → AB | C, A → aA | ε, B → bB | b, C → cC, D → d by eliminating ε-productions, unit productions and useless symbols, in that order. Verify that the language is unchanged. 10 marks
Model answer

A grammar is simplified so that every symbol and production is actually needed; this prepares it for conversion to a normal form. The safe order is: remove ε-productions, then unit productions, then useless symbols. The first two steps can leave new useless symbols behind, so useless symbols are removed last.

Step 1: Eliminate ε-productions.

  • Find the nullable variables. A is nullable because A → ε.
  • B is not nullable, since both of its bodies contain the terminal b.
  • S → AB needs B, so S is not nullable. C and D are not nullable either.
  • For each production, add copies with nullable variables omitted, then delete A → ε.
  • S → AB gives S → AB | B.
  • A → aA gives A → aA | a.

Result: S → AB | B | C, A → aA | a, B → bB | b, C → cC, D → d.

Step 2: Eliminate unit productions.

  • The unit productions are S → B and S → C.
  • Apart from the trivial pairs (X,X), the unit pairs are (S,B) and (S,C).
  • Replace S → B by the non-unit bodies of B, which are bB | b.
  • Replace S → C by the body of C, which is cC.

Result: S → AB | bB | b | cC, A → aA | a, B → bB | b, C → cC, D → d.

Step 3: Eliminate useless symbols. (a) Non-generating symbols.

  • The terminals a, b, c, d are generating.
  • A is generating (A → a), B is generating (B → b), D is generating (D → d), and S is generating (S → b).
  • C → cC never terminates, so C is non-generating. Delete C and every production containing it, which removes S → cC.

(b) Unreachable symbols.

  • From S we reach A and B; from A and B we reach only a and b.
  • D is unreachable, so delete D → d.

Non-generating symbols must be removed before unreachable ones; the reverse order can leave useless symbols behind.

Final grammar: S → AB | bB | b A → aA | a B → bB | b

Step 4: Verification.

  • In the original grammar, A derives a* and B derives b+, while C contributes no terminal string. So L = {a^m b^n | m ≥ 0, n ≥ 1}.
  • In the final grammar, S → AB derives a^m b^n with m ≥ 1, n ≥ 1, and S → bB | b derives b^n with n ≥ 1.
  • The union of these is again {a^m b^n | m ≥ 0, n ≥ 1}.
  • ε was never in the language, because B is not nullable, so removing A → ε loses nothing.

Conclusion: The simplified grammar has no ε-productions, no unit productions and no useless symbols, and it generates exactly the same language a* b+.

4 Convert the grammar S → aSb | A, A → cA | c into Chomsky normal form. Verify your answer by deriving the string acb in the new grammar. 10 marks
Model answer

A grammar is in Chomsky normal form (CNF) when every production has one of two forms: A → BC, where B and C are variables, or A → a, where a is a terminal. Every CFL without ε has a CNF grammar. In CNF every parse tree is binary, which is used by the CYK membership algorithm and in proving the pumping lemma.

The given grammar generates L = {a^n c^m b^n | n ≥ 0, m ≥ 1}.

Step 1: Remove ε-productions. There are none, and no variable is nullable.

Step 2: Remove unit productions.

  • S → A is a unit production. Replace it by the bodies of A: S → cA | c.
  • Grammar now: S → aSb | cA | c, A → cA | c.

Step 3: Remove useless symbols.

  • S and A are both generating (each has a production with body c).
  • Both are reachable from S, so nothing is removed.

Step 4: Replace terminals in long bodies.

  • For each terminal that appears in a body of length 2 or more, add a new variable: Ca → a, Cb → b, Cc → c.
  • S → aSb becomes S → Ca S Cb.
  • S → cA becomes S → Cc A.
  • A → cA becomes A → Cc A.
  • Bodies that are a single terminal, S → c and A → c, are already allowed.

Step 5: Break bodies longer than two variables.

  • S → Ca S Cb has three variables. Introduce D with D → S Cb.
  • The production becomes S → Ca D.

Final CNF grammar: S → Ca D | Cc A | c D → S Cb A → Cc A | c Ca → a Cb → b Cc → c

Every production is now either variable variable or a single terminal.

Step 6: Verification with acb. S ⇒ Ca D ⇒ a D ⇒ a S Cb ⇒ a c Cb ⇒ acb

The derivation takes 5 steps. In CNF a string of length n always needs 2n − 1 steps: n − 1 steps of the form A → BC and n steps of the form A → a. For n = 3 this gives 2(3) − 1 = 5, which matches.

Parse tree for acb in the CNF grammarDiagram in words: The root S has two children, Ca and D. Ca has the single child leaf a. D has two children, S and Cb. That S has the single child leaf c, and Cb has the single child leaf b. The yield read left to right is a c b.SCaDaSCbcb
Parse tree for acb in the CNF grammar

Conclusion: The grammar S → Ca D | Cc A | c, D → S Cb, A → Cc A | c, Ca → a, Cb → b, Cc → c is in CNF and generates {a^n c^m b^n | n ≥ 0, m ≥ 1}, the same language as the original grammar.

5 Convert the CNF grammar A1 → A2 A2 | a, A2 → A1 A2 | b into Greibach normal form. State the two rules used during the conversion. 10 marks
Model answer

A grammar is in Greibach normal form (GNF) if every production is A → aα, where a is a terminal and α ∈ V*. Each derivation step then produces exactly one terminal, so a string of length n is derived in n steps. GNF is also convenient for building a PDA from a grammar. The conversion starts from a CNF grammar whose variables are ordered A1, A2, ..., An.

Rules used:

  • Substitution rule: if A → Bγ and B → β1 | ... | βk, replace A → Bγ by A → β1γ | ... | βkγ. The language is unchanged.
  • Left-recursion removal: if A → Aα1 | ... | Aαr | β1 | ... | βs, where no βi starts with A, replace these by A → βi | βiZ for every i, and Z → αj | αjZ for every j, where Z is a new variable.

Step 1: Make every Ai → Aj γ satisfy j > i.

  • A1 → A2A2 | a. Here 2 > 1, so this is already acceptable.
  • A2 → A1A2 | b has a body starting with A1, and 1 < 2.
  • Substitute the bodies of A1: A2 → A2A2A2 | aA2 | b.

Step 2: Remove left recursion from A2.

  • Write A2 → A2(A2A2) | aA2 | b. Here α = A2A2, β1 = aA2 and β2 = b.
  • Introduce Z:
  • A2 → aA2 | b | aA2Z | bZ
  • Z → A2A2 | A2A2Z

Every A2 production now begins with a terminal.

Step 3: Back-substitute into A1.

  • A1 → A2A2 | a. Replace the leading A2 by each of its four bodies:
  • A1 → aA2A2 | bA2 | aA2ZA2 | bZA2 | a

Step 4: Back-substitute into Z.

  • Z → A2A2 gives aA2A2 | bA2 | aA2ZA2 | bZA2.
  • Z → A2A2Z gives aA2A2Z | bA2Z | aA2ZA2Z | bZA2Z.

Final GNF grammar: A1 → aA2A2 | bA2 | aA2ZA2 | bZA2 | a A2 → aA2 | b | aA2Z | bZ Z → aA2A2 | bA2 | aA2ZA2 | bZA2 | aA2A2Z | bA2Z | aA2ZA2Z | bZA2Z

Every body is a terminal followed only by variables, so the grammar is in GNF.

Step 5: Check with the string bb.

  • Original grammar: A1 ⇒ A2A2 ⇒ bA2 ⇒ bb.
  • GNF grammar: A1 ⇒ bA2 ⇒ bb.
  • The GNF derivation takes 2 steps for a string of length 2, as expected.

Conclusion: By ordering the variables, substituting earlier variables, removing left recursion with the new variable Z, and then back-substituting, the CNF grammar becomes an equivalent grammar in Greibach normal form.

6 State the pumping lemma for context-free languages and use it to prove that L = {a^k b^k c^k | k ≥ 1} is not context-free. Using this result, explain the closure properties of CFLs under union, concatenation, star, intersection and complement. 10 marks
Model answer

Pumping lemma for CFLs: if L is context-free, there is a constant n such that every z ∈ L with |z| ≥ n can be written z = uvwxy where:

  • (1) |vwx| ≤ n
  • (2) |vx| ≥ 1
  • (3) u v^i w x^i y ∈ L for all i ≥ 0

The lemma comes from the parse tree of a CNF grammar. A long enough string forces some root-to-leaf path on which a variable repeats, and the part of the tree between the two copies can be repeated or removed.

Part A: L = {a^k b^k c^k | k ≥ 1} is not context-free.

Step 1: Assume L is a CFL, and let n be its pumping constant.

Step 2: Choose z = a^n b^n c^n. Then z ∈ L and |z| = 3n ≥ n.

Step 3: Take any split z = uvwxy that satisfies (1) and (2).

  • The a's occupy positions 1 to n, and the c's occupy positions 2n+1 to 3n.
  • vwx is a block of at most n consecutive symbols.
  • Containing both an a and a c would need at least n+2 positions, so vwx cannot contain both.

Step 4: Pump with i = 0, which gives uwy.

  • Case (i): vwx contains no c. Then uwy loses |vx| ≥ 1 symbols, all a's or b's, but keeps n c's. The three counts are not equal, so uwy ∉ L.
  • Case (ii): vwx contains no a. Then uwy keeps n a's but has fewer b's or c's, so uwy ∉ L.

Step 5: Every allowed split fails condition (3). This contradicts the lemma, so L is not context-free.

Part B: Closure properties. Let G1 and G2, with start symbols S1 and S2 and disjoint sets of variables, generate L1 and L2. Let S be a new start symbol.

  • Union: add S → S1 | S2.
  • Concatenation: add S → S1S2.
  • Kleene star: add S → S1S | ε.
  • CFLs are also closed under reversal (reverse every production body), under homomorphism (replace each terminal a by h(a)), and under intersection with a regular language (run a PDA and a DFA together as a product machine).

CFLs are not closed under intersection.

  • L1 = {a^n b^n c^m | n, m ≥ 1} is a CFL; it is generated by S → XY, X → aXb | ab, Y → cY | c.
  • L2 = {a^m b^n c^n | n, m ≥ 1} is a CFL in the same way.
  • L1 ∩ L2 = {a^n b^n c^n | n ≥ 1}, which Part A shows is not a CFL.

CFLs are not closed under complement.

  • By De Morgan's law, L1 ∩ L2 = ¬(¬L1 ∪ ¬L2).
  • If CFLs were closed under complement, closure under union would then give closure under intersection.
  • That contradicts the result just shown.

Conclusion: The pumping lemma shows that {a^k b^k c^k} is not context-free. CFLs are closed under union, concatenation, star, reversal, homomorphism and intersection with regular sets, but not under intersection or complement.

Unit 4

Pushdown Automata

Syllabus: Definition and model of a pushdown automaton; Graphical notation; Instantaneous description; Language acceptance by pushdown automata; Design of pushdown automata; Deterministic and non-deterministic pushdown automata; Equivalence of pushdown automata and context-free grammars; Conversion between pushdown automata and context-free grammars; Two-stack pushdown automata; Applications of pushdown automata

One-page revision summary

  • A PDA is an ε-NFA with an unbounded LIFO stack, which gives it more power than a finite automaton.
  • Each PDA move depends on the current state, the input symbol or ε, and the stack top, and it replaces the top with a string (pop, keep or push).
  • In the transition diagram, a PDA edge from q to p is labelled "a, X / γ"; the start state has an incoming arrow and final states are double circles.
  • An instantaneous description (q, w, γ) captures the state, the unread input and the stack, and ⊢* traces a whole computation.
  • Acceptance by final state and acceptance by empty stack are equivalent for NPDAs; the conversions use a new bottom marker X0.
  • Design strategy: push symbols while reading the first part, pop to match the second part, and use an ε-move on Z0 to accept.
  • A DPDA allows at most one move in each situation; deterministic CFLs form a proper subset of CFLs, and every regular language is a DCFL.
  • Every DCFL has an unambiguous grammar, so inherently ambiguous CFLs need a nondeterministic PDA.
  • CFG to PDA: build a single-state PDA that expands variables by ε-moves and matches terminals, simulating a leftmost derivation.
  • PDA to CFG: triple variables [p X q] describe the net popping of X while moving from state p to state q.
  • A two-stack PDA can simulate a Turing machine tape, with one stack for each side of the head, so it is as powerful as a TM.
  • One stack cannot accept {a^n b^n c^n}, but two stacks can.
  • Applications of PDAs include compiler parsers (LL/LR), balanced-parenthesis checking, infix-to-postfix conversion, postfix well-formedness checking, XML/HTML tag matching, and modelling recursive calls.

Learn these by heart

  • P = (Q, Σ, Γ, δ, q0, Z0, F) with δ: Q × (Σ ∪ {ε}) × Γ → finite subsets of Q × Γ*.
  • Move relation: (q, aw, Xβ) ⊢ (p, w, γβ) iff (p, γ) ∈ δ(q, a, X).
  • L(P) = {w | (q0, w, Z0) ⊢* (f, ε, γ), f ∈ F}; N(P) = {w | (q0, w, Z0) ⊢* (q, ε, ε)}.
  • DPDA: |δ(q, a, X)| ≤ 1, |δ(q, ε, X)| ≤ 1, and δ(q, ε, X) ≠ ∅ implies δ(q, a, X) = ∅ for every a ∈ Σ.
  • CFG→PDA: δ(q, ε, A) = {(q, α) | A → α}; δ(q, a, a) = {(q, ε)}.
  • PDA→CFG: S → [q0 Z0 p]; (r, ε) ∈ δ(q, a, X) gives [q X r] → a; (r, Y1...Yk) ∈ δ(q, a, X) gives [q X rk] → a[r Y1 r1]...[r(k-1) Yk rk].

2-mark questions

1 Define a pushdown automaton formally. 2 marks
Model answer

A pushdown automaton is a 7-tuple P = (Q, Σ, Γ, δ, q0, Z0, F). Q is a finite set of states, Σ the input alphabet, Γ the stack alphabet, and q0 the start state. Z0 ∈ Γ is the initial stack symbol and F ⊆ Q the final states. The transition function is δ: Q × (Σ ∪ {ε}) × Γ → finite subsets of Q × Γ*.

2 What is an instantaneous description (ID) of a PDA? 2 marks
Model answer

An ID is a triple (q, w, γ). Here q is the current state, w is the unread part of the input and γ is the stack contents, with the top written leftmost. One move is written (q, aw, Xβ) ⊢ (p, w, αβ) when (p, α) ∈ δ(q, a, X). The relation ⊢* denotes zero or more moves.

3 List any four applications of pushdown automata. 2 marks
Model answer
  • Syntax analysis in compilers: LL and LR parsers are deterministic PDAs.
  • Checking balanced parentheses and the nesting of begin-end blocks.
  • Converting infix expressions to postfix and checking that a postfix expression is well formed.
  • Checking that HTML or XML tags are properly nested and matched.
4 Distinguish acceptance by final state and acceptance by empty stack. 2 marks
Model answer

Acceptance by final state: L(P) = {w | (q0, w, Z0) ⊢* (f, ε, γ), f ∈ F, γ any stack}. Acceptance by empty stack: N(P) = {w | (q0, w, Z0) ⊢* (q, ε, ε), q any state}. For nondeterministic PDAs the two modes accept exactly the same class of languages.

5 State two differences between a DPDA and an NPDA. 2 marks
Model answer
  • In a DPDA, |δ(q, a, X)| ≤ 1, and if δ(q, ε, X) is non-empty then δ(q, a, X) is empty for every input a. An NPDA may have several choices of move.
  • An NPDA accepts every context-free language. A DPDA accepts only the deterministic CFLs. For example, {ww^R} needs nondeterminism.
6 What is a two-stack pushdown automaton? Comment on its power. 2 marks
Model answer

A two-stack PDA has a finite control, an input tape and two independent stacks. Each move depends on the state, the input symbol (or ε) and the tops of both stacks, and it may rewrite both tops. It is as powerful as a Turing machine. It accepts non-context-free languages such as {a^n b^n c^n | n ≥ 1}.

10-mark questions

1 Explain the model of a pushdown automaton with a neat diagram. Give its formal definition, its graphical notation and the concept of instantaneous description with an example. 10 marks
Model answer

A pushdown automaton (PDA) is a finite automaton with ε-moves that also has a stack. The stack is a last-in-first-out store of unbounded size. This extra memory lets a PDA recognise the context-free languages, such as {a^n b^n}, which no finite automaton can accept.

1. Components of the model:

  • Input tape: holds the input string. It is read one symbol at a time from left to right.
  • Read head: moves only rightwards, and does not move on an ε-move.
  • Finite control: holds the current state.
  • Stack: initially holds only Z0. Only the top symbol can be read or replaced.
Model of a pushdown automatonDiagram in words: A horizontal box labelled "Input tape" holds cells a1 a2 ... an. An arrow from a small box labelled "Read head" points down to the current cell. A box labelled "Finite control (state q)" is connected to the read head by an arrow pointing to the control. A two-way arrow labelled "read top / replace top" links the finite control to a vertical box labelled "Stack", whose top cell is X and whose bottom cell is Z0.Read headInput tape:a1 a2 ... anFinite control(state q)Stack: topX, bottom Z0read top /replace top
Model of a pushdown automaton

2. Formal definition: P = (Q, Σ, Γ, δ, q0, Z0, F).

  • Q: finite set of states.
  • Σ: input alphabet.
  • Γ: stack alphabet.
  • q0: start state.
  • Z0 ∈ Γ: initial stack symbol.
  • F ⊆ Q: final states.
  • δ: Q × (Σ ∪ {ε}) × Γ → finite subsets of Q × Γ*.

If (p, γ) ∈ δ(q, a, X), then in state q, reading a with X on top, the PDA can go to p and replace X by γ. If γ = ε, X is popped. If γ = X, the stack is unchanged. If γ = YX, Y is pushed.

3. Graphical notation: states are circles and the start state has an incoming arrow. Final states are double circles. An edge from q to p labelled "a, X / γ" stands for the move (p, γ) ∈ δ(q, a, X).

4. Instantaneous description: an ID (q, w, γ) records the state, the unread input and the stack, with the top written leftmost. The move relation is defined as follows: (q, aw, Xβ) ⊢ (p, w, γβ) if (p, γ) ∈ δ(q, a, X). Here ⊢* is the reflexive transitive closure of ⊢.

5. Example: take Q = {q0, q1, q2}, Σ = {0, 1}, Γ = {0, Z0}, start state q0, start symbol Z0 and F = {q2}, with δ(q0, 0, Z0) = {(q0, 0Z0)}, δ(q0, 0, 0) = {(q0, 00)}, δ(q0, 1, 0) = {(q1, ε)}, δ(q1, 1, 0) = {(q1, ε)} and δ(q1, ε, Z0) = {(q2, Z0)}. For input 0011:

(q0, 0011, Z0) ⊢ (q0, 011, 0Z0) ⊢ (q0, 11, 00Z0) ⊢ (q1, 1, 0Z0) ⊢ (q1, ε, Z0) ⊢ (q2, ε, Z0).

The PDA ends in the final state q2, so 0011 is accepted.

Conclusion: the PDA is a finite control combined with a stack. IDs give a precise way to trace its computation step by step.

2 Define the two modes of acceptance of a PDA. Prove that a language accepted by final state can be accepted by empty stack and vice versa. 10 marks
Model answer

A PDA can signal acceptance in two ways: by entering a final state, or by emptying its stack. Both modes define the same class of languages for nondeterministic PDAs.

1. Definitions for P = (Q, Σ, Γ, δ, q0, Z0, F):

  • Final state: L(P) = {w | (q0, w, Z0) ⊢* (f, ε, γ) for some f ∈ F, γ ∈ Γ*}.
  • Empty stack: N(P) = {w | (q0, w, Z0) ⊢* (q, ε, ε) for some q ∈ Q}.

2. Theorem A (empty stack to final state): if L = N(PN), then L = L(PF) for some PDA PF.

Construction: add a new start state p0, a new final state pf and a new bottom marker X0.

  • δF(p0, ε, X0) = {(q0, Z0X0)}: push PN's start symbol above X0.
  • All moves of PN are copied unchanged.
  • For every state q of PN: δF(q, ε, X0) = {(pf, ε)}.

X0 becomes the top only when PN has emptied its own stack. At that moment PF moves to pf and accepts. Without X0, PF would block on an empty stack instead of reaching pf.

Empty stack to final state: PDA PF built from PNDiagram in words: A start arrow enters circle p0. An arrow labelled "ε, X0 / Z0X0" goes from p0 to a dashed box labelled "PN" containing q0. From every state inside the box, an arrow labelled "ε, X0 / ε" goes to the double circle pf.PNstartp0q0everystate of PNpf (final)ε, X0 / Z0X0ε, X0 / ε
Empty stack to final state: PDA PF built from PN

3. Theorem B (final state to empty stack): if L = L(PF), then L = N(PN) for some PDA PN.

Construction: add a new start state p0, a new erasing state pe and a new bottom marker X0.

  • δN(p0, ε, X0) = {(q0, Z0X0)}.
  • All moves of PF are copied unchanged.
  • For every f ∈ F and every Y ∈ Γ ∪ {X0}: (pe, ε) ∈ δN(f, ε, Y).
  • For every Y ∈ Γ ∪ {X0}: δN(pe, ε, Y) = {(pe, ε)}.

Whenever PF reaches a final state, PN may jump to pe and pop everything. X0 matters here too: PF might empty its own stack on a string it does not accept. Because X0 can be removed only in pe, PN never empties its stack by accident.

4. Correctness: in each construction, every accepting run of the old PDA becomes an accepting run of the new PDA, with one extra move at the start and some extra ε-moves at the end. Conversely, the new PDA can accept only by passing through the copied moves.

Conclusion: for NPDAs, L(P) and N(P) describe the same family, the context-free languages. For DPDAs, acceptance by empty stack is weaker. It accepts only those deterministic CFLs with the prefix property, that is, where no string in the language is a proper prefix of another.

3 Design a PDA accepting L = {a^n b^2n | n ≥ 1} by final state. Draw its transition diagram and show the sequence of instantaneous descriptions for aabbbb and for aabbb. 10 marks
Model answer

Each a must be matched by exactly two b's. The PDA can do this by pushing two stack symbols X for every a and popping one X for every b. The input is accepted when the stack is back to Z0 just as the input ends.

1. Idea:

  • In q0, read a's. Each a pushes XX.
  • On the first b, move to q1 and pop one X. Each further b pops one X.
  • In q1, if Z0 is on top, move to the final state q2 by an ε-move.

2. PDA: P = ({q0, q1, q2}, {a, b}, {X, Z0}, δ, q0, Z0, {q2}), where:

δ(q0, a, Z0) = {(q0, XXZ0)}
δ(q0, a, X)  = {(q0, XXX)}
δ(q0, b, X)  = {(q1, ε)}
δ(q1, b, X)  = {(q1, ε)}
δ(q1, ε, Z0) = {(q2, Z0)}

There is at most one move in every situation, and no ε-move competes with an input move. So this PDA is deterministic.

3. Transition diagram.

PDA for L = {a^n b^2n | n ≥ 1}, accepting by final stateDiagram in words: Three circles q0, q1 and q2. A start arrow enters q0. q2 is a double circle (final). q0 has a self-loop with two labels, "a, Z0 / XXZ0" and "a, X / XXX". An arrow from q0 to q1 is labelled "b, X / ε". q1 has a self-loop labelled "b, X / ε". An arrow from q1 to q2 is labelled "ε, Z0 / Z0".startq0q1q2 (final)a,Z0/XXZ0| a,X/XXXb, X / εb, X / εε, Z0 / Z0
PDA for L = {a^n b^2n | n ≥ 1}, accepting by final state

4. Trace for aabbbb (n = 2, four b's):

(q0, aabbbb, Z0) ⊢ (q0, abbbb, XXZ0) ⊢ (q0, bbbb, XXXXZ0) ⊢ (q1, bbb, XXXZ0) ⊢ (q1, bb, XXZ0) ⊢ (q1, b, XZ0) ⊢ (q1, ε, Z0) ⊢ (q2, ε, Z0)

The input is consumed and q2 is final, so aabbbb is accepted.

5. Trace for aabbb:

(q0, aabbb, Z0) ⊢ (q0, abbb, XXZ0) ⊢ (q0, bbb, XXXXZ0) ⊢ (q1, bb, XXXZ0) ⊢ (q1, b, XXZ0) ⊢ (q1, ε, XZ0).

No move is defined for (q1, ε, X), so the PDA halts in the non-final state q1. The string is rejected because one X is left unmatched.

6. Other rejections: a string such as aabbbbb with too many b's reaches (q1, b, Z0), where only the ε-move to q2 is possible, and then q2 has no move for the leftover b. A string like abab dies on (q1, a, X), which also has no move.

Conclusion: the PDA counts with the stack, using two X's per a. It is deterministic and accepts exactly {a^n b^2n | n ≥ 1}.

4 Design a deterministic PDA for L = {w c w^R | w ∈ {a, b}*} and trace it on abcba. Explain why {w w^R} needs a nondeterministic PDA, and state the conditions for a PDA to be deterministic. 10 marks
Model answer

A PDA for palindromes stores the first half of the input on the stack and then matches the second half against it. The centre marker c tells the machine exactly where to switch from storing to matching, so no guessing is needed.

1. Design idea:

  • q0: push every a or b read.
  • On reading c: go to q1 without changing the stack.
  • q1: pop when the input symbol equals the top of the stack.
  • When Z0 reappears in q1: go to the final state q2.

2. Transitions, with x ∈ {a, b} and Y ∈ {a, b, Z0}:

δ(q0, x, Y)  = {(q0, xY)}
δ(q0, c, Y)  = {(q1, Y)}
δ(q1, a, a)  = {(q1, ε)}
δ(q1, b, b)  = {(q1, ε)}
δ(q1, ε, Z0) = {(q2, Z0)}
DPDA for L = {w c w^R | w ∈ {a, b}*}Diagram in words: Circles q0 (start arrow), q1, and q2 (double circle, final). q0 has a self-loop with labels "a, Y / aY" and "b, Y / bY" for Y ∈ {a, b, Z0}. An arrow from q0 to q1 is labelled "c, Y / Y". q1 has a self-loop with labels "a, a / ε" and "b, b / ε". An arrow from q1 to q2 is labelled "ε, Z0 / Z0".q0 (start; Y:a, b or Z0)q1q2 (final)a, Y / aY;b, Y / bYc, Y / Ya, a / ε;b, b / εε, Z0 / Z0
DPDA for L = {w c w^R | w ∈ {a, b}*}

3. Trace on abcba:

(q0, abcba, Z0) ⊢ (q0, bcba, aZ0) ⊢ (q0, cba, baZ0) ⊢ (q1, ba, baZ0) ⊢ (q1, a, aZ0) ⊢ (q1, ε, Z0) ⊢ (q2, ε, Z0).

The machine ends in q2, so abcba is accepted.

4. Conditions for determinism: a PDA is deterministic if, for every q, a ∈ Σ and X ∈ Γ:

  • |δ(q, a, X)| ≤ 1 and |δ(q, ε, X)| ≤ 1, and
  • if δ(q, ε, X) is non-empty, then δ(q, a, X) is empty for every a.

The PDA above satisfies both conditions. The only ε-move is on Z0 in q1, and q1 has no input move on Z0.

5. Why {w w^R} needs nondeterminism: without the marker c, the middle of the input cannot be detected. We must replace the c-move with δ(q0, ε, Y) = {(q1, Y)}, which guesses that the middle has been reached. Now q0 has both an input move and an ε-move on the same top symbol, which breaks condition 2. Every branch is tried; the string is accepted if any guess leads to q2. It can be shown that no DPDA accepts {w w^R}, so the language is context-free but not deterministic context-free.

Conclusion: deterministic CFLs form a proper subset of CFLs. The centre marker c makes palindromes deterministic, while unmarked even palindromes require an NPDA.

5 State the equivalence of PDAs and CFGs. Explain the method of converting a CFG to a PDA, and convert the grammar S → aSa | bSb | c into a PDA. Show acceptance of abcba. 10 marks
Model answer

An important theorem of this unit says that a language is context-free if and only if some PDA accepts it. The proof has two parts:

  • For every CFG G there is a PDA P with N(P) = L(G).
  • For every PDA P there is a CFG G with L(G) = N(P).

This question covers the first direction.

1. Idea: the PDA simulates a leftmost derivation of G on its stack. The stack holds the part of the sentential form that has not yet been matched. When a variable is on top, the PDA guesses a production and expands it. When a terminal is on top, the PDA matches it against the input.

2. Construction: for G = (V, T, P, S), build PDA M = ({q}, T, V ∪ T, δ, q, S, ∅), accepting by empty stack.

  • Rule 1 (expand): for every variable A, δ(q, ε, A) = {(q, α) | A → α is a production}.
  • Rule 2 (match): for every terminal a, δ(q, a, a) = {(q, ε)}.

3. Applying the rules to S → aSa | bSb | c:

δ(q, ε, S) = {(q, aSa), (q, bSb), (q, c)}
δ(q, a, a) = {(q, ε)}
δ(q, b, b) = {(q, ε)}
δ(q, c, c) = {(q, ε)}

M = ({q}, {a, b, c}, {S, a, b, c}, δ, q, S, ∅), accepting by empty stack.

Single-state PDA for S → aSa | bSb | cDiagram in words: A single circle q with a start arrow. q has self-loops labelled "ε, S / aSa", "ε, S / bSb", "ε, S / c", "a, a / ε", "b, b / ε" and "c, c / ε".startqε, S / aSaε, S / bSbε, S / ca, a / εb, b / εc, c / ε
Single-state PDA for S → aSa | bSb | c

4. Acceptance of abcba:

(q, abcba, S) ⊢ (q, abcba, aSa) [expand S → aSa] ⊢ (q, bcba, Sa) [match a] ⊢ (q, bcba, bSba) [expand S → bSb] ⊢ (q, cba, Sba) [match b] ⊢ (q, cba, cba) [expand S → c] ⊢ (q, ba, ba) [match c] ⊢ (q, a, a) [match b] ⊢ (q, ε, ε) [match a]

The input is consumed and the stack is empty, so abcba ∈ N(M). The expansions follow the leftmost derivation S ⇒ aSa ⇒ abSba ⇒ abcba.

5. Correctness sketch: by induction on the number of moves, (q, w, S) ⊢* (q, ε, ε) holds exactly when S ⇒* w by a leftmost derivation. The matched input plus the stack contents always equals the current left sentential form.

Conclusion: any CFG can be converted mechanically into a single-state PDA that accepts by empty stack. The PDA is usually nondeterministic, because it must guess which production to apply.

6 Explain the construction of a CFG from a PDA that accepts by empty stack. Apply it to the PDA with δ(q0, a, Z) = {(q0, AZ)}, δ(q0, a, A) = {(q0, AA)}, δ(q0, b, A) = {(q1, ε)}, δ(q1, b, A) = {(q1, ε)}, δ(q1, ε, Z) = {(q1, ε)}, with start state q0 and start symbol Z, and simplify the grammar. 10 marks
Model answer

This is the second half of the PDA–CFG equivalence: for every PDA P there is a CFG G with L(G) = N(P). The variables of G are triples [p X q]. Variable [p X q] derives a string w exactly when P can read w, starting in state p with X on top, and end in state q with that X popped. The stack below X is never touched.

1. Construction rules:

  • R1: S → [q0 Z0 p] for every state p.
  • R2: if (r, ε) ∈ δ(q, a, X), add [q X r] → a. Here a may be ε.
  • R3: if (r, Y1...Yk) ∈ δ(q, a, X) with k ≥ 1, then for every choice of states r1, ..., rk add [q X rk] → a [r Y1 r1][r1 Y2 r2]...[r(k-1) Yk rk].

2. The given PDA: Q = {q0, q1}, Γ = {A, Z}. It pushes an A for each a, pops an A for each b, and finally pops Z, so N(P) = {a^n b^n | n ≥ 1}.

PDA accepting a^n b^n (n ≥ 1) by empty stackDiagram in words: Circle q0 has a start arrow and a self-loop labelled "a, Z / AZ" and "a, A / AA". An arrow from q0 to q1 is labelled "b, A / ε". q1 has self-loops labelled "b, A / ε" and "ε, Z / ε".startq0q1a, Z / AZ;a, A / AAb, A / εb, A / ε;ε, Z / ε
PDA accepting a^n b^n (n ≥ 1) by empty stack

3. Applying the rules:

  • R1: S → [q0 Z q0] | [q0 Z q1].
  • R3 on δ(q0, a, Z): for s, r ∈ {q0, q1}, [q0 Z r] → a [q0 A s][s Z r]. This gives four productions.
  • R3 on δ(q0, a, A): for s, r ∈ {q0, q1}, [q0 A r] → a [q0 A s][s A r]. This gives four productions.
  • R2: [q0 A q1] → b, [q1 A q1] → b and [q1 Z q1] → ε.

4. Simplification:

  • P never moves from q1 back to q0. So [q1 A q0] and [q1 Z q0] have no productions and are useless.
  • [q0 A q0] → a[q0 A q0][q0 A q0] | a[q0 A q1][q1 A q0]. Neither alternative can reach a terminal string, so [q0 A q0] is useless.
  • [q0 Z q0] → a[q0 A q0][q0 Z q0] | a[q0 A q1][q1 Z q0]. Both alternatives contain a useless variable, so [q0 Z q0] is useless.

The remaining productions are:

S → [q0 Z q1] [q0 Z q1] → a [q0 A q1][q1 Z q1] [q0 A q1] → a [q0 A q1][q1 A q1] | b [q1 A q1] → b [q1 Z q1] → ε

5. Renaming: let C = [q0 A q1], substitute [q1 A q1] = b and [q1 Z q1] = ε, and remove the unit production S → [q0 Z q1]. This gives:

S → aC C → aCb | b

C derives a^k b^(k+1) for k ≥ 0, so S derives a^(k+1) b^(k+1) = a^n b^n for n ≥ 1. Example: S ⇒ aC ⇒ aaCb ⇒ aabb.

Conclusion: the triple construction turns any empty-stack PDA into an equivalent CFG. Together with the CFG-to-PDA construction, it proves that PDAs accept exactly the context-free languages.

Unit 5

Turing Machines and Undecidability

Syllabus: Definition and model of a Turing machine; Instantaneous descriptions; Transition tables and transition diagrams; Language of a Turing machine; Design of Turing machines; Types of Turing machines; Church's thesis; Universal and restricted Turing machines; Decidable and undecidable problems; Halting problem of Turing machines; Post's correspondence problem and modified PCP; Classes P and NP; NP-hard and NP-complete problems

One-page revision summary

  • A Turing machine is a finite control with an infinite read/write tape. Each move changes state, writes a symbol and moves the head left or right.
  • An instantaneous description α1 q α2 records the tape contents, the state and the head position. ⊢ denotes one move and ⊢* denotes zero or more moves.
  • Transitions can be shown as a table with rows for states and columns for tape symbols, or as a diagram whose edges are labelled read/write,move.
  • The language of a TM is the set of inputs that lead it to a final state. Such languages are recursively enumerable, and they are recursive if the TM always halts.
  • TM design usually uses marking (replacing symbols by X or Y), storing information in the state, shuttling left and right, and multiple tracks.
  • Multi-tape, multi-track, two-way infinite, multi-head and nondeterministic TMs all accept exactly the recursively enumerable languages.
  • A single tape simulates k tapes in O(n^2) time, while a deterministic simulation of a nondeterministic TM may take exponential time.
  • Church's thesis states that every effectively computable function is Turing computable. It is a hypothesis supported by the equivalence of all known models.
  • A universal TM U takes an encoded pair <M, w> and simulates M on w. This is the idea of a stored-program computer.
  • The universal language Lu = {<M, w> | M accepts w} is recursively enumerable but not recursive.
  • Restricted machines remain fully powerful: a semi-infinite tape, two stacks, two counters, or a binary tape alphabet is enough to simulate any TM.
  • Decidable problems have TMs that always halt with the correct answer. Undecidable problems have no such TM.
  • The halting problem is undecidable, which is proved by diagonalisation, and its complement is not even recursively enumerable.
  • PCP and MPCP are undecidable, shown by reducing Lu to MPCP and then MPCP to PCP.
  • P ⊆ NP. The question P = NP is open, and an NP-complete problem lies in P only if P = NP.
  • SAT is NP-complete by the Cook–Levin theorem, and 3-SAT, CLIQUE, VERTEX COVER and HAMILTONIAN CYCLE are also NP-complete.

Learn these by heart

  • TM = (Q, Σ, Γ, δ, q0, B, F) with δ: Q × Γ → Q × Γ × {L, R}
  • L(M) = {w | q0w ⊢* α p β, p ∈ F}; recursive ⊂ recursively enumerable
  • If L and its complement are both recursively enumerable, then L is recursive
  • HALT = {<M, w> | M halts on w} is recursively enumerable but undecidable
  • PCP: find i1...im with wi1...wim = xi1...xim; MPCP additionally requires i1 = 1
  • A ≤p B and B ∈ P implies A ∈ P
  • X is NP-complete if and only if X ∈ NP and every L ∈ NP satisfies L ≤p X

2-mark questions

1 Define a Turing machine formally. 2 marks
Model answer

A Turing machine is a 7-tuple M = (Q, Σ, Γ, δ, q0, B, F). Q is a finite set of states, Σ the input alphabet, Γ the tape alphabet with Σ ⊂ Γ, and δ: Q × Γ → Q × Γ × {L, R} a partial transition function. q0 is the start state, B ∈ Γ − Σ the blank, and F ⊆ Q the final states. The machine has an infinite tape and a read/write head.

2 What is an instantaneous description (ID) of a Turing machine? Give an example. 2 marks
Model answer

An ID is a string α1 q α2. Here q is the current state, α1 is the tape contents to the left of the head, and α2 runs from the scanned cell to the last non-blank cell. The head reads the first symbol of α2. For example, XaqbY means the machine is in state q reading b. One move is written ID1 ⊢ ID2.

3 State Church's thesis and give its significance. 2 marks
Model answer

Church's (Church–Turing) thesis states that every function computable by an effective procedure, that is, an algorithm, can be computed by a Turing machine. It cannot be formally proved because 'effective procedure' is informal. It is accepted because lambda calculus, recursive functions and other proposed models proved equal in power to Turing machines. Hence the Turing machine serves as the formal definition of an algorithm.

4 Distinguish between recursively enumerable and recursive languages. 2 marks
Model answer

The language of a TM is L(M) = {w | q0w ⊢* α p β with p ∈ F}. A language is recursively enumerable if some TM accepts it; on strings outside the language that TM may loop forever. A language is recursive (decidable) if some TM accepts it and halts on every input. Every recursive language is recursively enumerable.

5 Define the classes P and NP. 2 marks
Model answer

P is the class of decision problems solvable by a deterministic Turing machine in polynomial time O(n^k) for some constant k. NP is the class solvable by a nondeterministic Turing machine in polynomial time. Equivalently, a proposed certificate for a yes-answer can be checked in polynomial time. Clearly P ⊆ NP.

6 Define NP-hard and NP-complete problems. 2 marks
Model answer

A problem X is NP-hard if every problem in NP reduces to X by a polynomial-time reduction; X itself need not belong to NP. X is NP-complete if X is in NP and X is NP-hard. SAT is NP-complete by the Cook–Levin theorem.

10-mark questions

1 Design a Turing machine that accepts L = {a^n b^n | n ≥ 1}. Give its transition table and transition diagram, and trace the instantaneous descriptions for the inputs aabb and abb. 10 marks
Model answer

A Turing machine can accept a^n b^n by repeatedly matching the leftmost unmarked a with the leftmost unmarked b. Each matched a is overwritten by X and each matched b by Y. The string is accepted when every a and every b has been matched.

Step 1 (Idea): Mark an a as X and move right past the remaining a's and Y's to the first b. Mark that b as Y and move back left to the nearest X. Then move one step right and repeat. When the head finds Y instead of a, check that only Y's remain before the blank.

Step 2 (Machine): M = (Q, Σ, Γ, δ, q0, B, F) with Q = {q0, q1, q2, q3, q4}, Σ = {a, b}, Γ = {a, b, X, Y, B} and F = {q4}.

Step 3 (Transition table; a missing entry means halt and reject):

  • q0: on a → (q1, X, R); on Y → (q3, Y, R)
  • q1: on a → (q1, a, R); on Y → (q1, Y, R); on b → (q2, Y, L)
  • q2: on a → (q2, a, L); on Y → (q2, Y, L); on X → (q0, X, R)
  • q3: on Y → (q3, Y, R); on B → (q4, B, R)
  • q4: accepting state, no moves
Turing machine transition diagram for a^n b^n (n ≥ 1)Diagram in words: Five circles q0, q1, q2, q3 and q4. q0 has an incoming start arrow, and q4 is drawn as a double circle. Arrow q0 → q1 labelled a/X,R. Self-loop on q1 labelled a/a,R and Y/Y,R. Arrow q1 → q2 labelled b/Y,L. Self-loop on q2 labelled a/a,L and Y/Y,L. Arrow q2 → q0 labelled X/X,R. Arrow q0 → q3 labelled Y/Y,R. Self-loop on q3 labelled Y/Y,R. Arrow q3 → q4 labelled B/B,R.startq0q1q2q3q4 (final)a/X,Ra/a,R; Y/Y,Rb/Y,La/a,L; Y/Y,LX/X,RY/Y,RY/Y,RB/B,R
Turing machine transition diagram for a^n b^n (n ≥ 1)

Step 4 (Trace for aabb): q0aabb ⊢ Xq1abb ⊢ Xaq1bb ⊢ Xq2aYb ⊢ q2XaYb ⊢ Xq0aYb ⊢ XXq1Yb ⊢ XXYq1b ⊢ XXq2YY ⊢ Xq2XYY ⊢ XXq0YY ⊢ XXYq3Y ⊢ XXYYq3B ⊢ XXYYBq4B

The machine reaches the final state q4, so aabb is accepted.

Step 5 (Trace for abb): q0abb ⊢ Xq1bb ⊢ q2XYb ⊢ Xq0Yb ⊢ XYq3b

δ(q3, b) is undefined, so the machine halts in a non-final state and abb is rejected. In the same way, aab is rejected: after both a's are marked, q1 reaches a blank without finding a b, and there is no move for that.

Conclusion: L(M) = {a^n b^n | n ≥ 1}. M halts on every input and takes O(n^2) moves, so the language is recursive.

2 Design a Turing machine that accepts all palindromes over {a, b}. Give its transition table and transition diagram, and trace the instantaneous descriptions for the inputs aba and ab. 10 marks
Model answer

A palindrome reads the same in both directions. The machine compares the first and last symbols of the remaining string, erases both if they match, and repeats. It accepts when nothing is left to compare.

Step 1 (Idea): In q0, read the leftmost symbol, remember it in the state (q1 for a, q3 for b) and replace it by B. Move right to the end of the string, step back one cell and check the last symbol. If it matches, erase it and return to the left end in q5. If a blank is found where a symbol was expected, the string was empty or had odd length, and the machine accepts.

Step 2 (Machine): Q = {q0, q1, q2, q3, q4, q5, qf}, Σ = {a, b}, Γ = {a, b, B}, F = {qf}.

Step 3 (Transition table; a missing entry means reject):

  • q0: a → (q1, B, R); b → (q3, B, R); B → (qf, B, R)
  • q1: a → (q1, a, R); b → (q1, b, R); B → (q2, B, L)
  • q2: a → (q5, B, L); B → (qf, B, R)
  • q3: a → (q3, a, R); b → (q3, b, R); B → (q4, B, L)
  • q4: b → (q5, B, L); B → (qf, B, R)
  • q5: a → (q5, a, L); b → (q5, b, L); B → (q0, B, R)
Turing machine accepting palindromes over {a, b}Diagram in words: Seven circles q0, q1, q2, q3, q4, q5 and qf. q0 is the start state and qf is a double circle. Arrows: q0 → q1 labelled a/B,R; q0 → q3 labelled b/B,R; q0 → qf labelled B/B,R. Self-loop on q1 labelled a/a,R and b/b,R. q1 → q2 labelled B/B,L. q2 → q5 labelled a/B,L; q2 → qf labelled B/B,R. Self-loop on q3 labelled a/a,R and b/b,R. q3 → q4 labelled B/B,L. q4 → q5 labelled b/B,L; q4 → qf labelled B/B,R. Self-loop on q5 labelled a/a,L and b/b,L. q5 → q0 labelled B/B,R.q0 (start)q1q2q3q4q5qf (accept)a/B,Rb/B,RB/B,Ra/a,R; b/b,RB/B,La/B,LB/B,Ra/a,R; b/b,RB/B,Lb/B,LB/B,Ra/a,L; b/b,LB/B,R
Turing machine accepting palindromes over {a, b}

Step 4 (Trace for aba): q0aba ⊢ Bq1ba ⊢ Bbq1a ⊢ Bbaq1B ⊢ Bbq2a ⊢ Bq5bB ⊢ q5BbB ⊢ Bq0bB ⊢ BBq3B ⊢ Bq4BB ⊢ BBqfB

The outer a's are matched and erased. Then the middle b is erased, and q4 finds a blank, so aba is accepted.

Step 5 (Trace for ab): q0ab ⊢ Bq1b ⊢ Bbq1B ⊢ Bq2b

The machine remembered a but the last symbol is b. δ(q2, b) is undefined, so it halts without accepting and ab is rejected.

Conclusion: The machine accepts exactly the palindromes over {a, b}, including the empty string. It halts on every input and takes O(n^2) moves.

3 Explain the different types of Turing machines (extensions and restrictions) and show that they are equivalent in power to the basic Turing machine. 10 marks
Model answer

The basic Turing machine has one semi-infinite or infinite tape, one head and a deterministic transition function. Many variants have been proposed. Some add features and some remove them, yet all of them accept exactly the recursively enumerable languages. This robustness supports Church's thesis.

Step 1 (Multi-track TM): The tape is divided into k tracks, and the head reads one k-tuple at a time. It is simulated by a standard TM whose tape alphabet is Γ^k, so each tuple becomes a single symbol.

Step 2 (Two-way infinite tape): The tape extends in both directions. A one-way tape with two tracks simulates it. The upper track holds the right half, the lower track holds the left half in reverse order, and a marker shows which track is active.

Step 3 (Multi-tape TM): There are k tapes, each with its own head. One move depends on all k scanned symbols. A single-tape TM simulates it using 2k tracks: k tracks hold the tape contents and k tracks hold a marker for each head position. For each simulated move, the machine sweeps across the tape to collect the scanned symbols and sweeps again to update them. If the multi-tape machine runs for n steps, the simulation takes O(n^2) steps.

Multi-tape Turing machineDiagram in words: One box labelled Finite Control. Three arrows go downward from it to three separate horizontal tapes, Tape 1, Tape 2 and Tape 3. Each arrow ends at a small head marker on its tape and is labelled read/write.Finite ControlTape 1Tape 2Tape 3read/writeread/writeread/write
Multi-tape Turing machine

Step 4 (Nondeterministic TM): δ gives a set of possible moves. A deterministic TM simulates it by exploring the tree of computations breadth-first, keeping a queue of IDs. It accepts if any branch reaches a final state. The simulation can be exponentially slower, but the class of languages accepted is unchanged.

Step 5 (Multi-head and multi-dimensional TMs): These allow several heads on one tape, or a 2-D grid. Both are simulated by marking head positions on extra tracks, or by laying the grid out row by row.

Step 6 (Restricted TMs):

  • A TM with a semi-infinite tape that never moves left of its start cell is as powerful as the general one.
  • Multi-stack machine: a deterministic PDA with two stacks can simulate a TM. One stack holds the tape to the left of the head and the other holds the tape from the head rightwards.
  • Counter machine: a counter holds a non-negative integer and can only be incremented, decremented or tested for zero. The argument has two stages. First, each stack is coded as a number in base r, where r is one more than the number of stack symbols, with the top symbol as the lowest digit. A push multiplies the number by r and adds the symbol's code; a pop divides it by r, and the remainder gives the popped symbol. A counter cannot multiply by itself, so a third counter acts as scratch space: decrement the stack counter once, add r to the scratch counter, repeat until zero, then copy back. Thus two stacks need three counters. Second, three counters holding i, j, k are packed into one counter as 2^i 3^j 5^k, with a second counter as scratch. Adding 1 to i means multiplying by 2, subtracting 1 means dividing by 2, and testing i = 0 means checking that the number is not divisible by 2; each is done by shifting the value into the scratch counter step by step while the finite control tracks remainders. So two counters are enough.
  • A TM with a binary tape alphabet, or with only a few states, still has full power.

Conclusion: Extended machines such as multi-tape and nondeterministic TMs, and restricted machines such as two-stack and two-counter machines, all accept exactly the recursively enumerable languages. Only the running time changes.

4 Explain the classes P and NP, NP-hard and NP-complete problems, polynomial-time reductions, and the method of proving a problem NP-complete, with examples. 10 marks
Model answer

Complexity theory classifies decidable problems by the resources they need. Running time is measured on Turing machines as a function of the input length n.

Step 1 (Class P): A decision problem is in P if a deterministic TM solves it in O(n^k) time for some constant k. Examples are checking whether a graph is connected, finding a shortest path, and testing whether a string belongs to a context-free language using the CYK algorithm.

Step 2 (Class NP): A problem is in NP if a nondeterministic TM solves it in polynomial time. Equivalently, there is a certificate of polynomial length that a deterministic TM can check in polynomial time. For example, for Hamiltonian cycle the certificate is an ordering of the vertices. Checking that each consecutive pair is joined by an edge and that every vertex appears once takes O(n^2) time. Since a deterministic machine is a special nondeterministic one, P ⊆ NP. Whether P = NP is an open problem.

Step 3 (Polynomial-time reduction): A ≤p B means there is a function f, computable in polynomial time, such that w ∈ A if and only if f(w) ∈ B. If B is in P and A ≤p B, then A is also in P.

Step 4 (NP-hard): A problem X is NP-hard if every problem in NP satisfies L ≤p X. X need not be in NP. The halting problem is NP-hard but undecidable, so it is not in NP.

Step 5 (NP-complete): X is NP-complete if X ∈ NP and X is NP-hard. The Cook–Levin theorem states that SAT, satisfiability of Boolean formulas, is NP-complete. Other NP-complete problems include 3-SAT, CLIQUE, VERTEX COVER, HAMILTONIAN CYCLE and the decision version of TSP.

Step 6 (Method to prove X NP-complete):

  • Show X ∈ NP by giving a certificate that can be verified in polynomial time.
  • Choose a known NP-complete problem Y and build a polynomial-time reduction Y ≤p X.
  • Prove that y is a yes-instance of Y exactly when f(y) is a yes-instance of X.

For example, 3-SAT ≤p CLIQUE: make one vertex for each literal occurrence, and join two vertices when they lie in different clauses and are not complementary. The formula with k clauses is satisfiable if and only if the graph has a clique of size k.

P, NP, NP-hard and NP-complete (assuming P ≠ NP)A Venn diagram of NP and NP-hard, drawn assuming P ≠ NP. The class P lies inside NP, in the part outside NP-hard. NP-hard overlaps NP and extends beyond it, and the overlap of NP and NP-hard is NP-complete.Universe: Decision problemsNPContains PNP-hardExtends beyond NPP lies inthis partNP-complete
P, NP, NP-hard and NP-complete (assuming P ≠ NP)

Conclusion: If any single NP-complete problem has a polynomial-time algorithm, then P = NP. This is why NP-completeness is taken as strong evidence that a problem is intractable.

5 What is the halting problem of Turing machines? Prove that it is undecidable, and explain decidable and undecidable problems along with the role of the universal Turing machine. 10 marks
Model answer

A problem is decidable if some Turing machine halts on every input and gives the correct yes or no answer, so its language is recursive. If no such machine exists, the problem is undecidable. The halting problem is the standard example of an undecidable problem.

Step 1 (Examples of decidable problems): Whether a DFA accepts a string w, whether a CFG generates w, and whether a regular language is empty.

Step 2 (Statement): HALT = {<M, w> | M is a TM that halts on input w}. The question is whether some algorithm can decide HALT for every pair <M, w>.

Step 3 (HALT is recursively enumerable): A universal Turing machine U takes the encoding <M, w>. It keeps the encoding of M on one tape, the simulated tape of M on another, and M's current state on a third. It simulates M step by step and accepts if the simulation halts. So HALT is accepted by U, although U may run forever on pairs that are not in HALT.

Step 4 (Proof of undecidability by contradiction):

  • Assume a TM H decides HALT. H always halts, outputting 'yes' if M halts on w and 'no' otherwise.
  • Construct a machine D that takes <M> as input and runs H on <M, <M>>.
  • If H says 'yes', D enters an infinite loop. If H says 'no', D halts.
  • Now run D on its own code <D>. If D halts on <D>, then H answered 'no', which means D does not halt on <D>. If D does not halt on <D>, then H answered 'yes', which means D halts on <D>.
  • Both cases are contradictions, so H cannot exist.
Machine D built from the halting decider HDiagram in words: Machine D, drawn as a box, takes the input code of M and passes the pair of M and its own code to H. H answers yes (halts) to a box loop forever and no (does not halt) to a box halt. The code of D is then fed to D as its input.DInput ⟨M⟩Hloop foreverhalt⟨D⟩, thecode of D⟨M, ⟨M⟩⟩yes (halts)no (doesnot halt)⟨D⟩ is fedto D as input
Machine D built from the halting decider H

Step 5 (Consequences):

  • HALT is recursively enumerable but not recursive.
  • Its complement is not recursively enumerable. If both a language and its complement were RE, the language would be recursive.
  • Reductions from HALT, or from the universal language Lu, show that further problems are undecidable. Examples are whether L(M) is empty, Rice's theorem for non-trivial properties, and Post's correspondence problem.

Conclusion: No algorithm can predict, for every program and input, whether the program will halt. This marks a basic limit on computation.

6 Define Post's Correspondence Problem (PCP) and the Modified PCP (MPCP). Illustrate with examples, and outline why PCP is undecidable. 10 marks
Model answer

Post's Correspondence Problem is a simple string-matching puzzle that turns out to be undecidable. It is often used to prove other problems undecidable, for example ambiguity of context-free grammars.

Step 1 (PCP definition): An instance consists of two lists of non-empty strings over an alphabet Σ, A = (w1, w2, ..., wk) and B = (x1, x2, ..., xk). A solution is a non-empty sequence of indices i1, i2, ..., im with each ij in {1, ..., k} such that wi1 wi2 ... wim = xi1 xi2 ... xim. The problem asks whether a given instance has a solution.

Step 2 (MPCP definition): The modified problem is the same, except that the solution must begin with index 1. That is, w1 wi2 ... wim = x1 xi2 ... xim.

Step 3 (Example with a solution): Let A = (aa, b, ba) and B = (a, ab, b). Try the sequence 1, 2. A side: w1 w2 = aa · b = aab B side: x1 x2 = a · ab = aab Both sides equal aab, so 1, 2 is a solution. It starts with index 1, so it is also an MPCP solution.

Step 4 (Example with no solution): Let A = (aab, ba) and B = (aa, b). Every |wi| is exactly one more than |xi|. For any sequence of m indices the A-string is m symbols longer than the B-string, so the two can never be equal. There is no solution.

Step 5 (Outline of undecidability):

  • First show Lu ≤ MPCP. Given <M, w>, build list pairs whose partial matches spell out the sequence of IDs of M on w, separated by #. The first pair is (#, #q0w#). Further pairs copy tape symbols, simulate each move of δ, and let the shorter A-string catch up once a final state appears. A solution exists if and only if M accepts w.
  • Then show MPCP ≤ PCP. Put a new symbol * after every symbol of each wi to get yi, and before every symbol of each xi to get zi. Add pair 0 as (*y1, z1) and a final pair ($, *$). Any PCP solution of the new instance must begin with pair 0, which forces the original pair 1 first.
  • Since Lu is undecidable, MPCP and then PCP are undecidable.
Reduction chain proving PCP undecidableDiagram in words: Three boxes in a row, labelled Lu, MPCP and PCP. An arrow from Lu to MPCP is labelled 'reduction 1', and an arrow from MPCP to PCP is labelled 'reduction 2'. Undecidability passes along the arrows from left to right.LuMPCPPCPreduction 1reduction 2
Reduction chain proving PCP undecidable

Conclusion: PCP is recursively enumerable, because we can search through sequences in order of length, but it is not decidable. MPCP is undecidable as well.

Public sources that settled doubtful points

Only the points the second AI pass doubted were looked up. These are the pages that confirmed or contradicted them; nothing here is copied from them.

8 pages

Further reading

Titles only, for your own study. Nothing on this page is copied from them. The units follow the official JNTUK R23 CSE syllabus (PDF) ↗.

  • Introduction to Automata Theory, Languages and Computation · J. E. Hopcroft, R. Motwani and J. D. Ullman
  • Theory of Computer Science: Automata, Languages and Computation · K. L. P. Mishra and N. Chandrasekaran
  • Elements of the Theory of Computation · H. R. Lewis and C. H. Papadimitriou
  • Theory of Computation · Vivek Kulkarni
  • Theory of Automata, Languages and Computation · Rajendra Kumar