-
Notifications
You must be signed in to change notification settings - Fork 0
/
AFD.info.htm
178 lines (166 loc) · 6.69 KB
/
AFD.info.htm
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
<!DOCTYPE HTML>
<html>
<head>
<title>AFD</title>
<link rel="stylesheet" type="text/css" href="widget/Toc/styles.css">
<style>
SECTION { margin-left: 1em;}
TD { padding: 0 1em;}
</style>
</head>
<body>
<dl class="menu">
<dt><a href="index.htm">Index</a><!-- <a href="xml/fr/doc/index.htm">Documentation</a> --></dt>
<dt><h3>Sommaire</h3></dt>
<dt><a href="#toc1">Préambule</a></dt>
<dt><a href="#toc2">Conversion AFN en AFD</a></dt>
<dd><dl>
<dt><a href="#toc21">ε-Closure</a></dt>
</dl></dd>
<dt><a href="#toc3">Minimisation</a></dt>
<dd><dl>
<dt><a href="#toc31">Nombre d'états</a></dt>
<dt><a href="#toc32">Alphabet</a></dt>
</dl></dd>
<dt><a href="#toc4">Reconnaissance</a></dt>
</dl>
<p id="back-top"><a href="#"><span></span>Haut de page</a></p>
<h1>AFD</h1>
<a name="toc1"></a>
<h2>Préambule</h2><section>
<p>
AFD = <a href="AF.info.htm">Automate Fini</a> Déterministe<br>
( DFA = Determinist Finite Automaton )
</p>
<ul>
<li>a au maximum une transition pour un état et un symbole.</li>
<li>n'a pas de transition ε.</li>
</ul>
<p>
Un AFD reconnait un ou plusieurs tokens.
Il est créé depuis un AFN ou par aggrégation d'AFD.
</p>
</section>
<a name="toc2"></a>
<h2>Conversion AFN en AFD</h2><section>
<ul>
<li>Un état d'un AFD correspond à des groupes d'états d'un AFN.</li>
<li>
L'<b>état initial</b> d'un AFD est égale à l'ε-Closure de l'état initial d'un AFN.
</li>
<li>
Pour chaque nouvel état d'un AFD et chaque symbole de l'alphabet : <br>
Une transition (s<sub>dfa1</sub>,c)→s<sub>dfa2</sub> est ajouté si s<sub>dfa2</sub> ≠ ∅ <br>
s<sub>dfa2</sub> est l'ensemble d'état d'un AFN accessible depuis s<sub>dfa1</sub> après avoir lu le symbole c, en considérant aussi les transitions ε.
</li>
<li>
Un état d'un AFD est un <b>état final</b> si il contient un état final d'un AFN.
</li>
</ul>
<a name="toc21"></a>
<h3>ε-Closure </h3><section>
<p>l'ε-Closure d'un état d'un AFN contient :</p>
<ul>
<li>cet état.</li>
<li>tous les états accessibles par des transitions ε depuis cet état.</li>
</ul>
</section>
</section>
<a name="toc3"></a>
<h2>Minimisation</h2><section>
<a name="toc31"></a>
<h3>Nombre d'états</h3><section>
<p>Les états ayant des lignes identiques dans la matrice sont regroupés en un état... enfin presque :</p>
<ol>
<li>On commence avec une partition initiale <code>Π</code> composé d'au moins deux groupes :
<ul>
<li>Les états finaux F reconnaissant un type de token (plusieurs groupes possibles) ou tous les états finaux.</li>
<li>Le reste des états S–F.</li>
</ul>
</li>
<li>Appliqué la procédure suivante pour créer une nouvelle partition :
<pre>
Π<sub>new</sub> = Π
PourChaque( groupe G de Π<sub>new</sub> )
partagé groupe G en sous-groupe de façon à ce que
deux états sont dans le même sous-groupe si et seulement si
pour tous les symboles, ces états pointent vers le même groupe de Π
replacé G dans Π<sub>new</sub> par l'ensemble des sous-groupes formé
</pre>
</li>
<li>Répété tant que quand <code>Π<sub>new</sub></code> est différent de <code>Π</code> </li>
<li>
Créé un nouvel AFD avec comme états la partition obtenue.
</li>
</ol>
<p>AFD avant et après réduction du nombre d'état:</p>
<table border="1" style="float:left;">
<tr><td><pre> \Symbole<br>Etat\</pre></td><th>a</th><th>b</th><th>c</th><th>d</th></tr>
<tr><th style="background:#6FB1FC;">1</th> <td>2</td><td>3</td><td>4</td><td>5</td></tr>
<tr><th style="background:#FC0 ;">2</th> <td>1</td><td>0</td><td>0</td><td>0</td></tr>
<tr><th style="background:#FC0 ;">3</th> <td>1</td><td>0</td><td>0</td><td>0</td></tr>
<tr><th style="background:#FC0 ;">4</th> <td>1</td><td>0</td><td>0</td><td>0</td></tr>
<tr><th style="background:#FC0 ;">5</th> <td>1</td><td>0</td><td>0</td><td>0</td></tr>
</table>
<table border="1" style="float:left; margin-left:2em;">
<tr><td><pre> \Symbole<br>Etat\</pre></td><th>a</th><th>b</th><th>c</th><th>d</th></tr>
<tr><th style="background:#6FB1FC;">1</th> <td>2</td><td>2</td><td>2</td><td>2</td></tr>
<tr><th style="background:#FC0 ;">2</th> <td>1</td><td>0</td><td>0</td><td>0</td></tr>
</table>
<div style="clear:both;"></div>
</section>
<a name="toc32"></a>
<h3>Alphabet</h3><section>
<p>Les symboles ayant des colonnes identiques dans la matrice sont regroupés dans un ensemble de caractères.</p>
<p>AFD avant et après réduction de l'alphabet:</p>
<table border="1" style="float:left;">
<tr><td><pre> \Symbole<br>Etat\</pre></td><th>a</th><th>b</th><th>c</th><th>d</th></tr>
<tr><th style="background:#6FB1FC;">1</th> <td>2</td><td>2</td><td>2</td><td>4</td></tr>
<tr><th style="background: ;">2</th> <td>2</td><td>2</td><td>2</td><td>3</td></tr>
<tr><th style="background:#FC0 ;">3</th> <td>2</td><td>2</td><td>2</td><td>4</td></tr>
<tr><th style="background: ;">4</th> <td>2</td><td>2</td><td>2</td><td>4</td></tr>
</table>
<table border="1" style="float:left; margin-left:2em;">
<tr><td><pre> \Symbole<br>Etat\</pre></td><th>[abc]</th><th>d</th></tr>
<tr><th style="background:#6FB1FC;">1</th> <td>2</td><td>4</td></tr>
<tr><th style="background: ;">2</th> <td>2</td><td>3</td></tr>
<tr><th style="background:#FC0 ;">3</th> <td>2</td><td>4</td></tr>
<tr><th style="background: ;">4</th> <td>2</td><td>4</td></tr>
</table>
<div style="clear:both;"></div>
</section>
</section>
<a name="toc4"></a>
<h2>Reconnaissance</h2><section>
<p>Résolution des ambiguïtés:</p>
<ol>
<li>La chaîne trouvée sera toujours la plus longue possible.</li>
<li>Priorité des régles : Si la chaîne trouvée reconnaît deux tokens. Premier arrivé, premier servi !</li>
</ol>
<p>Exemple d'implémentation recherchant la plus grande chaîne pouvant être trouvée:</p>
<pre>
function match( oDFA, sText, nIndex ){
var nState = oDFA.I, nStartIndex, nCurrentIndex, oMatched
nStartIndex = nCurrentIndex = nIndex || 0
while( nState = oDFA.nextState( nState, sText.charAt( nCurrentIndex++ ))){
if( oDFA.haveFinalState( nState )){
oMatched={ start:nStartIndex, end:nCurrentIndex }
}
}
return oMatched
}
</pre>
<p>Premier arrivé...</p>
<pre>
function searchToken( aTokens, sText, nIndex ){
var oMatched
for(var i=0; aTokens[i]; i++ )
if( oMatched = match( aTokens[i], sText, nIndex ))
return oMatched // ...first found
}
</pre>
</section>
<script type="text/javascript" src="http://ajax.googleapis.com/ajax/libs/jquery/1.4.3/jquery.min.js"></script>
<script type="text/javascript" src="widget/Toc/jquery.js"></script>
</body>
</html>