Take the 2-minute tour ×
MathOverflow is a question and answer site for professional mathematicians. It's 100% free, no registration required.

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?

share|improve this question
    
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. –  Emil Jeřábek Sep 11 '12 at 12:49
    
Actually I think the computational complexity of isomorphism checking is slower than the polynomial time algorithm above. –  Benjamin Steinberg Sep 11 '12 at 13:21
    
? 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. –  Emil Jeřábek Sep 11 '12 at 13:37
    
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. –  Benjamin Steinberg Sep 11 '12 at 13:48
    
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. ;) –  Alberto Sep 11 '12 at 13:53

1 Answer 1

up vote 2 down vote accepted

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.

share|improve this answer
    
Thank you Benjamin, if you work out a counterexample please publish it. –  Alberto Sep 11 '12 at 18:59
    
My original $R$ is not what I meant to write. I fixed it. –  Benjamin Steinberg Sep 12 '12 at 0:20
    
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$. –  Alberto Sep 12 '12 at 13:25

Your Answer

 
discard

By posting your answer, you agree to the privacy policy and terms of service.

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