Menu
Home
People
Places
Arts
History
Plants & Animals
Science
Life & Culture
Technology
Reference.org
Language equation
open-in-new
<h2 id="language-equations-and-context-free-grammars">Language equations and context-free grammars</h2> <p><a href="/facts/Seymour_Ginsburg/l5Are2u3">Ginsburg</a> and <a href="/facts/Henry_Gordon_Rice/ATbIj55o">Rice</a><a class="footnote-ref" id="fnref:1" href="#fn:1"><sup>1</sup></a> gave an alternative definition of <a href="/facts/Context-free_grammar/yu1FFdK4">context-free grammars</a> by language equations. To every context-free grammar G = ( V , Σ , R , S ) {\displaystyle G=(V,\Sigma ,R,S)} , is associated a system of equations in variables V {\displaystyle V} . Each variable X ∈ V {\displaystyle X\in V} is an unknown language over Σ {\displaystyle \Sigma } and is defined by the equation X = α 1 ∪ … ∪ α m {\displaystyle X=\alpha _{1}\cup \ldots \cup \alpha _{m}} where X → α 1 {\displaystyle X\to \alpha _{1}} , ..., X → α m {\displaystyle X\to \alpha _{m}} are all productions for X {\displaystyle X} . Ginsburg and Rice used a <a href="/facts/Fixed-point_iteration/05dQGazd">fixed-point iteration</a> argument to show that a solution always exists, and proved that the assignment X = L G ( X ) {\displaystyle X=L_{G}(X)} is the <i>least solution</i> to this system,[<i>clarify</i>] i.e. any other solution must be a subset[<i>clarify</i>] of this one. </p><p>For example, the grammar S → a S c ∣ b ∣ S {\displaystyle S\to aSc\mid b\mid S} corresponds to the equation system S = ( { a } ⋅ S ⋅ { c } ) ∪ { b } ∪ S {\displaystyle S=(\{a\}\cdot S\cdot \{c\})\cup \{b\}\cup S} which has as solution every superset of { a n b c n ∣ n ∈ N } {\displaystyle \{a^{n}bc^{n}\mid n\in {\mathcal {N}}\}} . </p><p>Language equations with added intersection analogously correspond to <a href="/facts/Conjunctive_grammars/yGvYGKBP">conjunctive grammars</a>. </p> <h2 id="language-equations-and-finite-automata">Language equations and finite automata</h2> <p><a href="/facts/Janusz_Brzozowski_(computer_scientist)/yDTf7NA8">Brzozowski</a> and Leiss<a class="footnote-ref" id="fnref:2" href="#fn:2"><sup>2</sup></a> studied <i>left language equations</i> where every concatenation is with a singleton constant language on the left, e.g. { a } ⋅ X {\displaystyle \{a\}\cdot X} with variable X {\displaystyle X} , but not X ⋅ Y {\displaystyle X\cdot Y} nor X ⋅ { a } {\displaystyle X\cdot \{a\}} . Each equation is of the form X i = F ( X 1 , . . . , X k ) {\displaystyle X_{i}=F(X_{1},...,X_{k})} with one variable on the right-hand side. Every <a href="/facts/Nondeterministic_finite_automaton/fW600oAl">nondeterministic finite automaton</a> has such corresponding equation using left-concatenation and union, see Fig. 1. If intersection operation is allowed, equations correspond to <a href="/facts/Alternating_finite_automaton/gHTT6fQq">alternating finite automata</a>. </p> <p><a href="/facts/Franz_Baader/t6bYooMc">Baader</a> and Narendran<a class="footnote-ref" id="fnref:3" href="#fn:3"><sup>3</sup></a> studied equations F ( X 1 , … , X k ) = G ( X 1 , … , X k ) {\displaystyle F(X_{1},\ldots ,X_{k})=G(X_{1},\ldots ,X_{k})} using left-concatenation and union and proved that their satisfiability problem is <a href="/facts/EXPTIME-complete/GbTmY8t5">EXPTIME-complete</a>. </p> <h2 id="conways-problem">Conway's problem</h2> <p><a href="/facts/John_Horton_Conway/g3PA1zoK">Conway</a><a class="footnote-ref" id="fnref:4" href="#fn:4"><sup>4</sup></a> proposed the following problem: given a constant finite language L {\displaystyle L} , is the greatest solution of the equation L X = X L {\displaystyle LX=XL} always regular? This problem was studied by <a href="/facts/Juhani_Karhum%25C3%25A4ki/gI7cz8nC">Karhumäki</a> and Petre<a class="footnote-ref" id="fnref:5" href="#fn:5"><sup>5</sup></a><a class="footnote-ref" id="fnref:6" href="#fn:6"><sup>6</sup></a> who gave an affirmative answer in a special case. A strongly negative answer to Conway's problem was given by Kunc<a class="footnote-ref" id="fnref:7" href="#fn:7"><sup>7</sup></a> who constructed a finite language L {\displaystyle L} such that the greatest solution of this equation is not recursively enumerable. </p><p>Kunc<a class="footnote-ref" id="fnref:8" href="#fn:8"><sup>8</sup></a> also proved that the greatest solution of inequality L X ⊆ X L {\displaystyle LX\subseteq XL} is always regular. </p> <h2 id="language-equations-with-boolean-operations">Language equations with Boolean operations</h2> <p>Language equations with concatenation and Boolean operations were first studied by <a href="/facts/Rohit_Parikh/8D9q6wuJ">Parikh</a>, <a href="/facts/Ashok_K._Chandra/wlq4zd4M">Chandra</a>, <a href="/facts/Joseph_Halpern/TWt4dnBh">Halpern</a> and <a href="/facts/Albert_R._Meyer/31B10sEp">Meyer</a> <a class="footnote-ref" id="fnref:9" href="#fn:9"><sup>9</sup></a> who proved that the satisfiability problem for a given equation is undecidable, and that if a system of language equations has a unique solution, then that solution is recursive. Later, Okhotin<a class="footnote-ref" id="fnref:10" href="#fn:10"><sup>10</sup></a> proved that the unsatisfiability problem is <a href="/facts/RE-complete/lqtossYw">RE-complete</a> and that every recursive language is a unique solution of some equation. </p> <h2 id="language-equations-over-a-unary-alphabet">Language equations over a unary alphabet</h2> <p>For a one-letter alphabet, Leiss<a class="footnote-ref" id="fnref:11" href="#fn:11"><sup>11</sup></a> discovered the first language equation with a nonregular solution, using complementation and concatenation operations. Later, Jeż<a class="footnote-ref" id="fnref:12" href="#fn:12"><sup>12</sup></a> showed that non-regular unary languages can be defined by language equations with union, intersection and concatenation, equivalent to <a href="/facts/Conjunctive_grammar/yGvYGKBP">conjunctive grammars</a>. By this method Jeż and Okhotin<a class="footnote-ref" id="fnref:13" href="#fn:13"><sup>13</sup></a> proved that every recursive unary language is a unique solution of some equation. </p> <h2 id="see-also">See also</h2> <ul><li><a href="/facts/Boolean_grammar/q2IP1ocH">Boolean grammar</a></li> <li><a href="/facts/Arden%2527s_rule/dfqragA1">Arden's rule</a></li> <li><a href="/facts/Set_constraint/pQf2bozS">Set constraint</a></li></ul> <h2 id="external-links">External links</h2> <ul><li><a href="http://www.math.utu.fi/dlt2007/tale/">Workshop on Theory and Applications of Language Equations (TALE 2007)</a></li></ul> <h2 id="references">References</h2> <ol> <li id="fn:1"><p>Ginsburg, Seymour; Rice, H. Gordon (1962). "Two Families of Languages Related to ALGOL". Journal of the ACM. 9 (3): 350–371. doi:10.1145/321127.321132. ISSN 0004-5411. S2CID 16718187. <a href="https://doi.org/10.1145%2F321127.321132" target="_blank">https://doi.org/10.1145%2F321127.321132</a> <a href="#fnref:1" class="footnote-back-ref">↩</a></p></li> <li id="fn:2"><p>Brzozowski, J.A.; Leiss, E. (1980). "On equations for regular languages, finite automata, and sequential networks". Theoretical Computer Science. 10 (1): 19–35. doi:10.1016/0304-3975(80)90069-9. ISSN 0304-3975. <a href="https://doi.org/10.1016%2F0304-3975%2880%2990069-9" target="_blank">https://doi.org/10.1016%2F0304-3975%2880%2990069-9</a> <a href="#fnref:2" class="footnote-back-ref">↩</a></p></li> <li id="fn:3"><p>Baader, Franz; Narendran, Paliath (2001). "Unification of Concept Terms in Description Logics". Journal of Symbolic Computation. 31 (3): 277–305. doi:10.1006/jsco.2000.0426. ISSN 0747-7171. <a href="https://doi.org/10.1006%2Fjsco.2000.0426" target="_blank">https://doi.org/10.1006%2Fjsco.2000.0426</a> <a href="#fnref:3" class="footnote-back-ref">↩</a></p></li> <li id="fn:4"><p>Conway, John Horton (1971). Regular Algebra and Finite Machines. Chapman and Hall. ISBN 978-0-486-48583-6. <a href="978-0-486-48583-6" target="_blank">978-0-486-48583-6</a> <a href="#fnref:4" class="footnote-back-ref">↩</a></p></li> <li id="fn:5"><p>Karhumäki, Juhani; Petre, Ion (2002). "Conway's problem for three-word sets". Theoretical Computer Science. 289 (1): 705–725. doi:10.1016/S0304-3975(01)00389-9. ISSN 0304-3975. <a href="https://doi.org/10.1016%2FS0304-3975%2801%2900389-9" target="_blank">https://doi.org/10.1016%2FS0304-3975%2801%2900389-9</a> <a href="#fnref:5" class="footnote-back-ref">↩</a></p></li> <li id="fn:6"><p>Karhumäki, Juhani; Petre, Ion (2002). The Branching Point Approach to Conway's Problem. Lecture Notes in Computer Science. Vol. 2300. pp. 69–76. doi:10.1007/3-540-45711-9_5. ISBN 978-3-540-43190-9. ISSN 0302-9743. <a href="978-3-540-43190-9" target="_blank">978-3-540-43190-9</a> <a href="#fnref:6" class="footnote-back-ref">↩</a></p></li> <li id="fn:7"><p>Kunc, Michal (2007). "The Power of Commuting with Finite Sets of Words". Theory of Computing Systems. 40 (4): 521–551. doi:10.1007/s00224-006-1321-z. ISSN 1432-4350. S2CID 13406797. <a href="/wiki/Doi_(identifier)" target="_blank">/wiki/Doi_(identifier)</a> <a href="#fnref:7" class="footnote-back-ref">↩</a></p></li> <li id="fn:8"><p>Kunc, Michal (2005). "Regular solutions of language inequalities and well quasi-orders". Theoretical Computer Science. 348 (2–3): 277–293. doi:10.1016/j.tcs.2005.09.018. ISSN 0304-3975. <a href="https://doi.org/10.1016%2Fj.tcs.2005.09.018" target="_blank">https://doi.org/10.1016%2Fj.tcs.2005.09.018</a> <a href="#fnref:8" class="footnote-back-ref">↩</a></p></li> <li id="fn:9"><p>Parikh, Rohit; Chandra, Ashok; Halpern, Joe; Meyer, Albert (1985). "Equations between Regular Terms and an Application to Process Logic". SIAM Journal on Computing. 14 (4): 935–942. doi:10.1137/0214066. ISSN 0097-5397. <a href="/wiki/Doi_(identifier)" target="_blank">/wiki/Doi_(identifier)</a> <a href="#fnref:9" class="footnote-back-ref">↩</a></p></li> <li id="fn:10"><p>Okhotin, Alexander (2010). "Decision problems for language equations". Journal of Computer and System Sciences. 76 (3–4): 251–266. doi:10.1016/j.jcss.2009.08.002. ISSN 0022-0000. <a href="https://doi.org/10.1016%2Fj.jcss.2009.08.002" target="_blank">https://doi.org/10.1016%2Fj.jcss.2009.08.002</a> <a href="#fnref:10" class="footnote-back-ref">↩</a></p></li> <li id="fn:11"><p>Leiss, E.L. (1994). "Unrestricted complementation in language equations over a one-letter alphabet". Theoretical Computer Science. 132 (1–2): 71–84. doi:10.1016/0304-3975(94)90227-5. ISSN 0304-3975. <a href="https://doi.org/10.1016%2F0304-3975%2894%2990227-5" target="_blank">https://doi.org/10.1016%2F0304-3975%2894%2990227-5</a> <a href="#fnref:11" class="footnote-back-ref">↩</a></p></li> <li id="fn:12"><p>Jeż, Artur (2008). "Conjunctive grammars generate non-regular unary languages". International Journal of Foundations of Computer Science. 19 (3): 597–615. doi:10.1142/S012905410800584X. ISSN 0129-0541. <a href="/wiki/Doi_(identifier)" target="_blank">/wiki/Doi_(identifier)</a> <a href="#fnref:12" class="footnote-back-ref">↩</a></p></li> <li id="fn:13"><p>Jeż, Artur; Okhotin, Alexander (2014). "Computational completeness of equations over sets of natural numbers". Information and Computation. 237: 56–94. CiteSeerX 10.1.1.395.2250. doi:10.1016/j.ic.2014.05.001. ISSN 0890-5401. <a href="/wiki/CiteSeerX_(identifier)" target="_blank">/wiki/CiteSeerX_(identifier)</a> <a href="#fnref:13" class="footnote-back-ref">↩</a></p></li> </ol>