18  Chomsky Normal Form and CFG depuration

In this chapter we introduce some transformations on grammars that could be used as a prepocessing step of some algorithms (e.g. the CYK algorithm Section 17.1) or could simplify inductive arguments.

18.1 Depuration of Grammars

Given a context-free grammar G=(V,\Sigma,P,S), the term depuration refers to the process of constructing an equivalent grammar G' more structured and without clearly redundant variables.

Important

A reference for this part of the course is (Hopcroft et al. 2007, sec. 7.1).

A variable of G is useful if it is involved in a production of a string of only terminal symbols, that is a variable is useful if it is reachable from S and it is productive.

We can define the reachable variables recursively follows: S is reachable from S (clearly), and if A is reachable and we have a rule A\ \boldsymbol{\to}\ \alpha with \alpha\in (V\cup \Sigma)^* then all the variables in \alpha are also reachable. Once we identified the reachable variables R\subseteq V, we can then remove all the the productions B\ \boldsymbol{\to}\ \beta with B\notin R.

We can define productive variables as the ones that eventually are able to generate a word in \Sigma^*. This can be computed using a recursive approach: if A\ \boldsymbol{\to}\ \alpha and \alpha\in \Sigma^*, then A is productive; if A\ \boldsymbol{\to}\ \alpha with \alpha\in (V\cup \Sigma)^* and every variable in \alpha is productive, then A is productive. Once we identified the productive variables R\subseteq V, we can then remove all the the productions B\ \boldsymbol{\to}\ \beta with B\notin R or with some variable in \beta not in R.

Warning

The order in which we perform the operations matters. Consider the grammar \begin{array}{lcl} S\ &\boldsymbol{\to}&\ AB\ \vert\ \textcolor{darkred}{\mathtt{a}}\\ B\ &\boldsymbol{\to}&\ \textcolor{darkred}{\mathtt{b}} \end{array} if we remove unreachable variables first and then the unproductive variables we still get a grammar with useless symbols. You need to remove the unproductive variables first, and then the unreachable ones.

A production of the form A\ \boldsymbol{\to}\ \varepsilon is a \varepsilon-production.

A variable A is nullable if it can derive the empty word \varepsilon. We can define recursively nullable variables: if A\ \boldsymbol{\to}\ \varepsilon is a production, then A is nullable; if A\ \boldsymbol{\to}\ \alpha and \alpha\in V^* with all the variables in \alpha nullable then A is also nullable.

Once we identified the nullable variables, we can then remove all productions of the form A\ \boldsymbol{\to}\ \varepsilon (with A\neq S), and for every production A\ \boldsymbol{\to}\ \alpha B\beta with B nullable, add the production A\ \boldsymbol{\to}\ \alpha\beta, and keep symplifying the new set of productions. Unless A=S, never write productions A\ \boldsymbol{\to}\ \varepsilon that might occur.

Example 18.1 For example removing the \varepsilon-productions from the grammar \begin{array}{lcl} S\ &\boldsymbol{\to}&\ ABC\ \vert\ \varepsilon\\ A\ &\boldsymbol{\to}&\ \varepsilon\\ B\ &\boldsymbol{\to}&\ \varepsilon\\ C\ &\boldsymbol{\to}&\ \varepsilon \end{array} gives the grammar S\ \boldsymbol{\to}\ ABC\ \vert\ AB\ \vert\ AC\ \vert\ BC\ \vert\ A \ \vert\ B\ \vert\ C\ \vert\ \varepsilon. Where clearly the variables A,B,C are useless.

A production of the form A\ \boldsymbol{\to}\ B is called unit production. The variable A is clearly redundant, its only job is to get expanded into B. Productions of the form A\ \boldsymbol{\to}\ B where a is a terminal are not unit productions. The technique to remove all unit productions that simply expands them until they disappear often works but not always. Consider for instance the productions A\ \boldsymbol{\to}\ B, B\ \boldsymbol{\to}\ C, C\ \boldsymbol{\to}\ A. What works is the following:

  • find all unit pairs, i.e. pairs of variables (A,B) where B can be derived from A using only unit productions. As for the other cases, there is an inductive construction of unit pairs: for each variable A, (A,A) is a unit pair; and if (A,B) is a unit pair and B\ \boldsymbol{\to}\ C is a production, the (A,C) is also a unit pair.
  • for each unit pair (A,B) add all the productions A\ \boldsymbol{\to}\ \alpha to G', where B\ \boldsymbol{\to}\ \alpha is a nonunit production in \mathcal P. For the unit pair (A,A) we add as productions in G' all nonunit productions of A.

