Theory of Computation (AD-501) Unit 3 Notes

How unit 3 is examined

This unit covers grammar types, CFG simplification, derivation trees and ambiguity, grammar-automata conversion, and the CNF and GNF conversions; CNF/GNF carries most of the marks.

Types of grammar

Not asked since 2022

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

Key points.

Chomsky classified grammars by the shape of their productions into Type 0, 1, 2 and 3.
Type 0 is unrestricted, Type 1 is context sensitive, Type 2 is context free and Type 3 is regular.
Each type is a proper subset of the one before it, so tighter rules give weaker but easier-to-process languages.

Context sensitive grammar

Definition. A context sensitive grammar (Type 1) has productions $\alpha\to\beta$ with $|\alpha|\le|\beta|$, where $\alpha,\beta\in(V\cup T)^*$ and $\alpha$ contains a variable.

Key points.

A production never shortens the string, so it is also called non-contracting; only $S\to\varepsilon$ is allowed if $S$ never appears on a right side.
Replacement of $A$ depends on its context, as in $\alpha A\beta\to\alpha\gamma\beta$.
Example: $\{a^nb^nc^n\}$ is context sensitive but not context free.
It is recognised by a linear bounded automaton.

Context free grammar

Definition. A context free grammar (Type 2) has every production of the form $A\to\alpha$, with a single variable $A$ on the left and $\alpha\in(V\cup T)^*$.

Key points.

The left side is one variable, so $A$ is replaced whatever surrounds it.
Example: $S\to aSb\mid\varepsilon$ generates $\{a^nb^n\}$.
It is recognised by a pushdown automaton.
It is used to describe programming-language syntax.

Regular grammar

Definition. A regular grammar (Type 3) is right linear, with productions $A\to aB$ or $A\to a$, or left linear, with $A\to Ba$ or $A\to a$, where $A,B\in V$ and $a\in T\cup\{\varepsilon\}$.

Key points.

A right linear grammar has at most one variable, at the right end of each right side.
A grammar that mixes left and right linear rules is not regular.
Regular grammars generate exactly the regular languages, accepted by finite automata.
Example: $S\to aS\mid b$ generates $a^*b$.

Derivation trees

Definition. A derivation (parse) tree for a CFG has the start symbol as root, variables as interior nodes and terminals or $\varepsilon$ as leaves, and each interior node with its children follows a production.

Key points.

The yield is the leaves read left to right, and it is the derived string.
A leftmost derivation always replaces the leftmost variable and a rightmost derivation the rightmost variable.
A tree hides the replacement order, so one tree corresponds to exactly one leftmost and one rightmost derivation.

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 (or rightmost) derivations.

Key points.

In $S\to A1B$, $A$ must produce only the zeros before the separating 1, so 00101 can be split only as $00\cdot1\cdot01$.
Leftmost: $S\Rightarrow A1B\Rightarrow0A1B\Rightarrow00A1B\Rightarrow001B\Rightarrow0010B\Rightarrow00101B\Rightarrow00101$.
Rightmost: $S\Rightarrow A1B\Rightarrow A10B\Rightarrow A101B\Rightarrow A101\Rightarrow0A101\Rightarrow00A101\Rightarrow00101$.
There is one parse tree, so the grammar is not ambiguous.

Asked: [7 marks] (Nov 2022) Check whether the given grammar is ambiguous. $S \to A1B$, $A \to 0A|\varepsilon$, $B \to 0B|1B|\varepsilon$ and construct leftmost and rightmost derivations for the string 00101.

Simplification of context free grammar

Definition. Simplification removes useless symbols, null ($\varepsilon$) productions and unit productions ($A\to B$) without changing the language.

Key points.

Remove useless symbols first: keep only variables that derive a terminal string and are reachable from $S$.
Nullable variables are found by $A\to\varepsilon$; every production is then rewritten with each subset of nullable variables dropped.
For a unit production $A\to B$, add $A\to\alpha$ for every non-unit $B\to\alpha$ and delete $A\to B$.
The safe order is null, then unit, then useless.

Conversion of grammar to automata machine and vice versa

Definition. A regular expression converts to a CFG by giving each sub-expression a variable: union becomes alternatives, concatenation a sequence, and star a recursive rule.

Key points.

For $(011+1)^*(01)^*$ take $S\to XY$.
$X\to ZX\mid\varepsilon$ with $Z\to011\mid1$ gives $(011+1)^*$.
$Y\to WY\mid\varepsilon$ with $W\to01$ gives $(01)^*$.
A regular grammar converts to an NFA with states as variables, $A\to aB$ as $\delta(A,a)=B$ and $A\to a$ as a move to a final state.

