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

Une grammaire régulière peut être « à gauche » ou « à droite ».

  • Une grammaire régulière à gauche est un ensemble de règles de la forme :

, sont des symboles non-terminaux et un symbole terminal.

  • Une grammaire régulière à droite est un ensemble de règles de la forme :

, 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

La 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

On 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

Considé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, A, S, C, S.

Définition formelle

Soit 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 utiles

  • Portail des mathématiques
Cet article est issu de Wikipedia. Le texte est sous licence Creative Commons - Attribution - Partage dans les Mêmes. Des conditions supplémentaires peuvent s'appliquer aux fichiers multimédias.