Take the 2-minute tour ×
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|improve this question

1 Answer 1

up vote 1 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|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? –  Leandro F. Vaz Nov 14 '11 at 2:01
1  
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. –  Leandro F. Vaz Nov 14 '11 at 2:09

Your Answer

 
discard

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

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