Chomsky normal form

In formal language theory, a context-free grammar is said to be in Chomsky normal form (named for Noam Chomsky) if all of its production rulesTemplate:Disambiguation needed are of the form:

$A\rightarrow BC$ or

$A\rightarrow \alpha$ or

$S\rightarrow \varepsilon$,

where $A$, $B$ and $C$ are nonterminal symbols, $\alpha$ is a terminal symbol (a symbol that represents a constant value), $S$ is the start symbol, and $\varepsilon$ is the empty string. Also, neither $B$ nor $C$ may be the start symbol, and the third production rule can only appear if $\varepsilon$ is in $L(G)$, namely, the language produced by the context-free grammar $G$.

Every grammar in Chomsky normal form is context-free, and conversely, every context-free grammar can be transformed into an equivalent one which is in Chomsky normal form. Several algorithms for performing such a transformation are known. Transformations are described in most textbooks on automata theory, such as Hopcroft and Ullman, 1979. As pointed out by Lange and Leiß, the drawback of these transformations is that they can lead to an undesirable bloat in grammar size. The size of a grammar is the sum of the sizes of its production rules, where the size of a rule is one plus the length of its right-hand side. Using $|G|$ to denote the size of the original grammar $G$, the size blow-up in the worst case may range from $|G|^{2}$ to $2^{2|G|}$, depending on the transformation algorithm used.

Alternative definition

Another way to define the Chomsky normal form (e.g., Hopcroft and Ullman 1978,and Hopcroft et al. 2006) is:

A formal grammar is in Chomsky reduced form if all of its production rules are of the form:

$A\rightarrow \,BC$ or

$A\rightarrow \,\alpha$,

where $A$, $B$ and $C$ are nonterminal symbols, and $\alpha$ is a terminal symbol. When using this definition, $B$ or $C$ may be the start symbol. Only those context-free grammars which do not generate the empty string can be transformed into Chomsky reduced form.

Converting a grammar to Chomsky Normal Form

1. Introduce $S_{0}$

   Introduce a new start variable, $S_{0}$ and a new rule $S_{0}\rightarrow S$ where $S$ is the previous start variable.

2. Eliminate all $\varepsilon$ rules

   $\varepsilon$ rules are rules of the form $A\rightarrow \varepsilon$, where $A\not =S_{0}$ and $A\in V$, where $V$ is the CFG's variable alphabet.

   Remove every rule with $\varepsilon$ on its right hand side (RHS). For each rule with $A$ in its RHS, add a set of new rules consisting of the different possible combinations of $A$ replaced or not replaced with $\varepsilon$. If a rule has $A$ as a singleton on its RHS, add a new rule $R=A\rightarrow \varepsilon$ unless $R$ has already been removed through this process. For example, examine the following grammar $G$:

   $S\rightarrow AbA\mid B$

   $B\rightarrow b\mid c$

   $A\rightarrow \varepsilon$

   $G$ has one $\varepsilon$ rule. When the $A\rightarrow \varepsilon$ is removed, we get the following:

   $S\rightarrow AbA\mid Ab\mid bA\mid b\mid B$

   $B\rightarrow b\mid c$

   Notice that we have to account for all possibilities of $A\rightarrow \varepsilon$ and so we actually end up adding 3 rules.

3. Eliminate all unit rules

   $A\rightarrow B;A,B\in V$

   After all the $\varepsilon$ rules have been removed, you can begin removing unit rules, or rules whose RHS contains one variable and no terminals (which is inconsistent with CNF).

   To remove $A\rightarrow B$

   $\forall B\rightarrow U$, where $U$ is a string of variables and terminals, add rule $A\rightarrow U$ unless this is a unit rule which has already been removed.

4. Clean up the remaining rules that are not in Chomsky normal form.

   Replace $A\rightarrow u_{1}u_{2}\dotso u_{k},k\geq 3,u_{1}\in V\cup \Sigma$ with $A\rightarrow u_{1}A_{1},A_{1}\rightarrow u_{2}A_{2},\dotsc ,A_{k-2}\rightarrow u_{k-1}u_{k}$, where $A_{i}$ are new variables.

   If $u_{i}\in \Sigma$, replace $u_{i}$ in above rules with some new variable $V_{i}$ and add rule $V_{i}\rightarrow u_{i}$.

See also

• Backus-Naur form
• CYK algorithm
• Greibach normal form
• Kuroda normal form

References

• John E. Hopcroft and Jeffrey D. Ullman, Introduction to Automata Theory, Languages and Computation, Addison-Wesley Publishing, Reading Massachusetts, 1979. ISBN 0-201-02988-X. (See chapter 4.)
• 20 year-old Real Estate Agent Rusty from Saint-Paul, has hobbies and interests which includes monopoly, property developers in singapore and poker. Will soon undertake a contiki trip that may include going to the Lower Valley of the Omo.
  
  My blog: http://www.primaboinca.com/view_profile.php?userid=5889534 (Pages 98–101 of section 2.1: context-free grammars. Page 156.)
• 20 year-old Real Estate Agent Rusty from Saint-Paul, has hobbies and interests which includes monopoly, property developers in singapore and poker. Will soon undertake a contiki trip that may include going to the Lower Valley of the Omo.
  
  My blog: http://www.primaboinca.com/view_profile.php?userid=5889534 (Pages 237–240 of section 6.6: simplified forms and normal forms.)
• 20 year-old Real Estate Agent Rusty from Saint-Paul, has hobbies and interests which includes monopoly, property developers in singapore and poker. Will soon undertake a contiki trip that may include going to the Lower Valley of the Omo.
  
  My blog: http://www.primaboinca.com/view_profile.php?userid=5889534 (Pages 103–106.)
• Cole, Richard. Converting CFGs to CNF (Chomsky Normal Form), October 17, 2007. (pdf)
• Sipser, Michael. Introduction to the Theory of Computation, 2nd edition.