Grammaires, automates et langages formels

Automates finis

Les automates finis sont des machines abstraites qui vérifient sous forme séquentielle si un mot, passé en entrée, appartient ou non à un langage donné. Ces automates sont dits finis car restreints à un ensemble fini d’états qui mémorisent des informations. Les automates finis ont trouvé des applications directes dans plusieurs domaines qui vont de l’analyse lexicale de langues artificielles et naturelles, en passant par la compression de l’information, la recherche de motifs dans un texte, ou la vérification de systèmes, tel que des circuits électroniques, dotés d’un nombre fini d’états. 2.2 Automates finis 2 22 2.2.1 Automates finis déterministes Les automates finis déterministes sont rapides et efficaces pour traiter des problèmes d’analyse des langages tel que la génération automatique de phrases (cf. définition 2.5) ainsi que leur recherche dans des données textuelles. Considérons les phrases : (1) Leonardo was an Italian mathematician (2) * mathematician an Leonardo Italian was Un automate fini A qui reconnaît un langage quelconque L, est capable alors de dire si les phrases (1) et (2) appartiennent à L (propriété analytique). Dans la suite, nous présentons formellement ces automates ainsi que leur version non-déterministe. Définition 2.16 (Automate fini déterministe). Un automate fini déterministe est un quintuplet A = (Q, Σ, δ, q0, F), où : 1. Q est un ensemble fini d’états, 2. Σ est un alphabet, 3. δ : Q × Σ −→ Q est la fonction de transition, 4. q0 ∈ Q est l’état initial, et 5. F ⊆ Q est l’ensemble des états finaux. Un automate fini A correspond à un graphe orienté (cf. A.16) formé par un ensemble fini d’états Q (les nœuds du graphe) et de transitions (les arcs du graphe) qui les relient. Un état est désigné comme initial (q0 ∈ Q) et certains autres sont finaux (F ⊆ Q). Un automate est à tout instant dans un état unique, la fonction de transition δ décrit alors comment l’automate passe à un autre état en lisant un symbole de l’alphabet. Chaque transition est définie comme un triplet (p, σ, q) de Q × Σ × Q (l’ensemble de transitions) où : p est l’état de départ, σ est un symbole de l’alphabet, et q est l’état d’arrivée. Si A a une transition étiquetée par un symbole σ qui relie p à q, ceci indique que lorsque l’automate est dans l’état p et lit σ, il passe à l’état q. Cette règle de transition est notée : δ(p, σ) = q. Considérons l’exemple 2.17 : Exemple 2.17. A1 = (Q, Σ, δ, q0, F), 1. Q : {q0, q1, q2, q3} 2. Σ : {0, 1} 2 Grammaires, automates et langages formels 23 3. δ : est décrite par la table de transition d’état suivante : 1 q δ(q, 0) δ(q, 1) q0. q0 q1 q1 q2 q1 q2, q3 q3 q3 q2 q2 4. q0 5. F : {q2} Un automate fini peut être représenté graphiquement par un diagramme d’étatstransitions comme celui de la figure 2.2. L’état initial, conventionnellement le premier à gauche, est distingué par un arc orienté vers un nœud aux contours en gras. Les états finaux sont indiqués par des nœuds avec double cercle. Les transitions sont des arcs orientés allant d’un nœud de départ vers un nœud d’arrivée. Les étiquettes des transitions se placent sur les arcs. Lorsque un automate a plusieurs transitions 2 reliant deux états, alors il est possible de placer sur un seul arc l’ensemble des étiquettes sous forme la d’une liste. Pour l’automate A1 de l’exemple 2.17, nous avons deux transitions (q3, 0, q2) et (q3, 1, q2) reliant q3 à q2 qui sont représentées par un seul arc étiqueté par 0, 1. 1 0 1 0, 1 1 0 0 q0 q1 q2 q3 Figure 2.2 – Diagramme d’états-transitions d’un automate fini Définition 2.18 (Chemin sur un automate fini). Un chemin sur un automate fini est une suite de transitions menant d’un état p à un état r dont la concaténation des étiquettes successives (l’étiquette du chemin) forment un mot wi , wi+1, . . . , wj−1, wj . Nous notons ceci comme p wi,j −−→ r. Un chemin réussi est nommé ainsi lorsque p = q0 et r ∈ F, c’est-à-dire quand il existe un chemin allant de l’état initial à l’un des états finaux. Définition 2.19 (Mot accepté par un automate fini). Un mot w de Σ ∗ est accepté par un automate fini A s’il existe un chemin réussi qui est étiqueté par w, soit q0 w−→ r, tel que r ∈ F. 1. Les tables de transition d’états sont une alternative pour décrire les automates finis. Les lignes représentent les états. L’état initial est marqué par un point après son nom et les états finaux avec une virgule. Les colonnes représentent l’alphabet. Les cellules, c’est-à-dire les intersections ligne/colonne, codent les transitions. 2. Soit un sous-ensemble T ⊆ Q × Σ × Q, tel que T = {(p, σ, q) | p ∈ Q, σ ∈ Σ, q ∈ Q, δ(p, σ) = q} 2.2 Automates finis 2 24 Définition 2.20 (Langage reconnu par un automate fini). Le langage reconnu par un automate fini A, noté L(A), est égal à l’ensemble des mots acceptés par A. En particulier, deux automates A1 et A2 sont dits équivalents s’ils reconnaissent le même langage, soit L(A1) = L(A2). En outre, remarquons qu’un automate fini peut accepter plusieurs mots, mais il reconnaît toujours un seul langage. L’inverse n’est pas vrai, pour un langage donné, il peut exister plusieurs automates qui le reconnaissent. 

