<= section précedente -\- section suivante =>
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
\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.
\Rightarrow^* : fermeture réflexive-transitive de \Rightarrow :
\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^*
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 :
récurrence sur la longueur d'une dérivation
il y a autant de A ou a, B ou b, C ou c dans \omega
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.
tous les a sont avant les b qui sont avant les c
Tout langage récursivement énumérable est engendré par une grammaire générale.
