Majeure 2
Langages et Compilation
Cours 2


Automates finis

jean-jacques.levy@inria.fr

26 janvier 1998

Les supports de cours sont en

http://www.polytechnique.fr/poly/edu/informatique/
http://www.polytechnique.fr/poly/~levy/

Livres:

• Kozen, Automata and Computability, Springer 1997.

  
  

• Hopcroft-Ullman, Formal languages and their Relation to Automata, Addison Wesley, 1969

  
  

• Aho-Ullman. The Theory of Parsing, Translation, and Compiling, volume 1 et 2: Parsing. Prentice-Hall, 1972.

  
  

• Aho, Sethi, Ullman, Compilers: Principle, Techniques, and Tools, Addison Wesley, 1986

Introduction

• Quelques exemples
• Automates finis déterministes
• Automates non-déterministes
• Automates minimaux
• Automates finis et langages réguliers
• Propriétés de fermeture
• Problèmes décidables
• Expressions régulières
• Automates en ML

Quelques exemples

• Mécanisme d'un distributeur automatique
• Protocoles réseau (bit alterné, etc)
• Peloton d'exécution (Firing squad problem)
• Systèmes réactifs
• Contrôle dans les circuits
• Analyseurs lexicaux

Distributeur à boissons

Il y a une fente pour les pièces de 1F, 2F, 5F, 10F. Le café sort si on met 5F. On peut aussi faire une machine avec buffer de longueur 1 ou 2, qui permet de mettre directement 10F pour avoir 2 cafés.

Protocoles réseau

Peloton d'exécution

Il y a une forte brûme sur le plateau. Le général convoque 400 soldats, les aligne, et veut les faire tirer, tous en même temps. A tout moment, le général et les soldats changent d'état de manière synchrone en ne tenant compte que de leurs 2 voisins immédiats. Il y a donc 3 types de machines: le général, les soldats et le soldat du bout de la chaîne.

Montrer qu'on peut trouver une solution en moins de 8 états pour les 3 types de machines quelquesoit le nombre de soldats.

Autre exemple

Automate fini acceptant tous les mots contenant un nombre pair de a et de b.

Automate fini

Un automate fini M est un quintuplet $(Q, \Sigma, \delta, q_0, F)$où:

$\Sigma$ est un alphabet (de terminaux ou tokens),
Q est un ensemble fini d'états,
$q_0 \in Q$ est l'état initial,
$F \subset Q$ est l'ensemble des états finaux,
$\delta : Q \times \Sigma \rightarrow Q$ est la fonction de transition

On peut étendre $\delta$ sur $Q \times \Sigma^* \rightarrow Q$ comme suit:

$\delta(q, \epsilon) = q$
$\delta(q, aw) = \delta(\delta(q,a), w)$

Le langage reconnu par l'automate M est:

$T(M) = \{w \mid \delta(q_0,w) \in F\}$

Graphiquement

Les mots de $\Sigma$ à analyser sont sur une bande (non modifiable). L'automate est un lecteur de bande. Initialement la tête de lecture est sur la première lettre du mot, l'automate est dans l'état q₀. Puis la tête de bande de déplace d'un cran vers la droite en changeant d'état en fonction du caractère lu, et ainsi de suite jusqu'à la fin du mot. Le mot est accepté si sa fin est obtenue dans un état de F.

Représentation des automates finis

Quatre méthodes:

• le contrôle fini d'un programme. Autant de points d'entrée (étiquettes ou procédures) que d'états:

  let c = ref( input_char() ) in 
  let rec 
      q() = if !c = `a` then begin c := get(); r() end else
            if !c = `b` then begin c := get(); t() end 
  and r() = if !c = `a` then begin c := get(); q() end else
            if !c = `b` then begin c := get(); s() end 
  and s() = if !c = `a` then begin c := get(); t() end else
            if !c = `b` then begin c := get(); r() end 
  and t() = if !c = `a` then begin c := get(); s() end else
            if !c = `b` then begin c := get(); q() end ;;
  

