Finding an isomorphism between finite automata

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

More specifically, heres an 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!

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$).

-
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).

-
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.

StackExchange Computer Science Q#5010, answer score: 5