Menu
Home
People
Places
Arts
History
Plants & Animals
Science
Life & Culture
Technology
Reference.org
Linear grammar
open-in-new
<h2 id="example">Example</h2> <p>An example of a linear grammar is <i>G</i> with <i>N</i> = {S}, Σ = {a, b}, <i>P</i> with start symbol <i>S</i> and rules </p> S → aSb S → ε <p>It generates the language { a i b i ∣ i ≥ 0 } {\displaystyle \{a^{i}b^{i}\mid i\geq 0\}} . </p> <h2 id="relationship-with-regular-grammars">Relationship with regular grammars</h2> <p>Two special types of linear grammars are the following: </p> <ul><li>the left-linear or left-regular grammars, in which all rules are of the form <i>A → αw</i> where <i>α</i> is either empty or a single nonterminal and <i>w</i> is a string of terminals;</li> <li>the right-linear or right-regular grammars, in which all rules are of the form <i>A → wα</i> where <i>w</i> is a string of terminals and <i>α</i> is either empty or a single nonterminal.</li></ul> <p>Each of these can describe exactly the <a href="/facts/Regular_language/ahxw67T1">regular languages</a>. A <a href="/facts/Regular_grammar/EFCPJB9K">regular grammar</a> is a grammar that is left-linear or right-linear. </p><p>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 <i>G</i> above can be replaced with </p> S → aA A → Sb S → ε <p>However, the requirement that <i>all</i> rules be left-linear (or all rules be right-linear) leads to a strict decrease in the expressive power of linear grammars. </p> <h2 id="expressive-power">Expressive power</h2> <p>All regular languages are linear; conversely, an example of a linear, non-regular language is { a<i>n</i>b<i>n</i> }. as explained above. All linear languages are <a href="/facts/Context-free_language/sHDxB5So">context-free</a>; conversely, an example of a context-free, non-linear language is the <a href="/facts/Dyck_language/L3ro6dWp">Dyck language</a> of well-balanced bracket pairs. Hence, the regular languages are a <a href="/facts/Proper_subset/SJGERmbA">proper subset</a> of the linear languages, which in turn are a proper subset of the context-free languages. </p><p>While regular languages are <a href="/facts/Deterministic_context-free_language/XDlUnBJ8">deterministic</a>, there exist linear languages that are nondeterministic. For example, the language of even-length <a href="/facts/Palindrome/PHo33zqN">palindromes</a> 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.<a class="footnote-ref" id="fnref:1" href="#fn:1"><sup>1</sup></a> This language is nondeterministic. Since nondeterministic context-free languages cannot be accepted in linear time , 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.<a class="footnote-ref" id="fnref:2" href="#fn:2"><sup>2</sup></a> </p><p>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. </p> <h2 id="closure-properties">Closure properties</h2> <h3>Positive cases</h3> <p>Linear languages are closed under <a href="/facts/Union_(set_theory)/KVVXKfWl">union</a>. Construction is the same as the construction for the union of context-free languages. Let L 1 , L 2 {\displaystyle L_{1},L_{2}} be two linear languages, then L 1 ∪ L 2 {\displaystyle L_{1}\cup L_{2}} is constructed by a linear grammar with S → S 1 | S 2 {\displaystyle S\to S_{1}|S_{2}} , and S 1 , S 2 {\displaystyle S_{1},S_{2}} playing the role of the linear grammars for L 1 , L 2 {\displaystyle L_{1},L_{2}} . </p><p>If <i>L</i> is a linear language and <i>M</i> is a <i>regular</i> language, then the <a href="/facts/Intersection_(set_theory)/RPfUNJh9">intersection</a> L ∩ M {\displaystyle L\cap M} is again a linear language; in other words, the linear languages are closed under intersection with regular sets. </p><p>Linear languages are closed under <a href="/facts/String_operations/08G9Cevy">homomorphism</a> and <a href="/facts/String_operations/08G9Cevy">inverse homomorphism</a>.<a class="footnote-ref" id="fnref:3" href="#fn:3"><sup>3</sup></a> </p><p>As a <a href="/facts/Corollary/ntQ8zR9N">corollary</a>, linear languages form a <a href="/facts/Cone_(formal_languages)/XbHtEWsV">full trio</a>. Full trios in general are language families that enjoy a couple of other desirable mathematical properties. </p> <h3>Negative cases</h3> <p>Linear languages are not closed under intersection. For example, let L 1 = { a n b n c m ∣ n , m ≥ 0 } , L 2 = { a n b m c m ∣ n , m ≥ 0 } {\displaystyle L_{1}=\{a^{n}b^{n}c^{m}\mid n,m\geq 0\},L_{2}=\{a^{n}b^{m}c^{m}\mid n,m\geq 0\}} , then their intersection is not only not linear, but also not context-free. See <a href="/facts/Pumping_lemma_for_context-free_languages/Le9Ba8gY">pumping lemma for context-free languages</a>. </p><p>As a corollary, linear languages are not closed under complement (as intersection can be constructed by <a href="/facts/De_Morgan%2527s_laws/dj3F8xpt">de Morgan's laws</a> out of union and complement). </p> <h2 id="references">References</h2> <ol> <li id="fn:1"><p>Hopcroft, John; Rajeev Motwani; Jeffrey Ullman (2001). Introduction to automata theory, languages, and computation 2nd edition. Addison-Wesley. pp. 249–253. <a href="/wiki/John_Hopcroft" target="_blank">/wiki/John_Hopcroft</a> <a href="#fnref:1" class="footnote-back-ref">↩</a></p></li> <li id="fn:2"><p>Greibach, Sheila (October 1966). "The Unsolvability of the Recognition of Linear Context-Free Languages". Journal of the ACM. 13 (4): 582–587. doi:10.1145/321356.321365. S2CID 37003419. <a href="https://doi.org/10.1145%2F321356.321365" target="_blank">https://doi.org/10.1145%2F321356.321365</a> <a href="#fnref:2" class="footnote-back-ref">↩</a></p></li> <li id="fn:3"><p>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 <a href="/wiki/Introduction_to_Automata_Theory,_Languages,_and_Computation" target="_blank">/wiki/Introduction_to_Automata_Theory,_Languages,_and_Computation</a> <a href="#fnref:3" class="footnote-back-ref">↩</a></p></li> </ol>