ou Représentation des automates finis (2)

let m() = 
  let rec m1 q c = match q with
        0 -> if c = `a` then let c = get() in m1 1 c else
             if c = `b` then let c = get() in m1 3 c else
             if c = eof then exit(0) 
      | 1 -> if c = `a` then let c = get() in m1 0 c else
             if c = `b` then let c = get() in m1 2 c
      | 2 -> if c = `a` then let c = get() in m1 3 c else
             if c = `b` then let c = get() in m1 1 c
      | 3 -> if c = `a` then let c = get() in m1 2 c else
             if c = `b` then let c = get() in m1 0 c
      | _ -> ()
  in let c = get() in  m1 0 c ;;

ou encore:

Représentation des automates finis (3)

let m() = 
  let rec m1 q c = if c = eof then exit (q) else
      let c' = get() in match q with
        0 -> if c = `a` then m1 1 c' else if c = `b` then m1 3 c'
      | 1 -> if c = `a` then m1 0 c' else if c = `b` then m1 2 c'
      | 2 -> if c = `a` then m1 3 c' else if c = `b` then m1 1 c'
      | 3 -> if c = `a` then m1 2 c' else if c = `b` then m1 0 c'
      | _ -> ()
  in let c = get() in  m1 0 c ;;

ou encore encore: Représentation des automates finis (3)

let m() = 
  let rec m1 q c = if c = eof then exit (q) else
      let c' = get() in match q, c  with
        0, `a` ->  m1 1 c'
      | 0, `b` ->  m1 3 c'
      | 1, `a` ->  m1 0 c'
      | 1, `b` ->  m1 2 c'
      | 2, `a` ->  m1 3 c'
      | 2, `b` ->  m1 1 c'
      | 3, `a` ->  m1 2 c'
      | 3, `b` ->  m1 0 c'
      | _ -> ()
  in let c = get() in  m1 0 c ;;

Représentation des automates finis (4)

• matrice $\vert Q\vert \times \vert\Sigma\vert$ de transition (éventuellement compressée).

  let mat =  make_matrix 10 10 0;;
  
  let m() = 
    let rec m1 q c = 
        if c = eof then exit (q) else
        let c' = get() in 
        let q' = mat.(q).(int_of_char c) in
        m1 q' c'
    in  let c = get() in  m1 0 c ;;
  

• listes d'association, ie listes de paires (q,a), pour chaque état.

Automates non déterministes

A chaque état, l'automate peut faire un choix non déterministe entre plusieurs transitions. Formellement, $\delta : Q \times \Sigma \rightarrow 2^Q$ et on étend $\delta$ comme suit

$$\delta(q, \epsilon) = \{q\} \quad\quad\quad \delta(q, aw) = \bigcup_{q' \in \delta(q, a)} \delta(q',w)$$

Le langage reconnu par l'automate non déterminite M est:

$T(M) = \{w \mid \delta(q_0,w) \cap F \neq \emptyset \}$

Un mot est accepté si une série de choix peut amener l'automate dans un des états finaux de F. Les mauvais choix ne comptent donc pas.

Exemples non déterministes

• $L = \{ xaay \mid x,y \in \Sigma^* \} \cup \{ xbby \mid x,y \in \Sigma^* \}$
• $L = L_1 \cup L_2$ où L₁ et L₂ sont reconnus par des automates finis

Déterminisation des automates finis

Théorème 1 [Rabin-Scott] Tout langage reconnu par un automate fini non déterministe peut aussi être reconnu par un automate fini déterministe.

Démonstration: on considère l'automate déterministe défini sur 2^Q, en prenant $\{ q_0 \}$ comme état initial et F comme ensemble de fin.

Remarque L'automate déterminisé peut avoir 2ⁿ états, si n est le nombre d'états de l'automate non-déterministe.

Automates finis et langages réguliers

Théorème 2 Les langages réguliers sont les langages reconnus par les automates finis.

