\( \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 Answer
\( \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 [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.