2
$\begingroup$

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.

1 Answers 1

0

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.

  • 0
    Yes, and $\{0,1\}^*$ is regular. I need to write a new proof. – 2011-11-14