Non-linear grammars

Question

I look for information about grammars which can be described by a non-linear equation such as a quadratic equation:

$\qquad \displaystyle G \to G G a \mid b$

or

$\qquad \displaystyle G \to G G \mid y G z \mid z G y \mid \varepsilon$

While there is lots of material about linear grammars, their connection with regular languages etc. "quadratic grammars" ( a term, which doesn't even seem to exist ) are only mentioned when an author presents some counterexamples for a parsing algorithm in order to show its limitations.

Is there an autonomous treatment of grammars which can be described by general polynomial equations?

• jmad: Would you allow all production rules of the form: $G → w_1 G w_2 G w_3$?
• David Lewis: Are you limiting these grammars to one non-terminal, $G$? Or are there arbitrarily many? If many, then you are probably into the realm of all context-free languages, which are sometimes described as the algebraic languages, as opposed to the rational languages, that is, the regular languages.
• schluehk: The one rule restriction is not necessary.
• schluehk: The one rule restriction is not necessary but jumping from regular grammars to the whole CFGs is a bit of a bold leap. One usually admits the existence of LL or LR grammars as useful restrictions for certain kinds of parsers. But then one seemingly stops to create intermediary grammars. Suppose I would like to express that a parser has O(N^k) complexity for grammars of a certain polynomial power. Is there a way to talk about it within the conventions of formal language theory?
• Tsuyoshi Ito: No one asked if you restrict to one rule (a context-free grammar with one rule is uninteresting). David Lewis’s question is whether you restrict to one nonterminal.

Answer 1

I'm going to attempt to answer your question, risking the possibility I have misunderstood you.

If we restrict context-free grammars to only a single nonterminal per rule, then the resulting class of grammars are exactly the linear grammars (by definition). However, if we allow more than one nonterminal per rule, then we are back at all context-free grammars.

This can quite easily be seen by considering the Chomsky normal form, in which any rule contains either exactly one terminal, two nonterminals or the empty string (in this last case the left hand side is further constrained to be the starting symbol). Any context-free language is described by some context-free grammar in Chomsky normal form, so we are back at the full range of languages.

I don't know about the case if you make the restriction to just one nonterminal.

• Raphael: I guess the OP is after languages that can not be described by linear grammars, such as the Dyck language.