[Solved]: Are there languages generated by linear grammar which aren't regular?

Problem Detail: 

Are there languages generated by linear grammer which aren't regular?

Asked By : Iancovici

Answered By : Shaull

Of course. Look at the first example on Wikipedia:

$\qquad S \to aSb \mid \varepsilon$

is linear and generates $\{a^nb^n \mid n \in \mathbb{N}\}$, a non-regular language.

If you mean left-linear, or right-linear, then no - they are equivalent to REG.

Best Answer from StackOverflow

Question Source : http://cs.stackexchange.com/questions/10079

 Ask a Question

 Download Related Notes/Documents