Language equation

Ginsburg and Rice[1] gave an alternative definition of context-free grammars by language equations. To every context-free grammar ${\displaystyle G=(V,\Sigma ,R,S)}$, is associated a system of equations in variables ${\displaystyle V}$. Each variable ${\displaystyle X\in V}$ is an unknown language over ${\displaystyle \Sigma }$ and is defined by the equation ${\displaystyle X=\alpha _{1}\cup \ldots \cup \alpha _{m}}$ where ${\displaystyle X\to \alpha _{1}}$, ..., ${\displaystyle X\to \alpha _{m}}$ are all productions for ${\displaystyle X}$. Ginsburg and Rice used a fixed-point iteration argument to show that a solution always exists, and proved that the assignment ${\displaystyle X=L_{G}(X)}$ is the least solution to this system, i.e. any other solution must be a subset of this one.

For example, the grammar ${\displaystyle S\to aSc\mid b\mid S}$ corresponds to the equation system ${\displaystyle S=(\{a\}\cdot S\cdot \{c\})\cup \{b\}\cup S}$ which has as solution every superset of ${\displaystyle \{a^{n}bc^{n}\mid n\in {\mathcal {N}}\}}$.

Language equations with added intersection analogously correspond to conjunctive grammars.

Brzozowski and Leiss[2] studied left language equations where every concatenation is with a singleton constant language on the left, e.g. ${\displaystyle \{a\}\cdot X}$ with variable ${\displaystyle X}$, but not ${\displaystyle X\cdot Y}$ nor ${\displaystyle X\cdot \{a\}}$. Each equation is of the form ${\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 ${\displaystyle S_{1}=1\cdot S_{1}\cup 0\cdot S_{2}\cup \{\epsilon \}}$, ${\displaystyle S_{2}=1\cdot S_{2}\cup 0\cdot S_{1}}$ where ${\displaystyle \epsilon }$ is the empty word.[2]^: 21

Baader and Narendran[3] studied equations ${\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[4] proposed the following problem: given a constant finite language ${\displaystyle L}$, is the greatest solution of the equation ${\displaystyle 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 ${\displaystyle L}$ such that the greatest solution of this equation is not recursively enumerable.

Kunc[8] also proved that the greatest solution of inequality ${\displaystyle LX\subseteq XL}$ is always regular.

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.

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.

• Boolean grammar
• Arden's rule
• Set constraint

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