Démonstration: Soit $G =(\Sigma, V_N, S, \mathcal{P})$ une grammaire régulière. Construisons M tel que L(G) = T(M). Posons $M = (Q, \Sigma, \delta, S, \{T\})$, où $T \not\in V_N$ et $Q = V_N \cup {T}$avec
$\delta(A, a) = B$ ssi $A \rightarrow aB$
$\delta(A, a) = T$ ssi $A \rightarrow a$

La réciproque est facile.

Automate minimal

Tout automate $(Q, \Sigma, \delta, q_0, F)$définit sur $\Sigma^*$ la relation d'équivalence: $x \mathcal{R} y$ ssi $\delta(q_0, x) = \delta(q_0, y)$.

Appelons index de $\mathcal{R}$ son nombre de classes d'équivalences. L'index de $\mathcal{R}$ n'est donc pas plus grand que le nombre d'états de Q.

En outre, $x \mathcal{R} y$ implique $xz \mathcal{R} yz$ pour tout z. La relation est fermée par facteur droit.

Lemme 3 Les 3 clauses suivantes sont équivalentes:

1.

L est reconnu par un automate fini.

2.

L est l'union de classes d'équivalence d'une relation d'équivalence fermée par facteur droit d'index fini.

3.

La relation $\mathcal{R}$, définie par $x \mathcal{R} y$ ssi pour tout z, on a $xz \in L \Leftrightarrow yz \in L$, est d'index fini.

Automate minimal (2)

Théorème 4 [Myhill - Nerode] L'automate minimal reconnaissant un langage L est unique à un isomorphisme près sur le nom des états.

De manière non constructive, nous avons démontré qu'il existe un automate minimal. Reste à trouver un algorithme efficace pour le trouver.

De la même manière, on peut déterminiser un automate et construire son automate minimal, ou essayer d'obtenir plus directement l'automate fini correspondant.

Construction de l'automate minimal

Soit $M = (Q, \Sigma, \delta, q_0, F)$

On considère la partition $\Pi = \{F,\; Q-F \}$

On itère la procédure suivante tant que $\Pi$ n'est pas stationnaire.

Pour tout $E \in \Pi$, on casse E en E₁, E₂, etc tels que, pour tous $q,q' \in E_i$, pour tout $E '\in \Pi$, et pour tout $a \in \Sigma$, on a $\delta(q, a) \in E '$ ssi $\delta(q', a) \in E '$.

A la fin, on élimine les états inaccessible depuis l'état initial.

Propriété de fermetures des langages réguliers

Les langages réguliers forment une algèbre de Boole (fermés par union, intersection et complément).

Si L est régulier, L^* est régulier.

On peut définir le produit de 2 langages L et L', par extension naturelle sur la concaténation des mots:
$LL' = \{uu' \mid u\in L, u'\in L' \}$.

Si L et L' sont réguliers, L L' est régulier.

Théorème 5 Les langages réguliers sont la plus petite classe de langages contenant les ensembles finis et fermée par produit, étoile et union.

Expressions régulières

Une expression régulière e représente un langage $[\hspace{-.3ex}[ e ]\hspace{-.3ex}]$

$[\hspace{-.3ex}[ a ]\hspace{-.3ex}] = \{ a \}$
$[\hspace{-.3ex}[ e + e' ]\hspace{-.3ex}] = [\hspace{-.3ex}[ e ]\hspace{-.3ex}] \cup [\hspace{-.3ex}[ e' ]\hspace{-.3ex}]$
$[\hspace{-.3ex}[ e e' ]\hspace{-.3ex}] = [\hspace{-.3ex}[ e ]\hspace{-.3ex}] [\hspace{-.3ex}[ e' ]\hspace{-.3ex}]$
$[\hspace{-.3ex}[ e^* ]\hspace{-.3ex}] = [\hspace{-.3ex}[ e ]\hspace{-.3ex}]^*$
$[\hspace{-.3ex}[ (e) ]\hspace{-.3ex}] = [\hspace{-.3ex}[ e ]\hspace{-.3ex}]$

Parfois, on écrit $e \mid e '$ au lieu de e + e '.

