Grammaire régulière

Un article de Wikipédia, l'encyclopédie libre.
Aller à : navigation, rechercher

En informatique théorique, en théorie des langages, une grammaire régulière, rationnelle ou à états finie 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[modifier | modifier le code]

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[modifier | modifier le code]

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[modifier | modifier le code]

On peut transformer de manière effective une grammaire régulière à droite en automate fini déterministe et vice et versa. Les non-terminaux correspondent aux états de l'automate.

Exemple[modifier | modifier le code]

Considérons la grammaire ci-dessus. L'automate correspondant est le suivant ː

Automate.png

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[modifier | modifier le code]

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[modifier | modifier le code]