%\begin{Exo}
%\end{Exo}

\begin{Cor}\ \\
\begin{Que}
Rappels~:
\begin{description}
\item[null(X) :] les non-terminaux qui engendrent le mot vide.
\item[premier(X) :] les terminaux qui commencent les chaines dérivées de X.
\item[suivant(X) :] les terminaux qui apparaissent à droite de X.
\end{description}

\[
\begin{array}{|lll|c|}
\multicolumn{3}{|c|}{\text{Non terminaux}} & Null(X) \\\hline
S_0 & \Rightarrow & aS\ m & Faux\\
S   & \Rightarrow & TU   & Vrai\\
T   & \Rightarrow & aTb | \epsilon & Vrai\\
U   & \Rightarrow & b | \epsilon & Vrai\\
\end{array}
\]

\[
\begin{array}{c||c|c||c|c||}
 & \multicolumn{2}{c||}{premier(X) : P(X)} & \multicolumn{2}{c||}{suivant(X) : S(X)}\\\hline\hline
S_0 & \{a\}         & \{a\}    & \emptyset                 & \emptyset \\
S  & P(T) \cup P(U) & \{a, b\} & \{m\}                     & \{m\} \\
T  & \{a\}          & \{a\}    & P(U) \cup S(S) \cup \{b\} & \{b, m\} \\
U  & \{b\}          & \{b\}    & S(S)                      & \{m\} \\
\end{array}
\]
\end{Que}

\begin{Que}
Rappel~:\\
$LL(1) \Longleftrightarrow \forall X, X \longrightarrow \alpha | \beta \Rightarrow premier(\alpha suivant(X)) \cap premier(\beta suivant(X)) = \emptyset$

\begin{equation*}
\begin{split}
T : premier(aTb\ suivant(T)) \cap premier(\epsilon\ suivant(T)) & = \{a\} \cap \{b, m\} = \emptyset\\
U : premier(b\ suivant(U)) \cap premier(\epsilon\ suivant(U)) & = \{b\} \cap \{m\} = \emptyset\\
\end{split}
\end{equation*}
La grammaire est donc $LL(1)$.
\end{Que}

\begin{Que}
La table d'analyse~:

\[
\begin{array}{c||c|c|c|}
   &a &b &m \\\hline\hline
So & S \rightarrow aSm &                  & \\\hline
S  & S \rightarrow TU  & S \rightarrow TU & S \rightarrow TU  \\\hline
T  & T \rightarrow aTb & T \rightarrow \epsilon & T \rightarrow \epsilon \\\hline
U  &                   & U \rightarrow b & U \rightarrow \epsilon \\\hline
\end{array}
\]
\end{Que}

\begin{Que}
Le langage engendré~:

\[
\begin{array}{lll}
S_0 & \Rightarrow & a\ S\ m\\
& \Rightarrow & a\ T\ U\ m\\
& \stackrel{*}{\Rightarrow} & a\ (a\ T\ b)^*\ U\ m\\
& \Rightarrow & a\ (a\ b)^*\ U\ m\\
& \Rightarrow & a\ (a\ b)^*\ b\ m \cup a\ (a\ b)^*\ m\\
& \Rightarrow & \{a^{n+1}b^{n+1}m, n \geq 0\} \cup \{a^{n+1}b^nm, n \geq 0\}\\
& \Rightarrow & \{a^{n}b^{n}m, n \geq 1\} \cup \{a^{n+1}b^nm, n \geq 0\}
\end{array}
\]
\end{Que}

\begin{Que}
Une grammaire LL(1) reconnaissant le langage.
\[
\{a^nb^nm, n \geq 0\} \cup \{a^{n+1}b^nm, n \geq 0\} \cup \{a^{n}b^{n+1}m, n \geq 0\}
\]

\[
\begin{array}{lll}
S_0    & \rightarrow & a\ S\ m\ |\ b\ m\ |\ m\\
S      & \rightarrow & T\ U\\
T      & \rightarrow & a\ T\ b\ |\ \epsilon\\
U      & \rightarrow & b\ V\ |\ \epsilon\\
V      & \rightarrow & b\ |\ \epsilon
\end{array}
\]

Explication : la grammaire~:

\[
\begin{array}{lll}
S_0    & \rightarrow & a\ S\ m\\
S      & \rightarrow & T\ U\\
T      & \rightarrow & a\ T\ b\ |\ \epsilon\\
U      & \rightarrow & b\ V\ |\ \epsilon\\
V      & \rightarrow & b\ |\ \epsilon
\end{array}
\]
reconnait $\{a^nb^nm, n \geq 1\} \cup \{a^{n+1}b^nm, n \geq 0\} \cup \{a^{n+1}b^{n+2}m, n \geq 0\}$

Il faut donc ajouter les mots $\{m, bm\}$ ce qui est fait avec $S_0$.
\end{Que}

\end{Cor}

