Theory of Computation (CS-501) Unit 3 Notes

How unit 3 is examined

Grammar types, CFG design and proofs, derivation trees, ambiguity, simplification and the CNF and GNF conversions; CFG, ambiguity, derivation trees and CNF carry the marks.

Types of grammar

<span style="display:inline-block;padding:.16em .6em;border:1.5px solid currentColor;border-radius:999px;font-size:.68em;font-weight:700;letter-spacing:.06em;text-transform:uppercase;opacity:.75">Not asked since 2022</span>

Definition. A grammar is $G=(V,T,P,S)$: variables, terminals, productions $\alpha\to\beta$ and a start symbol; it generates the language $L(G)=\{w\in T^*\mid S\Rightarrow^* w\}$.

Key points.

Chomsky classified grammars by the shape of productions into Type 0 (unrestricted), Type 1 (context sensitive), Type 2 (context free) and Type 3 (regular).
Each type is a proper subset of the one before, so $3\subset2\subset1\subset0$.

<mark>A grammar is a four-tuple (V, T, P, S) and its language is every terminal string derivable from S.</mark>

Context sensitive grammar

Definition. A context sensitive grammar (Type 1) has productions $\alpha A\beta\to\alpha\gamma\beta$ with $\gamma\neq\varepsilon$, so $|\text{left}|\le|\text{right}|$ and no production shrinks the string.

Key points.

$A\to\gamma$ applies only in the context $\alpha\_\beta$, hence the name.
It is accepted by a linear bounded automaton, a Turing machine limited to the input's length.
$S\to\varepsilon$ is allowed only if $S$ never appears on a right side.
Example: $a^nb^nc^n$ uses $S\to aSBC\mid aBC$, $CB\to BC$, $aB\to ab$, $bB\to bb$, $bC\to bc$, $cC\to cc$.

<mark>Context sensitive productions never decrease length, and LBAs accept exactly these languages.</mark>

Context free grammar

Definition. A CFG is $G=(V,T,P,S)$ where every production has the form $A\to\alpha$, one variable on the left and $\alpha\in(V\cup T)^*$ on the right.

Key points.

$V$ is the finite set of variables, $T$ the terminals, $P$ the productions and $S\in V$ the start symbol.
Example $S\to aSb\mid\varepsilon$ generates $\{a^nb^n\mid n\ge0\}$, e.g. $S\Rightarrow aSb\Rightarrow aaSbb\Rightarrow aabb$.
Design by matching: a recursion $S\to aSb$ pairs two counts, and independent parts get their own variable.
For a union of languages add $S\to S_1\mid S_2$; for a concatenation add $S\to S_1S_2$.
Context-free languages are closed under union, concatenation and star but not intersection.

Design answers (verified by listing strings).

$a^nb^mc^n$, $m,n\ge1$: $S\to aSc\mid aBc$, $B\to bB\mid b$. Integer: $S\to GN\mid N$, $G\to +\mid -$, $N\to DN\mid D$, $D\to0\mid1\mid\dots\mid9$.
$(011+1)^*(01)^*$: $S\to AB$, $A\to 011A\mid1A\mid\varepsilon$, $B\to01B\mid\varepsilon$.
$a^{n+2}b^{n+1}$ ($n=m$): $S\to aaAb$, $A\to aAb\mid\varepsilon$.
At least two a's: $V=\{S,X\}$, $T=\{a,b\}$, $S\to XaXaX$, $X\to aX\mid bX\mid\varepsilon$. No $bbb$: $S\to aS\mid bA\mid\varepsilon$, $A\to aS\mid bB\mid\varepsilon$, $B\to aS\mid\varepsilon$ ($S,A,B$ = 0,1,2 b's just read).
$a^ib^jc^k$, $i\ne j$ or $j\ne k$: $S\to S_1C\mid AS_2$, $S_1\to aS_1b\mid aP\mid bQ$, $P\to aP\mid\varepsilon$, $Q\to bQ\mid\varepsilon$, $C\to cC\mid\varepsilon$, $A\to aA\mid\varepsilon$, $S_2\to bS_2c\mid bR\mid cT$, $R\to bR\mid\varepsilon$, $T\to cT\mid\varepsilon$. And $a^ib^{2i}$: $S\to aSbb\mid\varepsilon$.

Union closure. Let $G_1,G_2$ generate $A,B$ with start symbols $S_1,S_2$ (variables renamed apart). Add a new start $S\to S_1\mid S_2$. Any derivation from $S$ first picks $S_1$ or $S_2$ and then stays in that grammar, so $L(G)=A\cup B$, which is context free.

Pumping lemma. If $L$ is a CFL there is $p$ such that every $z\in L$ with $|z|\ge p$ splits as $uvwxy$ with $|vwx|\le p$, $|vx|\ge1$ and $uv^iwx^iy\in L$ for all $i\ge0$.

$a^nb^nc^n$ is not CFL: take $z=a^pb^pc^p$. Since $|vwx|\le p$, $vwx$ misses at least one of $a,b,c$, so pumping to $i=2$ raises at most two counts and the third stays $p$; counts differ, $uv^2wx^2y\notin L$, a contradiction.
$a^ib^{2i}a^i$ is not CFL: take $z=a^pb^{2p}a^p$. As $|vwx|\le p<2p$, $vwx$ cannot touch both $a$-blocks; pumping with $i=2$ then breaks first $a$ count $=$ last $a$ count or $b$ count $=2\times a$ count. Contradiction.

<mark>A context-free grammar has productions $A\to\alpha$ with a single variable on the left.</mark>

Answer frame. Open with the 4-tuple definition; for a design question write the language in the form $a^nb^n$ core plus fixed parts, then productions, then one derivation of a short string; for a proof write assume CFL, choose $z$, split $uvwxy$, pump, contradiction.

Pitfall: In $a^nb^mc^n$ the $b$ count is independent, so it needs its own variable $B$, not the $S\to aSb$ pairing.

Asked: [14 marks] (Nov 2023) Construct CFG for (i) $a^nb^mc^n$, $m,n\ge1$ (ii) a integer Asked: [8 marks] (Dec 2024) Show that $L=\{a^nb^nc^n\mid n\ge1\}$ is not a context-free language Asked: [7 marks] (Nov 2019) Prove that the union of two context free languages is context free Asked: [7 marks] (Dec 2020, Jun 2020) Give CFG for R.E. $(011+1)^*(01)^*$ Asked: [7 marks] (Nov 2022) Construct CFG for $L=\{a^{n+2}b^{m+1}\mid n=m\}$ Asked: [7 marks] (Nov 2022) Show that $L=\{a^ib^{2i}a^i\mid i\ge0\}$ is not context free Asked: [7 marks] (Nov 2023) Define CFG in 4-tuple form for (i) at least two a's (ii) no triple b's Asked: [7 marks] (May 2023) Design a CFG for (i) $a^ib^jc^k$, $i\ne j$ or $j\ne k$ (ii) $a^ib^{2i}$ Asked: [7 marks] (May 2023) Define a context free grammar with example Asked: [7 marks] (Dec 2025) Explain context free grammar and derivation trees

Regular grammar

