Context free grammars and simplification notes — Unit 3

In Unit 2, we proved that regular languages (DFAs/REs) cannot count. They cannot handle languages with nested dependencies like $a^n b^n$.

To describe these more complex, nested languages (which form the foundation of all programming language syntax, like matching nested `{ }` brackets in C++), Noam Chomsky introduced Context-Free Grammars.

⇒1.1 The CFG Definition

A CFG is a 4-tuple $G = (V, T, P, S)$. The variables $V$, terminals $T$, and start symbol $S$ are the same as regular grammars. The massive power difference lies in the Production Rules $P$.

The CFG Rule: Every production must be in the form:
$A \rightarrow \alpha$

Where:
- $A \in V$ (Exactly ONE single Non-Terminal variable on the Left side).
- $\alpha \in (V \cup T)^*$ (The Right side can be literally ANYTHING. Any combination of terminals, non-terminals, mixed together in any order, or even the empty string $\epsilon$).

Because the left side is just a single isolated variable 'A', we can replace 'A' with $\alpha$ regardless of the surrounding context. Hence, "Context-Free".

⇒2.1 Solving the Counting Problem

How does a CFG solve $L = \{a^n b^n\}$? Through symmetric recursion.

Grammar:
$S \rightarrow aSb$
$S \rightarrow \epsilon$

Derivation of string `aaabbb`:
$S \Rightarrow aSb$
$\Rightarrow aaSbb$ (Replaced inner S with aSb)
$\Rightarrow aaaSbbb$ (Replaced inner S with aSb)
$\Rightarrow aaabbb$ (Replaced inner S with $\epsilon$)

Because the grammar enforces placing one 'a' on the left and one 'b' on the right simultaneously in a single rule, it is mathematically impossible to generate a mismatched number. A DFA could never do this.

⇒2.2 CFG for Palindromes

Generating strings that read the same forwards and backwards ($ww^R$).
$S \rightarrow 0S0 | 1S1 | 0 | 1 | \epsilon$

A derivation is the step-by-step sequence of applying production rules to convert the Start symbol into a string of pure terminals.

⇒3.1 Leftmost vs Rightmost Derivation

If a string contains multiple variables (e.g., $A B c D$), which one do you replace first?

• Leftmost Derivation (LMD): At every step, you strictly replace the leftmost non-terminal variable in the string. (This is how most actual compilers parse code).
• Rightmost Derivation (RMD): At every step, you strictly replace the rightmost non-terminal variable.

⇒3.2 The Parse Tree (Derivation Tree)

A visual, graphical representation of a derivation.
- The Root is the start symbol $S$.
- Internal nodes are non-terminal variables.
- The Leaves are terminal symbols (or $\epsilon$).
- Reading the leaves from left to right yields the final generated string (the yield of the tree).

Crucially, a Parse Tree completely ignores the arbitrary order of substitution (LMD vs RMD). It only shows the structural hierarchy.

This is a critical flaw that breaks compilers.

⇒4.1 The Definition

A Context-Free Grammar is Ambiguous if there exists even a single string in the language that can be generated by two completely different Parse Trees (which is mathematically equivalent to having two distinct Leftmost Derivations).

Consider a math expression grammar: $E \rightarrow E + E \mid E * E \mid id$.

Parse the string: `id + id id`. - Tree 1 groups it as `(id + id) id`.
- Tree 2 groups it as `id + (id * id)`.

Both trees are perfectly valid according to the grammar rules. However, they evaluate to completely different mathematical results. If a C++ compiler used an ambiguous grammar, the statement `x = 2 + 3 * 4` might compute to 14 on Monday and 20 on Tuesday. This is catastrophic.

There is no magic, universal algorithm to remove ambiguity from any grammar (it is an undecidable problem). It requires human engineering, specifically by forcing Precedence and Associativity into the grammar hierarchy.

⇒5.1 Enforcing Precedence

To fix the math expression grammar, we must force multiplication to happen structurally lower in the parse tree than addition, so it evaluates first.

We introduce new variable layers: $E$ (Expression), $T$ (Term), $F$ (Factor).
$E \rightarrow E + T \mid T$
$T \rightarrow T * F \mid F$
$F \rightarrow (E) \mid id$

This new grammar generates the exact same strings, but structurally forces `*` to be resolved before `+`. It is completely Unambiguous.

⇒5.2 Inherent Ambiguity

Some languages are so mathematically twisted that EVERY possible grammar you could ever write for them will be ambiguous. These are called Inherently Ambiguous Languages. (e.g., $L = \{a^n b^n c^m\} \cup \{a^n b^m c^m\}$).

Often, grammars contain garbage rules that bloat the compiler but do absolutely nothing useful. Before we can optimize a grammar into Normal Form, we must surgically remove three types of garbage, strictly in this order:

• 1. Elimination of Useless Symbols
• 2. Elimination of $\epsilon$-Productions
• 3. Elimination of Unit Productions

⇒6.1 Removing Useless Symbols

