PC 9
Automates finis

1. Automates finis
2. Exemples
3. Mots et langages
4. Automates déterministes
5. Expressions rationnelles

Automates finis Pour analyser des suites de symboles, on construit des diagrammes avec:

1. des sommets appelés états
2. des transitions étiquetées
3. des actions dans les états de reconnaissance.

On utilise les automates :

• Comme structure de données (généralisation des tries)
• Comme méthode de traitement de textes

Un exemple en traitement du signal Considérons le problème suivant : on veut éliminer dans une suite binaire les 0 ou les 1 isolés (considérés comme un bruit) (bounce filter).

L'automate est représenté sur la figure . La transformation est effectuée suivant la règle très simple :

filtre116mm81mm600Le filtre binaire

Programmation La programmation d'un automate est très simple : on suit le chemin en fonction des symboles de la donnée. Dans chaque état, on fait les actions correspondantes.

var c: char;
begin
1:   write('0');
     read(c);
     if c = '0' then goto 1;
     if c = '1' then goto 2;
     goto 99;

2:   write('1');
     read(c);
     if c = '0' then goto 1;
     if c = '1' then goto 3;
     goto 99;
 ...
99: 
    end;

Un autre exemple L'automate ci-dessous effectue la recherche du mot p=abaab dans un texte. kmp165mm66mm600Un automate de recherche La programmation utilise une fonction de remplacement:

où g(1)=0 et g(n)=k si le plus long préfixe de p[1..n-1] qui est aussi un suffixe est de longueur k-1.

L'algorithme de Knuth, Morris et Pratt On cherche le motif p[1..M] dans le texte t[1..N].

function kmp: integer;
 var i,j: integer;
 begin
  i:=1; j:=1; init;
  repeat
   if (j=0) or (a[i]=p[j])
    then begin i:=i+1; j:= j+1 end
    else j:=g[j];
  until (j>M) or (i>N);
  if j>M then kmp:= i-M else kmp:=i;
 end;

Complexité

• O(N+M) (au lieu de O(NM) pour l'algorithme na¨if). En effet, i+(i-j) augmente strictement à chaque étape.
• Surtout, il ne nécessite jamais de retour en arrière sur le texte.

recherche142mm38mm600La recherche dans un texte

Applications: recherche dans un dictionnaire (algorithme de Aho Corasick).

Le prétraitement Le calcul de g est fait par la procédure init:

procedure init;
 var i,j: integer;
 begin
  i:=1; j:=0; g[1]:= 0;
  repeat
   if (j=0) or (p[i]= p[j])
    then 
     begin i:= i+1; j:= j+1; g[i]:= j end
    else j:= g[j];
  until i>= M;
 end;

Mots et Langages Formels On définit en général un mot sur un alphabet A comme une suite finie de symboles pris dans A.

L'alphabet A peut être l'ensemble des caractères de base et les mots les lexèmes ou:

On utilise le mot vide noté .

Un langage formel est un ensemble de mots.

Automates déterministes

Un automate est déterministe si:

1. Il possède un seul état initial
2. De chaque état part au plus une flèche étiquetée par chaque symbole.

Par exemple, l'automate:

nondet165mm26mm700

n'est pas déterministe.

Déterminisation

Tout automate fini est équivalent à un automate fini déterministe. C'est une propriété fondamentale des automates.

Algorithme: on part d'un automate non-déterministe . On construit l'automate déterministe ayant

1. comme états les parties de Q
2. comme état initial I
3. comme transitions: (U,a,V) si V est l'ensemble des états atteignables depuis U par une transition a
4. comme états terminaux les tels que .

Complexité: si a n états, peut avoir états.

Exemple

nondet165mm26mm700Un automate non-déterministe

subset167mm65mm700Le résultat de l'algorithme

Généralisation

On peut admettre des transitions d'étiquette (transitions spontanées).

Pour déterminiser, il faut cette fois

1. prendre pour l'étape 2 les états atteignables depuis I par un -chemin.
2. et pour 3 l'ensemble des états atteignables par un chemin d'étiquette a.

Expressions Rationnelles

Pour spécifier des suites de symboles, on utilise

1. l'union notée | (ou +)
2. La concaténation (pas de symbole)
3. L'itération *

Utilisation

• Editeurs de texte (vi ou ed)
• Spécifications lexicales (Lex)
• commande grep sous Unix:

  grep <expression> <fichier>

  imprime les lignes du fichier contenant un bloc satisfaisant l'expression.

Exemples Identificateurs en Pascal:

Nombres sans signe en Pascal:

Avec les abréviations:

ident179mm28mm700Identificateurs en Pascal

relop159mm124mm700Opérateurs relationels

nombres183mm110mm700Nombres sans signe

La construction récursive

On peut construire récursivement un automate fini reconnaissant une expression rationnelle. L'automate construit est tel que:

1. Il a un seul état initial i
2. Il a un seul état final
3. Aucune flèche ne rentre dans i
4. Aucune flèche ne sort de t

Pour et a, on prend:

start124mm16mm700

thomson124mm115mm700Union, produit et étoile

• About this document ...