# Show that the Language L is not regular (pumping lemma) [closed]

$$L = \{cda^nb^n\mid n\in \Bbb N\} \cup \{a,b,d\}^*$$

Assuming $$L$$ is regular then there exist a pumping length $$n$$ for $$L$$. Lets use w = $$cda^nb^n$$.

Thus $$w \in L$$ and $$|w| = 2n+2$$ $$\implies$$ $$|w| \geq n$$.

$$w$$ can be splitted into three pieces $$w = xyz$$ with the following conditions:

• $$|xy| \leq n$$
• $$|y| \geq 1$$

Let be $$x = cda^j$$ and $$y = a^k$$ with $$k+j\leq n$$ and $$k\geq 1$$.

Now choose $$i = 2$$ so that $$xy^iz = xyyz = cda^ja^ka^ka^{n-j-k}b^n = cda^{n+k}b^n$$

$$w$$ has now more $$a$$'s than $$b$$'s (considering that $$k$$ is at least 1) $$\implies w \notin L \implies$$ $$L$$ is not regular.

Is that enough for the proof?

• I'm voting to close this question as off-topic because it is a request to grade work with no specific concerns raised. – David Richerby May 25 '19 at 22:34
• i defined $cda^j$ and $y=a^k$ with $k+j \leq n$, but if $k + j = n$then i have a problem because $|xy|$ is now greater than n. Maybe i could change the definition to $k + j \leq n-2$? Another question i have: can there be multiple correct choices for x,y and z which leads to the right conclusion? For example $x = cd$, $y = a^k with$ $1 \leq k \leq n-2$ which implies to the same solution. – lyarel May 25 '19 at 23:02

Let me explain the easiest way to show that this language isn't context-free. It it were, then its intersection with $$c(a+b+d)^*$$ would also be. This intersection is $$cda^nb^n$$. If the latter were context-free, then if we applied the homomorphism that erases $$c,d$$, the resulting language $$a^nb^n$$ would also be context-free; but we know that $$a^nb^n$$ isn't context-free.
• You chose the decomposition of $w$ into $xyz$. You cannot do this. Rather, the decomposition is given to you. – Yuval Filmus May 26 '19 at 14:51