Aller au contenu

Grammaire régulière

Un article de Wikipédia, l'encyclopédie libre.

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

[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é .

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 versa. Les non-terminaux correspondent aux états de l'automate.

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, B, 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 externes

[modifier | modifier le code]