Pumping Lemma for CF language exercise

242 Views Asked by At

I have this language $$ B=\{x\in \{a,b,c\}^*:(x\text{ not contains } aabb \text{ or } bbcc \text{ or } aaaa) \land \#(a,x)=\#(b,x)=\#(c,x)\} $$ The notation $ \#(s,x) $ indicates the number of occurrences of simbol $s$ in $x$.

I know that it isn't a CF language, but I can't find a string to use with Pumping Lemma in order to demonstrate it.

Any help is appreciated.

2

There are 2 best solutions below

5
On

$(ac)^n(b)^n$

Test the substrings and you should notice that pumping causes #a && #c != #b, #a != #c && #a != #b etc

0
On

The "usual" sentence to pump for $a^nb^nc^n$ (or variants, including ones where only the counts need to match) is something like $$a^pb^pc^p$$ but that won't quite work in this case because of the substring restrictions. So the challenge is to find a variant on that sentence which also satisfies the requirement that there is no $aabb$, $bbcc$ nor $aaaa$. The first two can easily be accomplished by reversing the string ($c^pb^pa^p$); to deal with the prohibition on $aaaa$, we need to use something like $$c^{2p}b^p(baa)^p$$ which has $2p$ instances of each alphabet symbol. As with $a^pb^pc^p$, it is evident that no substring of length $p$ can contain more than two different symbols, with the result that it cannot be pumped without making the symbol counts different from each other.