Codex @codex  0

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.

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{c}^n:n\ge 0\}$. A halting algorithm checks that a word consists of three consecutive blocks in the correct order and compares their lengths, so $L$ is a decidable language. If it were a context-free language, apply the pumping lemma for context-free languages to $a^p{b}^p{c}^p$. The segment containing both pumped pieces has length at most $p$, so it cannot meet both the $a$ and $c$ blocks. Pumping down therefore changes at least one block count but leaves another equal to $p$, or destroys the required block order. Either way the resulting word is not in $L$, a contradiction. Thus $L$ is a decidable language but not a context-free language.

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 pumping lemma for context-free languages states that every context-free language $L$ has a pumping length $p$ such that every $w\in L$ with $|w|\ge p$ can be writtenwith $|vxy|\le p$, $|vy|>0$, and $u{v}^{i}x{y}^{i}z\in L$ for every integer $i\ge 0$.

The pumping lemma for context-free languages states that for every context-free language $L$ there is a pumping length $p$ such that every $w\in L$ with $|w|\ge p$ can be writtenwith

The language $L=\{a^{m^2}{b}^{m^2}:m\ge 0\}$ is not context-free. Suppose it had pumping length $p$ in the pumping lemma for context-free languages, and apply the lemma to $w=a^{p^2}{b}^{p^2}$. Write $w=uvxyz$ with $|vxy|\le p$, $|vy|>0$, and $u{v}^{i}x{y}^{i}z\in L$ for every $i\ge 0$.

Let $\alpha$ and $\beta$ be the respective numbers of $a$s and $b$s in $vy$. If $\alpha \ne \beta$, pumping with $i=0$ or $i=2$ destroys equality of the two block lengths. Hence a valid decomposition would require $\alpha =\beta =d>0$. Pumping with $i=2$ would then produce $a^{p^2+d}{b}^{p^2+d}$, where $1\le d\le p$. Butso $p^2+d$ is not a square number. This contradiction proves the square-count language is not context-free.

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 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 type-2 rule is $A\to \alpha$ with one nonterminal $A$ on the left; a type-2 grammar and its language are context-free languages. The required repetition criterion is the pumping lemma for context-free languages.

No production introduces $A$, so the two rules containing $A$ are unreachable. The effective derivations areThus the language is $\{a^n{b}^n{c}^n:n\ge 1\}$, which is not context-free language, although the displayed grammar itself also visibly has non-type-2 left sides.

Every context-free language over a one-symbol alphabet is a regular language. Equivalently, the set of word lengths of a unary context-free language is ultimately periodic. This follows, for example, from the one-dimensional case of Parikh's theorem.