[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