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 :

$X\to Ya$

$X\to a$

$X\to ϵ$

où $X$, $Y$ sont des symboles non-terminaux et $a$ un symbole terminal.

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

$X\to aY$

$X\to a$

$X\to ϵ$

où $X$, $Y$ sont des symboles non-terminaux et $a$ un symbole terminal. De plus, comme pour toutes grammaires, on considère un non-terminal particulier appelé axiome et noté $S$.

Exemple

La grammaire suivante est une grammaire régulière à droite :

$S\to dA\mid rB\mid mC\mid ϵ$

$A\to oS$

$B\to eS$

$C\to iS$

Avec la grammaire précédente, on peut engendrer le mot $dodomi$. En effet : $S\to dA\to doS\to dodA\to dodoS\to dodomC\to dodomiS\to dodomi$.

É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 $S\to dA\to doS\to dodA\to dodoS\to dodomC\to dodomiS\to dodomi$ correspond à la lecture du mot $dodomi$ dans l'automate où on passe successivement dans les états : S, A, S, B, S, C, S.

Définition formelle

Soit une grammaire régulière à droite $G=\{N,\mathrm{\Sigma },P,S\}$, alors l'automate $A=\{Q,{\mathrm{\Sigma }}^{\prime },\delta ,Q_0,Q_T\}$ équivalent à G est défini tel que:

• $Q=N\cup \{q_t\}$ avec $Q$ l'ensemble des états et $q_t$ un état puits terminal,
• ${\mathrm{\Sigma }}^{\prime }=\mathrm{\Sigma }$ avec ${\mathrm{\Sigma }}^{\prime }$ l'ensemble des symboles terminaux
• $Q_0=S$ avec $Q_0$ l'état initial
• $\delta \in Q\times \mathrm{\Sigma }\to Q$ est la fonction de transition telle que, à la lecture d'un terminal $x$ à partir d'un état $q_i$ vers un autre état $q_f=\delta (q_i,x)$.

La lecture de $P$ permet de construire $\delta$. Pour chaque $Pi\in P$:

• Si $P_i=X\to aY$ alors on a $\delta (X,a)=Y$
• Si $P_i=X\to a$ alors on a $\delta (X,a)=q_t$
• Si $P_i=X\to ϵ$ alors on a $X\in Q_T$, $Q_T$ 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

• Cours sur les grammaires régulières (avec introduction sur les grammaires en général).