# Right definition of linear grammar

I was referring book by Peter Linz, which defines linear grammar as follows:

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.

The wikipedia page also defines it similar way at the top of Linear grammar page

a linear grammar is a context-free grammar that has at most one nonterminal in the right hand side of each of its productions.

By these definition, it seems that the production of the following form is allowed:

$S\rightarrow aSb$

But next on the same page, wikipedia defines it as follows:

linear grammars in which all nonterminals in right hand sides are at the left or right ends, but not necessarily all at the same end.

By this definition, it seems that the productions of the above form are not allowed.

Then what is correct definition?

• Do you mean (1) linear grammar is one which has at most one non terminal on right hand sides of each production (i.e. $S\rightarrow aSb, S\rightarrow aS, S\rightarrow Sb$) (2) left linear is one which have all non terminals on left ends (i.e. $S\rightarrow Sb$) (3) right linear is one which have all non terminals on right ends (i.e. $S\rightarrow aS$) and (4) we can have "another type of linear grammar (not having any specific name)" which can have productions of both forms: right linear and left linear ($S\rightarrow aS, S\rightarrow Sb$ but not $S\rightarrow aSb$ )) – anir Jul 21 '18 at 12:49