Download Fichier PDF

76
Chapitre 5. Compilation du filtrage syntaxique
e0
f
e1
g
ω
e2 ω e3
fω
a
e4
f ga
ceci est un jumpNode
fω
Fig. 5.7 – Cet automate a été construit à partir d’une clôture réduite , mais n’étant pas
canonique, une règle de transition d’états (δi = (e2 ,ω) −→δ e3 ) a été ajoutée afin de permettre un
changement de branche et remettre en cause le dernier choix effectué. Il permet en particulier
de reconnaı̂tre le terme f gb sans bloquer l’automate dans l’état e2 .
nous proposons d’étendre l’automate à mémoire, en lui ajoutant des règles de transition d’états
et une règle de transition de configuration, pour l’affranchir de ces deux étapes de mémorisation
et de recherche. Commençons par faire quelques remarques :
– lorsque l’automate doit s’arrêter et faire une recherche, il est forcément dans un état d’où
aucune arête étiquetée par un ω ne part ;
– si l’automate trouve, dans sa mémoire, un état e1 (appelé choix-ω ) d’où part une arête
étiquetée par un ω (δi : (e1 ,ω) −→δ e2 ) lui permettant, en utilisant le troisième mode de
déplacement, d’atteindre une position plus à droite, cet état e1 peut être déterminé statiquement en analysant la structure de l’automate : pour chaque état susceptible d’arrêter
l’automate, il suffit de parcourir en sens inverse les arêtes jusqu’à trouver un embranchement avec une arête ω qui aurait permis d’atteindre un point plus à droite sur la bande de
lecture. Si aucun choix-ω n’est trouvé, c’est qu’aucun état convenable n’aurait été trouvé
dans la mémoire et l’automate peut potentiellement se bloquer ;
– étant donné un état e susceptible d’arrêter l’automate et son choix-ω (δi : (e1 ,ω) −→δ e2 )
correspondant, le fait d’ajouter une règle de transition d’états δj : (e,ω) −→δ e2 appelée
jumpNode (voir figure 5.7), permettant de passer de l’état bloquant e à l’état e2 , en utilisant le troisième mode de déplacement de la tête de lecture, simule le comportement de
l’automate à mémoire.
L’automate de filtrage est une représentation d’un ensemble de suffixes L. Si, après avoir
lu une suite de symboles α ∈ Σ∗ , un choix entre le symbole s et ω apparaı̂t, c’est que les
deux termes αst1 . . . t#s β et αωβ 0 appartiennent à l’ensemble L. Pour tout état e, susceptible de
bloquer l’automate, tel que e soit un état de la branche correspondant à st1 . . . t#s (en supposant
qu’il n’y a pas de choix-ω dans cette branche), un jumpNode, reliant e à l’état fils de l’arête ω,
doit être créé.
Partant d’un automate de filtrage correspondant à une clôture réduite , la construction
d’un automate de filtrage avec jumpNode se décompose en trois étapes :
1. si aucune arête étiquetée par le symbole ω ne part de l’état initial e0 , un état particulier
d’échec ej ainsi qu’une règle de transition d’états δi = (e0 ,ω) −→δ ej sont ajoutés à
l’automate pour permettre de prendre en compte un échec du filtrage.