1
$\begingroup$

I have a problem to start my proof because I do not find a word $w$ where I can use the pumping lemma.

Task:

Be $\sum { =\left\{ a,b,c \right\} } $ and $S=\left\{ bx{ c }^{ m }|x\in { \left\{ a,b \right\} }^{ * }\wedge m\in N\wedge { |bx| }_{ a }-{ |bx| }_{ b }>m \right\} $

Proof with the the pumping lemma, that S is no regular language.

What I know is, that the word has to start we one $b$ following from n times $a$ or $b$ but $w$ needs to have one more $a$ than $b$ in it and $w$ also needs to have one more $b$ than $c$ in it to fulfill the condition. So it has to be something like this $W=b{a}^{2m+2}b^mc^m$? This language is very difficult for me, hope you see more than I.

P.S. Please no complete solutions of the full task.

|cite|improve this question
$\endgroup$
  • $\begingroup$ What does the notation $|bx|_a$ mean? Is it supposed to be the number of symbols in $bx$ equal to "$a$"? $\endgroup$ – dkaeae Jan 18 '19 at 14:42
  • $\begingroup$ Also, just picking a word $w$ which does not depend on the pumping length $p$ whatsoever is an approach which is bound to fail. $w$ must somehow depend on the pumping length (so that $|w| > p$), otherwise you cannot guarantee the lemma applies to it. $\endgroup$ – dkaeae Jan 18 '19 at 14:44
  • $\begingroup$ @dkaeae Yes, $|w|_a$ is pretty standard notation for "the number of $a$s in $w$. $\endgroup$ – David Richerby Jan 18 '19 at 14:45
  • $\begingroup$ @dkaeae Yes , but at the moment I can not find a $w$ where $|w|>p$ works and fulfill the condition of the language. I'am also not sure if I have to make Case distinction. Because I saw an example where the prof used a Case distinction to show the pumping lemma the language was something like that $ \{{ab} ^{n} c^n | n\in N \} $ $\endgroup$ – Lisa.Neust Jan 18 '19 at 14:56
  • $\begingroup$ @Lisa.Neust Don't worry about $p$. Either you require $m\ge p$ in your chosen word, or you write $W = ba^{2p+2}b^pc^p$. In both cases $|W|\ge p$, so the pumping property applies. $\endgroup$ – Hendrik Jan Jan 18 '19 at 15:36
1
$\begingroup$

So it has to be something like this $w=b{a}^{2m+2}b^mc^m$.

$b{a}^{2m+2}b^mc^m$ is not the general form for $w=bxc^m\in S$. If $x$ must be in the form of $a^*b^*$, $w$ will be something like $b{a}^{m+n+k+2}b^nc^m$ for some $n,k\ge0$. Just for completeness, $w$ could be like $baba^{m+1}c^m$ or $baba^{m+1}a^kb^kc^m$ or many other forms. Of course, it is totally fine if you just meant to choose one word so as to apply the pumping lemma.

Can you check word $ba^{p+2}c^{p}$, assuming the pumping length is $p$? This word is about as simple as you could get.

Exercise 1. Assuming the pumping length is $p$, can we pump $ba^{p+3}bc^p\in S$?

Exercise 2. Assuming the pumping length is $p$, can we pump $ba^{2p+2}b^pc^p\in S$?

|cite|improve this answer
$\endgroup$
  • $\begingroup$ Why isn't the "classic version" applicable in the example? $\endgroup$ – Hendrik Jan Jan 18 '19 at 15:38
  • $\begingroup$ @Apass.Jack Thanks for your answer. I also saw this version, but our prof told us not to use this. $\endgroup$ – Lisa.Neust Jan 18 '19 at 15:56
  • $\begingroup$ @HendrikJan Thanks. I was misleading since the classic version is applicable even although my answer was not wrong technically. I will update. By the way, Lisa, the general version is indeed more convenient more often than not, since it lets you pinpoint where you want to pump, removing much of case by case argument. Of course, your prof does have a point in insisting practicing the classic version. $\endgroup$ – John L. Jan 18 '19 at 16:01
  • $\begingroup$ Lets see I would choose a decomposition $w=xyz$ for$ba^{p+2}c^{p}$. So be $x=ba^i $,$y=ba^j$ and $z=b{a}^{p+2-i-j}c^p$. Now i would choose $k=0$ and we have $xy^0z=b{a}^{p+2-i}c^p$ and that it should be $p+2-j+p=2p-j+1<2p+3=1+p+2+p$ $\endgroup$ – Lisa.Neust Jan 18 '19 at 16:39
  • $\begingroup$ @Lisa.Neust All possible cases of $x$ and $y$ have to be dealt with. Case 1, $x$ is empty and $y=ba^j$. Case 2, $x=ba^i$ and $y=a^j$. It might be helpful if you read this answer. $\endgroup$ – John L. Jan 18 '19 at 17:09

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

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