1
$\begingroup$

My assignment is to prove that the language

$L = \{ a^{4n} b^m \mid n > m >= 0\}$ is not a regular language.

My first attempt was to prove that if if you set $a^l$ and $b^{l-1}$ you'd have an equal #a and #b if you "pump down" your $v$ so that it is $v^0$, so that the condition $n > m$ is no longer fulfilled. Then I realized I completely disregarded that it's $4n$ and not just $n$, so I wasted a lot of time on that.

Now I'm absolutely out of ideas, because as I see it you can always find an number $p$, so that you can pump a number of as however often you want as long as p is divisible by 4 because if you divide your word $z = uvw$, both $u$ and $v$ need to have a number of as divisible by 4 as to not break the $4n$ condition.

However, that would mean that you absolutely can not prove that $L$ is not regular using the pumping Lemma, which contradicts the assignment. Where is the flaw in my logic?

I would really appreciate some pointers.

$\endgroup$
0
$\begingroup$

Yes, you can use the pumping lemma. It looks like your line of thoughts just had a minor glitch.

Suppose your adversary claims the pumping lemma for $L$ works for some number $p\ge1$.
You can pick $z=a^{4(p+1)}b^p$, a word that "barely" satisfies the requirement.
Your adversary claims $z=uvw$ where $|v|\ge1$, $|uv|\le p$ and for all $n\geq 0$, $uv^{n}w\in L$.

Since $|uv|\le p<4(p+1)$ and $z$ starts with $4(p+1)$ consecutive $a$'s, there must be no $b$ in $uv$. That is, $v=a^i$ for some $i=|v|\ge1$.

Consider $uv^0w=uw$. Since $z$ "barely" satisfies the requirement, removing some $a$'s without removing any $b$ will make $z$ not satisfying the requirement. You have beaten your adversary, again.

The above proof works, in fact, for any language $M$ such that $L\subseteq M\subseteq \{w\mid \#_a(w)\ge4(\#_b(w)+1)\}$.

I have been saying "$z$ 'barely' satisfies the requirement", since it is easier to understand that way although it is not very rigorous. It should be quite easy for readers to make it rigorous.

$\endgroup$
  • 1
    $\begingroup$ If $z = a^{4(p+1)}b^p$ decomposes into $uvw$ with $|uv| \leq p$, we cannot have $v = a^ib^j$ with $j > 0$, so you actually only have the second case to consider where $j = 0$. Then you always pump down the word to $uw$ which always has less $a$s than needed for $p$ many $b$s. $\endgroup$ – ttnick Dec 1 '18 at 0:06
  • 1
    $\begingroup$ @PHPNick, up-voted your comment. Although my explanation is correct technically and could be applied to other situations, the solution could be simpler. (It looks like I have done too much pumping...) $\endgroup$ – Apass.Jack Dec 1 '18 at 0:19
  • $\begingroup$ Am I mistaken or is that the same concept as what I did with a^l and b^l-1 (in your case l = p). I feel like it is as I was trying to find a z that "barely" fulfills the requirements and then pump down and I just kept hitting my brain against an invisible wall for no reason. Either way, thanks a lot for your explicit answer. $\endgroup$ – Krios Dec 1 '18 at 10:45
  • $\begingroup$ Just to get clear on that, the requirement that is no longer fullfilled is n>m because a^4l-1 < b^l right? $\endgroup$ – Krios Dec 1 '18 at 10:58
  • $\begingroup$ Yes. Here is another description of $L$. $L= \{ a^{i} b^j \mid j\ge0, i\ge 4(j+1) , i \text{ is divisible by } 4\}$. The requirement we are referring to is $i\ge 4(j+1)$, that is, the number of $a$'s must be no less than 4 times the sum of the number of $b$'s and 1. Please check my updated answer. $\endgroup$ – Apass.Jack Dec 1 '18 at 14:36
0
$\begingroup$

Assume L is regular with pumping length p.

Choose n = floor (p/5) + 1, m = n-1. Then w = $a^{4n} b^m$ is in L, and has length ≥ p. Choose w = xyz.

If y contains only b's then $xy^kz$ is not in L for k ≥ n because there are too many b's.

If y contains both a's and b's then $xy^2z$ is not in L because it has the form $a^+b^+a^+b^+$ which is not in l.

Therefore y contains only a's. If the number of a's in y is no multiple of four then xz is not in L because the number of a's in xz is not a multiple of 4.

Finally, if the number of a's in y is a multiple of four then xz has too few a's.

$\endgroup$
0
$\begingroup$

I find it easiest to prove that the language is not recognised by any finite state machine.

Assume a finite state machine has processed the string $a^{4k}$, k ≥ 0 and ended up in the state $S_k$. The set of strings that lead from $S_k$ to an accepting state is exactly ${a^{4n} b^m : n+k > m > 0}$. For every k, this set of strings is different, therefore each state is different, therefore the set of states is not finite.

PS. The proof for the pumping lemma just shows quite easily that a language with a finite state machine must fulfil the conditions of the pumping lemma, so checking that the pumping lemma fails to apply to a language shows a contradiction to the existance of an FSM. I think showing directly that there is no limit to the number of states is easier, especially if the language is a bit more complex.

$\endgroup$
  • $\begingroup$ Yes, that has occured to me before and I agree with the infinite set of states. However it is absolutely necessary I solve this problem using the pumping-lemma, meaning I prove there's no way you can pump a sequence in all words and still have it be an element of L. I can not seem to find the right starting point for that though, all combinations I thought of so far didn't break a single rule of the pumping lemma. $\endgroup$ – Krios Nov 30 '18 at 21:18

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.