Théorie des langages : Cours théorie des langages langages et grammaires
Télécharger PDFChapitre 4 : Langages réguliers et automates d'états finis
Définition des langages réguliers
Un langage est régulier si et seulement s'il existe une grammaire régulière qui le génère.
L'ensemble des mots-clés, identificateurs, constantes, chiffres (entiers ou réels), parenthèses, séparateurs, etc., d'un langage de programmation est un langage régulier et peut être décrit par une grammaire régulière.
Propriétés des langages réguliers
Étant donné un alphabet VT, un langage régulier sur VT est défini de la façon suivante :
1. Cas de base
∅ (l'ensemble vide) est un langage régulier sur VT.
{ε} (l'ensemble contenant le mot vide) est un langage régulier sur VT.
{a} est un langage régulier sur VT pour tout symbole a ∈ VT.
2. Union finie
Un ensemble fini de mots L = {u₁, ..., uₖ} s'écrit sous la forme :
L = {u₁} ∪ {u₂} ∪ ... ∪ {uₖ}.
L est régulier car chaque {uᵢ} l'est et l'ensemble des langages réguliers est clos pour l'union.
3. Langage singulier
Pour tout mot u ∈ VT*, le langage {u} est régulier.
Si u peut s'écrire sous la forme u = a₁...aₙ avec aᵢ ∈ VT, alors le langage {u} s'écrit comme suit :
{u} = {a₁}{a₂}...{aₙ}.
Le langage {u} est régulier car :
- chaque {aᵢ} est un langage régulier,
- et la concaténation de langages réguliers est un langage régulier.
4. Fermeture de Kleene
Le langage VT*, qui est l'ensemble de tous les mots définis sur VT, est régulier.
Si VT = {a₁, ..., aₚ}, alors :
- le langage {a₁, ..., aₚ} est régulier,
- VT* est la fermeture de Kleene de ce langage.
Les grammaires et les automates
Les grammaires sont des systèmes de génération de langages.
Les langages sont reconnus par des machines formelles appelées automates ou systèmes reconnaisseurs, capables de déterminer si un mot donné appartient ou non à un langage.
Automates d'états finis (AEF)
Un langage est régulier si et seulement s'il existe un automate d'états finis qui le reconnaît.
- Si un langage est régulier, alors il existe un automate d'états finis qui le reconnaît.
- Si un langage est reconnu par un automate d'états finis, alors il est régulier.
Définition d'un automate d'états finis
Un automate d'états finis (ou automate fini) est une machine abstraite constituée d'états et de transitions. Cette machine traite des mots fournis en entrée en passant d'état en état selon les transitions définies à la lecture de chaque symbole.
L'automate est dit « fini » car il possède un nombre limité d'états distincts.
Un mot est reconnu par l'automate s'il est entièrement lu et que l'automate se trouve dans un état final. Dans tous les autres cas, il est rejeté.
Structure formelle d'un AEF
Un automate à états finis (AEF) est défini par un quintuplet :
A = (VT, Q, q₀, δ, F), où :
- VT est un alphabet fini (l'ensemble des symboles terminaux).
- Q est un ensemble fini non vide d'états, par exemple Q = {q₀, q₁, q₂, ...}.
- δ est une fonction de transition δ : Q × VT → Q, qui associe à chaque état et symbole un nouvel état (exemple : δ(qᵢ, a) = qⱼ).
- q₀ est l'état initial.
- F est l'ensemble des états finaux, avec F ⊆ Q.
Représentation graphique d'un AEF
Un automate fini peut être représenté par un graphe orienté et étiqueté :
- Les nœuds :
- Les nœuds sont étiquetés par les noms des états.
- L'état initial est représenté par un carré.
- Les états finaux sont représentés par des triangles.
- Les autres états sont représentés par des cercles.
- Les arcs orientés : Ils représentent les transitions de l'automate et sont étiquetés par un symbole terminal.
Pour améliorer la lisibilité, deux arcs de même orientation entre deux nœuds peuvent être fusionnés.
Un arc peut « boucler » sur un état, et des transitions peuvent partir d'un état final.
Représentation par une table de transitions
La table de transitions est une matrice équivalente à la représentation graphique.
Les lignes représentent les états de l'automate, et les colonnes représentent les symboles terminaux.
Le contenu de la table décrit les transitions entre les états en fonction des symboles lus. Une transition non définie est indiquée par un tiret (-).
Exemple d'un automate fini
Considérons l'automate A = (VT, Q, q₀, δ, F) avec :
- VT = {a, b}.
- Q = {q₀, q₁, q₂}.
- q₀ est l'état initial.
- F = {q₂} est l'état final.
La table de transition est la suivante :
| a | b | |
|---|---|---|
| q₀ | q₁ | - |
| q₁ | q₂ | q₀ |
| q₂ | - | q₂ |
Le langage reconnu par cet automate est :
L(A) = {a(ba)ⁿa / n ∈ ℕ}.
FAQ sur les langages réguliers et automates finis
1. Qu'est-ce qu'un langage régulier ?
Un langage régulier est un ensemble de mots qui peut être défini par une grammaire régulière ou reconnu par un automate d'états finis. Il est caractérisé par des structures simples et répétitives.
2. Comment un automate fini reconnaît-il un langage ?
Un automate fini reconnaît un langage en parcourant les transitions entre ses états selon les symboles du mot d'entrée. Si, après avoir lu tous les symboles, l'automate se trouve dans un état final, le mot est accepté.
3. Pourquoi la fermeture de Kleene est-elle importante pour les langages réguliers ?
La fermeture de Kleene (VT*) permet de générer tous les mots possibles à partir d'un alphabet fini, y compris les répétitions et les combinaisons de symboles. Elle est essentielle pour décrire des langages réguliers complexes.