1
$\begingroup$

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.

Improve this question
$\endgroup$
3
  • $\begingroup$ Where did you find that definition? $\endgroup$
    – Raphael ♦
    Apr 22, 2016 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, 2016 at 13:10
  • 1
    $\begingroup$ "this language is not regular" -- wrong. $\endgroup$
    – Raphael ♦
    Apr 22, 2016 at 13:29

2 Answers 2

Reset to default
2
$\begingroup$

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.

Improve this answer
$\endgroup$
4
  • $\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, 2016 at 13:04
  • $\begingroup$ @martinerk0 Your intuition is wrong, and contradicts your statement "I found a [regular] grammar for [$L$]". $\endgroup$
    – Raphael ♦
    Apr 22, 2016 at 13:29
  • $\begingroup$ Why would that grammar be regular? $\endgroup$
    – Martin
    Apr 22, 2016 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, 2016 at 13:32
1
$\begingroup$

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).

Improve this answer
$\endgroup$
1
  • $\begingroup$ I apologize, now I have correct definition of linear grammar. $\endgroup$
    – Martin
    Apr 22, 2016 at 13:10

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service and acknowledge that you have read and understand our privacy policy and code of conduct.

Not the answer you're looking for? Browse other questions tagged or ask your own question.