How to prove a language is not an FAD using homomorphism.

Question

Could anyone please let me know with an example on how shall one can prove the language is not a FAD using Homomorphism.

Answer 1

Here’s a simple example. Let $L=\{ab^n(cd)^{n+1}:n\ge 0\}$; we’ll use the fact that regularity is preserved by homomorphisms to show that $L$ is not regular. Let $\varphi_0:\{a,b,cd\}\to\{x,y\}$ be defined by $\varphi_0(a)=\varphi_0(b)=x$ and $\varphi_0(cd)=y$; $\varphi_0$ extends to a homomorphism $\varphi:\{a,b,cd\}^*\to\{x,y\}^*$. Then

$$\begin{align*} \{\varphi(w):w\in L\}&=\left\{\varphi\big(ab^n(cd)^{n+1}\big):n\ge 0\right\}\\ &=\left\{\varphi(a)\varphi\big(b^n\big)\varphi\big((cd)^{n+1}\big):n\ge 0\right\}\\ &=\left\{x\big(\varphi(b)\big)^n\big(\varphi(cd)\big)^{n+1}:n\ge 0\right\}\\ &=\left\{xx^ny^{n+1}:n\ge 0\right\}\\ &=\left\{x^ny^n:n\ge 1\right\}\;. \end{align*}$$

The language $L_D=\{x^ny^n:n\ge 1\}$ is well-known as an example of a context-free language that is not regular. If $L$ were regular, $L_D$ would have to be regular as well, since it’s the image of $L$ under a homomorphism; since $L_D$ is not regular, neither is $L$.

Note that in order to apply this method, you have to have some languages that you already know are not regular.