-
Notifications
You must be signed in to change notification settings - Fork 2
/
dfa_figure.tex
205 lines (200 loc) · 9.98 KB
/
dfa_figure.tex
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94
95
96
97
98
99
100
101
102
103
104
105
106
107
108
109
110
111
112
113
114
115
116
117
118
119
120
121
122
123
124
125
126
127
128
129
130
131
132
133
134
135
136
137
138
139
140
141
142
143
144
145
146
147
148
149
150
151
152
153
154
155
156
157
158
159
160
161
162
163
164
165
166
167
168
169
170
171
172
173
174
175
176
177
178
179
180
181
182
183
184
185
186
187
188
189
190
191
192
193
194
195
196
197
198
199
200
201
202
203
204
205
\begin{figure}[!ht]
\begin{centering}
\subfloat[\dfasr]{
\begin{tikzpicture}[scale=0.09]
\tikzstyle{every node}+=[fill=white,inner sep=0pt]
\draw [black] (-2.6,-23.8) -- (0.3,-23.8);
\draw (-3.1,-23.8) node [left] {$start$};
\fill [black] (0.3,-23.8) -- (-0.5,-23.3) -- (-0.5,-24.3);
\draw [black] (3.9,-24.1) circle (3);
\draw (3.9,-24.1) node {$0$};
\draw [black] (19.8,-9) circle (3);
\draw (19.8,-9) node {$1$};
\draw [black] (30,-19.6) circle (3);
\draw (30,-19.6) node {$2$};
\draw [black] (18.5,-36.1) circle (3);
\draw (18.5,-36.1) node {$3$};
\draw [black] (35.8,-39.1) circle (3);
\draw (35.8,-39.1) node {$4$};
\draw [black] (43.4,-13.2) circle (3);
\draw (43.4,-13.2) node {$5$};
\draw [black] (46.6,-27.4) circle (3);
\draw (46.6,-27.4) node {$6$};
\draw [black] (46.6,-27.4) circle (2.4);
\draw [black] (33.919,-41.432) arc (-43.70358:-186.66407:17.839);
\fill [black] (33.92,-41.43) -- (33,-41.67) -- (33.73,-42.36);
\draw (11.22,-45.77) node [below] {$d\mbox{ }\mbox{ }\mbox{ }\mbox{ }\mbox{ }$};
\draw [black] (6.22,-26) -- (16.18,-34.2);
\fill [black] (16.18,-34.2) -- (15.88,-33.3) -- (15.25,-34.07);
\draw (10.25,-30.59) node [below] {$c$};
\draw [black] (5.821,-21.8) arc (135.53989:64.02493:18.753);
\fill [black] (27.42,-18.08) -- (26.92,-17.28) -- (26.48,-18.18);
\draw (15.1,-15.77) node [above] {$b\mbox{ }\mbox{ }\mbox{ }\mbox{ }$};
\draw [black] (4.28,-21.129) arc (167.20329:99.84016:15.584);
\fill [black] (16.81,-9.23) -- (15.94,-8.87) -- (16.11,-9.86);
\draw (7.78,-12.8) node [above] {$a$};
\draw [black] (17.19,-7.545) arc (268.59189:-19.40811:2.25);
\draw (15.02,-2.94) node [above] {$a$};
\fill [black] (19.37,-6.04) -- (19.89,-5.26) -- (18.89,-5.23);
\draw [black] (32.505,-17.971) arc (150.77527:-137.22473:2.25);
\draw (37.37,-18.68) node [right] {$b$};
\fill [black] (32.82,-20.6) -- (33.27,-21.42) -- (33.76,-20.55);
\draw [black] (21.479,-35.863) arc (122.28011:-165.71989:2.25);
\draw (24.52,-40.0) node [below] {$c$};
\fill [black] (20.5,-38.32) -- (20.5,-39.26) -- (21.35,-38.73);
\draw [black] (17.251,-33.374) arc (-158.59999:-206.89281:26.653);
\fill [black] (17.25,-33.37) -- (17.42,-32.45) -- (16.49,-32.81);
\draw (14.87,-22.35) node [left] {$\mbox{ }\mbox{ }\mbox{ }\mbox{ }\mbox{ }\mbox{ }\mbox{ }\mbox{ }c$};
\draw [black] (22.205,-7.215) arc (120.91152:38.90637:15.136);
\fill [black] (41.76,-10.69) -- (41.65,-9.76) -- (40.87,-10.39);
\draw (33.11,-4.71) node [above] {$d$};
\draw [black] (22.741,-8.501) arc (88.91183:-1.11524:8.025);
\fill [black] (22.74,-8.5) -- (23.53,-9.02) -- (23.55,-8.02);
\draw (28.9,-9.49) node [right] {$a$};
\draw [black] (19.478,-33.265) arc (158.24167:132.00767:31.599);
\fill [black] (19.48,-33.27) -- (20.24,-32.71) -- (19.31,-32.34);
\draw (22.31,-25.55) node [left] {$c$};
\draw [black] (33.704,-36.958) arc (-140.13045:-186.74081:19.012);
\fill [black] (33.7,-36.96) -- (33.57,-36.02) -- (32.81,-36.66);
\draw (29.3,-30.79) node [left] {$\mbox{ }\mbox{ }d$};
\draw [black] (35.581,-42.078) arc (-13.66199:-186.01371:9.092);
\fill [black] (35.58,-42.08) -- (34.91,-42.74) -- (35.88,-42.97);
\draw (24.73,-49.48) node [below] {$d$};
\draw [black] (19.971,-11.995) arc (2.52337:-8.01617:115.218);
\fill [black] (19.97,-12) -- (19.51,-12.82) -- (20.51,-12.77);
\draw (20.52,-22.61) node [right] {$a$};
\draw [black] (21.88,-11.16) -- (27.92,-17.44);
\fill [black] (27.92,-17.44) -- (27.73,-16.52) -- (27,-17.21);
\draw (25.43,-12.83) node [right] {$b$};
\draw [black] (28.674,-22.291) arc (-27.74002:-42.01064:57.083);
\fill [black] (28.67,-22.29) -- (27.86,-22.77) -- (28.74,-23.23);
\draw (25.58,-29.72) node [right] {$b$};
\draw [black] (22.741,-8.416) arc (98.28712:61.53076:29.155);
\fill [black] (22.74,-8.42) -- (23.6,-8.8) -- (23.46,-7.81);
\draw (33.11,-7.86) node [above] {$a\mbox{ }\mbox{ }\mbox{ }\mbox{ }\mbox{ }$};
\draw [black] (32.077,-17.44) arc (131.12228:99.93712:17.189);
\fill [black] (32.08,-17.44) -- (33.01,-17.29) -- (32.35,-16.54);
\draw (34.99,-14.37) node [above] {$b$};
\draw [black] (44.959,-15.759) arc (26.66951:-1.27035:18.386);
\fill [black] (46.91,-24.42) -- (47.43,-23.63) -- (46.43,-23.61);
\draw (47.22,-19.58) node [right] {$c$};
\draw [black] (46.395,-13.207) arc (83.9582:-116.6654:14.567);
\fill [black] (38.32,-40.71) -- (38.81,-41.52) -- (39.26,-40.62);
\draw (59.61,-32.38) node [right] {$d$};
\draw [black] (44.57,-29.6) -- (37.83,-36.9);
\fill [black] (37.83,-36.9) -- (38.74,-36.65) -- (38.01,-35.97);
\draw (40.67,-31.79) node [left] {$d$};
\draw [black] (43.687,-26.684) arc (-106.00985:-124.32589:39.144);
\fill [black] (32.41,-21.38) -- (32.79,-22.25) -- (33.35,-21.42);
\draw (36.85,-24.99) node [below] {$b$};
\draw [black] (47.797,-30.145) arc (17.84688:-163.44093:15.041);
\fill [black] (19.06,-39.04) -- (18.81,-39.95) -- (19.77,-39.67);
\draw (38.73,-49.67) node [below] {$c$};
\draw [black] (21.796,-6.766) arc (132.94565:-21.89007:16.264);
\fill [black] (21.8,-6.77) -- (22.72,-6.59) -- (22.04,-5.85);
\draw (43.03,-4.76) node [above] {$a$};
\draw [black] (33.12,-40.423) arc (324:36:2.25);
\draw (28.55,-39.1) node [left] {$d$};
\fill [black] (33.12,-37.78) -- (32.77,-36.9) -- (32.18,-37.71);
\draw [black] (36.754,-41.934) arc (10.72301:-210.39871:10.898);
\fill [black] (16.65,-38.45) -- (15.81,-38.88) -- (16.67,-39.39);
\draw (23.75,-55.29) node [below] {$c$};
\draw [black] (34.94,-36.22) -- (30.86,-22.48);
\fill [black] (30.86,-22.48) -- (30.6,-23.38) -- (31.56,-23.1);
\draw (33.67,-28.75) node [right] {$b$};
\draw [black] (21.619,-6.618) arc (138.23159:-82.24481:19.498);
\fill [black] (21.62,-6.62) -- (22.52,-6.35) -- (21.78,-5.69);
\draw (54.06,-9.29) node [right] {$a$};
\end{tikzpicture}
\label{fig:dfatcc}
}
\hfill
\subfloat[\pmconer]{
\begin{tikzpicture}[scale=0.09]
\tikzstyle{every node}+=[inner sep=0pt]
\draw [black] (4.6,-12.2) circle (3);
\draw (4.6,-12.2) node {$1$};
\draw [black] (30.6,-24.2) circle (3);
\draw (30.6,-24.2) node {$2$};
\draw [black] (6.2,-48.3) circle (3);
\draw (6.2,-48.3) node {$3$};
\draw [black] (49.8,-49.5) circle (3);
\draw (49.8,-49.5) node {$4$};
\draw [black] (55.9,-12.2) circle (3);
\draw (55.9,-12.2) node {$5$};
\draw [black] (55.9,-34.2) circle (3);
\draw (55.9,-34.2) node {$6$};
\draw [black] (55.9,-34.2) circle (2.4);
\draw [black] (3.277,-9.52) arc (234:-54:2.25);
\draw (4.6,-4.95) node [above] {$P(a|a)$};
\fill [black] (5.92,-9.52) -- (6.8,-9.17) -- (5.99,-8.58);
\draw [black] (30.106,-21.253) arc (217.25487:-70.74513:2.25);
\draw (31.95,-17.1) node [above] {$P(b|b)$};
\fill [black] (32.64,-22.01) -- (33.58,-21.93) -- (32.97,-21.13);
\draw [black] (6.328,-51.286) arc (30.18097:-257.81903:2.25);
\draw (0.79,-55) node [below] {$P(c|c)$};
\fill [black] (3.91,-50.22) -- (2.97,-50.19) -- (3.47,-51.05);
\draw [black] (5.714,-45.34) arc (-171.29151:-183.63296:140.372);
\fill [black] (5.71,-45.34) -- (6.09,-44.47) -- (5.1,-44.62);
\draw (4.67,-37.32) node [left] {$\mbox{ }\mbox{ }\mbox{ }\mbox{ }\mbox{ }\mbox{ }\mbox{ }\mbox{ }P(c|a)$};
\draw [black] (7.079,-10.512) arc (122.2697:57.7303:43.399);
\fill [black] (53.42,-10.51) -- (53.01,-9.66) -- (52.48,-10.51);
\draw (30.25,-3.31) node [above] {$P(d|a)$};
\draw [black] (7.583,-12.513) arc (81.8726:48.57712:40.066);
\fill [black] (7.58,-12.51) -- (8.3,-13.12) -- (8.45,-12.13);
\draw (21.47,-15.28) node [above] {$P(a|b)$};
\draw [black] (7.532,-45.612) arc (151.86818:117.42301:48.336);
\fill [black] (7.53,-45.61) -- (8.35,-45.14) -- (7.47,-44.67);
\draw (17.3,-36.53) node [below] {$P(c|b)$};
\draw [black] (47.431,-47.66) arc (-129.36992:-156.24084:55.875);
\fill [black] (47.43,-47.66) -- (47.13,-46.77) -- (46.5,-47.54);
\draw (42.79,-39.65) node [left] {$P(d|b)$};
\draw [black] (46.917,-50.329) arc (-75.2387:-107.9144:67.363);
\fill [black] (46.92,-50.33) -- (46.02,-50.05) -- (46.27,-51.02);
\draw (27.86,-53.1) node [below] {$P(d|c)$};
\draw [black] (5.432,-15.082) arc (14.88666:-9.81113:70.847);
\fill [black] (5.43,-15.08) -- (5.15,-15.98) -- (6.12,-15.73);
\draw (8.31,-30.13) node [right] {$P(a|c)$};
\draw [black] (27.764,-23.221) arc (-109.71785:-119.83243:128.561);
\fill [black] (27.76,-23.22) -- (27.18,-22.48) -- (26.84,-23.42);
\draw (15.5,-19.20) node [below] {$P(b|a)$};
\draw [black] (31.568,-27.036) arc (14.17669:-104.88549:18.382);
\fill [black] (31.57,-27.04) -- (31.28,-27.93) -- (32.25,-27.69);
\draw (24,-46.09) node [left] {$P(b|c)$};
\draw [black] (7.592,-11.979) arc (93.95767:86.04233:328.286);
\fill [black] (7.59,-11.98) -- (8.42,-12.42) -- (8.36,-11.43);
\draw (30.25,-10.7) node [above] {$P(a|d)$};
\draw [black] (53.622,-14.151) arc (-51.2137:-78.03555:47.886);
\fill [black] (33.55,-23.67) -- (34.44,-23.99) -- (34.23,-23.02);
\draw (46.97,-19.61) node [above left] {$P(b|d)$};
\draw [black] (55.607,-31.214) arc (-175.27936:-184.72064:97.384);
\fill [black] (55.61,-31.21) -- (56.04,-30.38) -- (55.04,-30.46);
\draw (54.78,-27.2) node [above left] {$P(c|d)$};
\draw [black] (58.099,-14.237) arc (43.2333:-61.80904:21.727);
\fill [black] (52.53,-48.27) -- (53.47,-48.33) -- (53,-47.45);
\draw (64.42,-32.85) node [right] {$P(d|d)$};
\draw [black] (52.291,-51.151) arc (84.18903:-203.81097:2.25);
\draw (56.05,-55.84) node [below] {$P(d|d)$};
\fill [black] (50,-52.48) -- (49.43,-53.23) -- (50.42,-53.33);
\draw [black] (47.55,-51.483) arc (-51.43786:-131.71524:30.426);
\fill [black] (8.34,-50.4) -- (8.6,-51.31) -- (9.27,-50.56);
\draw (27.7,-58.68) node [below] {$P(c|d)$};
\draw [black] (32.939,-26.078) arc (49.80232:24.58692:59.422);
\fill [black] (32.94,-26.08) -- (33.23,-26.98) -- (33.87,-26.21);
\draw (42,-36.14) node [right] {$P(b|d)$};
\draw [black] (46.949,-48.567) arc (-109.23723:-149.82312:76.434);
\fill [black] (6.06,-14.82) -- (6.03,-15.77) -- (6.89,-15.26);
\draw (21.67,-32.85) node [right] {$P(a|d)$};
\draw [black] (57.526,-36.707) arc (60.70628:-227.29372:2.25);
\draw (56.94,-41.49) node [below] {$1$};
\fill [black] (54.9,-37.02) -- (54.07,-37.47) -- (54.94,-37.96);
\end{tikzpicture}
\label{fig:mctcc1}
}
%\hfill
\caption{DFA and PMC for $\mathcal{P}=a ; d ; c$ with $\Sigma=\{a,b,c,d\}$, and order $m=1$.}
\label{fig:dfa_mc_example}
\end{centering}
\end{figure}
\begin{center}
\end{center}