Automates et langages formels
Fiche de révision compacte sur les objets, équivalences et limites des modèles de reconnaissance.
Alphabets et langages
Vocabulaire de base
- Alphabet Σ
- Ensemble fini de symboles.
- Mot
- Suite finie de lettres de Σ.
- Langage
- Ensemble de mots sur Σ.
Opérations utiles
| Opération | Effet |
|---|---|
| Union | Réunit deux langages. |
| Concaténation | Colle deux mots ou langages. |
| Étoile de Kleene | Répète zéro ou plusieurs fois. |
Expressions régulières
Définition
Une expression régulière décrit un langage par union, concaténation et étoile de Kleene.
À retenir
a*désigne des suites deaquelconques.(ab)*désigneε,ab,abab, etc.
Mémo
Lire de l'intérieur vers l'extérieur évite la plupart des erreurs de priorité.
Automates finis
Comparaison
AFD
- Un seul état suivant par lettre.
- Lecture entièrement déterminée.
- Représentation standard des langages réguliers.
AFN
- Plusieurs transitions possibles.
- Peut avoir des choix ou des ε-transitions.
- Reconnaît les mêmes langages qu'un AFD.
Reconnaissance
- 1
On lit le mot symbole par symbole.
- 2
On suit les transitions autorisées.
Déterminisation
Équivalence et minimisation
Passages possibles
Idée essentielle
- Tout langage régulier admet une expression régulière.
- Tout langage régulier admet un automate fini.
Piège classique
Deux automates peuvent être différents tout en acceptant exactement le même langage.
Grammaires context-free
Définition
Une grammaire context-free réécrit un non-terminal par une suite de symboles.
Caractéristiques
- Elle décrit des structures récursives.
- Elle est plus expressive que les langages réguliers.
Vocabulaire
- Non-terminal
- Symbole réécrivable par une règle.
- Terminal
- Symbole du mot final.
- Production
- Règle de réécriture.
Automate à pile et reconnaissance
Comparaison
Automate fini
- Mémoire limitée à l'état courant.
- Convient aux langages réguliers.
Automate à pile
- Ajoute une pile comme mémoire.
- Reconnaît des langages context-free.
Reconnaissance
- 1
L'automate lit l'entrée symbole par symbole.
- 2
Il utilise la pile pour mémoriser une structure.
Exemple mental
Reconnaître des parenthèses bien formées avec une pile, en supposant que chaque ( est empilée et chaque ) dépile.
- On empile pour chaque ouverture.
- On dépile pour chaque fermeture.
La pile mémorise l'imbrication, donc un automate fini seul ne suffit pas.
Bilan express
Résumé
- Les langages réguliers se décrivent par expressions régulières et automates finis.
- AFD et AFN ont la même puissance expressive.
- La minimisation fournit un AFD canonique pour un langage régulier.
- Les langages context-free demandent une pile et des grammaires dédiées.