0
$\begingroup$

I've done pumping lemma proofs in the past but I'm honestly not even sure where to start on this problem.

Using the Pumping Lemma for Regular Languages show that the language $$L = \{a^i b^j c^k \mid i,j,k\text{ are non-negative integers, and }i=j\text{ or }j=k\} $$ is not regular.

$\endgroup$
1
$\begingroup$

Suppose that $L$ is regular, and let $p$ be the pumping length; then every $w\in L$ with $|w|\ge p$ can be written as $w=xyz$ in such a way that $|y|\ge 1$, $|xy|\le p$, and $xy^kz\in L$ for all $k\ge 0$. You want to get a contradicftion by choosing $w$ in such a way that at least one of the words $xy^kz$ is provably not in $L$.

What if you take $w=a^pb^p$? If $w=xyz$, where $|xy|\le p$ and $|y|\ge 1$, what letter appear in $y$? For what values of $k$ is $xy^kz\in 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.