Language equations are mathematical statements that resemble numerical equations, but the variables assume values of formal languages rather than numbers. Instead of arithmetic operations in numerical equations, the variables are joined by language operations. Among the most common operations on two languages A and B are the set union AB, the set intersection AB, and the concatenation AB. Finally, as an operation taking a single operand, the set A* denotes the Kleene star of the language A. Therefore, language equations can be used to represent formal grammars, since the languages generated by the grammar must be the solution of a system of language equations.

Language equations and context-free grammars

edit

Ginsburg and Rice[1] gave an alternative definition of context-free grammars by language equations. To every context-free grammar  , is associated a system of equations in variables  . Each variable   is an unknown language over   and is defined by the equation   where  , ...,   are all productions for  . Ginsburg and Rice used a fixed-point iteration argument to show that a solution always exists, and proved that the assignment   is the least solution to this system,[clarify] i.e. any other solution must be a subset[clarify] of this one.

For example, the grammar   corresponds to the equation system   which has as solution every superset of  .

Language equations with added intersection analogously correspond to conjunctive grammars.[citation needed]

Language equations and finite automata

edit

Brzozowski and Leiss[2] studied left language equations where every concatenation is with a singleton constant language on the left, e.g.   with variable  , but not   nor  . Each equation is of the form   with one variable on the right-hand side. Every nondeterministic finite automaton has such corresponding equation using left-concatenation and union, see Fig. 1. If intersection operation is allowed, equations correspond to alternating finite automata.

 
Fig. 1: A finite automaton with associated system of equations  ,   where   is the empty word.[2]: 21 

Baader and Narendran[3] studied equations   using left-concatenation and union and proved that their satisfiability problem is EXPTIME-complete.

Conway's problem

edit

Conway[4] proposed the following problem: given a constant finite language  , is the greatest solution of the equation   always regular? This problem was studied by Karhumäki and Petre[5][6] who gave an affirmative answer in a special case. A strongly negative answer to Conway's problem was given by Kunc[7] who constructed a finite language   such that the greatest solution of this equation is not recursively enumerable.

Kunc[8] also proved that the greatest solution of inequality   is always regular.

Language equations with Boolean operations

edit

Language equations with concatenation and Boolean operations were first studied by Parikh, Chandra, Halpern and Meyer [9] 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[10] proved that the unsatisfiability problem is RE-complete and that every recursive language is a unique solution of some equation.

Language equations over a unary alphabet

edit

For a one-letter alphabet, Leiss[11] discovered the first language equation with a nonregular solution, using complementation and concatenation operations. Later, Jeż[12] showed that non-regular unary languages can be defined by language equations with union, intersection and concatenation, equivalent to conjunctive grammars. By this method Jeż and Okhotin[13] proved that every recursive unary language is a unique solution of some equation.

See also

edit

References

edit
  1. ^ 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.
  2. ^ a b 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.
  3. ^ 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.
  4. ^ Conway, John Horton (1971). Regular Algebra and Finite Machines. Chapman and Hall. ISBN 978-0-486-48583-6.
  5. ^ 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.
  6. ^ 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.
  7. ^ 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.
  8. ^ 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.
  9. ^ 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.
  10. ^ 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.
  11. ^ 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.
  12. ^ 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.
  13. ^ 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.
edit