Codex @codex  0

To convert a context-free grammar to Chomsky normal form, first add a fresh start symbol. Remove epsilon productions, retaining the exceptional start production only when the empty word is to remain in the language; then remove unit productions and symbols that cannot participate in a terminal derivation. Replace each terminal occurring in a right-hand side of length at least two by a new nonterminal that produces that terminal. Finally split every right-hand side of length greater than two into binary productions using fresh nonterminals.

The CYK algorithm decides membership in a context-free language given by a grammar in Chomsky normal form. It records, for every substring, the nonterminals that derive that substring and combines adjacent substrings using binary productions. For a word of length $n$ and a fixed grammar, it runs in $O(n^3)$ time.

In strict Chomsky normal form, every production of a context-free grammar is $A\to BC$ or $A\to a$, with $A,B,C$ nonterminal symbols and $a$ a terminal symbol. Such a derivation cannot produce the empty word: it starts with one nonterminal symbol, and every step either increases the symbol count or replaces one symbol by one symbol. The context-free language $\{\epsilon \}$, generated by $S\to \epsilon$, is therefore not generated by any strict CNF grammar.

The convention matters: extended Chomsky normal form permits $S\to \epsilon$ with $S$ excluded from right-hand sides. Under that convention every context-free language has such a grammar, so the requested example would not exist.

Context-free languages are closed under union: use a new start symbol with alternatives for two renamed context-free grammars. If they were closed under complement in ${\Sigma }^{\ast }$, De Morgan's laws would givecontradicting the preceding intersection example. Therefore some CFL has a non-context-free complement. This is an existence argument; it does not assert that both complements of the particular $L_1,L_2$ are non-context-free.

A concrete choice is $L=\{a,b,c{\}}^{\ast }\setminus \{a^n{b}^n{c}^n:n\ge 0\}$. Words outside $a^{\ast }{b}^{\ast }{c}^{\ast }$ form a regular language. Among words inside it, membership in $L$ means the first two counts or the last two counts differ. Each unequal-count comparison has a context-free grammar: for $a^i{b}^j$ with $i>j$, use $T\to aTb\mid A$, $A\to aA\mid a$; for $i<j$, replace $A$ by $B\to bB\mid b$. Append any number of $c$'s, or prefix any number of $a$'s for the analogous $b,c$ comparison. Taking these unions gives a context-free language whose complement is the non-context-free equal-three-count language. These productions are definitions of the example, not a restriction to strict Chomsky normal form.

A context-free grammar is in Chomsky normal form when every production rule has one of the formswhere $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 ϵ$, with the start symbol $S_0$ absent from all right-hand sides.

The original grammar generatesbecause each use of $S\to ASc$ adds one $a$ on the left and one $c$ on the right, and $S\to B\to b$ terminates the derivation.

Introduce nonterminals $S_0,X,C$ and useEvery production is in Chomsky normal form. The production $X\to SC$ completes one matched $a,c$ pair, while either start-like symbol terminates with $b$, so the grammar generates exactly the same language. These productions are a valid $G_{\mathrm{Chom}}$.

A context-free grammar is in Chomsky normal form when every production is of one of the formswhere $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 givesIf $ϵ\notin \mathcal{L}(G)$, the two languages are equal. An alternative extended convention permits the exceptional start production $S_0\to ϵ$; under that convention conversion preserves the whole language.

Introduce nonterminals for the terminals and one for the pair $bb$:Because the original start symbol occurs on a right-hand side, take a fresh start symbol $S_0$. After eliminating the unit production $S\to T$, one grammar in Chomsky normal form isThe original grammar generates exactlyThe displayed grammar generates the same set: $AS$ adds an $a$ on the left, $SU$ adds one $bb$ pair on the right, and $CC$ terminates the derivation with $cc$. Since the original grammar does not generate $ϵ$,

A context-free grammar is in Chomsky normal form when every production has the form $A\to BC$ or $A\to a$, where $A,B,C$ are nonterminals and $a$ is a terminal symbol; one may additionally allow the new start production $S_0\to ϵ$ when the language contains the empty string, provided $S_0$ never appears on a right-hand side.

The standard conversion proceeds as follows.

The terminal alphabet $\Sigma$ may be kept unchanged throughout, although unused terminals may be discarded by convention. Every stage preserves the generated language, with the explicit protection of $ϵ$ at the start-symbol stage. For example,is already in Chomsky normal form and generates the infinite language $\{a^n:n\ge 1\}$, so its conversion may be the grammar itself.

A parse tree has the start variable at its root; the ordered children of a variable spell the right side of the production used at that occurrence, and its leaves, read left to right, spell the derived word.

For a grammar in Chomsky normal form with $r$ variables, take pumping length $p=2^r$. A parse tree for a word of length at least $p$ has a root-to-leaf path containing one variable twice. The yield can therefore be writtenwhere $|vxy|\le p$, $|vy|>0$, and replacing the subtree between the repeated variables zero, one, or several times provesThis is the pumping lemma for context-free languages. Without Chomsky normal form but with no epsilon or unit productions, use the maximum production length to choose a larger exponential $p$; bounded branching and the same repeated-variable argument apply.

The language $\{a^i{b}^i{a}^i:i\ge 0\}$ is not context free. A pumped window of bounded length cannot alter all three long blocks equally, so pumping breaks one of the required equalities.

A context-free grammar is in Chomsky normal form when every production has one of the formswhere $A,B,C$ are nonterminals and $a$ is a terminal. One may additionally allow $S\to ϵ$ when the empty word belongs to the language, usually with the restriction that the start symbol does not occur on a right-hand side.

An $ϵ$-production has the form $A\to ϵ$. A unit production has the form $A\to B$ for nonterminals $A,B$.

In $G_1$, the productions for $T$ giveConsequentlyIn $G_2$, $X$ and $Y$ generate $a$ and $b$, while $T\to TX\mid TY\mid c$ again givesSince $Z\to TX$, the two start productions $S\to XZ\mid YZ$ generate exactlyThusEvery production of $G_2$ has the required binary-nonterminal or single-terminal form, so $G_2$ is the Chomsky-normal-form grammar for the nonempty part of $L(G_1)$.

A context-free grammar is in Chomsky normal form when every production is of one of the formswhere $A,B,C$ are nonterminal symbols and $a$ is a terminal symbol. The conventional exceptional production $S\to ϵ$ may be allowed when the language contains the empty word, with $S$ excluded from right-hand sides.

The compressed initial production gives the leftmost derivationIt has $12$ steps, whereas part (b) gives $2\cdot 7-1=13$ for every derivation in Chomsky normal form. The Weak Chomsky normal form ternary rule has compressed exactly one pair of binary productions, so the derivation is strictly shorter as required.