15
$\begingroup$

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?

$\endgroup$
4
  • 1
    $\begingroup$ Are those algebraic form languages and context free languages the same ? $\endgroup$
    – François
    Commented Jun 19, 2015 at 16:40
  • 1
    $\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.
    Commented Jun 19, 2015 at 17:27
  • 3
    $\begingroup$ I don't see how to express Dyck languages in this framework. $\endgroup$
    – Raphael
    Commented Oct 30, 2016 at 19:40
  • $\begingroup$ If it is limited to regular languages, then you can compare them. Regular languages can be converted to finite state machine. And if you minimise two different finite state machines and you end up with the same answer for both, then they are infact the same. (They both handle the same language if they simplify to the same form.) You won't be able to do this for a CFG language, otherwise you would have solved the halting problem. $\endgroup$
    – clinux
    Commented Jun 18, 2022 at 10:51

0

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service and acknowledge you have read our privacy policy.