A variable is "useful" only if it satisfies TWO conditions:
1. Generating: It must eventually be able to derive a string of pure terminals. (e.g., if $A \rightarrow aA$, it loops forever and never produces a final string. $A$ is non-generating).
2. Reachable: There must be a path from the Start Symbol $S$ to reach the variable. (e.g., if $S \rightarrow aB$, and there's a rule $C \rightarrow d$, $C$ is unreachable dead code).

You must first delete all non-generating symbols, and THEN delete all unreachable symbols.

⇒7.1 Eliminating $\epsilon$-Productions

An $\epsilon$-production is a rule like $A \rightarrow \epsilon$. These make parse trees arbitrarily deep without adding any symbols.

1. Find all "Nullable" variables (variables that can eventually derive $\epsilon$).
2. For every rule that contains a nullable variable on the right side, add new rules simulating all possible combinations of that variable disappearing.

Example: Rule is $S \rightarrow aAbA$. $A$ is nullable.
New rules:
$S \rightarrow aAbA$ (Keep both)
$S \rightarrow abA$ (Drop first A)
$S \rightarrow aAb$ (Drop second A)
$S \rightarrow ab$ (Drop both A's)
3. Finally, delete the actual $A \rightarrow \epsilon$ rule.

⇒7.2 Eliminating Unit Productions

A Unit Production is a rule of the form $A \rightarrow B$, where a single variable points to exactly one other single variable. These are useless "middlemen" that just copy data.

1. Find all unit pairs $(A, B)$ meaning A can eventually derive B.
2. If $B ightarrow alpha$ (where $\alpha$ is NOT a unit production), add the rule $A \rightarrow alpha$ directly to A.
3. Delete all rules of the form $X \rightarrow Y$.

A standardized, highly structured mathematical format for CFGs. Grammars in CNF are predictable, making parser algorithms (like the CYK algorithm) much faster to execute.

⇒8.1 The Strict Rules of CNF

A grammar is strictly in CNF if EVERY single production rule is in one of two exact formats:

• $A \rightarrow BC$ (A variable is replaced by EXACTLY TWO variables).
• $A \rightarrow a$ (A variable is replaced by EXACTLY ONE terminal).

No mixing of terminals and variables (e.g., $A \rightarrow aB$ is illegal). No rules with three variables (e.g., $A \rightarrow BCD$ is illegal).

Mathematical Property: If a grammar is in CNF, any string of length $n$ will take EXACTLY $2n - 1$ derivation steps to generate. The parse tree becomes a perfect binary tree.

You can algorithmically convert any simplified CFG into CNF.

⇒9.1 The Conversion Algorithm

• Step 1: Ensure the grammar is simplified (No $\epsilon$, no units, no useless).
• Step 2: Isolate Terminals. For any rule of length > 1 containing terminals (e.g., $A \rightarrow aBc$), replace the terminal with a new dedicated variable.
  Create $X_a \rightarrow a$.
  Change the rule to $A \rightarrow X_a B X_c$.
  (Now, all long rules consist purely of variables).
• Step 3: Break long variable chains. If a rule has more than 2 variables (e.g., $A \rightarrow BCD$), break it down in a cascading fashion using new variables.
  Change to:
  $A \rightarrow BY_1$
  $Y_1 \rightarrow CD$.
  (Now, every rule is either $A \rightarrow BC$ or $A \rightarrow a$. The grammar is perfectly in CNF).

Another standard format, invented by Sheila Greibach. While CNF forces binary trees, GNF is specifically designed to make reading strings from left to right extremely efficient. It is heavily used in building Pushdown Automata.

⇒10.1 The Strict Rules of GNF

A grammar is strictly in GNF if EVERY single production rule is in the format:

$A \rightarrow a \alpha$

Where:
- $a$ is EXACTLY ONE terminal symbol at the absolute left position.
- $\alpha$ is a string of zero or more VARIABLES. ($V^*$).

Valid GNF rules: $A \rightarrow a$, $A \rightarrow aB$, $A \rightarrow aBCD$.
Invalid rules: $A \rightarrow Ba$ (variable first), $A \rightarrow ab$ (two terminals).

Mathematical Property: Because every single rule application guarantees exactly one new terminal is generated at the front, a string of length $n$ will be generated in exactly $n$ steps.

A major hurdle in converting to GNF (and building top-down parsers) is Left Recursion.

⇒11.1 The Infinite Loop

A grammar has Left Recursion if a variable can directly or indirectly derive a string starting with itself: $A \rightarrow A\alpha$.

A top-down parser trying to process this will see an 'A', and replace it with 'A $\alpha$'. It then sees the new 'A' and replaces it with 'A $\alpha$'. It loops infinitely, crashing the compiler with a Stack Overflow without ever reading a single terminal character.

⇒11.2 Eliminating Left Recursion

We mathematically transform left-heavy rules into right-heavy rules using a new variable.

Given: $A \rightarrow A\alpha mid \beta$ (where $\beta$ does not start with A).
Replace with:
$A \rightarrow \beta A'$
$A' \rightarrow \alpha A' mid \epsilon$

This generates the exact same language but completely eliminates the infinite loop.

Unit 3 is heavily algorithmic. You must be able to surgically modify grammars without changing the underlying language.

⇒12.1 University Exam Checklist

• Define a Context-Free Grammar. Why is it "Context-Free"? How is it mathematically more powerful than a Regular Grammar?
• Given a CFG, write the Leftmost and Rightmost derivations for a specific string.
• Draw a Parse Tree (Derivation Tree) for a given string.
• Define Ambiguity. Prove a given grammar is ambiguous by drawing two distinct parse trees for the same string.
• How do you mathematically remove inherent ambiguity? (Trick question: You can't. Explain why).
• Perform CFG Simplification: Show the exact step-by-step algorithms to remove Useless Symbols, $\epsilon$-productions, and Unit Productions.
• State the structural rules of Chomsky Normal Form (CNF).
• Convert a given CFG into CNF using the step-by-step algorithm.
• State the structural rules of Greibach Normal Form (GNF).
• Define Left Recursion and show the mathematical formula to eliminate it.