I'm trying to show that the language in the title is not regular but I don't know how to chose a decomposition $x = abc$ to express the word in the language because the $w \in \{a,b,c\}^*$ is kinda tricky for me, I know it means $ \{ a,b,c\} \cup\{ a,b,c\}^2 \cup ... \cup \{ a,b,c\}^k $ but I don't know how to chose the decompositons for a word in the language and proove that is not in the language by pumping lemma. Any tips ?

  • 1
    $\begingroup$ I need help for this example, I understand how to use pumping lemma $\endgroup$ – Eduard Valentin Jun 26 '17 at 9:05
  • $\begingroup$ You should probably choose $w$ to contain only $b$s and $c$s so you can tell the difference between $w$ and the $a^k$. $\endgroup$ – David Richerby Jun 26 '17 at 9:33
  • $\begingroup$ Good idea @DavidRicherby , let me try it $\endgroup$ – Eduard Valentin Jun 26 '17 at 9:47
  • $\begingroup$ @DavidRicherby can i chose w to be of the form $b^j$ or $c^j$ then i would have $x$ a word in L that is of the form $b^j a^k b^j $ then I can show with the pumping lemma that this word is not in the language ? Is that correct ? $\endgroup$ – Eduard Valentin Jun 26 '17 at 10:17
  • $\begingroup$ The pumping lemma can't show that a word isn't in the language, and $b^ja^kb^j$ (excellent choice of word, btw) is in the language. Rather, the pumping lemma says "If the langauge was regular, then $b^ja^kb^j$ being in the language would imply that a whole bunch of other words would be in it, too." But we know that some or all of those words aren't in the language, so we conclude that the language isn't regular. $\endgroup$ – David Richerby Jun 26 '17 at 17:29

After $n$ is fixed, you could choose $x = b^na^nb^n$. This string is clearly in $L$. By the Pumping lemma $x$ can be written as $uvw$, where $|uv| \leq n$ and $|v| \geq 1$. So for any choice of $u$ and $v$, $uv$ is a string consisting of only $b$s, and so is $v$. Thus $uv^iw = b...b(b...b)^ib...ba^nb^n$ which is not in $L$.

On @DavidRicherby comment:

The Pumping Lemma:

Let $L$ be a regular set. Then there is a constant $n$ such that if $z$ is any word in $L$, and $|z| \geq n$ we may write $z = uvw$ in such a way that $|uv| \leq n$, $|v| \geq 1$, and for all $i \geq 0$, $uv^iw \in L$.

How to use

1) Select the language you wish to to prove irregular.

2) The "adversary" picks $n$, the constant mentioned in the Pumping lemma. Once it has been picked, it may not be changed (fix it).

3) Select a string $z$ in $L$. Your choice may depend implicitly on the value of $n$.

We choose $z = b^na^nb^n$.

4) The "adversary" breaks $z$ into $u$, $v$, and $w$, subject to the constraints that $|uv| \leq n$ and $|v|$.

In my proof the prefix of $z$ consists of $n$ $b$'s, so any choice of $u$, $v$, and $w$ implies that $v$ consists solely of $b$s.

5) You achieve a contradiction to the pumping lemma by showing that there exists $i$ such that $uv^iw \notin L$.

Just choose $i=2n$ and we have unequal number of $b$s on the left and right sides of the substring $a^n$: $b^{2n + d}a^nb^n \notin L$.

This is how we prove.

| cite | improve this answer | |
  • $\begingroup$ Sorry, but this is a poor attempt at a pumping lemma proof. "By the Pumping lemma $x$ can be written as $uvw$, where $|uv|\leq n$ and $|v|\geq1$." That's not "by the pumping lemma". Any string of length at least $n$ can be written in that way. The pumping lemma is what lets you conclude that the language isn't regular. $\endgroup$ – David Richerby Jun 26 '17 at 9:35
  • $\begingroup$ @DavidRicherby, please first of all correct your comment before you downvote, it is not clear what you write. $\endgroup$ – fade2black Jun 26 '17 at 9:39
  • $\begingroup$ @DavidRicherby, secondly, what is wrong with the proof? Please refresh your knowledge in case you forgot or learn if you don't know at all how to use the lemma. en.wikipedia.org/wiki/Pumping_lemma_for_regular_languages $\endgroup$ – fade2black Jun 26 '17 at 9:43
  • $\begingroup$ My comment doesn't need to be "corrected" because it is already correct. The phrase "By the pumping lemma, X" means "Using the pumping lemma, I conclude that X is true". But the thing you state is not a conclusion of the pumping lemma: it's a premise of the lemma. (It's like saying "By Pythagoras, $3^2+4^2=5^2$". That's not "by Pythagoras": it's just arithmetic.) And, rather than just claiming that $b...b(b...b)^ib...ba^nb^n\notin L$, it would be clearer to demonstrate this for a specific $i$ (e.g., $i=0$; note that for $i=1$, the string is in $L$). $\endgroup$ – David Richerby Jun 26 '17 at 17:27
  • $\begingroup$ @DavidRicherby, please see updates. As for the wording "By the Pumping lemma", your carping about the introductory sentence "By the Pumping lemma..." is meaningless and not constructive and helpful. After all, it is you who suggested the same idea a bit later after my post. $\endgroup$ – fade2black Jun 26 '17 at 18:12

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