Problem 2 - Context-free Grammars

For languages on $\Sigma = \{ a, b, c \}$, prove the following:

1.

$\{ a^m b^n c^{m+n} \; \vert \; m,n \geq 1 \}$ is context-free.

2.

$\{ a^m b^n c^{mn} \; \vert \; m, n \geq 1 \}$ is not context-free.

1.

We shall prove that the context-free grammar $G = (V, T, P, S)$ where

• $V = \{A, B\}$
• $T = \{a, b, c\}$
• $P = \{S \rightarrow aAc \; \vert \; A \rightarrow aAc \; \vert \; bBc, B \rightarrow bBc \; \vert \; \epsilon \}$
• $S$ is the axiom.

generates the first language.

Let $w = a^m b^n c^{m+n}$ be a word of $\{ a^m b^n c^{m+n} \; \vert \; m,n \geq 1 \}$. Then, $w$ can be derivated from $S$ by the following sequence of reduction $S \Rightarrow aAc \Rightarrow^{m-1} a^m A c^m \Rightarrow a^m bBc c^m \Rightarrow^{n-1} a^m b^n B c^{m+n} \Rightarrow w$ by using first $m$ times the production $A\rightarrow aAc$ and then $n$ times the production $B\rightarrow bBc$. Thus, the language is at least a subset of $L(G)$.

The sortest word that can be produced is $abcc$ of length 4. And that is also by definition of $\{ a^m b^n c^{m+n} \; \vert \; m,n \geq 1 \}$ the shortest word from the language. By construction of the grammar, all the derivations have the same scheme. A word is guaranteed to have at least one leftmost $a$ and one rightmost $c$. Then it can go through a sequence of derivations adding at the same time one $a$ on the left and one $c$ one the right. To terminate, a derivation must use the $A\rightarrow bBc$ production that guarantees the word to have at least one $b$ between the $a$'s and the $c$'s (together with one $c$ so that the property that the number of $a$ plus the number of $b$ is equal to the number of $c$ is always true). Before reaching the final derivation (the $\epsilon$ one), the derivation yields $b$'s at the center together with $c$'s (always taking care of the above property) so that all the words derived from $S$ are words of $\{ a^m b^n c^{m+n} \; \vert \; m,n \geq 1 \}$. Thus, $L(G)$ is a subset of the language and in fact $L(G) = \{a^mb^nc^{m+n}\;\vert\;m,n\geq 1\}$.

2.

Let $N$ be the constant of the pumping lemma. We have $a^Nb^Nc^{NN}$ in the language and, by the pumping lemma, it can be said that $a^Nb^Nc^{NN} = uvwxy$ with $\vert vx\vert \geq 1$ and $\vert vwx\vert \leq N$. If $i\geq 0$, then $uv^iwx^iy$ is still a word of the language (this is the pumping lemma for CFL).

Many situations may occur:

• $v$ and/or $x$ may consist of only $a$'s, of only $b$'s or of only $c$'s. In this case, $uv^0wx^0y = uwy$ cannot be a word of the language since it won't verify the property that the number of $a$'s times the number of $b$'s is equal to the number of $c$'s.
• $v$ and $x$ can be a word of the form $a^kb^l$ $0\leq k,l\leq N$ (but both $v$ and $x$ cannot be empty words). For example, $v$ may consist of $a$'s and $x$ of $b$'s, or $v$ may be of the form $a^kb^l$ $k,l\geq 1$ while $x$ consists of $b$'s only, or $v$ may consist of $a$'s only whereas $x = a^kb^l$ $k,l\geq 1$. In this case also, the word $uv^0wx^0y = uwy$ cannot be a word of the language since the number of $a$'s and/or $b$'s may be altered so that the property of the language are vialoted.
• The situation is quite similar if $v$ and $x$ can be a word of the form $b^kc^l$ $0\leq k,l\leq N$ (but both $v$ and $x$ cannot be empty words).

The situation where $v$ and $x$ are shared between $a$'s and $c$'s cannot occur since $\vert vwyx\vert \leq N$. Since we have a contradiction in each possible situation, we conclude that the language proposed is not regular.