Definition. A regular grammar is right-linear (every production $A\to xB$ or $A\to x$, $x\in T^*$) or left-linear ($A\to Bx$ or $A\to x$); it generates exactly the regular languages.

Key points.

Regular expressions, finite automata and regular grammars are equivalent in power.
To build a grammar from a regular expression, give each sub-expression a variable and use one rule per operator.
For $\emptyset$ add no production, for $\varepsilon$ add $S\to\varepsilon$, and for a symbol $a$ add $S\to a$.
Union $r_1+r_2$: $S\to S_1\mid S_2$.
Concatenation $r_1r_2$: in $G_1$ replace each terminating $A\to x$ by $A\to xS_2$.
Star $r_1^*$: $S\to S_1\mid\varepsilon$ and each terminating $A\to x$ becomes $A\to xS$.
Example $a(a+b)^*$: $S\to aA$, $A\to aA\mid bA\mid\varepsilon$; each rule mirrors one operator, so the grammar generates exactly $L(r)$.

Identify the language. $B\to b^n$ ($n\ge1$), so $A\to a\mid b^n$ and $S\to Aa$ gives $aa$ or $b^na$: $L=\{aa\}\cup\{b^na\mid n\ge1\}$.

Exactly one $a$, at most two $b$'s. Strings: $a,ab,abb,ba,bab,bba$. $S\to aQ\mid bP$, $P\to aR\mid bU$, $U\to a$, $Q\to bR\mid\varepsilon$, $R\to b\mid\varepsilon$ ($P,U$ = one, two $b$'s before the $a$; $Q,R$ = zero, one after).

<mark>A regular grammar has only right-linear (or only left-linear) productions and equals a regular expression in power.</mark>

Answer frame. For RE to grammar: open with the equivalence, state the rules for union, concatenation and star, work $a(a+b)^*$, close with correctness. For design: list the strings, name a variable per stage, write productions, check two strings.

Asked: [7 marks] (Dec 2020, Jun 2020) How can we construct regular grammar from regular expression? Explain Asked: [7 marks] (Nov 2022) Identify the language generated by $G=(\{S,A,B\},\{a,b\},\{S\to Aa,A\to a\mid B,B\to bB\mid b\},S)$ Asked: [7 marks] (Nov 2022) Find a regular grammar for strings on $\{a,b\}$ with exactly one $a$ and no more than two $b$'s

Derivation trees

Definition. A derivation (parse) tree has root $S$, an interior node for each variable expanded by a production, its children the right side in order, and leaves (left to right) forming the derived string, the yield.

Key points.

A leftmost derivation always expands the leftmost variable, and a rightmost derivation the rightmost variable.
Every string of a CFG has a parse tree, and a leftmost and a rightmost derivation for each tree.
Different derivation orders of one tree give the same tree, so only different trees show ambiguity.

Example. $S\to aSb\mid ab$ for $aabb$: $S\Rightarrow aSb\Rightarrow aabb$ (leftmost and rightmost coincide).

<figure class="ds-fig" style="margin:1.4rem 0;overflow-x:auto"><svg xmlns="http://www.w3.org/2000/svg" id="dsfig-u3-01" viewBox="0 0 236 198" width="236" height="198" role="img" aria-label="Parse tree of aabb, S to aSb then S to ab"><style>#dsfig-u3-01 .e{stroke:#454C5A;stroke-width:1.4;fill:none}#dsfig-u3-01 .e.hi{stroke:#2340B8;stroke-width:2.6}#dsfig-u3-01 .n{fill:#FFFFFF;stroke:#16181D;stroke-width:1.4}#dsfig-u3-01 .n.hi{fill:#E3E9FC;stroke:#2340B8;stroke-width:2.2}#dsfig-u3-01 .n.rb-b{fill:#16181D;stroke:#16181D}#dsfig-u3-01 .n.rb-r{fill:#BD3227;stroke:#BD3227}#dsfig-u3-01 text{font-family:"JetBrains Mono",ui-monospace,Menlo,Consolas,monospace;font-size:13px}#dsfig-u3-01 .t{fill:#16181D;font-weight:500}#dsfig-u3-01 .t.inv{fill:#FFFFFF;font-weight:700}#dsfig-u3-01 .kd{stroke:#16181D;stroke-width:1.2}#dsfig-u3-01 .dot{fill:#16181D}#dsfig-u3-01 .ann{fill:#2340B8;font-size:11px;font-weight:700}#dsfig-u3-01 .lbl{fill:#6F7787;font-family:system-ui,-apple-system,sans-serif;font-size:12px;font-weight:700}#dsfig-u3-01 .ptr{fill:#2340B8;font-size:12px;font-weight:700}#dsfig-u3-01 .ah{fill:#454C5A}#dsfig-u3-01 .ah.hi{fill:#2340B8}#dsfig-u3-01 .wl rect{fill:#FFFFFF;stroke:#DCE0E7}#dsfig-u3-01 .wl .t{font-size:12px;font-weight:700}#dsfig-u3-01 .wl.hi rect{fill:#2340B8;stroke:#2340B8}#dsfig-u3-01 .wl.hi .t{fill:#FFFFFF}html.dark #dsfig-u3-01 .e{stroke:#B1B7C3}html.dark #dsfig-u3-01 .e.hi{stroke:#8FA3FF}html.dark #dsfig-u3-01 .n{fill:#161920;stroke:#E6E8ED}html.dark #dsfig-u3-01 .n.hi{fill:#1E2748;stroke:#8FA3FF}html.dark #dsfig-u3-01 .n.rb-b{fill:#E6E8ED;stroke:#E6E8ED}html.dark #dsfig-u3-01 .n.rb-r{fill:#FF7E71;stroke:#FF7E71}html.dark #dsfig-u3-01 .t{fill:#E6E8ED}html.dark #dsfig-u3-01 .t.inv{fill:#0F1115}html.dark #dsfig-u3-01 .kd{stroke:#E6E8ED}html.dark #dsfig-u3-01 .dot{fill:#E6E8ED}html.dark #dsfig-u3-01 .ann{fill:#8FA3FF}html.dark #dsfig-u3-01 .lbl{fill:#858D9C}html.dark #dsfig-u3-01 .ptr{fill:#8FA3FF}html.dark #dsfig-u3-01 .ah{fill:#B1B7C3}html.dark #dsfig-u3-01 .ah.hi{fill:#8FA3FF}html.dark #dsfig-u3-01 .wl rect{fill:#161920;stroke:#2A2E37}html.dark #dsfig-u3-01 .wl.hi rect{fill:#8FA3FF;stroke:#8FA3FF}html.dark #dsfig-u3-01 .wl.hi .t{fill:#0F1115}</style><defs><marker id="ah7" viewBox="0 0 10 10" refX="9" refY="5" markerWidth="7" markerHeight="7" orient="auto-start-reverse"><path class="ah" d="M0,1 L9,5 L0,9 z"/></marker><marker id="ahh7" viewBox="0 0 10 10" refX="9" refY="5" markerWidth="7" markerHeight="7" orient="auto-start-reverse"><path class="ah hi" d="M0,1 L9,5 L0,9 z"/></marker></defs><line class="e" x1="106" y1="39" x2="31" y2="103"/><line class="e" x1="106" y1="39" x2="106" y2="103"/><line class="e" x1="106" y1="39" x2="181" y2="103"/><line class="e" x1="106" y1="103" x2="81" y2="167"/><line class="e" x1="106" y1="103" x2="131" y2="167"/><circle class="n" cx="106" cy="39" r="17"/><text class="t" x="106" y="39" dy=".35em" text-anchor="middle">S</text><circle class="n" cx="31" cy="103" r="17"/><text class="t" x="31" y="103" dy=".35em" text-anchor="middle">a</text><circle class="n" cx="106" cy="103" r="17"/><text class="t" x="106" y="103" dy=".35em" text-anchor="middle">S</text><circle class="n" cx="81" cy="167" r="17"/><text class="t" x="81" y="167" dy=".35em" text-anchor="middle">a</text><circle class="n" cx="131" cy="167" r="17"/><text class="t" x="131" y="167" dy=".35em" text-anchor="middle">b</text><circle class="n" cx="181" cy="103" r="17"/><text class="t" x="181" y="103" dy=".35em" text-anchor="middle">b</text></svg><figcaption style="font-size:.82em;opacity:.72;margin-top:.45rem">Parse tree of aabb, S to aSb then S to ab</figcaption></figure>