Automates finis non-déterministes

Rappelons qu’un automate fini déterministe est à tout instant dans un état unique et que lorsque il lit un symbole en entrée, il est possible de déterminer avec certitude quel sera l’état suivant. En effet, la fonction de transition d’un dfa est égal à δ : Q×Σ −→ Q, c’est-à-dire, qu’à partir d’un état p et d’un symbole σ dans Q × Σ, elle a toujours un seul état q d’arrivée dans Q, soit δ(p, σ) = q. Cependant, lorsqu’à partir d’un symbole donné et d’un état de départ il est possible d’avoir comme destination plusieurs états d’arrivée, ou lorsqu’il est admis de changer d’état sans lire un symbole, ou lorsqu’on a la faculté de choisir quel sera le prochain état, ou de passer dans un autre d’état spontanément, est appelé automate fini nondéterministe (nfa). Au sens informatique, le non-déterminisme peut se comparer à une sorte de parallélisme où pour chaque transition qui comporte plus d’un état d’arrivée, l’automate fini a la capacité de créer simultanément plusieurs copies de lui-même et, pour chaque copie, d’explorer chacun des états d’arrivée possibles. 2.2 Automates finis 2 26 En outre, pour chaque automate fini non-déterministe il y a un automate fini déterministe équivalent. Autrement dit, tout automate fini non-déterministe peut être converti en un automate fini déterministe équivalent. Ceci est d’un grand intérêt puisque, même si les automates finis non-déterministes sont plus coûteux à utiliser, ils ont un nombre d’états et de transitions réduits, ils sont plus faciles à comprendre et à construire. Dans la suite, nous donnons une définition formelle d’un automate fini non-déterministe. Définition 2.26 (Automate fini non-déterministe). Un automate fini non-déterministe est un quintuplet N = (Q, Σ, δ, q0, F), où : 1. Q est un ensemble fini d’états, 2. Σ est un alphabet, 3. δ : Q × Σε −→ ℘(Q) est la fonction de transition, 4. q0 ∈ Q est l’état initial, et 5. F ⊆ Q est l’ensemble des états finaux. Les automates finis déterministes et non-déterministes sont similaires à l’exception du type de fonction de transition δ utilisée. Observons que cette fonction de transition se différencie par : 1. l’alphabet d’entrée de la fonction qui n’est pas simplement Σ mais l’union entre cet alphabet et un ensemble ne contentant que le mot vide {ε}, noté Σε 1 ; 2. la sortie de la fonction qui n’est plus constituée par un seul état, mais par un ensemble des parties de Q, noté ℘(Q), contenant zéro, un état ou plus. Cela est illustré par l’exemple 2.27. Exemple 2.27. N1 = (Q, Σ, δ, q0, F), 1. Q : {q0, q1, q2, q3} 2. Σ : {0, 1} 3. δ : est décrite par la table de transition d’état suivante : q δ(q, 0) δ(q, 1) q0., ∅ {q1, q2} q1, ∅ {q1} q2 {q3} ∅ q3, ∅ {q2} 4. q0 5. F : {q0, q1, q3} 1. Pour éviter toute confusion, il est requis que ε ne soit pas membre de Σ. 2 Grammaires, automates et langages formels 27 1 1 1 0 1 q2 q3 q1 q0 Figure 2.4 – Diagramme d’états-transitions d’un nfa Définition 2.28 (ε–transitions). Les transitions qui font passer un automate fini non-déterministe d’un état dans un autre sans qu’aucune opération de lecture d’un symbole ne soit effectuée, sont nommées des transitions spontanées ou ε–transitions. De même, un automate fini non-déterministe avec ε–transitions est abrégé en ε–nfa. Remarquons que ce type de transitions est possible car la fonction de transition accepte ε ∈ Σε en entrée. Exemple 2.29. Un automate équivalent à N1 (exemple 2.27) qui utilise des transitions spontanées est donné à figure 2.5. 1 1 ε ε 0 ε q4 q3 q2 q1 q0 Figure 2.5 – Diagramme d’états-transitions d’un ε–nfa Enfin, il est important de mentionner que tout automate fini non-déterministe a un automate fini déterministe équivalent. La démonstration de ceci est due à Rabin et Scott (1959) et consiste à construire à partir d’un automate fini non-déterministe N = (Q, Σ, δ, q0, F) qui reconnaît un langage L, un automate fini déterministe A = (Q0 , Σ, δ0 , q0 0 , F0 ) qui reconnaît aussi L.