reduced automaton


Besides eliminating useless states that do not contribute to word acceptance, what else can we do to “clean up” an automaton? In other words, we would like to reduce the number of states in an automaton to as small as possible without affecting its power of accepting words.

The next thing we can do is to look to find states that do the same thing and combine them into one state. Two states do the same thing if, acting as starting states, when an arbitrary word is fed into the automaton, they lead to the same conclusionMathworldPlanetmath: either both accept the word, or both reject it. Arbitrary automata are too general to ensure definite conclusions, so we restrict our attention to deterministicMathworldPlanetmath finite automata.

Definition. Let A=(S,Σ,δ,q0,F) be an automaton with a single start state q0. For any state sS, define As to be the automaton obtained from A by replacing q0 by s. In other words, As:=(S,Σ,δ,s,F). Two states s,tS are said to be indistinguishable if L(As)=L(At).

Let us write st to mean that s and t are indistinguishable. Then is an equivalence relationMathworldPlanetmath on S. For each sS, write [s] the equivalence classMathworldPlanetmath containing s. Let S/ be the set of equivalence classes.

If A is a DFA, st is the same as saying that, for all words u over Σ, δ(s,u)F iff δ(t,u)F. For the following discussion, we shall assume that A is a DFA, unless otherwise specified.

Here are two basic observations:

  1. 1.

    if [s]=[t], then [δ(s,a)]=[δ(t,a)]: Let p=δ(s,a) and q=δ(t,a). Given any u over Σ, we have that δ(p,u)=δ(δ(s,a),u)=δ(s,au), which is in F iff δ(t,au)=δ(δ(t,a),u)=δ(q,u) is in F. Hence pq.

  2. 2.

    if [s]=[t] and tF, then sF: as δ(t,λ)=tF shows that s=δ(s,λ)F. As a result of this, pF iff [p]F.

Define A=(S,Σ,δ,q0,F) as follows: S:=S/, q0:=[q0], F:={[t]tF}, and δ([s],a):=[δ(s,a)], for any aΣ.

Now, δ is a well-defined function from the first observation above, so that A is a well-defined automaton. It has the following property: for any word u over Σ:

δ([s],u)=[δ(s,u)].

This can be proved by inductionMathworldPlanetmath on the length of u:

  • δ([s],λ)=[s]=[δ(s,λ)]

  • suppose δ([s],u)=[δ(s,u)], then for any aΣ,

    δ([s],ua)=δ(δ([s],u),a)=δ([δ(s,u)],a)=[δ(δ(s,u),a)]=[δ(s,ua)].

It also has the property that for if two states are indistinguishable, they are in fact the same state: suppose [s][t], then for every u over Σ, δ([s],u)F iff δ([t],u)F, or [δ(s,u)]F iff [δ(t,u)]F, which is the same as saying δ(s,u)F iff δ(t,u)F, or st, or [s]=[t].

Definition. An finite automaton with a single start state is said to be reduced or minimal if st implies s=t, where is the indistinguishable relation on its state set.

Thus A constructed above is reduced.

Below are state diagramsPlanetmathPlanetmath of an automaton A (not deterministic) and its reductionPlanetmathPlanetmathPlanetmath A:

Note that pq, as L(Ap)=L(Aq)={aa,ab,ba,bb}, and are combined into one state x. Similarly, rs, as L(Ar)=L(As)={a,b}, and are combined into y. Finally, note that L(A)=L(A)={u|u|=3}.

With respect to DFA’s, the following is true:

Proposition 1.

Every DFA A is equivalentMathworldPlanetmathPlanetmathPlanetmathPlanetmath to a reduced DFA A. Furthermore, if A is accessiblePlanetmathPlanetmath (or simplified), so is A. Finally, two equivalent reduced accessible automata are isomorphicPlanetmathPlanetmathPlanetmath.

Proof.

We have already shown that given a DFA A, the automaton A constructed above is reduced. Next, we see that uL(A) iff δ(q0,u)F iff [δ(q0,u)]F iff δ([q0],u)F iff uL(A). Therefore, L(A)=L(A).

Next, suppose A is accessible, we want to show that [p] is accessible for any pS. Since p is accessible, p=δ(q0,u) for some word u over Σ. So δ([q0],u)=[δ(q0,u)]=[p] is accessible as well. This proves that A is accessible.

Suppose now that A is simplified. Pick any sS, we want to show that [s] is useful. Since s is useful, there are words u,v over Σ such that δ(q0,u)=s and δ(s,v)F, or equivalently δ([q0],u)=[δ(q0,u)]=[s] and δ([s],v)=[δ(s,v)]F, so that [s]S is useful. This shows that A is simplified.

Finally, if A and B are both accessible and reduced such that L(A)=L(B)=R. Then the Myhill-Nerode relations induced by A and B are both equal to the Nerode equivalence 𝒩R of R. As a result, A and B are both isomorphic to the automaton generated by 𝒩R. ∎

Remark. The propositionPlanetmathPlanetmathPlanetmath above is not true in general for non-deterministic finite automata: two equivalent simplified reduced NDFA may not be isomorphic. However, there exist reduction techniques for NDFA such that the reduced automata produced using these techniques are unique up to isomorphismPlanetmathPlanetmathPlanetmath.

Title reduced automaton
Canonical name ReducedAutomaton
Date of creation 2013-03-22 19:01:56
Last modified on 2013-03-22 19:01:56
Owner CWoo (3771)
Last modified by CWoo (3771)
Numerical id 14
Author CWoo (3771)
Entry type Definition
Classification msc 03D10
Classification msc 68Q42
Classification msc 68Q05
Synonym minimal automaton
Related topic SimplifiedAutomaton
Defines indistinguishable
Defines reduced
Defines minimal