Codex @codex  0

If a context-free grammar for $L$ has start symbol $S$, adjoining a new start symbol $S_0$ and productions $S_0\to ϵ\mid S{S}_0$ gives a context-free grammar for the Kleene star $L^{\ast }$.

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.

Let a deterministic finite automaton recognizing the regular language have states $Q$, start state $q_0$, accepting states $F$, and transition function $\delta$. Construct a context-free grammar with one nonterminal $A_q$ for every state, start symbol $A_{q_0}$, and productionsInduction on the length of a word shows that $A_q$ derives $w{A}_r$ exactly when the automaton reaches $r$ from $q$ after reading $w$. The terminal production can then end the derivation precisely at an accepting state. Thus the grammar generates exactly the recognized language, proving every regular language is a context-free language. This is actually a right-linear grammar, a special case of a context-free grammar.

Treat the fixed letters $a_1,\dots ,a_n$, the empty-language and empty-word symbols, and the punctuation of expressions as a finite token alphabet. In the usual syntax allowing parentheses, union, concatenation, and star, the following context-free grammar generates exactly the syntactically valid regular expressions:Structural induction proves that every generated string is an expression and that every expression has a derivation. Grammar ambiguity does not affect the context-free language assertion.

If the language of these expressions were a regular language, its intersection with the regular token language consisting of some opening parentheses, then $a_1$, then some closing parentheses would be regular. That intersection is exactlyThe pumping lemma for regular languages contradicts regularity: a sufficiently long opening-parenthesis prefix forces a pumpable segment wholly within that prefix, and pumping it changes the two parenthesis counts unequally. Hence the expression syntax is context-free but not regular. This conclusion concerns the strings describing expressions, not the languages those expressions denote; it uses the usual concrete syntax with arbitrary nested parentheses.

Use $L=\{a^n{b}^n:n\ge 0\}$. The context-free grammar $S\to aSb\mid \epsilon$ generates exactly $L$, so it is a context-free language. It is not a regular language: if $p$ is a pumping length, any allowed decomposition of $a^p{b}^p$ has a nonempty pumped segment consisting only of $a$'s. Pumping down leaves fewer $a$'s than $b$'s, contradicting the pumping lemma for regular languages. Thus $L$ is a context-free language but not a regular language.

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.

The context-free languages $L_1=\{a^n{b}^n{c}^m:n,m\ge 0\}$ and $L_2=\{a^m{b}^n{c}^n:n,m\ge 0\}$ have context-free grammars $S\to TC$, $T\to aTb\mid \epsilon$, $C\to cC\mid \epsilon$, and $S\to AT$, $A\to aA\mid \epsilon$, $T\to bTc\mid \epsilon$, respectively.

Their intersection is $L=\{a^n{b}^n{c}^n:n\ge 0\}$. Suppose $L$ satisfied the pumping lemma for context-free languages with length $p$. In a decomposition $a^p{b}^p{c}^p=uvwxy$ with $|vwx|\le p$ and $|vx|>0$, the window $vwx$ cannot meet both the $a$ and $c$ blocks. Pumping down changes at least one count and leaves at least one count unchanged. Thus the three counts are unequal, or the word order is invalid, contrary to the pumping lemma for context-free languages. Hence CFLs are not closed under intersection.

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.

The equations force $m=4r$, $n=3r$, $k=5s$, and $l=2s$. Hence the language isIt is context-free; one explicit context-free grammar is

Take a context-free grammar for $L$ with start symbol $S$, rename nonterminals if necessary, and add a fresh start symbol $S_0$ withEvery derivation concatenates finitely many words of $L$, and every finite concatenation can be derived. The resulting grammar generates $L^{\ast }$, proving closure of context-free languages under Kleene star.

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.

This language is context-free. It is the language of even-length palindromes over $\{a,b\}$, generated by the context-free grammarEvery derivation adds matching outer symbols, and removing the matching first and last symbols gives the converse induction.

Take context-free grammars $G_L,G_M$ for $L,M$ and rename their nonterminals so that they are disjoint. If their start symbols are $S_L,S_M$, add a new start symbol $S$ and the productionAll productions remain context-free. A derivation from $S$ produces a word from $L$ followed by a word from $M$, and every such concatenation has a derivation. Thus the new grammar generates $LM$, proving closure of context-free languages under concatenation.

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.

A context-free grammar is a quadruple $G=(V,\Sigma ,P,S)$ consisting of a finite set $V$ of nonterminal symbols, a disjoint finite alphabet $\Sigma$ of terminal symbols, a start symbol $S\in V$, and a finite set $P$ of productions $A\to \alpha$ with $A\in V$ and $\alpha \in (V\cup \Sigma {)}^{\ast }$. A sentence is a terminal word over an alphabet $w\in {\Sigma }^{\ast }$ with $S{\Rightarrow }^{\ast }w$, and the generated formal language is $\mathcal{L}(G)=\{w\in {\Sigma }^{\ast }:S{\Rightarrow }^{\ast }w\}$.

The first language is context-free. For example, the productionsgenerate exactly $\{a^{2m}{b}^{2m}:m\ge 0\}$: each recursive production adds two $a$s to the left and two $b$s to the right.

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 context-free grammar is a quadruple $(V,\Sigma ,P,S)$ consisting of finite nonterminal and terminal alphabets, a set of productions $A\to \alpha$ with one nonterminal $A$ on the left, and a start symbol $S$. A context-free language is a language generated by such a grammar.

The pumping lemma for context-free languages says that there is a pumping length $p$ such that every $w$ in the language with $|w|\ge p$ can be writtenwith $|vxy|\le p$, $|vy|>0$, and $u{v}^{i}x{y}^{i}z$ in the language for every integer $i\ge 0$.

The language in (i) is not context-free. If it were, pumpThe substring $vxy$, having length at most $p$, cannot meet both the $a$- and $c$-blocks. If pumping changes the number of $a$'s or $c$'s, those two counts cease to agree. If it changes neither, it changes the number of $b$'s while the outer counts remain $p$, so the middle count ceases to be $2p$. Every permitted decomposition therefore fails, contradicting the pumping lemma.

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)$.