linear grammar

An example of a linear grammar is G with N = {S}, Σ = {a, b}, P with start symbol S and rules

: S → aSb

: S → ε

It generates the language $\backslash \{\; a^ib^i\; \backslash mid\; i\; \backslash geq\; 0\backslash \}$.

Two special types of linear grammars are the following:

• the left-linear or left-regular grammars, in which all rules are of the form A → αw where α is either empty or a single nonterminal and w is a string of terminals;
• the right-linear or right-regular grammars, in which all rules are of the form A → wα where w is a string of terminals and α is either empty or a single nonterminal.

Each of these can describe exactly the regular languages.

A regular grammar is a grammar that is left-linear or right-linear.

Observe that by inserting new nonterminals, any linear grammar can be replaced by an equivalent one where some of the rules are left-linear and some are right-linear. For instance, the rules of G above can be replaced with

: S → aA

: A → Sb

: S → ε

However, the requirement that all rules be left-linear (or all rules be right-linear) leads to a strict decrease in the expressive power of linear grammars.

All regular languages are linear; conversely, an example of a linear, non-regular language is { {{math|aⁿbⁿ}} }. as explained above.

All linear languages are context-free; conversely, an 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 languages, which in turn are a proper subset of the context-free languages.

While regular languages are deterministic, there exist linear languages that are nondeterministic. For example, the language of even-length palindromes on the alphabet of 0 and 1 has the linear grammar S → 0S0 | 1S1 | ε. An arbitrary string of this language cannot be parsed without reading all its letters first which means that a pushdown automaton has to try alternative state transitions to accommodate for the different possible lengths of a semi-parsed string.{{cite book | last = Hopcroft | author-link = John Hopcroft | first = John |author2=Rajeev Motwani |author2-link=Rajeev Motwani |author3=Jeffrey Ullman |author3-link=Jeffrey Ullman | title = Introduction to automata theory, languages, and computation 2nd edition | year = 2001 | publisher = Addison-Wesley | pages = 249–253 }} This language is nondeterministic. Since nondeterministic context-free languages cannot be accepted in linear time {{clarify|date=July 2024|reason=Interpreted literally, this is a very strong claim: a proof of it would be a major breakthrough in complexity theory. Please clarify or include a citation.}}, linear languages cannot be accepted in linear time in the general case. Furthermore, it is undecidable whether a given context-free language is a linear context-free language.{{cite journal | last=Greibach | first=Sheila | title=The Unsolvability of the Recognition of Linear Context-Free Languages |date=October 1966 | journal=Journal of the ACM | volume=13 | issue=4 | pages=582–587 | doi=10.1145/321356.321365| s2cid=37003419 | doi-access=free }}

A language is linear iff it can be generated by a one-turn pushdown automaton – a pushdown automaton that, once it starts popping, never pushes again.

Linear languages are closed under union. Construction is the same as the construction for the union of context-free languages. Let $L\_1,\; L\_2$ be two linear languages, then $L\_1\backslash cup\; L\_2$ is constructed by a linear grammar with $S\; \backslash to\; S\_1|S\_2$, and $S\_1,\; S\_2$ playing the role of the linear grammars for $L\_1,\; L\_2$.

If L is a linear language and M is a regular language, then the intersection $L\; \backslash cap\; M$ is again a linear language; in other words, the linear languages are closed under intersection with regular sets.

Linear languages are closed under homomorphism and inverse homomorphism.John E. Hopcroft and Jeffrey D. Ullman, Introduction to Automata Theory, Languages, and Computation, Addison-Wesley Publishing, Reading Massachusetts, 1979. {{ISBN|0-201-02988-X}}., Ex. 11.1, pp. 282f

As a corollary, linear languages form a full trio. Full trios in general are language families that enjoy a couple of other desirable mathematical properties.

Linear languages are not closed under intersection. For example, let $L\_1\; =\; \backslash \{a^nb^nc^m\; \backslash mid\; n,\; m\; \backslash geq\; 0\backslash \},\; L\_2\; =\; \backslash \{a^nb^mc^m\; \backslash mid\; n,\; m\; \backslash geq\; 0\backslash \}$, then their intersection is not only not linear, but also not context-free. See pumping lemma for context-free languages.

As a corollary, linear languages are not closed under complement (as intersection can be constructed by de Morgan's laws out of union and complement).

{{Reflist}}

{{Formal languages and grammars}}

{{DEFAULTSORT:Linear Grammar}}

Category:Formal languages