Example 18.2 For example, removing the unit rules from the grammar \begin{array}{lcl} S\ &\boldsymbol{\to}&\ X_1\\ X_1\ &\boldsymbol{\to}&\ X_2\\ \vdots &\\ X_{n-1}\ &\boldsymbol{\to}&\ X_n\\ X_n\ &\boldsymbol{\to}&\ w \end{array} with w\in \Sigma^*, gives the grammar

\begin{array}{lcl} S\ &\boldsymbol{\to}&\ w\\ X_1\ &\boldsymbol{\to}&\ w\\ \vdots &\\ X_{n-1}\ &\boldsymbol{\to}&\ w\\ X_n\ &\boldsymbol{\to}&\ w \end{array}

The transformations above might interfere with each other un-doing the work of previous transformations.

Exercise 18.1 Find an order in which to apply the removal of useless variables, \varepsilon-productions, and unit productions to obtain an equivalent grammar.

18.2 Chomsky Normal Form

We conclude this chapter with a normal form for context-free grammars: the Chomsky Normal Form. This will be useful in some theoretical concstructions such as Example 21.1 or the Pumping Lemma (Lemma 21.1).

Definition 18.1 A grammar G=(V,\Sigma,R,S) is in Chomsky Normal Form if all its rules have one of the following forms

  • S\ \boldsymbol{\to}\ \varepsilon, or
  • A\ \boldsymbol{\to}\ \textcolor{darkred}{\mathtt{s}} with \textcolor{darkred}{\mathtt{s}}\in \Sigma, or
  • A\ \boldsymbol{\to}\ BC, with B,C\in V but B,C\neq S.

Theorem 18.1 Given a context-free grammar G, there is another context free grammar G' in Chomsky Normal Form s.t. \mathscr{L}(G)=\mathscr{L}(G').

Transforming a grammar G into an equivalent one in Chomsky Normal Form is an algorithmic procedure:

  • Step 1: Create a new start symbol. Just have a new start symbol S' and add the production S'\ \boldsymbol{\to}\ S.
  • Step 2: Change nonsolitary terminals into variables. Change each rule of the form A\ \boldsymbol{\to}\ \alpha\textcolor{darkred}{\mathtt{s}}\beta into A\ \boldsymbol{\to}\ \alpha N_s \beta and N_s\ \boldsymbol{\to}\ \textcolor{darkred}{\mathtt{s}}. Do this to all the rules removing terminals from RHS of the rules (unless it is the only symbol).
  • Step3: Make RHS at most binary. Transform each rule of the form A\ \boldsymbol{\to}\ X_1X_2\cdots X_n with n\geq 3 into \begin{array}{lcl} A\ &\boldsymbol{\to}&\ X_1A_1\\ A_1\ &\boldsymbol{\to}&\ X_2A_2\\ \vdots&&\\ A_{n-3}\ &\boldsymbol{\to}&\ X_{n-2}A_{n-2}\\ A_{n-2}\ &\boldsymbol{\to}&\ X_{n-1}X_n \end{array}
  • Step 4: Eliminate all \varepsilon-productions. As we saw in Section 18.1.
  • Step 5: Eliminate unit productions. As we saw in Section 18.1.

Exercise 18.2 Show that the grammar constructed in the proof of Theorem 18.1 is indeed in Chomsky Normal Form and equivalent to G.

Exercise 18.3 Given a context-free grammar G, how many symbols could have the equivalent context-free grammar in Chomsky Normal Form obtained using the algorithm from the proof of Theorem 18.1 (w.r.t. the number of symbols in G)? What if you exchange the order of steps 3 and 4? Is the algorithm still correct? What is the cost now?