Pumping Lemma for a regular language

123 Views Asked by At

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.

1

There are 1 best solutions below

0
On BEST ANSWER

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