$L=${$a^nb^nc^n : n \geq 0 $} CFG Recognizing

Question

Suppose $L=${$a^nb^nc^n : n \geq 0 $}

and

I. $h(L), h(a)=a, h(b)=bb, h(c)=b$

II. $L^R$

III. $L^*$

IV. $h(L), h(a)=a, h(b)=bb, h(c)=a$

Why just I is a CFG and other is not? anyone can help me to recognize other language that gives in this text?

thanks to all.

Answer 1

Popular tool for proving a language is not context-free is the Pumping Lemma. Let's recall its statement:

If $L$ is a context-free language, there exists $p\geq 1$ such that each $s\in L$ with $\left|s\right|\geq p$ can be written as $$s=xuyvz$$ in such a way, that

1. $\left|uyv\right|\leq p$
2. $\left|uv\right|\geq 0$ (i.e. at least one of $u$, $v$ is nonempty)
3. for each $n\geq 0$ we have $xu^nyv^nz\in L$

As an example, we can use it to show that $L=\left\{a^nb^nc^n\colon n\geq 0\right\}$ is not context-free. Indeed, suppose there exists $p$ that satisfies the condition from the Pumping Lemma. Then $a^pb^pc^p\in L$, and let $a^pb^pc^p=xuyvz$ be the corresponding decomposition. By condition $1$, $uyv$ cannot contain both $a$ and $c$. If it contains $a$, then $u$ contains $a$, since it constitutes the leftmost part of $uyv$. But then $v$ does not contain $c$, and so $xyz=xu^0yv^0z$ has unequal number of $a$ and $c$, hence $xu^0yv^0z\not\in L$, which contradicts condition $3$. Similarly, $uyv$ cannot contain $c$. Therefore $uyv$ must be contained in the $b^p$ block in the middle. But then "pumping" changes the number of $b$, while the number of $a$ and $c$ remains the same, hence condition $3$ does not hold. Therefore, there is no way to choose decomposition $a^pb^pc^p=xuyvz$ satisfying $1$-$3$, and so $L$ is not context-free.

Note that $L^R$ is isomorphic to $L$ in this particular case, so $L^R$ cannot be context-free. Almost verbatim, the above argument shows that $L^*$ is not context-free (the same choice of word - $a^pb^pc^p$ - can be used, and note that if the "pumped" word is in $L^*$, then it is in $L$ too, because of its structure).

In (IV), note that the image of $L$ by $h$ is $\left\{a^nb^{2n}a^n\colon n\geq 0\right\}$, take word $a^pb^{2p}a^p$ and show that no decomposition allows pumping (consider all possible placements of $uyv$).

On the other hand, in (I) image of $L$ by $h$ is $\left\{a^nb^{3n}\colon n\geq 0\right\}$ is generated by a simple context-free grammar:

$$S\rightarrow aSbbb \mid \epsilon$$