Linear grammar

Linear grammar

In computer science, a grammar is linear if it is context-free and all of its productions' right hand sides have at most one nonterminal.

A "linear language" is a language generated by some linear grammar.


A simple linear grammar is "G" with "N" = {S}, Σ = {a, b}, "P" with start symbol "S" and rules: S → aSb: S → εIt generates the language { a^ib^i | i >= 0}.

Relationship with regular grammars

Two special types of linear grammars are the following:
* the "left-linear" or left regular grammars, in which all nonterminals in right hand sides are at the left ends;
* the "right-linear" or right regular grammars, in which all nonterminals in right hand sides are at the right ends.Collectively, they are known as the regular grammars; both can describe exactly the regular languages.

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.

By inserting new nonterminals, every linear grammar can be brought into this form without affecting the language generated.For instance, the rules of "G" above can be replaced with: S → aA: A → Sb: S → ε

Hence, linear grammars of this special form can generate all linear languages.

Expressive power

We have seen that all regular languages are linear; the example gave a linear, non-regular language.All linear languages are context-free by definition; a simple example of a context-free, non-linear language is the Dyck language of well-balanced bracket pairs.

Hence, the regular languages are a proper subset of the linear ones, which in turn are a proper subset of the context-free languages.

Wikimedia Foundation. 2010.

Look at other dictionaries:

  • Grammar Explorer — is a language learning resource that was co funded by the European Commission as part of its [ en.html Lingua programme] within the SOCRATES programme. The grammar is based on the… …   Wikipedia

  • Linear B — Infobox Writing system name=Linear B type=Syllabary typedesc=with additional Logograms time=Late Bronze Age status=Extinct languages=Mycenaean Greek fam1= Linear A sisters=Cypro Minoan syllabary unicode=… …   Wikipedia

  • Regular grammar — Strictly regular grammars = In computer science, a right regular grammar (also called right linear grammar) is a formal grammar ( N , Σ, P , S ) such that all the production rules in P are of one of the following forms: # A → a where A is a non… …   Wikipedia

  • Parsing expression grammar — A parsing expression grammar, or PEG, is a type of analytic formal grammar that describes a formal language in terms of a set of rules for recognizing strings in the language. A parsing expression grammar essentially represents a recursive… …   Wikipedia

  • Context-free grammar — In formal language theory, a context free grammar (CFG) is a formal grammar in which every production rule is of the form V → w where V is a single nonterminal symbol, and w is a string of terminals and/or nonterminals (w can be empty). The… …   Wikipedia

  • Formal grammar — In formal semantics, computer science and linguistics, a formal grammar (also called formation rules) is a precise description of a formal language ndash; that is, of a set of strings over some alphabet. In other words, a grammar describes which… …   Wikipedia

  • Context-sensitive grammar — A context sensitive grammar (CSG) is a formal grammar in which the left hand sides and right hand sides of any production rules may be surrounded by a context of terminal and nonterminal symbols. Context sensitive grammars are more general than… …   Wikipedia

  • Controlled grammar — Controlled grammars[1] are a class of grammars that extend, usually, the context free grammars with additional controls on the derivations of a sentence in the language. A number of different kinds of controlled grammars exist, the four main… …   Wikipedia

  • Indexed grammar — An indexed grammar is a formal grammar which describes indexed languages. They have three disjoint sets of symbols: the usual terminals and nonterminals and the indices, which appear only in intermediate derivation steps.Productions can replace a …   Wikipedia

  • Discontinuous-constituent phrase structure grammar — (DCPSG) (distinct from Discontinuous Phrase Structure Grammar/DPSG) is a formalism for describing discontinuous phrase structures in natural language, such as verb phrases in VSO languages. The formalism was introduced in the slightly more… …   Wikipedia

Share the article and excerpts

Direct link
Do a right-click on the link above
and select “Copy Link”

We are using cookies for the best presentation of our site. Continuing to use this site, you agree with this.