I have a language $ L= \{ w \in \{a,b\}^* ; |w|_b=2i, i \ge 0 \}$ that is a language with even number of b's.

I found a grammar for it with these rules:

$S \rightarrow aS \ | \ bL \ | \ \lambda $

$L \rightarrow aL \ | \ bS \ $

How could I show that this language cannot be generated by linear grammar?

According to Wikipedia, a linear grammar is a context-free grammar that has at most one nonterminal in the right hand side of its productions.

  • $\begingroup$ Where did you find that definition? $\endgroup$ – Raphael Apr 22 '16 at 12:25
  • $\begingroup$ Sorry, my lecturer had bad defintion in slides, I edited it, But still, this language is not regular, and I think its not linear too. $\endgroup$ – Martin Apr 22 '16 at 13:10
  • 1
    $\begingroup$ "this language is not regular" -- wrong. $\endgroup$ – Raphael Apr 22 '16 at 13:29

Your grammar is right-regular and can thus be used to prove that $L \in \mathrm{REG}$. Since every regular grammar is linear, your claim is impossible to prove.

  • $\begingroup$ My intuition says this language is not regular, so I'm trying to prove its not linear either ( regular $\ne$ linear ) $\endgroup$ – Martin Apr 22 '16 at 13:04
  • $\begingroup$ @martinerk0 Your intuition is wrong, and contradicts your statement "I found a [regular] grammar for [$L$]". $\endgroup$ – Raphael Apr 22 '16 at 13:29
  • $\begingroup$ Why would that grammar be regular? $\endgroup$ – Martin Apr 22 '16 at 13:31
  • $\begingroup$ It's right-regular; just check the definition. It's trivial to transform it into a DFA. $\endgroup$ – Raphael Apr 22 '16 at 13:32

A grammar whose only rules are of the form $X \to uYv$ and $X \to w$, where $u,v,w$ are terminals, can only generate words of odd length. Your language also contains words of even length. If you also allow rules of the form $X \to \epsilon$, then you can construct a grammar for your language (exercise).

  • $\begingroup$ I apologize, now I have correct definition of linear grammar. $\endgroup$ – Martin Apr 22 '16 at 13:10

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.