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:

Introduction

Quelques exemples

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 q0. 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:

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)

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


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

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

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 2Q, en prenant $\{ q_0 \}$ comme état initial et F comme ensemble de fin.

Remarque L'automate déterminisé peut avoir 2n é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 E1, E2, 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:

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

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:

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



1/25/1998