Equivalence Relations on Strings Induced by Finite Automata

Much of the theory of finite automata is concerned with a natural equivalence relation on strings induced by the automaton. Given in Automata, we say that two strings and in are equivalent mod , iff in States, that is, iff the strings are taken to the same state by the action of the automaton.

The remarkable fact is that a finite automaton is characterized by two properties: that the equivalence relation is of finite index and that it is invariant under the extension of the strings by the same characters. The last property is stated in terms of appending more characters, say a list of them, to the head of the input (which means to the end of the tape).

Def: An equivalence relation on is called extension invariant

Note, extend
Fact 1. The equivalence relation induced by Automata is of finite index and extension invariant.

It is easy to see that this is true. The largest number of equivalence class in is the number of states of which is finite, and if then clearly

Fact 2. Any extension invariant equivalence relation such that is finite can be defined by a finite automaton.

We build the automaton by using the elements of as states. Extension invariance allows us to define . These links between automata and finite index, extension invariant equivalence relations is independent of the final states. The link is defined in terms of compute_list.

When we add final state information, we can say more about the equivalence relation. Indeed another remarkable fact emerges, namely, if we designate those strings belonging to certain equivalence classes of as ``accepted'', then we can find a minimal state automaton whose final states accept exactly the designated strings. Moreover, the automaton is essentially unique.

Fact 3. Given any language , it induces an equivalence relation defined by iff for all z in , . We call this the equivalence relation induced by L. If is accepted by a finite automaton, then we can show that the equivalence relation induced by this automaton is a refinement of . Moreover, we can build a finite automaton with as states that will be the unique minimal automaton accepting .

These remarkable facts are aggregated into the well-known Myhill-Nerode Theorem which we discuss and prove next. It is the centerpiece of Hopcroft and Ullman's section 3.2.