\( \newcommand{\matr}[1] {\mathbf{#1}} \newcommand{\vertbar} {\rule[-1ex]{0.5pt}{2.5ex}} \newcommand{\horzbar} {\rule[.5ex]{2.5ex}{0.5pt}} \)
deepdream of a sidewalk
Show Question
\( \newcommand{\cat}[1] {\mathrm{#1}} \newcommand{\catobj}[1] {\operatorname{Obj}(\mathrm{#1})} \newcommand{\cathom}[1] {\operatorname{Hom}_{\cat{#1}}} \newcommand{\multiBetaReduction}[0] {\twoheadrightarrow_{\beta}} \newcommand{\betaReduction}[0] {\rightarrow_{\beta}} \newcommand{\betaEq}[0] {=_{\beta}} \newcommand{\string}[1] {\texttt{"}\mathtt{#1}\texttt{"}} \newcommand{\symbolq}[1] {\texttt{`}\mathtt{#1}\texttt{'}} \)
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