NON$-$CFLS

EXAMPLE $,2\mathrm{.}36$

Use the pumping lemma to show that the language $B=\{a^n{b}^n{c}^n|n0\}$ is not

context free.

We assume that $B$ is a CFL and obtain a contradiction. Let $p$ be the pumping

length for $B$ that is guaranteed to exist by the pumping lemma. Select the string

$s=a^p{b}^p{c}^p.$ Clearly $s$ is a member of $B$ and of length at least $p.$ The pumping

lemma states that $s$ can be pumped, but we show that it cannot. In other words,

we show that no matter how we divide $s$ into uvxyz, one of the three conditions

of the lemma is violated.NON$-$CFLS

First, condition $2$ stipulates that either $v$ or $y$ is nonempty. Then we consider

one of two cases, depending on whether substrings $v$ and $y$ contain more than

one type of alphabet symbol.

When both $v$ and $y$ contain only one type of alphabet symbol, $v$ does not

contain both a$\text{'}$s and b$\text{'}$s or both b$\text{'}$s and c$\text{'}$s$,$ and the same holds for $y.$ In

this case the string $u{v}^{2}x{y}^{2}z$ cannot contain equal numbers of a$\text{'}$s$,$ b$\text{'}$s$,$ and

c$\text{'}$s$.$ Therefore it cannot be a member of $B.$ That violates condition $1$ of

the lemma and is thus a contradiction.

When either $v$ or $y$ contain more than one type of symbol $u{v}^{2}x{y}^{2}z$ may

contain equal numbers of the three alphabet symbols but not in the correct

order. Hence it cannot be a member of $B$ and a contradiction occurs.NON$-$CFLS

First, condition $2$ stipulates that either $v$ or $y$ is nonempty. Then we consider

one of two cases, depending on whether substrings $v$ and $y$ contain more than

one type of alphabet symbol.

When both $v$ and $y$ contain only one type of alphabet symbol, $v$ does not

contain both a$\text{'}$s and b$\text{'}$s or both b$\text{'}$s and c$\text{'}$s$,$ and the same holds for $y.$ In

this case the string $u{v}^{2}x{y}^{2}z$ cannot contain equal numbers of a$\text{'}$s$,$ b$\text{'}$s$,$ and

c$\text{'}$s$.$ Therefore it cannot be a member of $B.$ That violates condition $1$ of

the lemma and is thus a contradiction.

When either $v$ or $y$ contain more than one type of symbol $u{v}^{2}x{y}^{2}z$ may

contain equal numbers of the three alphabet symbols but not in the correct

order. Hence it cannot be a member of $B$ and a contradiction occurs. $2\mathrm{.}2$ a$.$ Use the languages $A=\{a^m{b}^n{c}^n|m,n0\}$ and $B=\{a^n{b}^n{c}^m|m,n0\}$

together with Example $2\mathrm{.}36$ to show that the class of context$-$free languages

is not closed under intersection.

b$.$ Use part $($a$)$ and DeMorgan's law $($Theorem $0\mathrm{.}20)$ to show that the class of

context$-$free languages is not closed under complementation.