List grammar $S\to a\mid\wedge\mid(T)$, $T\to T,S\mid S$. As printed, $(((a,a),\wedge(a)),a)$ is not derivable, since $\wedge(a)$ needs a comma; the intended string is $(((a,a),\wedge,(a)),a)$.

Leftmost:
S=>(T)=>(T,S)=>(S,S)=>((T),S)=>((T,S),S)=>((T,S,S),S)=>((S,S,S),S)
=>(((T),S,S),S)=>(((T,S),S,S),S)=>(((S,S),S,S),S)=>(((a,S),S,S),S)
=>(((a,a),S,S),S)=>(((a,a),^,S),S)=>(((a,a),^,(T)),S)=>(((a,a),^,(S)),S)
=>(((a,a),^,(a)),S)=>(((a,a),^,(a)),a)   [^ stands for the wedge]
Rightmost:
S=>(T)=>(T,S)=>(T,a)=>(S,a)=>((T),a)=>((T,S),a)=>((T,(T)),a)=>((T,(S)),a)
=>((T,(a)),a)=>((T,S,(a)),a)=>((T,^,(a)),a)=>((S,^,(a)),a)=>(((T),^,(a)),a)
=>(((T,S),^,(a)),a)=>(((T,a),^,(a)),a)=>(((S,a),^,(a)),a)=>(((a,a),^,(a)),a)

