Grammaire régulière

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

Une grammaire régulière, rationnelle ou à états finie permet de décrire un langage régulier. Bien que les expressions rationnelles soient le modèle de définition le plus courant d'un langage régulier, en particulier dans le domaine des langages de programmation, il ne s'en trouve pas moyen que, techniquement, la reconnaissance d'un mot d'un langage régulier s'effectue par la traduction d'expressions rationnelles en grammaire régulière.

Sommaire

1 Notation
2 Définition
3 Mise en œuvre
- 3.1 Exemple de conversion
4 Liens utiles

[modifier] Notation

Une grammaire régulière se note de la même manière qu'une grammaire hors-contexte:

G = {N,Σ, P, S}

où

N

est le vocabulaire non terminal,

Σ

est le vocabulaire terminal,

P

est l'ensemble des règles de production et $S \in N$ est le non terminal initial.

[modifier] Définition

L'ensemble des grammaires régulières est inclus dans l'ensemble des grammaires hors-contexte. Aussi les règles de production ne doivent comporter aucun symbole terminal dans leur partie gauche.

De plus, les règles de production doivent être de l'une des 2 formes suivantes:

grammaire régulière à droite

$X \rightarrow Ya$

$X \rightarrow a$

$X \rightarrow \epsilon$

grammaire régulière à gauche

$X \rightarrow aY$

$X \rightarrow a$

$X \rightarrow \epsilon$

où $X,Y \in N$ , $a \in \Sigma$ et

ε

est le mot vide.

A la vue des règles de production, on peut en déduire que le principe d'une grammaire régulière est de reconnaitre un mot en partant d'une de ses extrémités et de progresser vers l'autre bout du mot en reconnaissant un seul caractère à la fois.

[modifier] Mise en œuvre

Puisqu'une grammaire dite régulière est également hors-contexte, il est possible de mettre en œuvre une grammaire régulière par le biais d'un automate à pile. Il est cependant plus à propos d'utiliser un automate fini déterministe. La traduction d'une grammaire régulière en un automate est aisée, voire mécanique.

Soit une grammaire régulière à gauche $G = {N,Σ, P, S}$ , alors l'automate $A = {Q,Σ',δ, 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 puit terminal,
$Σ' = Σ$ avec $Σ'$ l'ensemble des symboles terminaux
$Q 0 = S$ avec $Q 0$ l'état initial</math>
$\delta \in Q \times \Sigma \rightarrow 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 = δ(q i, t)$ .

La lecture de

P

permet de construire

δ

. Pour chaque $Pi \in P$ :

Si $P_i = X \rightarrow aY$ alors on a $δ(X, a) = Y$
Si $P_i = X \rightarrow a$ alors on a $δ(X, a) = q t$
Si $P_i = X \rightarrow \epsilon$ alors on a $X \in Q_T$ , $Q T$ L'ensemble des états terminaux.