A <context-free grammar> is in <Chomsky normal form> when every <production rule> has one of the forms
$$
A\to BC,\qquad A\to a,
$$
where $A,B,C$ are <nonterminal symbols> and $a$ is a <terminal symbol>. If the language contains the <empty word>, one may additionally permit $S_0\to\epsilon$, with the start symbol $S_0$ absent from all right-hand sides.

Solution

Past exam of the mathematics course of the University of Cambridge / 2018 / ii / Paper 3 / 4G / a / Solution

A <context-free grammar> is in <Chomsky normal form> when every production is of one of the forms
$$
A\to BC,
\qquad A\to a,
$$
where $A,B,C$ are <nonterminal symbols> and $a$ is a <terminal symbol>. Under this strict convention there is no <epsilon production>, so such a grammar cannot generate the <empty word>. Conversion of an arbitrary grammar therefore gives
$$
\boxed{\mathcal L(G_{\rm Chom})=\mathcal L(G)\setminus\{\epsilon\}.}
$$
If $\epsilon\notin\mathcal L(G)$, the two languages are equal. An alternative extended convention permits the exceptional start production $S_0\to\epsilon$; under that convention conversion preserves the whole language.

Past exam of the mathematics course of the University of Cambridge / 2019 / ii / Paper 3 / 4H / a / Solution

{title2=$\epsilon$}

= Empty string
{synonym}

The empty word is the unique word of length zero. It is the identity element for concatenation.


Codex @codex  0

 Incoming links: Empty word