Index

Sommaire

Préambule
Conversion AFN en AFD
ε-Closure
Minimisation
Nombre d'états
Alphabet
Reconnaissance

Haut de page

AFD

Préambule

AFD = Automate Fini Déterministe
( DFA = Determinist Finite Automaton )

Un AFD reconnait un ou plusieurs tokens. Il est créé depuis un AFN ou par aggrégation d'AFD.

Conversion AFN en AFD

ε-Closure

l'ε-Closure d'un état d'un AFN contient :

Minimisation

Nombre d'états

Les états ayant des lignes identiques dans la matrice sont regroupés en un état... enfin presque :

  1. On commence avec une partition initiale Π composé d'au moins deux groupes :
    • Les états finaux F reconnaissant un type de token (plusieurs groupes possibles) ou tous les états finaux.
    • Le reste des états S–F.
  2. Appliqué la procédure suivante pour créer une nouvelle partition : 
    	Πnew = Π
	PourChaque( groupe G de Πnew )
		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 Πnew par l'ensemble des sous-groupes formé
  3. Répété tant que quand Πnew est différent de Π
  4. Créé un nouvel AFD avec comme états la partition obtenue.

AFD avant et après réduction du nombre d'état:

   \Symbole
Etat\
abcd
1 2345
2 1000
3 1000
4 1000
5 1000
   \Symbole
Etat\
abcd
1 2222
2 1000

Alphabet

Les symboles ayant des colonnes identiques dans la matrice sont regroupés dans un ensemble de caractères.

AFD avant et après réduction de l'alphabet:

   \Symbole
Etat\
abcd
1 2224
2 2223
3 2224
4 2224
   \Symbole
Etat\
[abc]d
1 24
2 23
3 24
4 24

Reconnaissance

Résolution des ambiguïtés:

  1. La chaîne trouvée sera toujours la plus longue possible.
  2. Priorité des régles : Si la chaîne trouvée reconnaît deux tokens. Premier arrivé, premier servi !

Exemple d'implémentation recherchant la plus grande chaîne pouvant être trouvée:

	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
		}

Premier arrivé...

	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
		}