Fdtxjr

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 A ∪ B, the set intersection A ∩ B, and the concatenation A⋅B. 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

Ginsburg and Rice^[1]
gave an alternative definition of context-free grammars 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 Vdisplaystyle V. Each variable X∈Vdisplaystyle Xin V is an unknown language over Σdisplaystyle Sigma and is defined by equation X=α1∪…∪αmdisplaystyle X=alpha _1cup ldots cup alpha _m where X→α1displaystyle Xto alpha _1, ..., X→αmdisplaystyle Xto alpha _m are all productions for Xdisplaystyle X. Ginsburg and Rice used a fixed-point iteration argument to show that a solution always exists, and proved that the assignment X=LG(X)displaystyle X=L_G(X) is the least solution to this system, i.e. any other solution must be a componentwise subset of this one.

Language equations with added intersection analogously correspond to conjunctive grammars.

Language equations and finite automata

Brzozowski and Leiss^[2] studied left language equations where every concatenation is with a singleton constant language on the left, e.g. a⋅Xdisplaystyle acdot X with variable Xdisplaystyle X, but not X⋅Ydisplaystyle Xcdot Y nor X⋅adisplaystyle Xcdot a. Each equation is of the form Xi=F(X1,...,Xk)displaystyle X_i=F(X_1,...,X_k) 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 S1=1S1∪0S2displaystyle S_1=1S_1cup 0S_2, S2=1S2∪0S1∪ϵdisplaystyle S_2=1S_2cup 0S_1cup epsilon where ϵdisplaystyle epsilon is the empty word.

Baader and Narendran^[3] studied equations F(X1,…,Xk)=G(X1,…,Xk)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 EXPTIME-complete.

Conway's problem

Conway^[4] proposed the following problem: given a constant finite language Ldisplaystyle L, is the greatest solution of equation LX=XLdisplaystyle LX=XL 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 Ldisplaystyle L such that the greatest solution of this equation is not recursively enumerable.

Kunc^[8] also proved that the greatest solution of inequality LX⊆XLdisplaystyle LXsubseteq XL is always regular.

Language equations with Boolean operations

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

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

• Boolean grammar


• Arden's rule


• Set constraint

References

External links

• Workshop on Theory and Applications of Language Equations (TALE 2007)

This set theory-related article is a stub. You can help Wikipedia by expanding it. v t e