$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?


closed as unclear what you're asking by David Richerby, Evil, Discrete lizard May 26 at 10:16

Please clarify your specific problem or add additional details to highlight exactly what you need. As it's currently written, it’s hard to tell exactly what you're asking. See the How to Ask page for help clarifying this question. If this question can be reworded to fit the rules in the help center, please edit the question.

  • 1
    $\begingroup$ I'm voting to close this question as off-topic because it is a request to grade work with no specific concerns raised. $\endgroup$ – David Richerby May 25 at 22:34
  • $\begingroup$ 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. $\endgroup$ – lyarel May 25 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.

  • $\begingroup$ Yeah, that seems to be right, but I want to understand the pumping lemma. I would appreciate it if you could tell me where I made a mistake. $\endgroup$ – lyarel May 26 at 14:41
  • $\begingroup$ You chose the decomposition of $w$ into $xyz$. You cannot do this. Rather, the decomposition is given to you. $\endgroup$ – Yuval Filmus May 26 at 14:51

Not the answer you're looking for? Browse other questions tagged or ask your own question.