<figure class="ds-fig" style="margin:1.4rem 0;overflow-x:auto"><svg xmlns="http://www.w3.org/2000/svg" id="dsfig-u3-02" viewBox="0 0 886 774" width="886" height="774" role="img" aria-label="Parse tree of (((a,a),^,(a)),a); ^ is the wedge"><style>#dsfig-u3-02 .e{stroke:#454C5A;stroke-width:1.4;fill:none}#dsfig-u3-02 .e.hi{stroke:#2340B8;stroke-width:2.6}#dsfig-u3-02 .n{fill:#FFFFFF;stroke:#16181D;stroke-width:1.4}#dsfig-u3-02 .n.hi{fill:#E3E9FC;stroke:#2340B8;stroke-width:2.2}#dsfig-u3-02 .n.rb-b{fill:#16181D;stroke:#16181D}#dsfig-u3-02 .n.rb-r{fill:#BD3227;stroke:#BD3227}#dsfig-u3-02 text{font-family:"JetBrains Mono",ui-monospace,Menlo,Consolas,monospace;font-size:13px}#dsfig-u3-02 .t{fill:#16181D;font-weight:500}#dsfig-u3-02 .t.inv{fill:#FFFFFF;font-weight:700}#dsfig-u3-02 .kd{stroke:#16181D;stroke-width:1.2}#dsfig-u3-02 .dot{fill:#16181D}#dsfig-u3-02 .ann{fill:#2340B8;font-size:11px;font-weight:700}#dsfig-u3-02 .lbl{fill:#6F7787;font-family:system-ui,-apple-system,sans-serif;font-size:12px;font-weight:700}#dsfig-u3-02 .ptr{fill:#2340B8;font-size:12px;font-weight:700}#dsfig-u3-02 .ah{fill:#454C5A}#dsfig-u3-02 .ah.hi{fill:#2340B8}#dsfig-u3-02 .wl rect{fill:#FFFFFF;stroke:#DCE0E7}#dsfig-u3-02 .wl .t{font-size:12px;font-weight:700}#dsfig-u3-02 .wl.hi rect{fill:#2340B8;stroke:#2340B8}#dsfig-u3-02 .wl.hi .t{fill:#FFFFFF}html.dark #dsfig-u3-02 .e{stroke:#B1B7C3}html.dark #dsfig-u3-02 .e.hi{stroke:#8FA3FF}html.dark #dsfig-u3-02 .n{fill:#161920;stroke:#E6E8ED}html.dark #dsfig-u3-02 .n.hi{fill:#1E2748;stroke:#8FA3FF}html.dark #dsfig-u3-02 .n.rb-b{fill:#E6E8ED;stroke:#E6E8ED}html.dark #dsfig-u3-02 .n.rb-r{fill:#FF7E71;stroke:#FF7E71}html.dark #dsfig-u3-02 .t{fill:#E6E8ED}html.dark #dsfig-u3-02 .t.inv{fill:#0F1115}html.dark #dsfig-u3-02 .kd{stroke:#E6E8ED}html.dark #dsfig-u3-02 .dot{fill:#E6E8ED}html.dark #dsfig-u3-02 .ann{fill:#8FA3FF}html.dark #dsfig-u3-02 .lbl{fill:#858D9C}html.dark #dsfig-u3-02 .ptr{fill:#8FA3FF}html.dark #dsfig-u3-02 .ah{fill:#B1B7C3}html.dark #dsfig-u3-02 .ah.hi{fill:#8FA3FF}html.dark #dsfig-u3-02 .wl rect{fill:#161920;stroke:#2A2E37}html.dark #dsfig-u3-02 .wl.hi rect{fill:#8FA3FF;stroke:#8FA3FF}html.dark #dsfig-u3-02 .wl.hi .t{fill:#0F1115}</style><defs><marker id="ah8" viewBox="0 0 10 10" refX="9" refY="5" markerWidth="7" markerHeight="7" orient="auto-start-reverse"><path class="ah" d="M0,1 L9,5 L0,9 z"/></marker><marker id="ahh8" viewBox="0 0 10 10" refX="9" refY="5" markerWidth="7" markerHeight="7" orient="auto-start-reverse"><path class="ah hi" d="M0,1 L9,5 L0,9 z"/></marker></defs><line class="e" x1="431" y1="39" x2="31" y2="103"/><line class="e" x1="431" y1="39" x2="581" y2="103"/><line class="e" x1="431" y1="39" x2="831" y2="103"/><line class="e" x1="581" y1="103" x2="381" y2="167"/><line class="e" x1="581" y1="103" x2="731" y2="167"/><line class="e" x1="581" y1="103" x2="781" y2="167"/><line class="e" x1="381" y1="167" x2="381" y2="231"/><line class="e" x1="381" y1="231" x2="81" y2="295"/><line class="e" x1="381" y1="231" x2="456" y2="295"/><line class="e" x1="381" y1="231" x2="681" y2="295"/><line class="e" x1="456" y1="295" x2="331" y2="359"/><line class="e" x1="456" y1="295" x2="481" y2="359"/><line class="e" x1="456" y1="295" x2="581" y2="359"/><line class="e" x1="331" y1="359" x2="231" y2="423"/><line class="e" x1="331" y1="359" x2="381" y2="423"/><line class="e" x1="331" y1="359" x2="431" y2="423"/><line class="e" x1="231" y1="423" x2="231" y2="487"/><line class="e" x1="231" y1="487" x2="131" y2="551"/><line class="e" x1="231" y1="487" x2="231" y2="551"/><line class="e" x1="231" y1="487" x2="331" y2="551"/><line class="e" x1="231" y1="551" x2="181" y2="615"/><line class="e" x1="231" y1="551" x2="231" y2="615"/><line class="e" x1="231" y1="551" x2="281" y2="615"/><line class="e" x1="181" y1="615" x2="181" y2="679"/><line class="e" x1="181" y1="679" x2="181" y2="743"/><line class="e" x1="281" y1="615" x2="281" y2="679"/><line class="e" x1="431" y1="423" x2="431" y2="487"/><line class="e" x1="581" y1="359" x2="531" y2="423"/><line class="e" x1="581" y1="359" x2="581" y2="423"/><line class="e" x1="581" y1="359" x2="631" y2="423"/><line class="e" x1="581" y1="423" x2="581" y2="487"/><line class="e" x1="581" y1="487" x2="581" y2="551"/><line class="e" x1="781" y1="167" x2="781" y2="231"/><circle class="n" cx="431" cy="39" r="17"/><text class="t" x="431" y="39" dy=".35em" text-anchor="middle">S</text><circle class="n" cx="31" cy="103" r="17"/><text class="t" x="31" y="103" dy=".35em" text-anchor="middle">(</text><circle class="n" cx="581" cy="103" r="17"/><text class="t" x="581" y="103" dy=".35em" text-anchor="middle">T</text><circle class="n" cx="381" cy="167" r="17"/><text class="t" x="381" y="167" dy=".35em" text-anchor="middle">T</text><circle class="n" cx="381" cy="231" r="17"/><text class="t" x="381" y="231" dy=".35em" text-anchor="middle">S</text><circle class="n" cx="81" cy="295" r="17"/><text class="t" x="81" y="295" dy=".35em" text-anchor="middle">(</text><circle class="n" cx="456" cy="295" r="17"/><text class="t" x="456" y="295" dy=".35em" text-anchor="middle">T</text><circle class="n" cx="331" cy="359" r="17"/><text class="t" x="331" y="359" dy=".35em" text-anchor="middle">T</text><circle class="n" cx="231" cy="423" r="17"/><text class="t" x="231" y="423" dy=".35em" text-anchor="middle">T</text><circle class="n" cx="231" cy="487" r="17"/><text class="t" x="231" y="487" dy=".35em" text-anchor="middle">S</text><circle class="n" cx="131" cy="551" r="17"/><text class="t" x="131" y="551" dy=".35em" text-anchor="middle">(</text><circle class="n" cx="231" cy="551" r="17"/><text class="t" x="231" y="551" dy=".35em" text-anchor="middle">T</text><circle class="n" cx="181" cy="615" r="17"/><text class="t" x="181" y="615" dy=".35em" text-anchor="middle">T</text><circle class="n" cx="181" cy="679" r="17"/><text class="t" x="181" y="679" dy=".35em" text-anchor="middle">S</text><circle class="n" cx="181" cy="743" r="17"/><text class="t" x="181" y="743" dy=".35em" text-anchor="middle">a</text><circle class="n" cx="231" cy="615" r="17"/><text class="t" x="231" y="615" dy=".35em" text-anchor="middle">,</text><circle class="n" cx="281" cy="615" r="17"/><text class="t" x="281" y="615" dy=".35em" text-anchor="middle">S</text><circle class="n" cx="281" cy="679" r="17"/><text class="t" x="281" y="679" dy=".35em" text-anchor="middle">a</text><circle class="n" cx="331" cy="551" r="17"/><text class="t" x="331" y="551" dy=".35em" text-anchor="middle">)</text><circle class="n" cx="381" cy="423" r="17"/><text class="t" x="381" y="423" dy=".35em" text-anchor="middle">,</text><circle class="n" cx="431" cy="423" r="17"/><text class="t" x="431" y="423" dy=".35em" text-anchor="middle">S</text><circle class="n" cx="431" cy="487" r="17"/><text class="t" x="431" y="487" dy=".35em" text-anchor="middle">^</text><circle class="n" cx="481" cy="359" r="17"/><text class="t" x="481" y="359" dy=".35em" text-anchor="middle">,</text><circle class="n" cx="581" cy="359" r="17"/><text class="t" x="581" y="359" dy=".35em" text-anchor="middle">S</text><circle class="n" cx="531" cy="423" r="17"/><text class="t" x="531" y="423" dy=".35em" text-anchor="middle">(</text><circle class="n" cx="581" cy="423" r="17"/><text class="t" x="581" y="423" dy=".35em" text-anchor="middle">T</text><circle class="n" cx="581" cy="487" r="17"/><text class="t" x="581" y="487" dy=".35em" text-anchor="middle">S</text><circle class="n" cx="581" cy="551" r="17"/><text class="t" x="581" y="551" dy=".35em" text-anchor="middle">a</text><circle class="n" cx="631" cy="423" r="17"/><text class="t" x="631" y="423" dy=".35em" text-anchor="middle">)</text><circle class="n" cx="681" cy="295" r="17"/><text class="t" x="681" y="295" dy=".35em" text-anchor="middle">)</text><circle class="n" cx="731" cy="167" r="17"/><text class="t" x="731" y="167" dy=".35em" text-anchor="middle">,</text><circle class="n" cx="781" cy="167" r="17"/><text class="t" x="781" y="167" dy=".35em" text-anchor="middle">S</text><circle class="n" cx="781" cy="231" r="17"/><text class="t" x="781" y="231" dy=".35em" text-anchor="middle">a</text><circle class="n" cx="831" cy="103" r="17"/><text class="t" x="831" y="103" dy=".35em" text-anchor="middle">)</text></svg><figcaption style="font-size:.82em;opacity:.72;margin-top:.45rem">Parse tree of (((a,a),^,(a)),a); ^ is the wedge</figcaption></figure>

<mark>A leftmost derivation expands the leftmost variable at every step and a rightmost derivation the rightmost.</mark>

Answer frame. For leftmost/rightmost: define both, give $E\to E+E\mid id$ style grammar with a short string, write both derivations, draw the tree. For a given string: write productions used, the derivation line by line, then the tree with root $S$, closing with the yield.

