-1
$\begingroup$

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

| cite | improve this question | |
$\endgroup$
  • 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 '19 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 '19 at 23:02
2
$\begingroup$

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.

| cite | improve this answer | |
$\endgroup$
  • $\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 '19 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 '19 at 14:51

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