Homorphism and Context Free Grammar

Question

Could you explain me concept of homomorphisms and usage of it to the following problem which requires to prove that $L$ is not context-free?

$$L=\{ba^{n-1}ba^nb:n\ge 1\}$$

Thanks

Answer 1

$L$ is context-free: it’s generated by the productions

$$\begin{align*} &S\to bAb\\ &A\to ba\mid aAa\;. \end{align*}$$

Any derivation must take the form

$$S\Rightarrow bAb\Rightarrow^n ba^nAa^nb\Rightarrow ba^nba^{n+1}b\;,$$

where $n\ge 0$.

Thus, homomorphisms have nothing to do with this problem, but I’ve added a brief explanation of them anyway.

---

Let $\Sigma$ and $T$ be alphabets. Let $h_0:\Sigma\to T^*$ be any map that sends each letter of $\Sigma$ to some word of $T$. For instance, if $\Sigma=\{a,b\}$ and $T=\{0,1,2\}$, we might have $h_0(a)=012$ and $h_0(b)=22$. Such a map can be extended to a map $h$ from $\Sigma^*$ to $T$: if $w=\sigma_1\sigma_2\dots\sigma_n$ is any word in $\Sigma^*$, we define

$$h(w)=h(\sigma_1)h(\sigma_2)\dots h(\sigma_n)\;.$$

In my little example, for instance, this would give us $h(aaba)=01201222012$. Such a map $h$ is a string homomorphism from $\Sigma^*$ to $T^*$. If $L_1\subseteq\Sigma^*$ is a language over the alphabet $\Sigma$,

$$h[L_1]=\{h(w):w\in L\}$$

is a language over the alphabet $T$, called the homomorphic image of $L_1$ under $h$. If $L_2\subseteq T^*$ is a language over the alphabet $T$,

$$h^{-1}[L_2]=\{w\in\Sigma^*:h(w)\in L_2\}$$

is a language over the alphabet $\Sigma$, called the inverse homomorphic image of $L_2$ under $h$. An important fact about the class of context-free languages is that it is preserved under homomorphisms and inverse homomorphisms: if $L_1$ is context-free, so is $h[L_1]$, and if $L_2$ is context-free, so is $h^{-1}[L_2]$.

Thus, if $L$ is a context-free language, every homomorphic image of $L$ is also context-free. If you can find a homomorphic image of $L$ that you already know is not context-free, you’ll have proved that $L$ is not context-free. Alternatively, if you can find an inverse homomorphic image of $L$ that you know is not context-free, you’ll have shown that $L$ is not context-free.

This can be done, for instance, with the language

$$L=\{baba^2ba^3b\dots ba^{n-1}ba^nb:n\ge 1\}\;.$$

If $h(b)=a$ and $h(a)=aa$, then

$$h[L]=\left\{a^{(n+1)+2\sum_{k=1}^nk}:n\ge 1\right\}=\left\{a^{(n+1)^2}:n\ge 1\right\}\;,$$

a language that is easily shown not to be context-free using the pumping lemma. Thus, $L$ isn’t context-free either.