[关闭]
@weixin 2015-01-20T22:28:45.000000Z 字数 3510 阅读 2198

convert regular expression to dfa

compile

How to convert regulare expression to dfa

I'm self-teaching The basics of compiler. Here is the solution of some exercises.
- Exercise 2.2. Given the regular expression a*(a|b)aa :
a) construct an equvivalent NFA ;
b) convert the NFA to DFA.
for a , here is my solution : 2-2-nfa

  1. digraph G {
  2.                 rankdir=LR;
  3.                 node [shape = none]; "";
  4.                 node [shape = doublecircle]; 7;
  5.                 node [shape = circle];
  6.                 "" -> 0;
  7.                 0->1 [label = "ε"];
  8.                 1->0 [label = "a"];
  9.                 1->2 [label = "ε"];
  10.                 2->3 [label = "ε"];
  11.                 2->4 [label = "ε"];
  12.                 3->5 [label = "a"];
  13.                 4->5 [label = "b"];
  14.                 5->6 [label = "a"];
  15.                 6->7 [label = "a"];
  16. }

for b, here are the steps:
A = ε−closure(0) = [0,1,2,3,4]
B = move(A,a) = [0,5] = ε−closure(0,5) = [0,1,2,3,4,5]
C = move(A,b) = [5] = ε−closure(5) = [5]
D = move(B,a) = [0,6] = ε−closure(0,6) = [0,1,2,3,4,5,6]
E = move(B,b) = [5] = C ( C is the same as E )
F = move(C,a) = [6]
G = move(C,b) = {}
H = move(D,a) = {0,5,6,7} = ε−closure(0,7) = {0,1,2,3,4,5,6,7}
I = move(D,b) = {5} = C
J = move(F,a) = {7}
K = move(F,b) = {}
L = move(H,a) = H
m = move(H,b) = [5] = C

all cases already appeares, so no need to repeat. Be aware that any subsets contains 7 would be the new destination.
2-2-dfa
the graphviz script :

  1. digraph G {
  2.                 rankdir=LR;
  3.                 node [shape = doublecircle]; F G;
  4.                 node [shape = none]; "";
  5.                 node [shape = circle];
  6.                 ""->A;
  7.                 A->B [label = "a"];
  8.                 A->C [label = "b"];
  9.                 B->C [label = "b"];
  10.                 B->D [label = "a"];
  11.                 D->C [label = "b"];
  12.                 D->F [label = "a"];
  13.                 F->F [label = "a"];
  14.                 F->C [label = "b"];
  15.                 C->E [label = "a"];
  16.                 E->G [label = "a"];
  17. }

in the above pic:
A = [0,1,2,3,4]
B = [0,1,2,3,4,5]
C = [5]
D = [0,1,2,3,4,5,6]
F = {0,1,2,3,4,5,6,7}
E = [6]
G = {7}

the above pic is wrong, here is the correct solution :
correct

  1. digraph G {
  2.                 rankdir=LR;
  3.                 node [shape = doublecircle]; F G;
  4.                 node [shape = none]; "";
  5.                 node [shape = circle];
  6.                 ""->A;
  7.                 A->B [label = "a"];
  8.                 A->C [label = "b"];
  9.                 B->C [label = "b"];
  10.                 B->D [label = "a"];
  11.                 D->C [label = "b"];
  12.                 D->F [label = "a"];
  13.                 F->F [label = "a"];
  14.                 F->C [label = "b"];
  15.                 C->E [label = "a"];
  16.                 E->G [label = "a"];
  17. }

at node F, there should be a loop.

for a), the solution is :
2-3-NFA
the above one is not correct, the correct shold be :
2-3-NFA-correct

  1.  digraph G {
  2.                 rankdir=LR;
  3.                 node [shape = doublecircle]; 0;
  4.                 node [shape = none]; "";
  5.                 node [shape = circle];
  6.                 ""->0;
  7.                 7->0 [label = "ε"];
  8.                 0->1 [label = "ε"];
  9.                 1->2 [label = "ε"];
  10.                 2->4 [label = "a"];
  11.                 1->3 [label = "ε"];
  12.                 3->4 [label = "b"];
  13.                 4->5 [label = "ε"];
  14.                 4->6 [label = "b"];
  15.                 5->7 [label = "a"];
  16.                 6->7 [label = "b"];
  17. }

node 0 is the destination, not 7.

for b), the steps:
A = ε−closure(0) = [0,1,2,3]
B = move(A,a) = {4} = ε−closure(4) = {4,5}
C = move(B,a) = {7} = ε−closure(7) = {0,1,2,3,7}
D = move(B,b) = {6}
E = move(C,a) = {4} = ε−closure(4) = {4,5} = B
F = move(C,b) = {4} = ε−closure(4) = {4,5} = B
G = move(D,a) = {}
H = move(D,b) = {7} = ε−closure(7) = {0,1,2,3,7} = C

hence the dfa is like this way :
2-3-dfa

Here A = [0,1,2,3]
B = {4,5}
C = {0,1,2,3,7}
D = {6} 

  1. digraph G {
  2.                 rankdir=LR;
  3.                 node [shape = doublecircle]; A C;
  4.                 node [shape = none]; "";
  5.                 node [shape = circle];
  6.                 ""->A;
  7.                 A->B [label = "a"];
  8.                 A->B [label = "b"];
  9.                 B->C [label = "a"];
  10.                 C->B [label = "a"];
  11.                 C->B [label = "b"];
  12.                 B->D [label = "b"];
  13.                 D->C [label = "b"];
  14. }

regulare expression is ((a|b)(a|bb))*,
so aaba, aabbb, abbba are all plausible solution, also the paths of the above string could be found on this graph.

添加新批注
在作者公开此批注前，只有你和作者可见。
回复批注