CS 422 — Automata Theory Fall 2009
CS106
Compiler Principles and Construction
Fall 2011
Lecture 3
NFA to DFA, DFA Minimization
MUST FIT
Dr. Zhiyao Liang
NFA to DFA, DFA minimization; Dr. Zhiyao Liang
1
NFA = DFA
Two finite accepters are equivalent if both accept the same language, that is,
L(M1) = L(M2)
Given any NFA, M1, (or DFA M2), we can prove that, there is always a DFA, M2, (or NFA, M1) such that L(M1) = L(M2).
So the power of NFA is the same as DFA.
2
NFA to DFA, DFA minimization; Dr. Zhiyao Liang
The DFA and NFA that accept
{{10)n : n 0 }
3
NFA to DFA, DFA minimization; Dr. Zhiyao Liang
NFA = DFA
Theorem
Let L be the language accepted by a non-deterministic finite accepter MN = (QN, , N, q0, FN) . Then there exists a deterministic finite accepter MD = (QD, , D, {q0}, FD) such that L(MN) = L(MD).
Proof: Construct MD based on MN .
Idea: A set of concurrently active states at a certain time of the NFA => a state of the DFA.
4
NFA to DFA, DFA minimization; Dr. Zhiyao Liang
The procedure: NFA_to_DFA
Create a graph GD with vertex {q0}. Identify this vertex as the initial vertex.
Repeat the following steps until no more edges are missing:
Take any vertex {qi, qj, …, qk} of GD that has no outgoing edge for some a .
Compute δ*N (qi, a), δ*N(qj, a), …, δ*N(qk, a).
Form the union of all these δ* yielding the set {ql, qm, …, qn}.
Create a vertex for GD labeled {ql, qm, …, qn} if it does not already exist.
Add to GD an edge from {qi, qj, …, qk} to {ql, qm, …, qn} and label it with a.
Every state of GD whose label contains and qf FN is identified as a final vertex.
If MN accepts , the vertex q0 in GD is also made a final vertex.
5
NFA to DFA, DFA minimization; Dr. Zhiyao Liang
This procedure is not clear. Should start with q0
5
Example NFA_to_DFA
Convert the following NFA into an equivalent DFA
6
NFA to DFA, DFA minimization; Dr. Zhiyao Liang
NFA_to_ DFA: the initial state
The DFA must have an initial state. So create a graph GD with vertex {q0}. Identify this vertex as the initial vertex.
Figures of JFLAP : An initial state is created labeled with {q0}. Note that {q0} in the DFA corresponds to the q0 of the NFA.
7
NFA to DFA, DFA minimization; Dr. Zhiyao Liang
NFA_to_DFA
The state {q0} needs to handle all symbols in = {a, b}.
How does {q0} handle the symbol a?
In the NFA, δ*N(q0, a) = {q1, q2}. So the graph GD, make a state labeled with {q1, q2}, since it does not exists in the GD, and make an edge from the state {q0} to the state {q1, q2}.
8
NFA to DFA, DFA minimization; Dr. Zhiyao Liang
NFA_to_DFA
How does {q0} handle the symbol b?
In the NFA, δ*N(q0, b) = . So the graph GD, make a state labeled with (empty), since it does not exist in the GD yet. Make an edge from the state {q0 } to the state labelled with b.
We are done with {q0} since all
symbols are handled.
9
NFA to DFA, DFA minimization; Dr. Zhiyao Liang
NFA_to_DFA
How does the state {q1, q2} handle the symbol a?
In the NFA, δ*N(q1, a) = {q1, q2}. δ*N(q2, a) = . {q1, q2} = {q1, q2}. In the graph GD we do not create a new state labeled with . {q1, q2} since it does exist. We make an edge from the state {q1, q2} to the state . {q1, q2} labeled with a.
10
NFA to DFA, DFA minimization; Dr. Zhiyao Liang
NFA_to_DFA
How does the state {q1, q2} handle the symbol b?
In the NFA, δ*N(q1, b) = . δ*N(q2, b) = {q0}. {q0} = {q0}. In the graph GD we do not need to create a new state labeled with {q0} since it does exist. We make an edge from the state {q1, q2} to the state {q0}. Now we are done with {q1, q2 } , since all symbols are handled.
11
NFA to DFA, DFA minimization; Dr. Zhiyao Liang
NFA_to_DFA
How does the state {} handle the symbols a and b?
Since {} represent some finished computation and it is a trap state, all edges {} loop back to itself. So we make an edge from {} to {} labeled with “a,b”. Now we are done with {q0, q1 } , since all symbols are handled.
12
NFA to DFA, DFA minimization; Dr. Zhiyao Liang
NFA_to_DFA
Now all states in GD have handled all symbols. One more step: what is the final state of the DFA?
Any state whose label contains q1 is a final state. So we have one final states. The DFA is constructed, see the right upper one, The right lower one is the answer given in [linz]
13
NFA to DFA, DFA minimization; Dr. Zhiyao Liang
NFA_to_ DFA
Example: Convert this NFA to a DFA.
14
NFA to DFA, DFA minimization; Dr. Zhiyao Liang
Example: In the middle of running NFA_to_DFA
15
NFA to DFA, DFA minimization; Dr. Zhiyao Liang
NFA_to_ DFA: finally
16
NFA to DFA, DFA minimization; Dr. Zhiyao Liang
Reducing states in a DFA
(example: two equivalent DFAs)
17
NFA to DFA, DFA minimization; Dr. Zhiyao Liang
Distinguishable and Indistinguishable DFA’s
Two states p and q of a DFA are called indistinguishable if
* (p, w) F implies * (q, w) F ,
and
* (p, w) F implies * (q, w) F ,
for all w *. (note that it means if and only if)
If there exists some string w * such that
* (p, w) F and * (q, w) F
or vice versa, then the states p and q are said to be distinguishable by string w.
18
NFA to DFA, DFA minimization; Dr. Zhiyao Liang
Procedure: mark
This procedure marks all pairs of distinguishable states.
1. Remove all inaccessible states.
2. Consider all pairs of states (p, q). If p F and q F or vice versa, mark the pair (p, q) as distinguishable.
3. Repeat the following step until no previously unmarked pairs are marked: For all pairs (p, q) and all a , compute (p, a) = pa and (q, a) = qa. If the pair (pa, qa) is marked as distinguishable, mark (p, q) as distinguishable.
19
NFA to DFA, DFA minimization; Dr. Zhiyao Liang
Procedure: reduce
Given a DFA M = (Q, , , q0, F), we construct a reduced DFA M’ = (Q’, , ’, q0’, F’) as follows:
Use procedure mark to find all pairs of distinguishable states. Then find the sets of all indistinguishable states , say {qi, qj, …, qk}, {ql, qm, …, qn}, …. Note that:
If (q, q’) is not a pair found by mark, then q and q’ belong to the same set.
A state q occurs in exactly one of these sets,
Two states from two different sets are distinguishable, why?
20
NFA to DFA, DFA minimization; Dr. Zhiyao Liang
Procedure: reduce, cont.
2. For each set {qi, qj, …, qk} of such indistinguishable states, create a state labeled ij…k for M.
3. For each transition rule of the form (qr, a) = qp, find the sets to which qr and qp belong. If qr {qi, qj, …, qk} and qp {ql, qm, …, qn}, add to ’ a rule ’ (ij…k, a) = lm…n.
4. The initial state q0’ is that state of M’ whose label includes the 0.
5. F’ is the set of all the states whose label contains i such that qi F.
21
NFA to DFA, DFA minimization; Dr. Zhiyao Liang
Minimization Theorem [ Peter Linz]
Given any DFA M, application of the procedure reduce yields another DFA M’ such that
L(M) = L(M’)
Furthermore, M’ is minimal in the sense that there is no other DFA with a smaller number of states which also accepts L(M).
22
NFA to DFA, DFA minimization; Dr. Zhiyao Liang
Proof of the minimization theorem
After running the procedure mark, two different states are in two different sets if and only if they are distinguishable.
It is obvious that two states in two different sets are distinguishable.
Two states, say q and q’ in the same set are indistinguishable.
Suppose they are distinguishable by a certain string w, then exactly only one of * (q, w) and * (q’, w) will be a final state. Then, the procedure mark should have decided that the two states (q, a) and (q’, a) are distinguishable. So q and q’ should also be found distinguishable, and cannot be in the same set; contradiction.
NFA to DFA, DFA minimization; Dr. Zhiyao Liang
23
Proof of the minimization theorem, cont.
Now we prove that M’ has minimum number of states, the challenging part.
The theory is established by Myhill and Nerode in 1958.
Given an alphabet , and a regular language L, we can partition the strings in the set * into disjoint parts, such that for any two strings x and y in the same part, it is impossible to find any string z such that only one of xz and yz is in L. (We consider non-trivial case, each part is non-empty).
For any DFA M such that accepts L, it must be true that the number of states in M is no less than the number of parts (described above), for the following reason:
For any state q of M, let L(q) be set of strings as {w | (q0, w) = q} . Then L(q) must be a subset of one certain part.
Since the union L(q) for all states q, and the union of the parts, are both *, the number parts cannot be more than the number of states.
The procedure reduce produces a DFA such that L(q) is a part we talked about. Therefore, it has minimum number of states.
NFA to DFA, DFA minimization; Dr. Zhiyao Liang
24
Example
Reduce the following DFA to a minimal one.
25
NFA to DFA, DFA minimization; Dr. Zhiyao Liang
Procedures: mark and reduce
Mark: find the distinguishable pairs:
At first, mark the (final, non-final) pairs:
(q0, q4), (q1, q4), (q2, q4) and (q3, q4).
Now for any pair (q, q’), and any symbol ,
if ((q, ), (q’, )) is a known distinguishable pair, mark (q, q’) as distinguishable.
For example: since (q1, 1) = q4 and (q0, 1) = q3, and (q3, q4) is a known distinguishable pair, (q0, q1) is also marked as a distinguishable pair.
Eventually the pairs (q0, q1), (q0, q2), (q0, q3), (q0, q4), (q1, q4), (q2, q4) and (q3, q4) are marked as distinguishable.
Reduce:
So the remaining pairs, (q1, q2), (q1, q3), and (q2, q3) are undistinguishable, and the states are partitioned into the sets {q0}, {q1, q2, q3}, and {q4}.
26
NFA to DFA, DFA minimization; Dr. Zhiyao Liang
The minimal DFA:
27
NFA to DFA, DFA minimization; Dr. Zhiyao Liang
Reading Assignment
Please read the topics on Regular languages and regular grammars
28
NFA to DFA, DFA minimization; Dr. Zhiyao Liang
Exercise
Convert the following NFA into an equivalent DFA.
NFA to DFA, DFA minimization; Dr. Zhiyao Liang
29
Exercise
Minimize the states in the DFA depicted in the following diagram.
NFA to DFA, DFA minimization; Dr. Zhiyao Liang
30
Reference
Myhill & Nerode. Linear automaton transformations. In In Proc. of the American Mathematical Society 9, pages 541–544, 1958.
“DFA minimisation using the Myhill-Nerode theorem”, by Johanna Hogberg and Lars Larsson.
However, the algorithm presented in the appendix of this paper seems to be unclear ( for both correctness and step details), while the theory is presented clear in the main part.
NFA to DFA, DFA minimization; Dr. Zhiyao Liang
31
/docProps/thumbnail.jpeg