Asked: [7 marks] (Dec 2024, Dec 2025) For the grammar $S\to aSb\mid ab$, derive "aabb" and draw its parse tree Asked: [7 marks] (Jun 2020) What are leftmost and rightmost derivations? Explain with suitable example Asked: [6 marks] (Dec 2024) For $S\to a/\wedge/(T)$, $T\to T,S/S$ find leftmost derivation, rightmost derivation and parse tree for $(((a,a),\wedge(a)),a)$

Ambiguity in grammar

Definition. A CFG is ambiguous if some string in $L(G)$ has two or more distinct parse trees, equivalently two distinct leftmost derivations.

Key points.

Ambiguity is a property of the grammar, not the language, since another grammar for the same language may be unambiguous.
To prove ambiguity, pick one string and show two different trees or two different leftmost derivations.
To show unambiguity you must argue every string has one tree; there is no general algorithm to decide it.
Ambiguity is harmful because the tree fixes the meaning: $id+id*id$ could mean $(id+id)*id$.
Remedy one: rewrite to force precedence, with higher-precedence operators at lower levels.
Remedy two: force associativity by recursing only on the side of the operator, e.g. left recursion for left-associative.
Remedy three: choose one rule (e.g. dangling else binds to the nearest if).
Some languages are inherently ambiguous: every grammar for them is ambiguous.

<figure class="ds-fig" style="margin:1.4rem 0;overflow-x:auto"><svg xmlns="http://www.w3.org/2000/svg" id="dsfig-u3-03" viewBox="0 0 286 262" width="286" height="262" role="img" aria-label="Tree 1 of id+idid: id + (id * id)"><style>#dsfig-u3-03 .e{stroke:#454C5A;stroke-width:1.4;fill:none}#dsfig-u3-03 .e.hi{stroke:#2340B8;stroke-width:2.6}#dsfig-u3-03 .n{fill:#FFFFFF;stroke:#16181D;stroke-width:1.4}#dsfig-u3-03 .n.hi{fill:#E3E9FC;stroke:#2340B8;stroke-width:2.2}#dsfig-u3-03 .n.rb-b{fill:#16181D;stroke:#16181D}#dsfig-u3-03 .n.rb-r{fill:#BD3227;stroke:#BD3227}#dsfig-u3-03 text{font-family:"JetBrains Mono",ui-monospace,Menlo,Consolas,monospace;font-size:13px}#dsfig-u3-03 .t{fill:#16181D;font-weight:500}#dsfig-u3-03 .t.inv{fill:#FFFFFF;font-weight:700}#dsfig-u3-03 .kd{stroke:#16181D;stroke-width:1.2}#dsfig-u3-03 .dot{fill:#16181D}#dsfig-u3-03 .ann{fill:#2340B8;font-size:11px;font-weight:700}#dsfig-u3-03 .lbl{fill:#6F7787;font-family:system-ui,-apple-system,sans-serif;font-size:12px;font-weight:700}#dsfig-u3-03 .ptr{fill:#2340B8;font-size:12px;font-weight:700}#dsfig-u3-03 .ah{fill:#454C5A}#dsfig-u3-03 .ah.hi{fill:#2340B8}#dsfig-u3-03 .wl rect{fill:#FFFFFF;stroke:#DCE0E7}#dsfig-u3-03 .wl .t{font-size:12px;font-weight:700}#dsfig-u3-03 .wl.hi rect{fill:#2340B8;stroke:#2340B8}#dsfig-u3-03 .wl.hi .t{fill:#FFFFFF}html.dark #dsfig-u3-03 .e{stroke:#B1B7C3}html.dark #dsfig-u3-03 .e.hi{stroke:#8FA3FF}html.dark #dsfig-u3-03 .n{fill:#161920;stroke:#E6E8ED}html.dark #dsfig-u3-03 .n.hi{fill:#1E2748;stroke:#8FA3FF}html.dark #dsfig-u3-03 .n.rb-b{fill:#E6E8ED;stroke:#E6E8ED}html.dark #dsfig-u3-03 .n.rb-r{fill:#FF7E71;stroke:#FF7E71}html.dark #dsfig-u3-03 .t{fill:#E6E8ED}html.dark #dsfig-u3-03 .t.inv{fill:#0F1115}html.dark #dsfig-u3-03 .kd{stroke:#E6E8ED}html.dark #dsfig-u3-03 .dot{fill:#E6E8ED}html.dark #dsfig-u3-03 .ann{fill:#8FA3FF}html.dark #dsfig-u3-03 .lbl{fill:#858D9C}html.dark #dsfig-u3-03 .ptr{fill:#8FA3FF}html.dark #dsfig-u3-03 .ah{fill:#B1B7C3}html.dark #dsfig-u3-03 .ah.hi{fill:#8FA3FF}html.dark #dsfig-u3-03 .wl rect{fill:#161920;stroke:#2A2E37}html.dark #dsfig-u3-03 .wl.hi rect{fill:#8FA3FF;stroke:#8FA3FF}html.dark #dsfig-u3-03 .wl.hi .t{fill:#0F1115}</style><defs><marker id="ah9" viewBox="0 0 10 10" refX="9" refY="5" markerWidth="7" markerHeight="7" orient="auto-start-reverse"><path class="ah" d="M0,1 L9,5 L0,9 z"/></marker><marker id="ahh9" viewBox="0 0 10 10" refX="9" refY="5" markerWidth="7" markerHeight="7" orient="auto-start-reverse"><path class="ah hi" d="M0,1 L9,5 L0,9 z"/></marker></defs><line class="e" x1="106" y1="39" x2="31" y2="103"/><line class="e" x1="106" y1="39" x2="81" y2="103"/><line class="e" x1="106" y1="39" x2="181" y2="103"/><line class="e" x1="31" y1="103" x2="31" y2="167"/><line class="e" x1="181" y1="103" x2="131" y2="167"/><line class="e" x1="181" y1="103" x2="181" y2="167"/><line class="e" x1="181" y1="103" x2="231" y2="167"/><line class="e" x1="131" y1="167" x2="131" y2="231"/><line class="e" x1="231" y1="167" x2="231" y2="231"/><circle class="n" cx="106" cy="39" r="17"/><text class="t" x="106" y="39" dy=".35em" text-anchor="middle">E</text><circle class="n" cx="31" cy="103" r="17"/><text class="t" x="31" y="103" dy=".35em" text-anchor="middle">E</text><circle class="n" cx="31" cy="167" r="17"/><text class="t" x="31" y="167" dy=".35em" text-anchor="middle">id</text><circle class="n" cx="81" cy="103" r="17"/><text class="t" x="81" y="103" dy=".35em" text-anchor="middle">+</text><circle class="n" cx="181" cy="103" r="17"/><text class="t" x="181" y="103" dy=".35em" text-anchor="middle">E</text><circle class="n" cx="131" cy="167" r="17"/><text class="t" x="131" y="167" dy=".35em" text-anchor="middle">E</text><circle class="n" cx="131" cy="231" r="17"/><text class="t" x="131" y="231" dy=".35em" text-anchor="middle">id</text><circle class="n" cx="181" cy="167" r="17"/><text class="t" x="181" y="167" dy=".35em" text-anchor="middle"></text><circle class="n" cx="231" cy="167" r="17"/><text class="t" x="231" y="167" dy=".35em" text-anchor="middle">E</text><circle class="n" cx="231" cy="231" r="17"/><text class="t" x="231" y="231" dy=".35em" text-anchor="middle">id</text></svg><figcaption style="font-size:.82em;opacity:.72;margin-top:.45rem">Tree 1 of id+id*id: id + (id * id)</figcaption></figure>

