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

\documentclass[10pt]{article}
\usepackage{fullpage}
\usepackage[francais]{babel}
\usepackage[latin1]{inputenc}
\usepackage[dvips]{epsfig}


%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%% pour numeroter question et exercices %%%%%%%%
\newcounter{numeroquestion}
\def\Exo{\addtocounter{numeroquestion}{1}
     \vspace{.5cm}\underline{\bf Exercice} \arabic{numeroquestion} :\ }
 
\newcounter{numerocorrection}
\def\Corr{\addtocounter{numerocorrection}{1}
     \vspace{.5cm}\underline{\bf Correction} \arabic{numerocorrection} :\ }

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

\begin{document}

\medskip

\begin{center}
{\large Grammaires et analyse -  Semaine du 14/10/2002}
\end{center}

\begin{center}
{\large  Langages Rationels, Reconnaissables, Algebriques}
\end{center}


\begin{center}

{\small Dominique Poulalhon, Aurelian Lavric , Yan Jurski}

\end{center}

\medskip



\Exo 
Soit $\Sigma = \{a,b\}$. 
Donner une expression rationnelle pour les langages suivants:
\begin{itemize}
\item Tous les mots dans $\Sigma^*$ avec au plus trois $a$,
\item Tous les mots avec exactement une occurrence du facteur $aaa$.
\end{itemize}

\Exo
Donner un automate d\'eterministe qui accepte le langage suivant:
\begin{itemize}
\item $L_1 = \{w \in \{a,b\}^* : $ chaque $b$ dans $w$ est suivi
imm\'ediatement d'un $a\}$
\item $L_2 = \{w \in \{a,b\}^* : $ le nombre de $a$ dans $w$ est divisible
 par $2\}$
\item $L_3 = \{w \in \{a,b\}^* : $ le nombre de $a$ dans $w$ est divisible
 par $3\}$
\end{itemize}

\Exo 
Donner un automate qui reconnaisse les langages algebriques suivant :
\begin{enumerate}

\item 
$ S \rightarrow a.U ~|~ b.S ~|~ e.f.V ~|~ V ~|~ \epsilon$\\
$ U \rightarrow b.S ~|~ e.V ~|~ c.U$\\
$ V \rightarrow f.S ~|~ c $\\

\item
$ S \rightarrow T.a ~|~ \epsilon$\\
$T \rightarrow S.b ~|~ c$\\

\end{enumerate}


\Exo Soit G une grammaire pour un langage L. On note $\tilde{L}$ le
langage constitue des mots de L ecrit de droite a gauche.  Comment
construire une grammaire pour $\tilde{L}$ a partir de G ?


\Exo Comment construire un automate qui reconnait $\tilde{L}$ a partir
d'un automate A qui reconnait L ?

\Exo Vous vous rapellez de la technique pour l'exo 2-1 ? Utilisez les
remarques des exercices 3 et 4 pour construire un automate pour le
langage suivant.

$ S \rightarrow S1 ~|~ S2$\\
$ S1 \rightarrow a.U ~|~ b.V ~|~ c ~|~ d.S1 ~|~ \epsilon$\\
$ U \rightarrow c.S1 ~|~ a.V$\\
$ V \rightarrow a.S1 ~|~ b.U ~|~ c$\\
$ S2 \rightarrow A.a.c ~|~ B.b ~|~ C ~|~ a$\\
$ A \rightarrow S2.a ~|~ S2.b ~|~ B.a$\\
$ B \rightarrow A.a ~|~ b$\\

\Exo Determinisez et minimisez l'automate de l'exercice precedent.

\Exo Nous avons vu que le langage des mots qui ont autant de a que de
b n'est pas reconnaissable. Est-il algebrique ? Si oui donnez en une
grammaire, puis un automate via les techniques precedentes.

\pagebreak

\Corr
\begin{itemize}

\item $b^*~|~b^*.a.b^*~|~b^*.a.b^*.a.b^*~|~|b^*.a.b^*.a.b^*.a.b^*$

\item $((b~|~a.b~|~a.a.b)^* ~|~ \epsilon).a.a.a.((b~|~b.a~|~b.a.a)^*~|~\epsilon) $
\end{itemize}


\Corr


\Corr 2) ne pas repondre de facon automatique, il faut qu'ils
``s'impregnent du Pb''


\Corr chaque regle est remplacee par sa regle miroir. Ainsi, si on a
une derivation, pour w dans L, on montre comment construire la
derivation dans $\tilde{L}$


\Corr on inverse les sens des arcs. Les finaux deviennent initiaux, et
les initiaux finaux. Si ce dernier point pose Pb, introduire un etat
initial, et une $\epsilon$ transition de cet etat vers les etats qu'on
souhaite initiaux.

\Corr On melange des constructions d'automate. Je ne l'ai pas fait.
Au sujet de la determinisation + minimisation je ne les ferais
pas. C'est juste au cas ou on a un Pb de temps.

\Corr Le langage a ete vu au TD1, ca serait trop fort qu'ils cherchent
a trouver un automate. Pour memoire il s'agit de :\\
$ S \rightarrow a.S.b.S~|~b.S.a.S~|~\epsilon$


\end{document}









