0
$\begingroup$

Is this problem algorithmically decidable?

L1 and L2 are both regular languages with alphabet $\Sigma$. Does L1 = L2?

I think that it is decidable because you can write regular expressions for each language and see if they are the same. But I'm not sure how to prove it since I see that you prove something is decidable by showing a Turing Machine

Improve this question
$\endgroup$
0

2 Answers 2

Reset to default
0
$\begingroup$

It is decidable, all you have to do is use the closure properties of finite automata + emptiness checking; let me know if you want me details.

I’m not sure exactly how you’d check the equivalence of two regular expressions, other than by converting to automata, so unless this is a practical issue you’re trying to resolve and you receive input in terms of regular expressions, I’d think about it in terms of automata.

As for creating the Turing machine that actually does this, it’s probably not strictly necessary to write out the formal description, as long as you can argue why it’s possible to do so.

Improve this answer
$\endgroup$
2
  • $\begingroup$ thank you! could you expand on "closure properties of finite automata + emptiness checking"? i see that you can convert both regular languages to a DFA and then use EQ_DFA since EQ_DFA is a decidable language. is that what you mean? $\endgroup$
    – IrCa
    Commented Jul 19, 2020 at 23:33
  • $\begingroup$ @IrCa Yep; if you can use that equality of DFAs is decidable then that approach works too. $\endgroup$
    – Reed Oei
    Commented Jul 20, 2020 at 1:03
0
$\begingroup$

This is an alternative approach to Reed's solution.

Since $L_1$ and $L_2$ are regular, there exist DFA $M_1$ and $M_2$ with $T(M_1) = L_1$ and $T(M_2) = L_2$. Minimize those DFA to get $M_1'$ and $M_2'$ using Hopcroft/Ullman algorithm and then check $M_1' \cong M_2'$ (isomorphic) by running BFS on $M_1'$ and $M_2'$ in parallel. Every time you first hit a node in the BFS, keep track of which node in $M_1'$ corresponds to which node in $M_2'$. If you then hit a node for the second time in the BFS, then check if this correspondence is preserved.

Improve this answer
$\endgroup$
2
  • $\begingroup$ could you stop after your first sentence and then use EQ_DFA since that is decidable? $\endgroup$
    – IrCa
    Commented Jul 19, 2020 at 23:45
  • $\begingroup$ If $\textrm{EQ}_{\textrm{DFA}}$ is defined as $\textrm{EQ}_{\textrm{DFA}} := \{(M_1, M_2) \in \{M \mid M \textrm{ is a } DFA\}^2 \mid T(M_1) = T(M_2)\}$ and you have proved that $\textrm{EQ}_{\textrm{DFA}}$ is decidable, then yes. $\endgroup$
    – Niki
    Commented Jul 19, 2020 at 23:52

Not the answer you're looking for? Browse other questions tagged or ask your own question.