<figure class="ds-fig" style="margin:1.4rem 0;overflow-x:auto"><svg xmlns="http://www.w3.org/2000/svg" id="dsfig-u3-04" viewBox="0 0 286 262" width="286" height="262" role="img" aria-label="Tree 2 of id+idid: (id + id) * id"><style>#dsfig-u3-04 .e{stroke:#454C5A;stroke-width:1.4;fill:none}#dsfig-u3-04 .e.hi{stroke:#2340B8;stroke-width:2.6}#dsfig-u3-04 .n{fill:#FFFFFF;stroke:#16181D;stroke-width:1.4}#dsfig-u3-04 .n.hi{fill:#E3E9FC;stroke:#2340B8;stroke-width:2.2}#dsfig-u3-04 .n.rb-b{fill:#16181D;stroke:#16181D}#dsfig-u3-04 .n.rb-r{fill:#BD3227;stroke:#BD3227}#dsfig-u3-04 text{font-family:"JetBrains Mono",ui-monospace,Menlo,Consolas,monospace;font-size:13px}#dsfig-u3-04 .t{fill:#16181D;font-weight:500}#dsfig-u3-04 .t.inv{fill:#FFFFFF;font-weight:700}#dsfig-u3-04 .kd{stroke:#16181D;stroke-width:1.2}#dsfig-u3-04 .dot{fill:#16181D}#dsfig-u3-04 .ann{fill:#2340B8;font-size:11px;font-weight:700}#dsfig-u3-04 .lbl{fill:#6F7787;font-family:system-ui,-apple-system,sans-serif;font-size:12px;font-weight:700}#dsfig-u3-04 .ptr{fill:#2340B8;font-size:12px;font-weight:700}#dsfig-u3-04 .ah{fill:#454C5A}#dsfig-u3-04 .ah.hi{fill:#2340B8}#dsfig-u3-04 .wl rect{fill:#FFFFFF;stroke:#DCE0E7}#dsfig-u3-04 .wl .t{font-size:12px;font-weight:700}#dsfig-u3-04 .wl.hi rect{fill:#2340B8;stroke:#2340B8}#dsfig-u3-04 .wl.hi .t{fill:#FFFFFF}html.dark #dsfig-u3-04 .e{stroke:#B1B7C3}html.dark #dsfig-u3-04 .e.hi{stroke:#8FA3FF}html.dark #dsfig-u3-04 .n{fill:#161920;stroke:#E6E8ED}html.dark #dsfig-u3-04 .n.hi{fill:#1E2748;stroke:#8FA3FF}html.dark #dsfig-u3-04 .n.rb-b{fill:#E6E8ED;stroke:#E6E8ED}html.dark #dsfig-u3-04 .n.rb-r{fill:#FF7E71;stroke:#FF7E71}html.dark #dsfig-u3-04 .t{fill:#E6E8ED}html.dark #dsfig-u3-04 .t.inv{fill:#0F1115}html.dark #dsfig-u3-04 .kd{stroke:#E6E8ED}html.dark #dsfig-u3-04 .dot{fill:#E6E8ED}html.dark #dsfig-u3-04 .ann{fill:#8FA3FF}html.dark #dsfig-u3-04 .lbl{fill:#858D9C}html.dark #dsfig-u3-04 .ptr{fill:#8FA3FF}html.dark #dsfig-u3-04 .ah{fill:#B1B7C3}html.dark #dsfig-u3-04 .ah.hi{fill:#8FA3FF}html.dark #dsfig-u3-04 .wl rect{fill:#161920;stroke:#2A2E37}html.dark #dsfig-u3-04 .wl.hi rect{fill:#8FA3FF;stroke:#8FA3FF}html.dark #dsfig-u3-04 .wl.hi .t{fill:#0F1115}</style><defs><marker id="ah10" viewBox="0 0 10 10" refX="9" refY="5" markerWidth="7" markerHeight="7" orient="auto-start-reverse"><path class="ah" d="M0,1 L9,5 L0,9 z"/></marker><marker id="ahh10" viewBox="0 0 10 10" refX="9" refY="5" markerWidth="7" markerHeight="7" orient="auto-start-reverse"><path class="ah hi" d="M0,1 L9,5 L0,9 z"/></marker></defs><line class="e" x1="156" y1="39" x2="81" y2="103"/><line class="e" x1="156" y1="39" x2="181" y2="103"/><line class="e" x1="156" y1="39" x2="231" y2="103"/><line class="e" x1="81" y1="103" x2="31" y2="167"/><line class="e" x1="81" y1="103" x2="81" y2="167"/><line class="e" x1="81" y1="103" x2="131" y2="167"/><line class="e" x1="31" y1="167" x2="31" y2="231"/><line class="e" x1="131" y1="167" x2="131" y2="231"/><line class="e" x1="231" y1="103" x2="231" y2="167"/><circle class="n" cx="156" cy="39" r="17"/><text class="t" x="156" y="39" dy=".35em" text-anchor="middle">E</text><circle class="n" cx="81" cy="103" r="17"/><text class="t" x="81" y="103" dy=".35em" text-anchor="middle">E</text><circle class="n" cx="31" cy="167" r="17"/><text class="t" x="31" y="167" dy=".35em" text-anchor="middle">E</text><circle class="n" cx="31" cy="231" r="17"/><text class="t" x="31" y="231" dy=".35em" text-anchor="middle">id</text><circle class="n" cx="81" cy="167" r="17"/><text class="t" x="81" y="167" dy=".35em" text-anchor="middle">+</text><circle class="n" cx="131" cy="167" r="17"/><text class="t" x="131" y="167" dy=".35em" text-anchor="middle">E</text><circle class="n" cx="131" cy="231" r="17"/><text class="t" x="131" y="231" dy=".35em" text-anchor="middle">id</text><circle class="n" cx="181" cy="103" r="17"/><text class="t" x="181" y="103" dy=".35em" text-anchor="middle"></text><circle class="n" cx="231" cy="103" r="17"/><text class="t" x="231" y="103" dy=".35em" text-anchor="middle">E</text><circle class="n" cx="231" cy="167" r="17"/><text class="t" x="231" y="167" dy=".35em" text-anchor="middle">id</text></svg><figcaption style="font-size:.82em;opacity:.72;margin-top:.45rem">Tree 2 of id+id*id: (id + id) * id</figcaption></figure>

Removal. $E\to E+T\mid T$, $T\to T*F\mid F$, $F\to id\mid(E)$ has one tree for every string, with $*$ binding tighter than $+$.

Show $S\to aSbS\mid bSaS\mid\varepsilon$ ambiguous with $abab$:

