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 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 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 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 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 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 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 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$ – Apass.Jack Jan 18 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 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$ – Apass.Jack Jan 18 at 17:09

Your Answer

By clicking "Post Your Answer", you acknowledge that you have read our updated terms of service, privacy policy and cookie policy, and that your continued use of the website is subject to these policies.

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