Exemples
(a+b)^*abb est l'ensemble des mots sur a et b finissant par abb
(a+b)^*w(a+b)^* est l'ensemble des mots contenant w. Un peu d'algèbre

Ajoutons et 1 en posant $[\hspace{-.3ex}[ 0 ]\hspace{-.3ex}] = \emptyset$ et $[\hspace{-.3ex}[ 1 ]\hspace{-.3ex}] = \{ \epsilon \}$.

Les lois suivantes sont vérifiées:

1 e + e' = e' + e

2 e + (e' + e'') = (e + e') + e''

3 e + 0 = e

4 e + e = e

5 e(e'e'') = (e e') e''

6 1 e = e 1 = e

7 e (e' + e'') = e e' + e e''

8 (e + e') e'' = e e'' + e' e''

9 0 e = e 0 = 0

10 1 + e e ^* = e ^*

11 1 + e ^* e = e ^*

Un peu d'algèbre (2)

Et en notant $e \leq e '$ quand e + e ' = e ', ie $[\hspace{-.3ex}[ e ]\hspace{-.3ex}] \subset [\hspace{-.3ex}[ e ' ]\hspace{-.3ex}]$, on a aussi:

$$e ' + e e '' \leq e '' \Rightarrow e ^* e ' \leq e ''$$ 12

$$e ' + e '' e \leq e '' \Rightarrow e ' e ^* \leq e ''$$ 13

On peut montrer que les 13 axiomes ou règles précédentes permettent de déduire toutes les équations sur les expressions régulières (théorie équationnelle complète, cf DEA SPP pour plus de détails).

Montrer, par exemple, que (ee ')^* e = e(e 'e)^*, ou e e ^* = e ^* e, ou (e ^* e ')^*e ^* = (e + e ')^*, etc.

Expressions régulières et langages réguliers

Proposition 6 Expressions régulières et langages réguliers coincident.

Décidabilité sur les automates finis Il existe des algorithmes pour décider de pratiquement toutes les propriétés sur les automates finis. Par exemple:

T(M) est-il vide?

T(M) est-il infini?

T(M) = T(M') ?

Autres formes d'automates

On ne change pas la force de reconnaissance des automates finis si on considère les automates avec des:

• transitions incomplètes. Si un état q ne propose pas de transitions pour toutes les lettres de l'alphabet, l'automate peut se bloquer dans ce cas, et le mot est refusé.

  
  

• transitions vides. Si une transition vide relie q à q', l'automate peut faire les transitions issues de q et de q', car il a le droit d'aller spontanément vers q'.

  
  

• transitions vides par défaut. Si transition vide par défaut relie q à q', l'automate (incomplet) peut faire les transitions issues de q, mais aussi celles de q' ssi une lettre ne figure pas dans les transitions possibles à partir de q.

Expressions régulières et Unix

Les commandes shell d'Unix autorisent les expressions régulières. D'autres commandes comme

/bin/sh (Bourne) pour les noms de fichiers,
sed, ed (Thomson) Stream editor, Editor
grep Get Regular ExPression
Emacs ESC-x re-search-forward
awk Interpréteur C (Aho, Weinberger, Kernighan)
lex (Lesk) Méta-compilateur d'expressions régulières pour C

recherchent des expressions régulières dans les fichiers. Tous ont leur syntaxe propre. En général, ils essaient d'avoir les expressions régulières les plus déterministes possible, sauf awk.

Expressions régulières et Unix (2)

On considèrera Awk, Lex et Camllex la prochaine fois.

Regardez le manuel sous Unix entre-temps

% man awk
% man lex
% man sed

Exercices

• Débutants: on exécute un automate non déterministe donné par une expression régulière donné sous forme d'un type ML.
• Moyens: On considère un automate non de´terministe donné par des listes de transitions, ou par une expression régulière. On veut le déterminiser et minimiser l'automate obtenu.
• Forts: Filtrage: KMP (Knuth, Morris, Pratt), BM (Boyer, Moore).