-
Notifications
You must be signed in to change notification settings - Fork 0
/
AF.info.htm
94 lines (89 loc) · 2.74 KB
/
AF.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
<html>
<head>
<title>Les automates finis</title>
<link rel="stylesheet" type="text/css" href="css/fa.css">
<link rel="stylesheet" type="text/css" href="css/Thompson.css">
<style>
h2 {
margin: 0;
}
</style>
</head>
<body>
<a href="index.htm">Index</a> - <a href="xml/fr/doc/index.htm">Documentation</a>
<h1>Les automates finis</h1>
<p>Un automate fini est composé par :</p>
<table cellspacing="10">
<tr><th>Identifiant</th><td><b>Description</b></td><th>Symbole graphique</th></tr>
<tr>
<th>I</th>
<td class="desc">Un état initial, I ∈ S.</td>
<th><div class="fa Initial" title="état initial"></div></th>
</tr>
<tr>
<th>F</th>
<td class="desc">Un ensemble d'état final, F ⊆ S.</td>
<th><div class="fa Final" title="état final"></div></th>
</tr>
<tr>
<th></th>
<td class="desc">Note : Symbole graphique d'un état initial et final.</td>
<th><div class="fa InitialFinal" title="état initial et final"></div></th>
</tr>
<tr>
<th>A</th>
<td class="desc">Un alphabet composé de symbole: caractère, ensemble de caractère (négatif ou non).</td>
<th></th>
</tr>
<tr>
<th>S</th>
<td class="desc">Un ensemble d'état.</td>
<th></th>
</tr>
<tr>
<th valign="top">T</th>
<td valign="top" class="desc">Un ensemble de transitions. <br>
(s1,a)→s2 est une transition avec s1,s2 ∈ S et a ∈ A.</td>
<th>
<div class="fa TransitionSymbol" title="transition pour un caractère"></div><br>
<div class="fa TransitionCharclass" title="transition pour un ensemble de caractère."></div><br>
<div class="fa TransitionEpsilon" title="transition ε"></div><br>
<div class="fa SelfLoop" title="boucle sur soit"></div>
</th>
</tr>
</table>
<table cellspacing="20">
<tr>
<th valign="top"><div class="fa TransitionSymbol"></div></th>
<td>
<h2>Transition à un caractère</h2>
<p>La machine passe d'un état à un autre en lisant un caractère.</p>
</td>
</tr>
<tr>
<th valign="top"><div class="fa TransitionCharclass"></div></th>
<td>
<h2>Transition pour un ensemble de caractère</h2>
<p>
Si le caractère lu fait partie de l'ensemble de caractère accepté, la machine change d'état.
</p>
<p>
L'automate perd en performance avec mais cette perte reste négligeable en utilisant des caches mémoires.<br>
Ce type de transition est nécessaire pour les ensembles de caractères négatifs.<br>
Elles permettent aussi de compresser l'automate.
</p>
</td>
</tr>
<tr>
<th valign="top"><div class="fa TransitionEpsilon"></div></th>
<td>
<h2>Transition ε (epsilon)</h2>
<p>
La machine passe d'un état à un autre sans lire de caractère.<br>
Ce type de transition est utilisé dans les AFN.
</p>
</td>
</tr>
</table>
</body>
</html>