equivalent automata

Two automata are said to be equivalentMathworldPlanetmathPlanetmathPlanetmathPlanetmathPlanetmath if they accept the same languagePlanetmathPlanetmath. Explicitly, if A1=(S1,Σ1,δ1,I1,F1) and A2=(S2,Σ2,δ2,I2,F2) are two automata, then A1 is equivalent to A2 if L(A1)=L(A2). We write A1A2 when they are equivalent. It is clear that is an equivalence relation on the class of automata.

First, note that if A1A2, then every symbol αΣ1 in a word aL(A1) is a symbol α in Σ2. In other words, every symbol in a word accepted by A1 (or A2) belongs to Σ:=Σ1Σ2. As a result, L(A1)=L(A2)Σ*. If Bi is an automaton obtained from Ai by replacing the alphabet Σi with Σ, where i=1,2, then BiAi. This shows that we may, without loss of generality, assume outright, in the definition of equivalence of A1 and A2, that they have the same underlying alphabet.

The most striking aspect of equivalence of automata is the following:

Proposition 1.

Every non-deterministic automaton is equivalent to a deterministicMathworldPlanetmath one.


Suppose A=(S1,Σ,δ1,I1,F1) be a non-deterministic automaton. We seek a deterministic automaton B=(S1,Σ,δ2,I2,F2) such that AB. Recall that the difference between A and B lie in the transition functions: δ1 is a function from S1×Σ to P(S1), whereas δ2 is a function from S2×Σ to S2, and the fact that I2 is required to be a singleton. The key to finding B is to realize that δ1 can be converted into a function from P(S1)×Σ to P(S1).

Now, define S2:=P(S1), I2:=I1. For TS1 and αΣ, let


As usual, we extend δ2 so it is defined on all of S2×Σ*. We want to show that


for any sS1 and any aΣ*. This can be done by inductionMathworldPlanetmath on the length of a:

  • if a=λ, then δ2({s},λ)={s}=δ1(s,λ) by definition;

  • if aΣ, then δ2({s},a)=s{s}δ1(s,a)=δ1(s,a), again by definition;

  • if a=bα, where bΣ* and αΣ, then by the induction step, δ2({s},b)=δ1(s,b), so that δ2({s},a)=δ2({s},bα)=δ2(δ2({s},b),α)=δ2(δ1(s,b),α)=tδ1(s,b)δ1(t,α)=δ1(δ1(s,b),α)=δ1(s,bα)=δ1(s,a).

Suppose a is accepted by A, so that δ1(s,a)F1 for some sI1. Then

δ2(I2,a)=sI2δ1(s,a)=sI1δ1(s,a), (1)

which has non-empty intersectionMathworldPlanetmath with F1. So, we want F2 to consists of every element of S2 that has non-empty intersection with F1. Formally, we define F2:={FS1FF1}. So what we have just shown is that L(A)L(B).

On the other hand, if a is accepted by B, then (1) above says that sI1δ1(s,a)F2, or (sI1δ1(s,a))F1, or δ1(s,a)F1 for some sI1, which means a is accepted by A, proving the propositionPlanetmathPlanetmath. ∎

Title equivalent automata
Canonical name EquivalentAutomata
Date of creation 2013-03-22 18:03:21
Last modified on 2013-03-22 18:03:21
Owner CWoo (3771)
Last modified by CWoo (3771)
Numerical id 6
Author CWoo (3771)
Entry type Definition
Classification msc 03D05
Classification msc 68Q45