Show Question
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 both appear as LHS symbols in another rule excluding the start rule, or
2. one symbol that does not appear as a LHS symbol.

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.

### Chomsky normal form (standard definition)

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

\begin{align*} S &\to BC \\ S &\to a \\ A &\to BC \\ A &\to a \\ \end{align*}

where $$a$$ is a terminal symbol, $$S$$ is the start symbol and $$A, B$$ and $$C$$ are non-terminal symbols.

It is assumed that $$\varepsilon$$ can appear on the RHS of a rule.

## Context

grammar → context-free grammar → context-free language → context-free language closure → Chomsky normal form → pushdown automaton → deterministic pushdown automaton