\documentclass[a4paper]{article}

\usepackage[latin1]{inputenc}
\usepackage[francais]{babel}
\usepackage{amsmath,amssymb,xspace,a4wide}

\pagestyle{empty}

\newcounter{comptexo}
\newcommand{\debexo}[1][]{\refstepcounter{comptexo} \medskip
  \noindent{\bf Exercice \arabic{comptexo} : #1}\smallskip\newline\indent }
\newcommand{\finexo}{\medskip}
\newenvironment{exo}{\debexo}{\finexo}

\renewcommand{\epsilon}{\varepsilon}
\renewcommand{\leq}{\leqslant}
\renewcommand{\geq}{\geqslant}


\def\remarque#1{\vskip6pt\par\noindent{\em Remarque : {#1}}\par\vskip6pt}
\def\bar{\,|\,}

%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%
\begin{document}
%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%

\begin{center}
  {\large Grammaires et analyse -  Semaine du 18/11/2002}\smallskip\\
  {\large Réductions de grammaires}\smallskip\\
  {\small Yan Jurski, Aurelian Lavric, Dominique Poulalhon}
\end{center}

%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%
\bigskip
%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%
 


%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%
\section{Élimination des symboles inutiles}
%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%

\begin{exo}
  Dans chacune des grammaires suivantes, quels symboles ne sont pas
  co-accessibles?
\[
  \begin{array}{ccccc}
    \begin{array}{l}
      S\rightarrow aS \bar Sb
    \end{array} &
    \begin{array}{l}
      S\rightarrow aS \bar Sb \bar c\\
    \end{array} &
    \begin{array}{l}
      S\rightarrow aS \bar Sb \bar A
    \end{array} &
    \begin{array}{l}
      S\rightarrow aS \bar Ab\\
      A\rightarrow cB \\
      B\rightarrow dA
    \end{array}&
    \begin{array}{l}
      S\rightarrow aS \bar Ab\\
      A\rightarrow cB \\
      B\rightarrow dA \bar e
    \end{array}\\
    \mbox{(a)} & \mbox{(b)} & \mbox{(c)} & \mbox{(d)} & \mbox{(e)}
  \end{array}
\]
\end{exo}

%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%

\begin{exo}
  Dans chacune des grammaires suivantes, quels symboles ne sont pas
  accessibles?
\[
  \begin{array}{cccc}
    \begin{array}{l}
      S\rightarrow b
    \end{array} &
    \begin{array}{l}
      S\rightarrow a \bar bS\\
      A\rightarrow c\bar dA
    \end{array} &
    \begin{array}{l}
      S\rightarrow a \bar bS \bar aA\\
      A\rightarrow c\bar dA
    \end{array} &
    \begin{array}{l}
      S\rightarrow a\bar Sa\\
      A\rightarrow bB\bar c\\
      B\rightarrow Aa\bar aB\bar a
    \end{array}\\
    \mbox{(a)} & \mbox{(b)} & \mbox{(c)} & \mbox{(d)}
  \end{array}
\]
\end{exo}

%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%

\begin{exo}
  On considère maintenant la grammaire $G$ suivante:
\[
  \begin{array}{l}
    S \rightarrow AB \bar CA \bar BD\\
    B \rightarrow BC \bar AB\\
    A \rightarrow a\\
    C \rightarrow aB \bar b\\
    D \rightarrow d 
  \end{array}
\]

\begin{enumerate}
\item
  Déterminez les variables non co-accessibles de $G$, et éliminez les
  productions qui en contiennent; on notera $G_1$ la grammaire ainsi
  obtenue.

  Déterminez ensuite les variables non accessibles de $G_1$, et
  éliminez toutes les productions de $G_1$ qui en contiennent; on
  notera $G_2$ la grammaire ainsi obtenue.
\item
  Déterminez les variables non accessibles de $G$, et éliminez les
  productions correspondantes; on notera $G'_1$ la grammaire ainsi
  obtenue. 

  Déterminez ensuite les variables non co-accessibles de $G'_1$, et
  éliminez toutes les productions de $G'_1$ qui en contiennent; on
  notera $G'_2$ la grammaire ainsi obtenue.
\item
  Comparez les grammaires $G_2$ et $G'_2$.  Conclusion?
\end{enumerate}
\end{exo}


%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%
\section{Élimination des $\epsilon$-productions}
%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%

\begin{exo}
  On considère la grammaire suivante:
\[
  \begin{array}{l}
    S\rightarrow aA\bar bB\\
    A\rightarrow BC \bar BD \bar EE \bar BDE \\
    B\rightarrow \epsilon \bar aB \bar D \\
    C\rightarrow cD \bar dE \\
    D\rightarrow c\bar dE \bar BB \\
    E\rightarrow \epsilon \bar aE \bar Eb
  \end{array} 
\]
  Déterminez les symboles effaçables de cette grammaire; le langage
  défini contient-il le mot vide?  Construisez la grammaire obtenue à
  partir de la grammaire précédente après élimination des
  $\epsilon$-productions.
\end{exo}

%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%

\begin{exo}
  Mêmes questions pour la grammaire suivante:
\[ 
  \begin{array}{l}
    S\rightarrow ABA \bar BAB \\
    A \rightarrow \epsilon \bar aA \\
    B \rightarrow \epsilon \bar Bb
  \end{array} 
\]
\end{exo}


%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%
\section{Élimination des productions unaires}
%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%

\begin{exo}
  Éliminez les productions unaires dans la grammaire suivante:
\[ 
  \begin{array}{l}
    S\rightarrow aS \bar bAb \bar B\\
    A\rightarrow cA \bar B \\
    B\rightarrow b \bar Ab
  \end{array} 
\]
\end{exo}

%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%
\section{Instructions conditionnelles}
%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%

\begin{exo}
  On considère les deux grammaires suivantes:
\[
  \begin{array}{cc}
    \begin{array}{l}
      S\rightarrow s \bar ixtSeS \bar ixtS
    \end{array} &
    \begin{array}{l}
      S\rightarrow s \bar ixtAeS\bar ixtS \\
      A\rightarrow s \bar ixtAeA
    \end{array}\\
    \mbox{(a)} & \mbox{(b)}
  \end{array}
\]

\begin{enumerate}
\item
  Montrez que la grammaire (a) est ambiguë.  Qu'en est-il
  de la grammaire (b)?
\item
  Montrez que les grammaires (a) et (b) définissent le même langage
  $\cal L$.  Ce langage est-il rationnel?  Est-il déterministe?
\item
  La grammaire suivante est-elle ambiguë?  Le langage défini est-il
  déterministe?
\[
  \begin{array}{c}
    \begin{array}{l}
      S \rightarrow s \bar ixtSeSf \bar ixtSf
    \end{array}
  \end{array}
\]
\end{enumerate}
\end{exo}



%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%
%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%
\end{document}
%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%
%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%






