Chomsky normal form

related topics
{math, number, function}
{language, word, form}

In computer science, a context-free grammar is said to be in Chomsky normal form if all of its production rules are of the form:

where A, B and C are nonterminal symbols, α is a terminal symbol (a symbol that represents a constant value), S is the start symbol, and ε is the empty string. Also, neither B nor C may be the start symbol.

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. 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 22 | G | , depending on the transformation algorithm used (Lange and Leiß, 2009).

Contents

Alternative definition

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

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

where A, B and C are nonterminal symbols, and α is a terminal symbol. When using this definition, B or C may be the start symbol.

Converting a grammar to Chomsky Normal Form


Remove every rule with ε 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 ε. If a rule has A as a singleton on its RHS, add a new rule R = A \rightarrow \epsilon unless R has already been removed through this process. For example, examine the following grammar G:

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

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



with A \rightarrow u_1 A_1 , A_1 \rightarrow u_2 A_2 , ... , A_{k-2} \rightarrow u_{k-1} u_k where Ai are new variables.

If u_i \in \Sigma, replace ui in above rules with some new variable vi and add rule v_i \rightarrow u_i.

Full article ▸

related documents
Uncountable set
Nash embedding theorem
Simple LR parser
Divisor
Binary function
Lagrange's theorem (group theory)
Logical disjunction
Complement (set theory)
De Moivre's formula
Greedy algorithm
Lipschitz continuity
Parity (mathematics)
Identity element
Ordered field
Graded algebra
Box-Muller transform
Amicable number
Euphoria (programming language)
Normal subgroup
Kernel (category theory)
Compiler-compiler
PSPACE-complete
Hidden Markov model
Goldbach's weak conjecture
Regular language
Topological ring
Linear congruential generator
CYK algorithm
Twin prime conjecture
PILOT