0
$\begingroup$

I am trying to use the Pumping Lemma to prove the language $$L=\{a^nb^mc^md^n\}$$ is not regular. However, I am having trouble when selecting the values of x, y, and z to show that xyz is contained within the language (before proceeding to show that it is not contained in the language when selecting a value of i for v, as uvw = y, where |v| > 0.)

Any ideas?

Thank you.

$\endgroup$
  • $\begingroup$ What values can $n$ and $m$ take? $\endgroup$ – angryavian May 7 at 18:31
0
$\begingroup$

Suppose for sake of contradiction that $L$ is regular, and let $p$ be the pumping length.

Consider the word $a^p bc d^p$. If we write this word in the form $xyz$ such that $|xy| \le p$ and $|y| > 0$, then $y=a^k$ for some $0 < k \le p$. But then $xy^2z = a^{p+k} bc d^p \notin L$.

$\endgroup$

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

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