Formula. $\text{CFG}: S\to XY;\ X\to ZX\mid\varepsilon;\ Z\to011\mid1;\ Y\to WY\mid\varepsilon;\ W\to01$.

Asked: [7 marks] (Nov 2023) Write given CFG for R.E $(011 + 1)^*(01)^*$.

Chomsky hierarchy of grammar

Definition. The Chomsky hierarchy orders grammars as Type 0 (unrestricted) $\supset$ Type 1 (context sensitive) $\supset$ Type 2 (context free) $\supset$ Type 3 (regular).

Type	Grammar	Machine
0	Unrestricted	Turing machine
1	Context sensitive	Linear bounded automaton
2	Context free	Pushdown automaton
3	Regular	Finite automaton

Chomsky normal form and Greibach normal form

Definition. A CFG is in CNF if every production is $A\to BC$ or $A\to a$; it is in GNF if every production is $A\to a\alpha$, a terminal followed by zero or more variables.

Key points.

First simplify the grammar (null, unit, useless).
CNF: replace each terminal in a long right side by a new variable $C_a\to a$.
CNF: break right sides longer than 2 by chaining new variables.
GNF: order variables $A_1..A_n$ and make every $A_i\to A_j\gamma$ have $j>i$ by substitution.
GNF: remove left recursion $A\to A\alpha\mid\beta$ by $A\to\beta\mid\beta Z$, $Z\to\alpha\mid\alpha Z$.
GNF: back-substitute upwards until every right side starts with a terminal.

Example (CNF). Add $C_0\to0$, $C_1\to1$, $D\to AA$, $E\to BB$:

Head	Productions
$S$	$C_0B\mid C_1A$
$A$	$C_0S\mid C_1D\mid0$
$B$	$C_1S\mid C_0E\mid1$
$D,E,C_0,C_1$	$D\to AA,\ E\to BB,\ C_0\to0,\ C_1\to1$

Example (GNF). Substituting gives $A_3\to A_3A_1A_3A_2\mid aA_3A_2\mid b$. Remove left recursion with $Z\to A_1A_3A_2\mid A_1A_3A_2Z$:

Head	GNF productions
$A_3$	$aA_3A_2\mid b\mid aA_3A_2Z\mid bZ$
$A_2$	$aA_3A_2A_1\mid bA_1\mid aA_3A_2ZA_1\mid bZA_1\mid a$
$A_1$	$A_2A_3$ with $A_2$ expanded: each $A_2$ alternative followed by $A_3$
$Z$	each $A_1$ alternative followed by $A_3A_2$ or $A_3A_2Z$

Answer frame. Open with the CNF and GNF definitions and their shapes; state the conversion steps as numbered points; for a numerical, simplify first, then show the new variables and the final table; close with the final production list.

Asked: [7 marks] (Nov 2022) Construct a grammar in CNF for $G$ with $V=\{S,A,B\}$, $T=\{0,1\}$, $P:\{S\to0B|1A,\ A\to0S|1AA|0,\ B\to1S|0BB|1\}$. Asked: [7 marks] (Nov 2022) Construct the grammar in GNF for $G: A_1\to A_2A_3,\ A_2\to A_3A_1|a,\ A_3\to A_1A_2|b$. Asked: [7 marks] (Nov 2023) Explain Greibach and Chomsky Normal Form.

Last-minute revision

A grammar is $G=(V,T,P,S)$.
Type 0 is unrestricted, Type 1 has $|\alpha|\le|\beta|$, Type 2 has a single variable on the left, and Type 3 is right or left linear.
Ambiguous means two parse trees for one string.
Simplify in the order null, unit, useless.
CNF is $A\to BC\mid a$.
GNF is $A\to a\alpha$.
Left recursion $A\to A\alpha\mid\beta$ becomes $A\to\beta\mid\beta Z$.
The grammar $S\to A1B$ is unambiguous for 00101.
$(011+1)^*(01)^*$ needs $S\to XY$.

Memory hooks

Type numbers go down as power goes down: 0 is Turing, 1 is LBA, 2 is PDA, 3 is FA.
CNF has two variables or one terminal; GNF starts with a terminal.
Simplify order is N-U-U: null, unit, useless.

Coverage checklist

Types of grammar: covered.
context sensitive grammar: covered.
context free grammar: covered.
regular grammar: covered.
Derivation trees: covered.
ambiguity in grammar: Nov 2022 proof.
simplification of context free grammar: covered.
conversion of grammar to automata machine and vice versa: Nov 2023 numerical.
Chomsky hierarchy of grammar: covered.
Chomsky normal form and Greibach normal form: Nov 2022 CNF, Nov 2022 GNF, Nov 2023 explain.

Account

Theory of Computation (AD-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

Chomsky normal form and Greibach normal form

Last-minute revision

Memory hooks

Coverage checklist