Essay About Q0 And State Q Of A Dfa A

Minimization of Dfas
Essay Preview: Minimization of Dfas
Report this essay
CIS 262 Fall 2015: Minimization of DFAs
This handout explains the algorithm for minimizing a DFA. Given a DFA A = (Q;; q0; F; ), we want to
construct a DFA B such that (1) both DFAs A and B accept exactly the same language, and (2) the DFA
B has as few states as possible. The algorithm proceeds in three steps: remove unreachable states, compute
equivalent states, and merge equivalent states.
Step 1: Removing Unreachable States
A state q of a DFA A is said to be reachable if there is a path from the initial state to the state q by following a
sequence of transitions. That is, q is reachable i there exists a string w such that (q0;w) = q. It is easy to
see that unreachable states are redundant, and can be removed without changing the language that the DFA
accepts. When we construct a DFA manually, there is no reason to include unreachable states, but when
a DFA is constructed by an algorithm (for instance, by the determinization algorithm for translating NFAs
to DFAs), it may contain unreachable states. If the DFA is represented by listing its states and transitions,
then the set of reachable states of a DFA can be computed using an algorithm for searching in graphs (for
example, the depth-rst-search algorithm).
Henceforth, we will assume that the set Q of states contains only reachable states.
Step 2: Computation of Equivalent States
Dene two states q and q0 to be equivalent if for all strings w, the states (q;w) and (q0;w) are either
both accepting or both non-accepting. Conversely, the states q and q0 are distinguishable if there exists a
string w such that only one of the states (q;w) and (q0;w) is accepting. Intuitively, two equivalent q and
q0 states can be merged: no matter what additional input string follows, the decision of the DFA regarding
whether to accept or reject is identical from both these states.
The algorithm below computes the set of distinguishable pairs of states:
Initialize: S := f(q; q0) j exactly one of q or q0 is in F g.
Repeat
S := S [ f(q; q0) j ((q; a); (q0; a)) 2 S for some a 2 g
Until S does not change.
The logic of the algorithm is simple: an accepting state is distinguishable from a non-accepting state, and
if we have declared two states s and s0 to be distinguishable, and there is an a-labeled transition from state
q to s, and also an a-labeled transition from state q0 to s0, then we can conclude that states q and q0 are
distinguishable. Below is the proof that this algorithm works correctly.
1. Termination: If Q contains n states, then there are only n2 pairs of states. The algorithm only adds
pairs to the set S, and stops when no new pair can be added. Thus, the loop cannot execute for more
than n2 iterations, and the algorithm must terminate.
2. We claim that if the algorithm adds a pair (q; q0) to the set S during the k-th iteration of the loop,
then the states q and q0 are distinguishable. The proof is by induction on k.
Base case, k = 0, means that the algorithm adds (q; q0) to S initially. In this case, only one of them is
accepting. Then of the two states (q; “) and (q0; “), only one is accepting, and thus, by denition
of distinguishability, the states q and q0 are distinguishable.
For inductive case, suppose that the algorithm adds (q; q0) to S during (k+1)-th iteration. Then, there
must be a symbol a such that (s; s0) is already in S, for s = (q; a) and s0 = (q0; a). Since the pair
(s; s0) is added to S during the k-th iteration or earlier, by strong induction hypothesis, states s and
s0 must be distinguishable. Thus, there must be a string w such that only one of the states (s;w)
and (s0;w) is accepting. It follows that only one of the states (q; aw) and (q0; aw) is accepting.
Hence the states q and q0 are distinguishable.
3. We now need to show that if two states q and q0 are distinguishable, then the algorithm adds the pair
(q; q0) to the set S.
Consider two distinguishable states q and q0. By denition, there must exist a string w such that only
one of the states (q;w) and (q0;w) is accepting. Let k be the length of shortest such string. The
claim is that the algorithm adds the pair (q; q0) to the set S during the k-th iteration of the loop. The
proof is by induction on k, and is left as an exercise.
We have not described how to eciently implement the algorithm: this amounts to choosing an appro-
priate data structure for the set S and deciding on the order in which dierent pairs should be processed
within the loop-body. We will not focus on this aspect in this course, but let us note that there is a very
nice implementation of this algorithm with running time O(n log n), where n is the number of states.
Step 3: Building Minimal DFA by Merging Equivalent States
The algorithm