Two Methods:
Expression
Decomposition
String
Differentiation
Expression Decomposition.
Example : (A+B) *
(C+D) + EF + G
1. We have: E1:
(A+B) * (C+D) and
E2: EF+G
2. For E1, we have: E11: (A+B) *
E12:
(C+D) which should become just
‘C+D’
3. For E11, we have: E111: (A+B) which becomes A+B
4. For
E111, we have A and
B
5. For
‘A’ we have a NFSA that looks
like:
|
1 |
A |
2 |
0 |
outgoing
transition from the only accepting always.
6. For
‘B’ we have a NFSA that looks like:
|
3 |
B |
4 |
0 |
7. For
E111, we have a NFSA that looks like:
|
1 |
l |
2 |
4 |
|
2 |
A |
3 |
0 |
|
4 |
B |
5 |
0 |
|
3 |
l |
6 |
0 |
|
5 |
l |
6 |
0 |
Above is
truly nondeterministic due to the Empty-transitions.
8. For
E11: (A+B) * , we have:
|
7 |
l |
1 |
8 |
|
1 |
l |
2 |
4 |
|
2 |
A |
3 |
0 |
|
4 |
B |
5 |
0 |
|
3 |
l |
6 |
0 |
|
5 |
l |
6 |
0 |
|
6 |
l |
1 |
8 |
State-7 is the new initial state,
for the sake of simplicity, and state-8
is the new accepting state and there
is no outgoing transition from it.
9.
Similarly, for E12: C+D, we will get a NFSA that looks like:
|
9 |
l |
10 |
12 |
|
10 |
C |
11 |
0 |
|
12 |
D |
13 |
0 |
|
11 |
l |
14 |
0 |
|
13 |
l |
14 |
0 |
10. For
E1: (A+B) * (C+D)
we will get:
|
7 |
l |
1 |
8 |
|
1 |
l |
2 |
4 |
|
2 |
A |
3 |
0 |
|
4 |
B |
5 |
0 |
|
3 |
l |
6 |
0 |
|
5 |
l |
6 |
0 |
|
6 |
l |
1 |
8 |
|
8 |
l |
9 |
0 |
|
9 |
l |
10 |
12 |
|
10 |
C |
11 |
0 |
|
12 |
D |
13 |
0 |
|
11 |
l |
14 |
0 |
|
13 |
l |
14 |
0 |
11. For
E2: EF+G
we will get:
|
15 |
l |
16 |
20 |
|
16 |
E |
17 |
0 |
|
17 |
l |
18 |
0 |
|
18 |
F |
19 |
0 |
|
19 |
l |
22 |
0 |
|
20 |
G |
21 |
0 |
|
21 |
l |
22 |
0 |
The
second step of converting an NFSA to an equivalent DFSA:
Example:
|
7 |
l |
1 |
8 |
|
1 |
l |
2 |
4 |
|
2 |
A |
3 |
0 |
|
4 |
B |
5 |
0 |
|
3 |
l |
6 |
0 |
|
5 |
l |
6 |
0 |
|
6 |
l |
1 |
8 |
|
8 |
l |
9 |
0 |
|
9 |
l |
10 |
12 |
|
10 |
C |
11 |
0 |
|
12 |
D |
13 |
0 |
|
11 |
l |
14 |
0 |
|
13 |
l |
14 |
0 |
1.
Calculate the empty-closure of each state.
The empty-closure of a state,
i, is a set of one or more states such
that
a.
the state itself, i,
is included (so it is never empty)
b.
any state that can be reached from this state i on a
chain of one or more empty transitions. And no other state is included.
7: 7,1,8,2,4,9,10,12
1: 1,2,4
2: 2
4: 4
3: 3,6,1,8,9,10,12,2,4
5: 5,6,1,8,9,10,12,2,4
6: 6,1,8,9,10,12,2,4
8: 8,9,10,12
9: 9,10,12
10: 10
12: 12
11: 11,14
13: 13,14
14: 14
2.
Identify a state after another until no more state is
found, starting with the Initial
state as a combination of one
or more NFSA states.
a. Initial state:
#1: 718249AC
b.
Next states from #1:
On A: #2: 3618924AC
On B: #3: 5618924AC
On C: #4: BE
On D: #5: DE
c.
Next states from #2:
On A: #2
On B: #3
On C: #4
On D: #5
d.
Next states from #3:
On A: #2
On B: #3
On C: #4
On D: #5
e.
Next states from #4: No transition
f.
Next states from #5: No transition
Transition
table
|
|
A |
B |
C |
D |
|
1 |
2 |
3 |
4 |
5 |
|
2 |
2 |
3 |
4 |
5 |
|
3 |
2 |
3 |
4 |
5 |
|
4* |
|
|
|
|
|
5* |
|
|
|
|
3. Minimization
a. Make the DFSA
completely specified.
|
|
A |
B |
C |
D |
|
1 |
2 |
3 |
4 |
5 |
|
2 |
2 |
3 |
4 |
5 |
|
3 |
2 |
3 |
4 |
5 |
|
4* |
6 |
6 |
6 |
6 |
|
5* |
6 |
6 |
6 |
6 |
|
6 |
6 |
6 |
6 |
6 |
By inspection, states 1,2, and 3 are
equivalent and 4and 5 are equivalent.
b. So the
resulting minimized DFSA looks like:
|
|
A |
B |
C |
D |
|
1 |
1 |
1 |
2 |
2 |
|
2* |
|
|
|
|
c.
In general, we need to find equivalent states.
Two states are equivalent if
and only if there is no “Distinguishing sequence”
between the two states.
A string of
zero or more (input) symbols is distinguishing for two states if the
string drives
the acceptor into an accepting state from one state and into a
non-accepting state from the
other state of the two.
In a way, the absence of a distinguishing
string for two states means that there is no
difference between the two states as far as
string acceptance is concerned. That is,
the acceptor will accept the same string
starting from either state.
d.
How to identify the presence or absence of a
distinguishing string for every pair of
two strings.
|
|
A |
B |
C |
|
1 |
1 |
2 |
4 |
|
2 |
2 |
3 |
4 |
|
3 |
3 |
1 |
5 |
|
4* |
4 |
5 |
6 |
|
5* |
5 |
4 |
6 |
|
6 |
6 |
6 |
6 |
a.
First, any accepting state and any non-accepting state
cannot be equivalent
because the empty string is distinguishing the two
state.
b.
So, we only need to check among accepting states and
among non-accepting
S3tates.
c.
Non-accepting states: 1,2,3,6
|
|
2 |
3 |
6 |
|
1 |
2/3 |
2/1, 4/5 |
2/6, X |
|
2 |
|
1/3, 4/5 |
3/6, X |
|
3 |
|
|
1/6, X |
As state-4 and state-5 are
equivalent, three states 1,2, and 3 are also
equivalent.
e. Final
minimized DFSA
|
|
A |
B |
C |
|
1 |
1 |
1 |
4 |
|
4* |
4 |
4 |
6 |
|
6 |
6 |
6 |
6 |
B. String Differentiation
Examples:
D a (abc)
= bc
D a (ab)
= b
D a (a)
= l
D a (bc)
= f (Empty-set)
D a ( l) = f (Empty-set)
Rules:
1. D a
(E1+E2) = D a (E1)
+ D a (E2)
2. D a
(E1.E2) = D a (E1). E2
+ D a (E2) if l is
in E1
3. D a
(E *) = D a (E).E*
D a (ac+bc) * = D a (ac+bc)
. (ac+bc)*
= c (ac+bc) *
D a (ac+bc+l ) *
= D a (ac+bc+l) . (ac+bc+l)*
= c (ac+bc)
*