0
$\begingroup$

I was solving some hard exercises on context free grammer.

Consider the language L={w∈{a,b}^{*} :the length of the longest substring of all b’s in w is longer than any of the length of substring of just a’s in w}.

Prove that L is not context free.

I have tried this problem using pumping lemma and closure properties. How to go about it? Any help would be appreciated.

$\endgroup$
  • $\begingroup$ Got it. Used pumping lemma on a^mb^{m+1}c^m. $\endgroup$ – user3523469 Oct 21 '17 at 2:19
0
$\begingroup$

Let $p$ be the pumping length. Then $b^pa^{p+1}\in L$ and also $b^{r}a^{p+1}$ for many $r>p$, contradiction.

$\endgroup$
  • $\begingroup$ Isn't this proof for just regular languages? I am trying to use pumping lemma for context free. $\endgroup$ – user3523469 Oct 20 '17 at 20:54
0
$\begingroup$

Let $p$ be the pumping length. Then $а^{p}b^{p+1}a^{p}\in L$. $w = xyzuv. |yu|>=1 |yzu|<= p$.

If yzu is only of 1 letter it's easy to see that $xy^{0}zu^{0}v$ it's not in L.

If yzu consist of 2 letters , then $xy^{0}zu^{0}v = а^{p-r}b^{p+1-t}a^{p}$ or $ а^{p}b^{p+1-t}a^{p-r}$ and since $p>=p+1-t$ the string obviously are not in L

$\endgroup$

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.