finite-automataequivalenceautomaton

Equivalence between two automata


Which is the best or easiest method for determining equivalence between two automata?

I.e., if given two finite automata A and B, how can I determine whether both recognize the same language?

They are both deterministic or both nondeterministic.


Solution

  • Two nondeterministic finite automota (NFA's) are equivalent if they accept the same language.

    To determine whether they accept the same language, we look at the fact that every NFA has a minimal DFA, where no two states are identical. A minimal DFA is also unique. Thus, given two NFA's, if you find that their corresponding minimal DFA's are equivalent, then the two NFA's must also be equivalent.

    For an in-depth study on this topic, I highly recommend that you read An Introduction to Formal Language and Automata.