@weixin
2015-01-20T22:28:45.000000Z
字数 3510
阅读 1836
compile
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
:
for a , here is my solution :
digraph G {
rankdir=LR;
node [shape = none]; "";
node [shape = doublecircle]; 7;
node [shape = circle];
"" -> 0;
0->1 [label = "ε"];
1->0 [label = "a"];
1->2 [label = "ε"];
2->3 [label = "ε"];
2->4 [label = "ε"];
3->5 [label = "a"];
4->5 [label = "b"];
5->6 [label = "a"];
6->7 [label = "a"];
}
for b, here are the steps:
A =
B =
C =
D =
E =
F =
G =
H =
I =
J =
K =
L =
m =
all cases already appeares, so no need to repeat. Be aware that any subsets contains 7 would be the new destination.
the graphviz script :
digraph G {
rankdir=LR;
node [shape = doublecircle]; F G;
node [shape = none]; "";
node [shape = circle];
""->A;
A->B [label = "a"];
A->C [label = "b"];
B->C [label = "b"];
B->D [label = "a"];
D->C [label = "b"];
D->F [label = "a"];
F->F [label = "a"];
F->C [label = "b"];
C->E [label = "a"];
E->G [label = "a"];
}
in the above pic:
A =
B =
C = [5]
D =
F =
E = [6]
G =
the above pic is wrong, here is the correct solution :
digraph G {
rankdir=LR;
node [shape = doublecircle]; F G;
node [shape = none]; "";
node [shape = circle];
""->A;
A->B [label = "a"];
A->C [label = "b"];
B->C [label = "b"];
B->D [label = "a"];
D->C [label = "b"];
D->F [label = "a"];
F->F [label = "a"];
F->C [label = "b"];
C->E [label = "a"];
E->G [label = "a"];
}
at node F, there should be a loop.
((a|b)(a|bb))*
, for a), the solution is :
the above one is not correct, the correct shold be :
digraph G {
rankdir=LR;
node [shape = doublecircle]; 0;
node [shape = none]; "";
node [shape = circle];
""->0;
7->0 [label = "ε"];
0->1 [label = "ε"];
1->2 [label = "ε"];
2->4 [label = "a"];
1->3 [label = "ε"];
3->4 [label = "b"];
4->5 [label = "ε"];
4->6 [label = "b"];
5->7 [label = "a"];
6->7 [label = "b"];
}
node 0 is the destination, not 7.
for b), the steps:
A =
B =
C =
D =
E =
F =
G =
H =
hence the dfa is like this way :
Here A =
B =
C =
D =
digraph G {
rankdir=LR;
node [shape = doublecircle]; A C;
node [shape = none]; "";
node [shape = circle];
""->A;
A->B [label = "a"];
A->B [label = "b"];
B->C [label = "a"];
C->B [label = "a"];
C->B [label = "b"];
B->D [label = "b"];
D->C [label = "b"];
}
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.