Automates et analyse des langages

Automates finis

Un automate ressemble à un graphe, et est composé d'états (représentés par des cercles), et des transitions (représentées par des flèches). Un automate fini permet de reconnaitre des chaînes de caractères possibles du langage.

Chaque transition qui mène à un état correspond à une lecture.

Notre automate débute avec un état initial, peut accepter des transitions en fonction de ce qu'il lit et de l'étiquette de la transition, et se termine dans un état final. La concaténation des différentes étiquettes du chemin parcouru dans l'automate nous donne un mot accepté par le langage de l'automate.

Dans le cas d'un langage vide, nous avons un état initial, et un état final qui ne sont reliés par aucune transition.

Théorème de Kleene4

“A language is regular iff it can be accepted by a finite automaton.”

« Un langage est régulier ssi il peut être accepté par un automate fini. »

Comme le théorème de Kleene nous affirme que les langages réguliers sont des langages décidés par des automates finis, nous pouvons construire un automate fini pour toute expression rationnelle.

Table des matières Haut

Automates finis non déterministes

Un AFN [automate fini non déterministe] (avec transitions vides) se compose de :

• Σ : l'ensemble des symboles d'entrée, l'alphabet⁹.
• S : l'ensemble fini d'états.
• s₀ ∈ S : l'état initial.
• F ⊆ S : l'ensemble des états finaux, ou ensemble des états d'acceptation (représentés par un double cercle).
• Δ ⊆ S x (Σ ∪ {ε}) x S : la relation de transition, ou fonction de transition, qui donne pour chaque état et pour chaque symbole de Σ ∪ {ε} l'ensemble des états suivants.

Nous pouvons remarquer que cet automate est non déterministe, car la lecture d'un caractère "a" dans l'état 0 peut mener soit à un retour à l'état 0, soit à l'état 1. Nous ne pouvons donc pas déterminer vers quel état l'automate se place après la lecture du caractère "a".

Table des matières Haut

Les tables de transitions

Nous pouvons représenter nos automates sous une forme graphique, mais nous pouvons aussi les représenter sous la forme d'un tableau à deux entrées : les états et les symboles d'entrée (dans notre cas, nous avons aussi ε).

Si nous reprennons notre exemple, nous pouvons construire la table suivante :

Nous constatons que notre automate est non déterministe car nous avons plus d'une valeur pour la lecture d'un caractère a dans l'état S₀.

La ligne correspondant à l'état S₃ ne possède pas de valeur car nous n'avons pas de transitions depuis cet état.¹⁰

Table des matières Haut

Automates finis déterministes

Lorsque nous avons un automate qui, pour chaque état et pour chaque symbole d'entrée, ne possède qu'au maximum une seule transition possible, nous n'avons plus de choix. Nous parlons alors d'automate fini déterministe [AFD].

Dans ce cas, notre AFD ne peut adopter qu'un et un seul comportement pour un mot donné 

• Il ne possède pas de transition-ε
• Il ne possède qu'au maximum un état d'arrivée pour un caractère lu depuis un état de départ

Table des matières Haut

Automates complets

Si nous sommes en présence d'un AFD qui possède exactement un état d'arrivée pour un caractère lu depuis un état de départ, nous parlons alors d'automate fini déterministe [AFD] complet.

Table des matières Haut

Automates à pile

Si nous tentons de construire l'automate correspondant au langage non régulier¹² aⁿbⁿ, nous ne pouvons pas assurer que le nombre de a soit identique au nombre de b.

La solution est d'utiliser une pile que nous remplissions à chaque lecture d'un caractère a et que nous dépilons ensuite à chaque lecture d'un caractère b.

Un automate à pile se compose de :

• Σ : l'ensemble des symboles d'entrée, l'alphabet.
• Q : l'ensemble fini d'états.
• q₀ &isin ;Q : l'état initial.
• F ⊆ Q : l'ensemble des états finaux, ou ensemble des états d'acceptation.
• Δ fini ⊆ Q⁺ x (Σ ∪ {ε}) x Q^* : la relation de transition.

Table des matières Haut

Complémentation

Nous avons parfois besoin de créer un automate qui accepte tout ce qui n'appartient pas au langage. Cet automate est l'inverse de notre automate de départ, et nous parlons de complément.

Pour construire un automate A' qui accepte le complément de l'automate A, nous devons 

• Rendre A déterministe
• Le compléter 
  • Ajouter un état mort
  • Ajouter des transitions vers cet état
  • Appliquer la propriété suivante : chaque chaîne conduit à un seul état
• inverser les états finaux et non finaux

You are on the French version of the site, but your system indicates that you prefer to use the English language.
The entire site is not translated yet, but the menus and buttons on the interface are largely translated.

Would you like to reach the page in English?
Click here to continue in English: Consult the English version of this page

U bevindt zich op de Franse versie van de site, maar uw systeem geeft aan dat u liever de Nederlandse taal gebruikt.
De hele site is nog niet vertaald, maar de menu's en knoppen op de interface zijn grotendeels vertaald.

Wilt u de pagina in het Nederlands bereiken?
Klik hier om door te gaan in het Nederlands: Raadpleeg de Nederlandse versie van deze pagina

Sie befinden sich in der französischen Version der Website, Ihr System gibt jedoch an, dass Sie die deutsche Sprache bevorzugen.
Die gesamte Site ist noch nicht übersetzt, aber die Menüs und Schaltflächen auf der Benutzeroberfläche sind weitgehend übersetzt.

Möchten Sie die Seite auf Deutsch erreichen?
Klicken Sie hier, um fortzufahren: Konsultieren Sie die deutsche Version dieser Seite