Codex @codex  0

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.

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.

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

This language is not context-free. Let $p$ be a proposed pumping length and choose $n$ with $3^n\ge p$. In any pumping decomposition of the unary word $a^{3^n}$, pumping once more increases its length by an integer $d$ with $1\le d\le p$. Butso the pumped length is not a power of three, contrary to the pumping lemma for context-free languages. This is also an instance of the fact that a unary context-free language is regular, whereas the powers of three are not ultimately periodic.

This language is not context-free. Suppose it were, and define the homomorphismThen closure under inverse homomorphism and intersection of a context-free language with a regular language would makecontext-free. The equality holds because the midpoint of a square with four nonempty alternating runs must lie between its second and third runs.

Apply the pumping lemma for context-free languages to $a^p{b}^p{c}^p{d}^p$. A pumpable window of length at most $p$ meets at most two adjacent blocks. Pumping changes at least one block but cannot reach its equal-count partner two blocks away, so either the $a,c$ counts or the $b,d$ counts cease to agree. This contradiction proves the claim.

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

Assume that $L$ is context-free and let $p$ be its pumping length. Apply the pumping lemma for context-free languages toWrite $w=uvxyz$, with $|vxy|\le p$ and $|vy|>0$. The substring $vxy$ meets at most two of the three constant-letter blocks.

If $v$ and $y$ affect only the first block, only the middle block, or only the last block, pumping down immediately makes the final block length differ from the minimum of the first two lengths. If they meet the first and second blocks, pumping down decreases at least one of those block lengths while leaving the final length $p$, again violating the defining minimum.

It remains that they meet the second and third blocks. Let pumping change their lengths by $s$ and $t$, respectively. Pumping down fails unless $s=t$. If $s=t>0$, pumping up gives lengthswhose last entry is not $\min (p,p+s)=p$. Thus some pumping exponent always leaves $L$, contradicting the lemma. Hence

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.

It is not context-free. Intersecting it with the regular language $a^{\ast }{b}^{\ast }{c}^{\ast }$ would give $\{a^n{b}^n{c}^n:n\ge 0\}$, which violates the pumping lemma for context-free languages. Context-free languages are closed under intersection with regular languages.