1: S=>aSbS=>abS=>abaSbS=>ababS=>abab      (first S -> e, second S -> aSbS)
2: S=>aSbS=>abSaSbS=>abaSbS=>ababS=>abab  (first S -> bSaS, inner S -> e)

Two different leftmost derivations of $abab$ (two parse trees), so the grammar is ambiguous.

Test $S\to SS\mid a\mid b$ with $aab$: $S\Rightarrow SS\Rightarrow SSS\Rightarrow aSS\Rightarrow aaS\Rightarrow aab$ (tree $(aa)b$) and $S\Rightarrow SS\Rightarrow aS\Rightarrow aSS\Rightarrow aaS\Rightarrow aab$ (tree $a(ab)$). Two trees, so ambiguous.

<mark>A grammar is ambiguous if one string has two different parse trees or two different leftmost derivations.</mark>

Answer frame. Open with the definition; give $E\to E+E\mid E*E\mid id$, draw the two trees for $id+id*id$; then explain the remedies precedence, associativity, rewriting, in that order; close with the unambiguous grammar. For "show ambiguous" give definition, string, two derivations, conclusion.

Asked: [7 marks] (Dec 2020, Jun 2020) Show that $S\to aSbS\mid bSaS\mid\epsilon$ is ambiguous Asked: [7 marks] (Nov 2023) What is meant by ambiguous grammar? Test whether $S\to SS/a/b$ is ambiguous Asked: [7 marks] (May 2023) What is Ambiguity? Explain taking any two examples Asked: [7 marks] (Dec 2025, Jun 2025) Explain ambiguity in grammar and methods to remove it Asked: [7 marks] (Jun 2025) Explain ambiguity in context-free grammars with an example. How can it be resolved?

Simplification of context free grammar

Definition. Simplifying a CFG removes useless symbols, null productions and unit productions without changing the language (apart from $\varepsilon$).

Key points.

A symbol is generating if it derives a terminal string, and reachable if it appears in a sentential form derived from $S$.
Useless symbols are non-generating or unreachable, and are removed with their productions.
Remove non-generating symbols first, then unreachable ones; the reverse order can leave junk.
Null and unit productions are then removed (next topics).

Solved. $S\to AB\mid Ca$, $B\to BC\mid AB$, $A\to a$, $C\to aB\mid b$. Generating: $A$ ($a$), $C$ ($b$), $S$ ($Ca$); $B$ never ends, so drop $B$: $S\to Ca$, $A\to a$, $C\to b$. Reachable from $S$: $S,C$; drop $A$. Result: $S\to Ca$, $C\to b$.

Solved. $S\to AC\mid B$, $A\to a$, $C\to c\mid BC$, $E\to aA\mid e$. $B$ has no production so it is non-generating: $S\to AC$, $C\to c$. $E$ is unreachable, so its null rule $E\to e$ goes with it; the unit $S\to B$ went with $B$. Result: $S\to AC$, $A\to a$, $C\to c$.

<mark>Remove non-generating symbols first and unreachable symbols second to get a reduced grammar.</mark>

Answer frame. Open with generating and reachable; list the generating set, delete, list the reachable set, delete; close with the reduced grammar and its language.

Asked: [7 marks] (Nov 2023, Dec 2024) Find the CFG with no useless symbols equivalent to $S\to AB/Ca$, $B\to BC/AB$, $A\to a$, $C\to aB/b$ Asked: [8 marks] (Dec 2024) Find a reduced grammar for $P:\{S\to AC/B, A\to a, C\to c/BC, E\to aA/e\}$

Conversion of grammar to automata machine and vice versa

Definition. A right-linear grammar and a finite automaton are interconvertible: variables become states and each production becomes a transition.

Key points.

Grammar to NFA (right-linear): $A\to aB$ gives $A\xrightarrow{a}B$, and $A\to a$ gives a move to a final state.
Automaton to grammar: for each $\delta(p,a)=q$ write $p\to aq$, and for each final $f$ write $f\to\varepsilon$.
A left-linear grammar is handled directly: $A\to Bx$ is $B\xrightarrow{x}A$, $A\to x$ is $q_0\xrightarrow{x}A$, and $S$ is final.

Solved. $S\to Ab\mid ab$, $A\to Ab\mid Bb$, $B\to Ba\mid a$ is left-linear; $P$ splits $ab$.

From	on a	on b
$q_0$ (start)	$B$, $P$	none
$B$	$B$	$A$
$P$	none	$S$
$A$	none	$A$, $S$
$S$ (final)	none	none

Accepts $ab$ and $a^mb^n$ with $m\ge1$, $n\ge2$.

<mark>Right-linear productions map to NFA transitions, one production per move.</mark>

Asked: [7 marks] (Dec 2020) Construct NFA for the grammar $S\to Ab/ab$, $A\to Ab/Bb$, $B\to Ba/a$

Chomsky hierarchy of grammar

Definition. The Chomsky hierarchy orders grammars into four classes, each properly inside the previous, each with a matching machine.

Type	Grammar	Rule form	Automaton	Example
0	Unrestricted	$\alpha\to\beta$, $\alpha$ has a variable	Turing machine	halting-problem languages
1	Context sensitive	$\lvert\alpha\rvert\le\lvert\beta\rvert$	Linear bounded automaton	$a^nb^nc^n$
2	Context free	$A\to\alpha$	Pushdown automaton	$a^nb^n$
3	Regular	$A\to aB\mid a$	Finite automaton	$a^b^$

<mark>Type 0, 1, 2, 3 are accepted by TM, LBA, PDA and FA, each class inside the one above.</mark>

Asked: [8 marks] (Dec 2024) Discuss the Chomsky hierarchy of languages with their grammar constraints and corresponding automata

Killing null and unit productions

Definition. A null production is $A\to\varepsilon$ and a unit production is $A\to B$ with $B$ a variable.

Key points.

Null removal: find nullable variables ($A\Rightarrow^*\varepsilon$), then for each rule add every copy with nullable symbols omitted and delete $A\to\varepsilon$.
Unit removal: for each $A\to B$ and each non-unit rule $B\to\alpha$, add $A\to\alpha$, then delete all unit rules.
Do null first, then unit, then useless symbols; $\varepsilon$ itself cannot be kept unless $S\to\varepsilon$ is retained.

<mark>Remove null productions first, then unit productions, then useless symbols.</mark>

Chomsky normal form

Definition. A CFG is in CNF if every production is $A\to BC$ (two variables) or $A\to a$ (one terminal), with $\varepsilon$ excluded.

Key points.

Every CFL without $\varepsilon$ has a CNF grammar.
Steps: remove null productions, remove unit productions, remove useless symbols, replace terminals in long rules by new variables, and break rules longer than two variables.
A CNF derivation of a length-$n$ string takes $2n-1$ steps, and its parse trees are binary.

Solved. $S\to ABA$, $A\to aA\mid\varepsilon$, $B\to bB\mid\varepsilon$.

Nullable: $A,B,S$. Drop nulls: $S\to ABA\mid AB\mid BA\mid AA\mid A\mid B$, $A\to aA\mid a$, $B\to bB\mid b$.
Units $S\to A\mid B$ replaced: $S\to aA\mid a\mid bB\mid b$ added.
Terminals: $X\to a$, $Y\to b$. Break $ABA$: $D\to BA$.

