8. CFG Normal Forms

Feb 1, 2022

Substitution rules

• modify grammar to produce an equivalent grammar that produces same strings
• Substitute $B\to y$ to obtain equivalent grammar:

Original $$\begin{array}{rl}A& \to xBz\\ B& \to y_1\end{array}$$

Equivalent $$\begin{array}{rl}A& \to xBz\text{ | }x{y}_{1}z\end{array}$$

$ϵ$-productions

• when $X$ is a nullable variable, also eliminate $ϵ$-productions: $X\to ϵ$
• after removing $ϵ$-productions all nullable variables disappear (except for start variable)

Original $$\begin{array}{rl}S& \to aMb\\ M& \to aMb\\ M& \to ϵ\end{array}$$

Equivalent $$\begin{array}{rl}S& \to aMb\text{ | }ab\\ M& \to aMb\text{ | }ab\end{array}$$

Unit productions

• unit production occurs when a single variable occurs on both sides, e.g. $X\to Y$
• eliminate unit productions using substitution rule

Original   $$\begin{array}{rl}S& \to aA\\ A& \to a\\ A& \to B\\ B& \to A\\ B& \to bb\end{array}$$

Intermediate (substitute A → B) $$\begin{array}{rl}S& \to aA\text{ | }aB\\ A& \to a\\ B& \to A\text{ | }B\\ B& \to bb\end{array}$$

Intermediate (remove B → B) $$\begin{array}{rl}S& \to aA\text{ | }aB\\ A& \to a\\ B& \to A\\ B& \to bb\end{array}$$

Final equivalent (remove B → A) $$\begin{array}{rl}S& \to aA\text{ | }aB\\ A& \to a\\ B& \to bb\end{array}$$

Useless variables & productions

• productions that do not generate any useful string with only terminals or is unreachable
• in grammar:   $S\to aSb\text{ | }ϵ\text{ | }A$     $A\to aA$
  $A$ is useless because once it appears it is not possible to eliminate it and derivation never terminates
• in grammar:   $S\to A$     $A\to aA\text{ | }ϵ$     $B\to ba$
  $B$ is useless because it cannot be reached from $S$
• variable is useful when it eventually produces a string with only terminals, i.e. if there exists a derivation from $S\to ...\to w\in L(G)$
• a production $A\to x$ is useless if any of its variables (on left or right) is useless:

  VARIABLES     GRAMMAR    PRODUCTIONS
                S → aSb    
                S → ε      
                S → A  --- useless
    useless --- A → aA --- useless
    useless --- B → C ---- useless
    useless --- C → D ---- useless

Simplification steps

To remove all unwanted variables and productions:

1. remove nullable variables
2. remove unit productions
3. remove useless variables

Removing useless variables

1. find all variables that can produce strings with only terminals or $ϵ$ (possibly useful variables)
   • generate a set of variable names that meet this condition
   • repeat in rounds until no new variables can be found
2. Remove productions that use variables that are not in the set identified in step 1
3. Find all variables reachable from S
   • use dependency graph where nodes are variables to identify unreachable variables
4. Keep only reachable variables to produce final grammar with only useful variables

Chomsky normal form

• simplification is needed to produce a grammar in Chomsky normal form
• in CNF all productions have form:   $A\to BC$   or   $A\to a$
• any grammar that does not generate $ϵ$ has a corresponding CNF representation
  • if not in CNF, we can always obtain equivalent grammar in CNF
• CNF is useful for parsing and proving theorems and easy to find for any CFG that does not generate $ϵ$

Converting to CNF

General procedure for obtaining CNF:

1. remove nullable variables, unit productions, (optionally) useless variables
2. then from every symbol $a$, introduce new variable $T_a$ and add production $T_a\to a$
   • in productions with length $\ge$ 2, replace $a$ with $T_a$
   • productions of form $A\to a$ do not need to change
3. split and replace any production of form $A\to C_1{C}_2\dots C_n$ with:
   
   $A\to C_1{V}_1$
   $V_1\to C_2{V}_2$
   $⋮$
   $V_{n-2}\to C_{n-1}{C}_n$
   
   introducing new intermediate variables $V_1,V_2,\dots ,V_{n-2}$

Example: converting to Chomsky normal form

1. introduce new variables for terminals: $T_a,T_b,T_c$
2. introduce new intermediate variable $V_1$ to break up $S\to AB{T}_a$
3. introduce new intermediate variable $V_2$ to break up $A\to T_a{T}_a{T}_b$

Original ≠ CNF $$\begin{array}{rl}S& \to ABa\\ A& \to aab\\ B& \to Ac\end{array}$$

Step 1 ≠ CNF $$\begin{array}{rl}S& \to AB{T}_a\\ A& \to T_a{T}_a{T}_b\\ B& \to A{T}_c\\ T_a& \to a\\ T_b& \to b\\ T_c& \to c\end{array}$$

Step 2 ≠ CNF $$\begin{array}{rl}S& \to A{V}_1\\ V_1& \to B{T}_a\\ A& \to T_a{T}_a{T}_b\\ B& \to A{T}_c\\ T_a& \to a\\ T_b& \to b\\ T_c& \to c\end{array}$$

Step 3 = CNF $$\begin{array}{rl}S& \to A{V}_1\\ V_1& \to B{T}_a\\ A& \to T_a{V}_2\\ V_2& \to T_a{T}_b\\ B& \to A{T}_c\\ T_a& \to a\\ T_b& \to b\\ T_c& \to c\end{array}$$

Greinbach normal form

• all productions have form $A\to a{V}_1{V}_2\dots V_k$   $k\ge 0$
• GNF is very good for parsing strings, better than Chomsky
• It is difficult to create a grammar in GNF or to convert to it

Example: converting to Greinbach normal form

Original ≠ GNF $$\begin{array}{rl}S& \to abSb\\ S& \to aa\end{array}$$

Final = GNF $$\begin{array}{rl}S& \to a{T}_{b}S{T}_b\\ S& \to a{T}_a\\ T_a& \to a\\ T_b& \to b\end{array}$$