1
$\begingroup$

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?

Improve this question
$\endgroup$

1 Answer 1

Reset to default
3
$\begingroup$

They second quote from Wikipedia has lost its context. Here it is complete, with emphasis added:

Another special type of linear grammar is the following:

  • 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.

A linear grammar has at most one non-terminal on the right-hand side of any rule, as per Linz' definition.

But any linear grammar can be transformed into an equivalent linear grammar of that special type, simply by adding a new non-terminal. Wikipedia goes on to show an example of this transformation. So it is possible to assume wolog that a linear grammar is in that form, if it turns out to be helpful.

Improve this answer
$\endgroup$
2
  • $\begingroup$ 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$ )) $\endgroup$
    – RajS
    Commented Jul 21, 2018 at 12:49
  • $\begingroup$ @anlr: That's basically what Wikipedia is saying, yes. I personally wouldn't have phrased it that way; the point is that the restricted form (non-terminals are always at one end) does not restrict the expressivity of linear grammars. Nevertheless, the key point of a linear grammar is that every rhs has at most one non-terminal. That's why it's called linear. It's like a linear polynomial: the largest exponent must be one (and you can canonicalise by collapsing all the linear terms into a single term). $\endgroup$
    – rici
    Commented Jul 21, 2018 at 14:38

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service and acknowledge you have read our privacy policy.

Not the answer you're looking for? Browse other questions tagged or ask your own question.