Les automates

Les automates

Les automates et les machines à états finies sont nés quasiment en mˆeme temps que l’informatique et ont été intensivement étudiés et utilisés durant les 50 dernières années. D’abord modèles d’étude théoriques riches et puissants, leur succès s’explique aussi par leur efficacité pratique et le nombre impressionnant d’applications pour lesquelles ils se révèlent particulièrement bien adaptés. Les machines à états trouvent leur utilité dans la conception de composants électroniques, la recherche de motifs, le cryptage, la compression de donnée, la linguistique avec les analyses morphologique, syntaxique et sémantique, la correction orthographique, la reconnaissance de la parole, etc. Des graphes aux transducteurs en passant par les automates, les applications des machines à états finies sont beaucoup trop nombreuses pour en dresser une liste exhaustive. Ce chapitre aborde les définitions formelles des automates. Il constitue la première étape de l’exposé qui nous mènera progressivement du modèle mathématique au modèle informatique abstrait puis à son implémentation concrète. Il s’agit donc ici de définir le plus formellement possible les abstractions mathématiques sur lesquelles reposeront les définitions d’abstractions logicielles.

Mots et langages

Un automate sert notamment à modéliser et à construire une grammaire. Cette grammaire définit un langage, autrement dit un ensemble de mots autorisés que l’automate est capable de reconnaˆıtre. 

Définitions

Soit Σ un ensemble appelé alphabet dont les éléments sont appelés lettres. Un mot w sur l’alphabet Σ est une suite finie de lettres (σ1, σ2, …, σn) avec pour longueur n ≥ 0 notée |w|. On désigne la ieme ` lettre du mot par wi . Si n = 0, w est appelé mot vide et noté ǫ. L’ensemble des mots sur l’alphabet Σ est noté Σ∗ et Σ+ = Σ∗ \ {ǫ}. Le produit ou concaténation de deux mots u, v ∈ Σ ∗ s’obtient en écrivant séquentiellement les lettres de u puis celles de v : u · v = u1 u2 … un v1 v2 … vm Par simplification et partout o`u cela ne prˆete pas à confusion on omettra le · en écrivant uv plutˆot que u ·

Les automates

Le produit d’un mot u avec lui-mˆeme répété k fois s’écrit u k avec u 0 = ǫ. Si w = uw′ v on dit que w ′ est un facteur de w, u est un préfixe de w et v est un suffixe de w. Un langage sur l’alphabet Σ est un sous-ensemble de Σ∗ . 2.1.2 Opérations sur les langages Soient A et B deux langages. On généralise le produit de mots aux langages comme suit : A · B = {ab | a ∈ A, b ∈ B} On définit les opérations booléennes sur les langages par : A ∩ B = {w | w ∈ A et w ∈ B} A ∪ B = {w | w ∈ A ou w ∈ B} A \ B = {w | w ∈ A et w /∈ B} A △ B = (A ∪ B) \ (A ∩ B) = {w | w ∈ A ∪ B et w /∈ A ∩ B} A = Σ∗ \ A = {w | w ∈ Σ ∗ et w /∈ A}

Automates finis

2.2.1 Définition Pour accroˆıtre la généricité et s’adapter aux besoins algorithmiques on ajoute à la définition traditionnelle des automates la possibilité d’associer à chaque état une information quelconque appelée « tag ». L’ensemble τ associe les états de l’automate à leur tag de manière bijective. Soit A(Σ, Q, I, F, ∆, T, τ ) un 7-uplet d’ensembles finis définit comme suit : Σ Un alphabet Q Un ensemble d’états I ⊆ Q Un ensemble d’états initiaux F ⊆ Q Un ensemble d’états finaux ou terminaux ∆ ⊆ Q × (Σ ∪ {ǫ}) × Q Un ensemble de transitions T Un ensemble de tags τ ⊂ (Q × T) Un ensemble associant les états à leur tags respectifs L’étiquette d’une transition (q, σ, p) est la lettre σ, q est sa source et p sa destination ou but. Lorsque σ = ǫ (le mot vide) la transition est appelée epsilon-transition. On appelle transitions entrantes de l’état s, l’ensemble des transitions (q, σ, p) ∈ ∆ telles que p = s et inversement, on appelle transitions sortantes l’ensemble des transitions (q, σ, p) ∈ ∆ telles que q = s. On notera P(X) l’ensemble des parties d’un ensemble X et |X| son nombre d’éléments