Math and science::Theory of Computation

Chomsky normal form

Context-free grammars can differ in their rule sets yet generate the same language. From the set of such equivalent grammars, some are easier to reason about.

One type of context-free grammar that is convenient to work with is the Chomsky normal form.

Chomsky normal form

A context-free grammar is in Chomsky normal form iff the RHS of every rule is either:

1. two symbols that [what?], or
2. one symbol that [what?].

The above definition is non-standard. The more common definition is on the back side.

There is an important theorem regarding Chomsky normal form below. Can you remember it?

Any context-free language is generated by a context-free grammar in Chomsky normal form.