Sign up ×
Mathematics Stack Exchange is a question and answer site for people studying math at any level and professionals in related fields. It's 100% free, no registration required.

I need to know if my solution for a problem related with regular languages and pumping lemma is correct.

So, let $L = \{a^ib^jc^k \mid i, j,k \ge 0 \mbox{ and if } i = 1 \mbox{ then } j=k \}$

Now i need to use the pumping lemma to prove that this language is not regular. I wrote my proof like this:

Let's assume that $L$ is regular.

Let $|w|= p$ be the pumping length and $q = p -1$.

Now if we consider $i = 1$ then $j=k$, so now i can pick a string from $L$ such as $w = ab^qc^q=xyz$. Since $q = p - 1$, it implies that $x = a$, $y=b^q$ and $z=c^q$. It satisfies the property $|xy| \le p$ and $|y| \gt 0$.

Assuming that $L$ is regular, then $\forall_i\ge_0\ xy^iz \in L$, but if we choose $i=2$ we have $xy^2z$, which means that we have more $b's$ than $c's$, and we reached a contradiction, therefore $L$ is not regular, which completes the proof.

Is my proof correct? i'm having some doubts related with my $q = p - 1$, but i think that it makes sense to choose a $q$ like that to "isolate" $y=b^q$, that will make the proof trivial after.

Thanks in advance.

share|cite|improve this question

1 Answer 1

up vote 0 down vote accepted

You cannot choose $x$, $y$ and $z$. That is, the following statement does not help you prove that the language is not regular:

Since $q=p−1$, it implies that $x=a$, $y=b^q$ and $z=c^q$. It satisfies the propery $|xy| \le p$ and $|y|>0$.

The pumping lemma states that for every regular language $L$, there exists a string $xyz \in L$ with $|xyz| \ge p$, $|xy| \le p$ and $|y| \ne 0$ such that $xy^iz \in L$ for all $i \ge 0$.

Therefore, if you wish to prove a language is not regular, you may go by contradiction and show that for all $xyz \in L$ with $|xyz| \ge p$, $|xy| \le p$ and $|y| \ne 0$, there exists an $i \ge 0$ such that $xy^iz \not\in L$. Note how the quantifiers flip.

You are only showing that one choice of $x$, $y$ and $z$ violates the pumping lemma, but you must show that all choices violate the pumping lemma.

share|cite|improve this answer
Yes, but i used that subset of the language. If that subset is not regular, then the language can't be regular right? – user19410 Nov 14 '11 at 2:01
I'm not sure what you are referring to, but what you just said is not true. For example, $\{ 0^n1^n : n \ge 0 \} \subset \{ 0, 1 \}^*$. – Zach Langley Nov 14 '11 at 2:05
Yes, and $\{0,1\}^*$ is regular. I need to write a new proof. – user19410 Nov 14 '11 at 2:09

Your Answer


By posting your answer, you agree to the privacy policy and terms of service.