Result:

S -> AD | AB | BA | AA | XA | YB | a | b
D -> BA
A -> XA | a       B -> YB | b       X -> a     Y -> b

Solved. $S\to aSb\mid SS\mid\varepsilon$: drop null: $S\to aSb\mid SS\mid ab$ ($S\to S$ is discarded). No unit rules. Terminals $X\to a$, $Y\to b$; break $XSY$ with $D\to SY$.

Result: $S\to XD\mid SS\mid XY$, $D\to SY$, $X\to a$, $Y\to b$. For $\varepsilon$ add a new start $S_0\to S\mid\varepsilon$.

<mark>CNF allows only rules $A\to BC$ and $A\to a$ (no $\varepsilon$).</mark>

Answer frame. Open with the CNF definition; list the five steps in order; apply them one by one on the given grammar, showing the grammar after each step; close with the final table and a note on $\varepsilon$.

Asked: [7 marks] (Nov 2019, Dec 2025, Jun 2025) Find the CNF for $S\to ABA$, $A\to aA\mid\varepsilon$, $B\to bB\mid\varepsilon$ Asked: [7 marks] (Jun 2025) Convert $S\to aSb\mid SS\mid\varepsilon$ to CNF

Greibach normal form

Definition. A CFG is in GNF if every production is $A\to a\alpha$, with terminal $a$ first and $\alpha$ a string of variables.

Key points.

Every CFL without $\varepsilon$ has a GNF grammar, and each derivation step then produces one terminal.
Number the variables $A_1,\dots,A_n$ and make every rule $A_i\to A_j\gamma$ satisfy $j>i$ by substitution.
Left recursion $A\to A\alpha\mid\beta$ is replaced by $A\to\beta\mid\beta Z$, $Z\to\alpha\mid\alpha Z$.
Back-substitute from the last variable upward so every rule starts with a terminal.

Solved. $A_1\to A_2A_3$, $A_2\to A_3A_1\mid b$, $A_3\to A_1A_2\mid a$ (checked to the same strings up to length 7).

$A_3\to A_1A_2\Rightarrow A_2A_3A_2\Rightarrow A_3A_1A_3A_2\mid bA_3A_2$, so $A_3\to A_3A_1A_3A_2\mid bA_3A_2\mid a$.
Remove left recursion: $A_3\to bA_3A_2\mid a\mid bA_3A_2Z\mid aZ$, $Z\to A_1A_3A_2\mid A_1A_3A_2Z$.
Back-substitute: $A_2\to bA_3A_2A_1\mid aA_1\mid bA_3A_2ZA_1\mid aZA_1\mid b$.
$A_1\to\alpha A_3$ for each $\alpha$ among those five $A_2$ rules, and $Z\to\alpha A_3A_3A_2\mid\alpha A_3A_3A_2Z$ for the same five $\alpha$.

Solved. $S\to AB$, $A\to BS\mid b$, $B\to SA\mid a$ with $S,A,B$ as 1, 2, 3.

$B\to SA\Rightarrow ABA\Rightarrow BSBA\mid bBA$, so $B\to BSBA\mid bBA\mid a$; remove left recursion: $B\to bBA\mid a\mid bBAZ\mid aZ$, $Z\to SBA\mid SBAZ$.
$A\to bBAS\mid aS\mid bBAZS\mid aZS\mid b$.
$S\to\gamma$ for each $\gamma=\alpha B$ with $\alpha$ among those five $A$ rules, so $S\to bBASB\mid aSB\mid bBAZSB\mid aZSB\mid bB$; $Z\to\gamma BA\mid\gamma BAZ$ for the same five $\gamma$.

<mark>GNF makes every production start with one terminal followed only by variables.</mark>

Answer frame. Open with the definition; state the ordering rule $A_i\to A_j\gamma$, $j>i$; substitute, remove left recursion with $Z$, back-substitute; close by listing every rule and noting it starts with a terminal.

Asked: [7 marks] (Nov 2019, Dec 2024) Convert $A_1\to A_2A_3$, $A_2\to A_3A_1\mid b$, $A_3\to A_1A_2\mid a$ to GNF Asked: [6 marks] (Dec 2024) Convert $S\to AB$, $A\to BS/b$, $B\to SA/a$ into GNF

Last-minute revision

CFG is $(V,T,P,S)$ with every rule $A\to\alpha$; regular grammar is right- or left-linear only.
Chomsky types 0, 1, 2, 3 match TM, LBA, PDA, FA.
Union of CFLs: new start $S\to S_1\mid S_2$; CFLs are not closed under intersection.
Pumping lemma for CFL: $z=uvwxy$, $|vwx|\le p$, $|vx|\ge1$, $uv^iwx^iy\in L$; use $a^pb^pc^p$.
Leftmost expands the leftmost variable; rightmost the rightmost; the tree yield is the string.
Ambiguous means one string, two trees; fix by precedence layering, associativity, rewriting.
$S\to SS\mid a\mid b$ and $S\to aSbS\mid bSaS\mid\varepsilon$ are ambiguous, shown with $aab$ and $abab$.
Reduce a grammar: remove non-generating, then unreachable, then null, then unit symbols.
CNF is $A\to BC\mid a$; GNF is $A\to a\alpha$.
CNF of $S\to ABA$ gives $S\to AD\mid AB\mid BA\mid AA\mid XA\mid YB\mid a\mid b$.
Left recursion $A\to A\alpha\mid\beta$ becomes $A\to\beta\mid\beta Z$, $Z\to\alpha\mid\alpha Z$.

Memory hooks

Types 0 to 3: Turing, Linear bounded, Pushdown, Finite (TLPF).
Ambiguity is two maps for one place: two trees for one string.
Reduction order: Generate, then Reach.
Simplify order: Null, Unit, Useless (N-U-U).

Coverage checklist

Types of grammar: no past questions; covered.
context sensitive grammar: no past questions; covered.
context free grammar: CFG designs, 4-tuple definitions, union proof, two pumping-lemma proofs, R.E. to CFG, definition with derivation trees.
regular grammar: RE to grammar, identify the language, one a and at most two b's.
Derivation trees: aabb tree, leftmost and rightmost, list grammar.
ambiguity in grammar: $aSbS$, $SS$, two examples, removal.
simplification of context free grammar: two useless-symbol questions.
conversion of grammar to automata machine and vice versa: NFA for the left-linear grammar.
Chomsky hierarchy of grammar: hierarchy table.
killing null and unit productions: no past questions; covered.
Chomsky normal form: $S\to ABA$ and $S\to aSb\mid SS\mid\varepsilon$.
Greibach normal form: both GNF conversions.

Account

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

How unit 3 is examined

Types of grammar

Context sensitive grammar

Context free grammar

Regular grammar

Derivation trees

Ambiguity in grammar

Simplification of context free grammar

Conversion of grammar to automata machine and vice versa

Chomsky hierarchy of grammar

Killing null and unit productions

Chomsky normal form

Greibach normal form

Last-minute revision

Memory hooks

Coverage checklist