4
$\begingroup$

Given two regular expressions $R$ and $S$ on an alphabet $\Sigma$ it is possible to decide their equivalence as follows:

  1. build two finite automata $M_R$ and $M_S$ such that $L(R) = L(M_R)$ and $L(S) = L(M_S)$
  2. build an automaton $M$ such that $L(M) = (L(M_R) - L(M_S)) \cup (L(M_S) - L(M_R))$
  3. test emptyness of $L(M)$ using a reachability algorithm on $M$

I was wondering if there is another way to decide equivalence. Suppose $M_R$ and $M_S$ are the minimal DFA (without epsilon-moves) such that $L(R) = L(M_R)$ and $L(S) = L(M_S)$. If they have a different number of states, then $R$ and $S$ are not equivalent. Otherwise let $m$ be the number of states of the two automata. Is it true that $L(M_R) = L(M_S)$ iff ${x \in L(M_R) : |x| \leq m +1 } = {x \in L(M_S) : |x| \leq m +1 }$? How to prove that with the Myhill-Nerode theorem?

$\endgroup$
6
  • $\begingroup$ The minimal automaton of a given language is unique, so if you can compute it, you can decide equivalence more easily just by checking whether the two automata are isomorphic. $\endgroup$ Sep 11, 2012 at 12:49
  • $\begingroup$ Actually I think the computational complexity of isomorphism checking is slower than the polynomial time algorithm above. $\endgroup$ Sep 11, 2012 at 13:21
  • $\begingroup$ ? Isomorphism checking for DFA can be done in more or less linear time (depending on the computational model), whereas checking all words whose length is bounded by the size of the automata needs exponential time. $\endgroup$ Sep 11, 2012 at 13:37
  • $\begingroup$ Yes, I agree that isomorphism checking is fast. I think the algorithm above, which is the standard one, is usually used because one doesn't have to minimize first (although minimizing is pretty fast). Emptiness testing is essentially linear step 2 above is essentially quadratic. I think minimizing is slightly above quadratic but I don't remember. $\endgroup$ Sep 11, 2012 at 13:48
  • $\begingroup$ Thank you very much... But actually I wasn't bothering about computational complexity, but just about the correctness of the last statement, and how to prove it if it is true. ;) $\endgroup$
    – Alberto
    Sep 11, 2012 at 13:53

1 Answer 1

2
$\begingroup$

If $M_R$ and $M_S$ have $m,n$ states respectively, then one has that $L(M_R)=L(M_S)$ iff they have the same words of length at most $mn-1$. This is essentially the content of your algorithm. Suppose that they are different and let $w$ be a minimal length word accepted by one of the machines and not the other. If $w$ has length greater than $mn-1$, then when you run $w$ from the initial state of $M_R\times M_S$, you will get a loop. This loop will give you a factorization $w=xuy$ where $u$ reads a loop in both $M_R$ and $M_S$. So then $xy$ will be accepted in one of the machines and not the other and have smaller length.

I don't think your proposed bound would work but I have to think a little to get an example.

Added. I believe this is a counter example. Let m be an integer. Consider over a unary alphabet the languages $R=\lbrace a^n\mid n\not\equiv m-2 \pmod m\rbrace$ and $S=\lbrace 1,a,..,a^{m-3}\rbrace\cup \lbrace a^n\mid n\geq m-1\rbrace$. Then both of these are recognized by an $m$-state automaton (I believe both are minimal) and the shortest word in one, but not the other, is $a^{2m-2}$, which has length $2m-2$. I hope this works.

$\endgroup$
2
  • $\begingroup$ Thank you Benjamin, if you work out a counterexample please publish it. $\endgroup$
    – Alberto
    Sep 11, 2012 at 18:59
  • $\begingroup$ That is indeed correct. Restating a little bit, we can also say what follows. The index $\mathsf{ind}(L)$ of a regular language is the size of the smallest DFA that accepts $L$. Let $m >1$ be a natural number and define $L_1 = \{a^n : n \text{ not multiple of } m\}$ and $L_2 = \{a^n : n \geq 1,\ n \neq m\}$. Then $L_1$ and $L_2$ are regular languages over the unary alphabet $\{a\}$, $\mathsf{ind}(L_1) = \mathsf{ind}(L_2) = m+2$, $\{x \in L_1 : |x| < 2m \} = \{x \in L_2 : |x| < 2m \}$ but $L_1 \neq L_2$. $\endgroup$
    – Alberto
    Sep 12, 2012 at 13:25

Your Answer

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

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