2
$\begingroup$

Im having trouble figuring out how to determine if two finite automata are the same apart from renumbered states.

More specifically, heres an example: example

It's easy to generate a regular expression by hand and see that both FA produce: b + (ab*a(a+b)), though their states are renumbered, they are identical.

What I'm trying to do is figure out a way to check if the two states are the same apart from state renumbering without generating a regular expression.

Since the states are just renumbered, I'm thinking it has something to do with permutations of the states(1 2 3 4) but am not seeing how to determine if they are equivalent. I'm thinking it has something to do with input like this and relating it to the 24 permutations of the states:

Left       Right
1 a 2      4 a 3
1 b 4      4 b 1
2 a 3      3 a 2
2 b 2      3 b 3
3 a 4      2 a 1
3 b 4      2 b 1

Im more so trying to figure out the algorithm to renumber the states Any ideas or help is greatly appreciated!

$\endgroup$
  • $\begingroup$ Check out this paper (reference obtained via Wikipedia). $\endgroup$ – Raphael Oct 11 '12 at 7:23
  • $\begingroup$ Thanks for that link! I think I couldn't find much information because I didn't think of using the word isomorphic in my search. Thanks for clearing that up $\endgroup$ – user3115 Oct 11 '12 at 22:23
3
$\begingroup$

I can identify a permutation on the set of states $\{1,2,3,4\}$ the turns the left-hand diagram into the right-hand one. In other words, if you renumber the states on the left-hand diagram, you get the right-hand diagram. Thus the two automata are identical up to renumbering.

$\endgroup$
  • $\begingroup$ I guess what Im confused with is this: Will there ever be permutation on the states on one FA that doesn't yield equivalence with the other as long as they have the same number of states?? $\endgroup$ – user3115 Oct 11 '12 at 6:55
  • 1
    $\begingroup$ @NoahJones Sure. Compare $a \to b \to c$ with $a \to \{b,c\}$. $\endgroup$ – Raphael Oct 11 '12 at 7:20
5
$\begingroup$

Here's a simpler approach to testing whether two descriptions of regular languages $L_1, L_2$ are descriptions of the same language ($L_1 = L_2$).

  1. Compute the complement of $L_2$, denoted $\overline{L_2}$. If it's represented as a DFA, this can be done in polynomial time (linear I believe).

  2. Compute the intersection of the automata, $L_1 \cap \overline{L_2} $. If they're both DFAs, then this is can be done in quadratic time and space.

If the intersection is null, then you know there's no word in $L_1$ which is not in $L_2$, meaning that $L_1 \subseteq L_2$.

Perform the same test with $L_1$ and $L_2$ interchanged. If $L_1 \subseteq L_2$ and $L_2 \subseteq L_1$, then the langauges are equal, meaning the minimal DFAs are isomorphic. If your input DFAs are known to be minimal, this will test for isomorphism.

$\endgroup$
3
$\begingroup$

Your question seems to concern only deterministic finite automata $\mathcal{A}_1 = (Q, A, \cdot_1, i_1, F_1)$ and $\mathcal{A}_2 = (Q, A, \cdot_2, i_2, F_2)$ with the same set of states $Q = \{1, ..., n \}$. It is simpler to deal with complete automata (just add a new state $0$ in both automata and put $q \cdot a = 0$ when $q \cdot a$ is undefined) Here is a simple approach. You have to find a permutation $\pi$ on $\{0, 1, ..., n \}$ such that $\pi(0) = 0$, $\pi(i_1) = i_2$, $\pi(F_1) = F_2$ and for all $q \in \{0, 1, ..., n \}$ and $a \in A$, $\pi(q \cdot_1 a) = \pi(q) \cdot_2 a$.

This gives you a simple algorithm to find $\pi$. Start in $i_1$ and perform a depth-first search of the graph of $\mathcal{A}_1$ to compute $\pi$ step by step. Then verify that $\pi$ satisfies the required properties.

In your example, $i_1 = 1$ and $i_2 = 4$, thus $\pi(1) = 4$. Then $2 = 1 \cdot_1 a$ whence $$ \pi(2) = \pi(1 \cdot_1 a) = \pi(1)\cdot_2 a = 4 \cdot_2 a = 3. $$ Next $3 = 2 \cdot_1 a$ whence $$ \pi(3) = \pi(2 \cdot_1 a) = \pi(2)\cdot_2 a = 3 \cdot_2 a = 2. $$ Finally, $4 = 3 \cdot_1 a$ whence $$ \pi(4) = \pi(3 \cdot_1 a) = \pi(3)\cdot_2 a = 2 \cdot_2 a = 1. $$ It remains to check that $\pi$ defines an isomorphism, but this is now easy: \begin{align} \pi(1 \cdot_1 b) &= \pi(4) = 1 \text{ and } \pi(1)\cdot_2 b = 4 \cdot_2 b = 1 \\ \pi(2 \cdot_1 b) &= \pi(2) = 3 \text{ and } \pi(2)\cdot_2 b = 3 \cdot_2 b = 3 \\ \pi(3 \cdot_1 b) &= \pi(4) = 1 \text{ and } \pi(3)\cdot_2 b = 2 \cdot_2 b = 1 \\ \pi(4 \cdot_1 a) &= \pi(0) = 0 \text{ and } \pi(0)\cdot_2 a = 0 \cdot_2 a = 0 \\ \pi(4 \cdot_1 b) &= \pi(0) = 0 \text{ and } \pi(0)\cdot_2 b = 0 \cdot_2 b = 1 \\ \end{align} Finally $F_1= \{4\}$ and $F_2 = \{1\} = \pi(F_1)$.

$\endgroup$

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy