Test whether two languages are equal, when give in algebraic form
This sub-problem is motivated by Algorithm to test whether a language is regular.
Suppose we have two languages $L_1,L_2$ that are expressed in "algebraic" form, as formalized below. I want to determine whether $L_1 = L_2$.
Is this decidable? If yes, can anyone suggest an algorithm for this? If not, can anyone suggest a semi-algorithm (one that returns "equal", "not equal", or "I'm not sure"; where we want it to return "not sure" as rarely as possible).
Motivation: A solution to this sub-problem would be helpful for solving Algorithm to test whether a language is regular
Algebraic form. Here's one possible definition of what I mean by a representation of a language in algebraic form. Such a language is given by
$$L = \{E : S\}$$
where $E$ is a word-expression and $S$ is a system of linear inequalities over the length-variables, with the following definitions:
Each of $x,y,z,\dots$ is a word-expression. (These represent variables that can take on any word in $\Sigma^*$.)
Each of $x^r,y^r,z^r,\dots$ is a word-expression. (Here $x^r$ represents the reverse of the string $x$.)
Each of $a,b,c,\dots$ is a word-expression. (Implicitly, $\Sigma=\{a,b,c,\dots\}$, so $a,b,c,\dots$ represent a single symbol in the underlying alphabet.)
Each of $a^\eta,b^\eta,c^\eta,\dots$ is a word-expression, if $\eta$ is a length-variable.
The concatenation of word-expressions is a word-expression.
Each of $m,n,p,q,\dots$ is a length-variable. (These represent variables that can take on any natural number.)
Each of $|x|,|y|,|z|,\dots$ is a length-variable. (These represent the length of a corresponding word.)
My goal is something rich enough to capture many of the examples we see in textbook exercises. (Feel free to suggest modifications to this formalization if it makes the equality-testing problem easier while still remaining expressive enough to capture many of the examples we see in textbooks.)
Some easier cases. If the original problem is too hard, here are some sub-cases that would still be interesting:
If $L_1,L_2$ are two languages specified in "algebraic" form as above, and $L_1\ne L_2$, let $d(L_1,L_2)$ denote the length of the shortest word that is an element of one of $L_1,L_2$ but not the other. Can we upper-bound $d(L_1,L_2)$ as a function of the length of the descriptions of $L_1,L_2$? Is it guaranteed to always be polynomial? at most singly-exponential?
Motivation: If we could prove it is always polynomial, this might help us exhibit a witness that $L_1 \ne L_2$.
If we omit the reversal operation (we do not allow $x^r,y^r,\dots$), does the problem become easier?
algorithms formal-languages regular-languages decision-problem
D.W.♦D.W.
$\begingroup$ Are those algebraic form languages and context free languages the same ? $\endgroup$ – François Jun 19 '15 at 16:40
$\begingroup$ @FrançoisG., no. For instance, $\{w^\eta w^\eta : w \in \Sigma^*, \eta \in \mathbb{N}\}$ is not context-free but has an algebraic form. (I don't know whether every context-free language has an algebraic form expression; I don't see any reason to expect this to be true.) I know that testing equality of two context-free languages is undecidable. I don't know how hard the first sub-case (at the end of the question) is if $L_1,L_2$ are two context-free languages. $\endgroup$ – D.W.♦ Jun 19 '15 at 17:27
$\begingroup$ I don't see how to express Dyck languages in this framework. $\endgroup$ – Raphael♦ Oct 30 '16 at 19:40
Browse other questions tagged algorithms formal-languages regular-languages decision-problem or ask your own question.
Algorithm to test whether a language is regular
Algorithm to test whether a language is context-free
prove decidability and recognizability
Algorithm that deside if there are two words $x$ and $y$ in the same length such that $x\in L(A_1)$ and $y\in L(A_2)$
Is the word problem for regular languages in ALogTime?
Regular language such that L(r) = L(r₁) L(r) ∪ L(r₂)
Determining if given languages are regular or recursively enumerable
Is the symmetric difference of a non regular language L and a finite language f non regular?
Is unification over regular expression equations doable?