184 views
0 votes
0 votes

A linear language is one for which there exists a linear grammar

[A linear grammar is a grammar in which at most one variable can occur on the right side of any production, without restriction on the position of this variable. Clearly, a regular grammar is always linear, but not all linear grammars are regular]

Let $L$ be any linear language not containing $λ$. Show that there exists a grammar $G = (V, T,S, P)$ all of whose productions have one of the forms

                    $A\rightarrow aB,$

                    $A\rightarrow Ba,$

                    $A\rightarrow a,$
where $a∈ T$ ,   $A, B∈ V,$ such that $L = L (G)$.

Please log in or register to answer this question.

Related questions

0 votes
0 votes
0 answers
3
0 votes
0 votes
0 answers
4