# Show that a language cannot be generated by linear grammar

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.

• Where did you find that definition?
– Raphael
Apr 22, 2016 at 12:25
• 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. Apr 22, 2016 at 13:10
• "this language is not regular" -- wrong.
– Raphael
Apr 22, 2016 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.

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

• I apologize, now I have correct definition of linear grammar. Apr 22, 2016 at 13:10