Grammaire régulière
En informatique théorique, en théorie des langages, une grammaire régulière, rationnelle ou à états finis est une grammaire hors-contexte particulière qui décrit un langage régulier. Les grammaires régulières donnent donc une autre possibilité que les expressions rationnelles et les automates finis pour décrire un langage régulier.
Définition
modifierUne grammaire régulière peut être « à gauche » ou « à droite ».
- Une grammaire régulière à gauche est un ensemble de règles de la forme :
où , sont des symboles non-terminaux et un symbole terminal.
- Une grammaire régulière à droite est un ensemble de règles de la forme :
où , sont des symboles non-terminaux et un symbole terminal. De plus, comme pour toutes grammaires, on considère un non-terminal particulier appelé axiome et noté .
Exemple
modifierLa grammaire suivante est une grammaire régulière à droite :
Avec la grammaire précédente, on peut engendrer le mot . En effet : .
Équivalence entre automates finis et grammaires régulières
modifierOn peut transformer de manière effective une grammaire régulière à droite en automate fini déterministe et vice versa. Les non-terminaux correspondent aux états de l'automate.
Exemple
modifierConsidérons la grammaire ci-dessus. L'automate correspondant est le suivant :
La suite de dérivations correspond à la lecture du mot dans l'automate où on passe successivement dans les états : S, A, S, B, S, C, S.
Définition formelle
modifierSoit une grammaire régulière à droite , alors l'automate équivalent à G est défini tel que:
- avec l'ensemble des états et un état puits terminal,
- avec l'ensemble des symboles terminaux
- avec l'état initial
- est la fonction de transition telle que, à la lecture d'un terminal à partir d'un état vers un autre état .
La lecture de permet de construire . Pour chaque :
- Si alors on a
- Si alors on a
- Si alors on a , L'ensemble des états terminaux.
Le même type de jeu de règles peut être établi pour une grammaire régulière à gauche.
Liens externes
modifier- Cours sur les grammaires régulières (avec introduction sur les grammaires en général).