Table des matières

<= section précedente -\- section suivante =>

Grammaires Générales

Grammaire générale (déf.)

Une grammaire générale est un quadruplet:

  • G=\left(V, \Sigma, R, S\right)
  • V = ensemble de symboles
  • \Sigma \subset V : ensemble de symboles terminaux
  • \left( V \setminus \Sigma \right) : ensemble des symboles non-terminaux
  • s \in\left( V \setminus \Sigma \right) : start symbole
  • R : ensemble des règles, sous-ensemble fini de V^* \left(V\setminus\Sigma\right)V^* \times V^* où V^* \left(V\setminus\Sigma\right) contient au moins 1 symbole non-terminal

Notation

  • \left(u,v\right)\in R se note u\rightarrow_R v
  • u \Rightarrow_{R\;ou\;G} v : passage au contexte
  • u \Rightarrow_G v \Leftrightarrow \exists \omega ,\omega \prime \in V^* t.q.
    • u=\omega\; l\; \omega \prime et \displaystyle f\rightarrow_G r
    • v = \omega\; r\; \omega\prime
  • \Rightarrow^* : fermeture réflexive-transitive de \Rightarrow :
    • \displaystyle L\left(G\right)=\left\{\omega\in\Sigma^* | S\Rightarrow_G^* \omega\right\}
  • \omega_0 \Rightarrow \omega_1 \Rightarrow \ldots \Rightarrow \omega_n : dérivation de longueur n
  • \left(V \setminus \Sigma\right)\rightarrow\left(V \setminus \Sigma\right) V^* ou \Sigma^*
· 2009/10/20 17:03 · Maurice Lanselle

Exemples


Exemple particulier

Quelle est cette grammaire?

\begin{eqnarray} \bar{V} & = & \left\{S,a,b,c,A,B,C,T_a,T_b,T_c\right\} \\ \Sigma & = & \left\{a,b,c\right\} \\ S & = & s \\ R & =\left\{ \right. & S \rightarrow ABCS \\ & & S \rightarrow T_c \\ & & CA \rightarrow AC \\ & & BA \rightarrow AB \\ & & CB \rightarrow BC \\ & & CT_c \rightarrow T_c c\\ & & BCT_c\rightarrow BT_b c \\ & & BT_b\rightarrow T_b b \\ & & ABT_b \rightarrow AT_a b \\ & & AT_a \rightarrow T_a a \\ & & T_a \rightarrow \epsilon \\ & \left.\right\} & \end{eqnarray}

Réponse : Soit L=\left\{a^nb^nc^n | n\in \mathbb{N} \right\} : L \subset L\left(G\right)
Pour le voir, déroulons des dérivations:

\begin{eqnarray} S & \Rightarrow & ABCS \\ & \vdots & \\ & \Rightarrow & \left(ABC\right)^n S \\ & \Rightarrow & \left(ABC\right)^n T_c \\ & \Rightarrow & \left(ABC\right)^{n-1} ABC T_c \\ & \Rightarrow & \left(ABC\right)^{n-1} AB T_c c \\ & \vdots & \\ & \Rightarrow & A^n B^n C^n T_c \\ & \Rightarrow & A^n B^n C^{n-1} T_c c \\ & \vdots & \\ & \Rightarrow & A^n B^n C T_c c^{n-1} \\ & \Rightarrow & A^n B^n T_b c^n \\ \end{eqnarray}

Est-ce que L\left( G\right) \subset L aussi? Des ingrédients de la preuve :

  1. récurrence sur la longueur d'une dérivation
  2. il y a autant de A ou a, B ou b, C ou c dans \omega
  3. il y a au plus 1 T_c , 1 T_b et 1 T_a dans une dérivation de G. Les remplacements se font dans cet ordre.
  4. tous les a sont avant les b qui sont avant les c

Théorème

Tout langage récursivement énumérable est engendré par une grammaire générale.

Preuve

Admis.

Exercice

L=\left\{ a^{n^2} | n \in \mathbb{N} \right\} . Ecrire une grammaire1) que engendre L.

<= section précedente -\- section suivante =>

1) zut! j'ai construit une MT qui le décide au lieu d'une grammaire qui l'engendre!