[go: up one dir, main page]
Scribd
Upload
396 views23 pages

DFA Minimization

This document discusses deterministic finite automata (DFA) minimization. It defines a DFA as a 5-tuple (Q, Σ, δ, q0, F) where Q is a finite set of states, Σ is an input alphabet, δ is a transition function, q0 is the starting state, and F is a set of accepting states. The task of DFA minimization is to transform a given DFA into an equivalent DFA with the minimum number of states. The document outlines an algorithm that labels pairs of states as distinct or equivalent based on their transitions and acceptance. It then merges any equivalent states to produce the minimized DFA.

Uploaded by

Saurabh Tiwari
Copyright
© Attribution Non-Commercial (BY-NC)
We take content rights seriously. If you suspect this is your content, claim it here.
Available Formats
Download as PPT, PDF, TXT or read online on Scribd
396 views23 pages

DFA Minimization

This document discusses deterministic finite automata (DFA) minimization. It defines a DFA as a 5-tuple (Q, Σ, δ, q0, F) where Q is a finite set of states, Σ is an input alphabet, δ is a transition function, q0 is the starting state, and F is a set of accepting states. The task of DFA minimization is to transform a given DFA into an equivalent DFA with the minimum number of states. The document outlines an algorithm that labels pairs of states as distinct or equivalent based on their transitions and acceptance. It then merges any equivalent states to produce the minimized DFA.

Uploaded by

Saurabh Tiwari
Copyright
© Attribution Non-Commercial (BY-NC)
We take content rights seriously. If you suspect this is your content, claim it here.
Available Formats
Download as PPT, PDF, TXT or read online on Scribd
You are on page 1/ 23

DFA Minimization

Jeremy Mange CS 6800 Summer 2009

DFA

Deterministic Finite Automata (DFSA)

(Q, , , q0, F)

Q (finite) set of states alphabet (finite) set of input symbols transition function q0 start state F set of final / accepting states

DFA

Often representing as a diagram:

DFA Minimization

Some states can be redundant:


The following DFA accepts (a|b)+ State s1 is not necessary

DFA Minimization

So these two DFAs are equivalent:

DFA Minimization

This is a state-minimized (or just minimized) DFA

Every remaining state is necessary

DFA Minimization

The task of DFA minimization, then, is to automatically transform a given DFA into a state-minimized DFA

Several algorithms and variants are known Note that this also in effect can minimize an NFA (since we know algorithm to convert NFA to DFA)

DFA Minimization Algorithm

Recall that a DFA M=(Q, , , q0, F) Two states p and q are distinct if

p in F and q not in F or vice versa, or for some in , (p, ) and (q, ) are distinct

Using this inductive definition, we can calculate which states are distinct

DFA Minimization Algorithm


Create lower-triangular table DISTINCT, initially blank For every pair of states (p,q):

If p is final and q is not, or vice versa DISTINCT(p,q) =

Loop until no change for an iteration:

For every pair of states (p,q) and each symbol If DISTINCT(p,q) is blank and DISTINCT( (p,), (q,) ) is not blank

DISTINCT(p,q) =

Combine all states that are not distinct

Very Simple Example


s0 s1 s2 s0 s1 s2

Very Simple Example


s0 s1 s2

s0 s1 s2

Label pairs with where one is a final state and the other is not

Very Simple Example


s0 s1 s2

s0 s1 s2

Main loop (no changes occur)

Very Simple Example


s0 s1 s2

s0 s1 s2

DISTINCT(s1, s2) is empty, so s1 and s2 are equivalent states

Very Simple Example

Merge s1 and s2

More Complex Example

More Complex Example

Check for pairs with one state final and one not:

More Complex Example

First iteration of main loop:

More Complex Example

Second iteration of main loop:

More Complex Example

Third iteration makes no changes

Blank cells are equivalent pairs of states

More Complex Example

Combine equivalent states for minimized DFA:

Conclusion

DFA Minimization is a fairly understandable process, and is useful in several areas


Regular expression matching implementation Very similar algorithm is used for compiler optimization to eliminate duplicate computations John Hopcraft describes another more complex algorithm that is O(k (n log n) )

The algorithm described is O(kn2)

Possible Exam Question

Question: Inductively define when two states in a DFA are distinct. Answer:

Two states p and q are distinct if p F and q F or vice versa, or for some , (p, ) and (q, ) are distinct

References

Ullman, A. V., Hopcroft, J. E. and Ullman, J. D. (1974) The Design and Analysis of Computer Algorithms. Addison-Wesley.

Hopcroft, J. (1971) An N Log N Algorithm for Minimizing States in a Finite Automaton. Stanford University.
Parthasarathy, M. and Fleck, M. (2007) DFA Minimization. University of Illinois at Urbana-Champaign.
http://www.cs.uiuc.edu/class/fa07/cs273/Handouts/minimization/minimization.pdf

You might also like