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