We were said at school that the language $L$ over an alphabet $\sum = \{a,b\}$ where the number of $a$'s is twice the number of $b$'s, formally $L = \{ w \in \{a,b\}^* \mid |w|_a = 2|w|_b \}$ cannot be generated by linear grammar. I was wondering, is there a way to prove it, to make it clear why is that so? I was thinking about applying the pumping lemma might work, but I wasn't succesful proving it.

  • 1
    $\begingroup$ Of course you can not use the Pumping lemma; not the context-free one, at least. The language is context-free, after all! $\endgroup$ – Raphael Apr 15 '17 at 17:21
  • $\begingroup$ Hint: proof by contradiction. Assume it was linear, so you'd have a linear grammar. Now build a derivation for a word not in the language. $\endgroup$ – Raphael Apr 15 '17 at 17:22
  • 2
    $\begingroup$ Well, recently we saw a pumping lemma for linear languages. $\endgroup$ – Hendrik Jan Apr 15 '17 at 20:29

Your Answer

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

Browse other questions tagged or ask your own question.