2
$\begingroup$

Suppose we call two finite state machines equivalent if they "perform the same computation" - they accept the same language, or they produce the same output for any given input. Is there an algorithm for checking if two finite state machines are equivalent?

$\endgroup$
7
$\begingroup$

Given two deterministic finite automata $A_1,A_2$, you can construct the product automaton $A_1 \times A_2$ using the product construction. Let a mixed state be one which is accepting in $A_1$ and rejecting in $A_2$, or vice versa. The two automata are equivalent iff no mixed stated is reachable from the initial state.

$\endgroup$

Your Answer

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

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