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

\begin{Cor}\ \\
\begin{Que}
Automate fini $\Rightarrow$ Automate fini déterministe.

Puis on applique la construction suivante~:
\begin{enumerate}
\item À l'état initial $q_0$, on associe le non-terminal initial $S_{q_0}$.
\item À chaque état $q_i$, on associe le non-terminal $S_{q_i}$.
\item Puis au choix, soit la construction avec $\epsilon$
\begin{itemize}
\item Aux transitions $(q_i,a,q_j)$, on associe les règles 
$S_{q_i} \rightarrow a\ S_{q_j}$.
\item Pour chaque état terminal $q$, on ajoute les règles
$S_q \rightarrow \epsilon$.
\end{itemize}
soit la construction sans $\epsilon$ (possible si l'état initial n'est pas terminal)
\begin{itemize}
\item Aux transitions $(q_i,a,q_j)$, avec $q_j$ non terminal, on associe les règles $S_{q_i} \rightarrow a\ S_{q_j}$.
\item Aux transitions $(q_i,a,q_j)$, avec $q_j$ terminal, on associe les règles $S_{q_i} \rightarrow a\ S_{q_j}\ |\ a$.
\end{itemize}
\end{enumerate}

\[
\left. \begin{array}{lll}
\text{automate déterministe} & \Rightarrow & \text{grammaire non ambigüe}\\
\text{algorithme de construction} & \Rightarrow & \text{aucune récursivité à gauche}\\
\end{array}
\right\}
 \Rightarrow \text{LL(1)}
\]
\end{Que}

\begin{Que}
Le langage reconnu par la grammaire~:
\[
\begin{array}{lll}
S_0 & \Rightarrow & S\ m\\
& \stackrel{*}{\Rightarrow} & S\ (aa + ba)^*\ m\\
& \Rightarrow & c\ T\ (aa + ba)^*\ m\\
& \stackrel{*}{\Rightarrow} & c\ (a + d)^*\ T\ (aa + ba)^*\ m\\
& \Rightarrow & c\ (a + d)^*\ a\ U\ (aa + ba)^*\ m\\
& \stackrel{*}{\Rightarrow} & c\ (a + d)^*\ a\ b^+\ (aa + ba)^*\ m
\end{array}
\]

Un automate non déterministe reconnaissant le langage.

\begin{figure}[H]
\centering\epsfig{file=exo2nfa.eps}
\caption{Automate reconnaissant $c\ (a + d)^*\ a\ b^+\ (aa + ba)^*\ m$}
\end{figure}

On construit l'automate déterministe.
\[
\begin{array}{c||c|c|c|c|c|}
         & a        & b     & c     & d     & m \\\hline
\{0\}    &          &       & \{1\} &       & \\
\{1\}    & \{1, 2\} &       & \{1\} &       & \\
\{1, 2\} & \{1, 2\} & \{3\} & & \{1\} & \\
\{3\}    & \{4\}    & \{3, 4\} & & & \{6\} \\
\{4\}    & \{5\}    & & & & \\
\{3, 4\} & \{4, 5\} & \{3, 4\} & & & \{6\} \\
\{5\}    & \{4\} & \{4\} & & & \{6\} \\
\{4, 5\} & \{4, 5\} & \{4\} & & & \{6\}
\end{array}
\]

Un automate déterministe reconnaissant le langage.

\begin{figure}[H]
\centering\epsfig{file=exo2dfa.eps}
\caption{Automate reconnaissant $c\ (a + d)^*\ a\ b^+\ (aa + ba)^*\ m$}
\end{figure}


On obtient la grammaire LL(1) reconnaissant le même langage.
\[
\begin{array}{lll}
S_0    & \rightarrow & c\ S_1\\
S_1    & \rightarrow & a\ S_{12}\ |\ d\ S_1 \\
S_{12} & \rightarrow & a\ S_{12}\ |\ b\ S_3\ |\ d\ S_1\\
S_{3}  & \rightarrow & a\ S_4\ |\ b\ S_{34}\ |\ m\\
S_{4}  & \rightarrow & a\ S_5\\
S_{34} & \rightarrow & a\ S_{45}\ |\ b\ S_{34}\ |\ m\\
S_{5}  & \rightarrow & a\ S_{4}\ |\ b\ S_{4}\ |\ m\\
S_{45} & \rightarrow & a\ S_{45}\ |\ b\ S_{4}\ |\ m
\end{array}
\]

\end{Que}
\end{Cor}

