Two automata are said to be equivalent if they accept the same language. Explicitly, if and are two automata, then is equivalent to if . We write when they are equivalent. It is clear that is an equivalence relation on the class of automata.
First, note that if , then every symbol in a word is a symbol in . In other words, every symbol in a word accepted by (or ) belongs to . As a result, . If is an automaton obtained from by replacing the alphabet with , where , then . This shows that we may, without loss of generality, assume outright, in the definition of equivalence of and , that they have the same underlying alphabet.
The most striking aspect of equivalence of automata is the following:
Every non-deterministic automaton is equivalent to a deterministic one.
Suppose be a non-deterministic automaton. We seek a deterministic automaton such that . Recall that the difference between and lie in the transition functions: is a function from to , whereas is a function from to , and the fact that is required to be a singleton. The key to finding is to realize that can be converted into a function from to .
Now, define , . For and , let
As usual, we extend so it is defined on all of . We want to show that
for any and any . This can be done by induction on the length of :
if , then by definition;
if , then , again by definition;
if , where and , then by the induction step, , so that .
Suppose is accepted by , so that for some . Then
which has non-empty intersection with . So, we want to consists of every element of that has non-empty intersection with . Formally, we define . So what we have just shown is that .
On the other hand, if is accepted by , then (1) above says that , or , or for some , which means is accepted by , proving the proposition. ∎
|Date of creation||2013-03-22 18:03:21|
|Last modified on||2013-03-22 18:03:21|
|Last modified by||CWoo (3771)|