\documentstyle{amsart}

\textheight 250mm
\textwidth 180mm
\hoffset -32mm
\voffset -24mm
\begin{document}
\noindent
\begin{tabular}{l c r}
\hline
Institut Galil\'ee - Universit\'e Paris 13  & \hskip 7cm \quad & Th\'eorie des langages \\
DEUG MIAS 2\`eme ann\'ee     & \hskip 8cm \quad  & 24 mars 2000\\
\hline
\end{tabular}


\begin{center}\Huge
Devoir \`a la maison \`a rendre le 7 avril\\
\end{center}


Sauf quand cela vous est explicitement demand\'e, ne faites pas de preuves, donnez simplement la r\'eponse.\\
Par ailleurs, on adopte les conventions suivantes :\\
le mot vide est not\'e $\epsilon$ ;
l'alphabet de r\'ef\'erence est not\'e $\Sigma$ (sigma) ;
les non-terminaux sont \'ecrits en majuscule ;
les terminaux sont \'ecrits en minuscule.


Merci d'indiquer, en face de chaque question, combien de temps vous y avez consacr\'e. Cela ne modifiera en rien votre note, c'est simplement pour me donner une id\'ee du temps qu'un \'el\`eve passe en moyenne \`a tel ou tel type de question avant de r\'eussir (ou pas~!) \`a y r\'epondre.


En cas de probl\`eme dans l'\'enonc\'e, vous pouvez me contacter \`a 
Cyril.Banderier@@inria.fr.




\section{Mono\"{\i}des}

\subsection{} Rappelez la d\'efinition d'un mono\"{\i}de.

\subsection{} ``Moralement'', qu'est-ce qu'un mono\"{\i}de libre ?
% C'est un mono\"{\i}de pour lequel on a une "base", i.e. un ensemble d'\'el\'ements sans relation entre eux (ils sont libres) et qui engendrent le mono\"{\i}de (ils sont g\'en\'erateurs).

\subsection{} Donnez un exemple de mono\"{\i}de libre et d'un mono\"{\i}de non libre.

\subsection{} L'\'etoile d'un langage $\cal L$ est d\'efinie par $L^*=\cup_{n\geq 0} U^n.$
Donnez tous les mots de longueur $<10$ de $\{ab,b\}^*$.

\section{Grammaires}

Pour les questions suivantes, on travaille avec l'alphabet $\Sigma=\{a,b\}$. 

\subsection{} Pour chacun des langages $L_i$ suivants, donnez une grammaire $G_i$ qui le reconnaisse.\\
$L_1$=\{les mots ne contenant pas deux $a$ cons\'ecutifs\} ;\\
% S-UV    U-bU|e     V-aBV|\epsilon    B-bB|b   b*(ab+)*
$L_2$=\{les mots contenant autant de $a$ que de $b$\} ;\\
%S- aSb |bSa| \e[silon        Non r\'egulier Sg non rationnelle
$L_3$ =\{les mots ne contenant que des $a$ (au moins un) puis que des $b$ (au moins un)\} ;\\
%S\rightarrowaA|bB \qquad A\rightarrow aA|\epsilon B \rightarrow bB|\epsilon R\'egulier a+b+
$L_4$=\{les mots ne contenant que des $a$  puis que des $b$, avec
``nombre de $b$'' $>$ ``nombre de $a$'' $> 0$\} ;\\
% S \rightarrow aSb |bS |\epsilon
%Pas r\'egulier Lemme \'etoile
$L_5$=\{les mots dont la parit\'e du nombre de $a$ \'egale celle du nombre de $b$\}\\
(par exemple $ababaa \in L_5, bbba\in L_5$ mais $bba \not \in L_5$ et $ababa \not \in L_5$).
% S- SaSbS| SbSaS | SaSaS |SbSbS |\epsilon

\subsection{} Deux des langages sont r\'eguliers, lesquels ? Donnez une grammaire {\em r\'eguli\`ere} pour chacun de ces deux langages. 

\subsection{} Prouvez \`a l'aide du lemme de l'\'etoile  qu'au moins 
l'un des langages ci-dessus n'est pas r\'egulier. 


\section{Expressions r\'eguli\`eres}

Une {\em expression r\'eguli\`ere} est une fa\c con de coder sous forme compacte un langage r\'egulier, en n'utilisant que
${}^*$ (pour l'\'etoile), $+$ (pour l'union), $-$ (pour la diff\'erence), le parenth\'esage et les lettres de l'alphabet.\\
$(a+b)$ d\'esigne ainsi l'union de $\{a\}$ et $\{b\}$, c'est-\`a-dire $\{a,b\}$\\
$(a+b)^*$ d\'esigne ainsi l'\'etoile de $\{a,b\}$, c'est-\`a-dire $\{a,b\}^*$, tous les mots du langage. 



\subsection{} Construisez un automate qui reconnaisse l'expression
r\'eguli\`ere $(a^* b^*)^*b + (ba)^*$. 

\subsection{} Quel est le langage reconnu par l'automate suivant~?
(Donnez la r\'eponse sous la forme d'une expression r\'eguli\`ere.)

\vskip 5cm

\subsection{} Donnez (sous forme d'une expression r\'eguli\`ere) le
langage engendr\'e par la grammaire suivante~:\\
$A\rightarrow aBb|aC|\epsilon$ \qquad $B\rightarrow Ab|a$ \qquad
$C\rightarrow bC|A$ \quad  (avec $A$ comme axiome).\\
 Donnez un arbre de d\'erivation de $aabbb$.
La grammaire est-elle ambig\"ue~?

\section{Automates}

\subsection{} Donner un automate qui engendre le m\^eme langage que
l'automate de la question 3.2, mais dont tous les \'etats soient accessibles.

\subsection{} D\'eterminisez ce nouvel automate.

\subsection{} Minimisez ce dernier automate (c'est-\`a-dire donnez un automate [pas forc\'ement d\'eterministe] qui reconnaisse le m\^eme langage mais qui a le moins d'\'etats possibles). 


\section{Analyse et th\'eorie des langages}
Soit $\cal L$ un langage et notons $\ell_n$ le nombres de mots de $\cal L$ longueur $n$.
Consid\'erons maintenant la s\'erie $L(z)$ (dite ``s\'erie
g\'en\'eratrice du langage 
$\cal L$'') 
$$L(z)= \sum_{n\geq 0} \ell_n z^n .$$

Un th\'eor\`eme du \`a Noam Chomsky et Marcel-Paul Sch\"utzenberger (1963) dit que\\ 
$\bullet$ si $\cal L$ est un langage r\'egulier alors $L(z)$ est une fraction rationnelle, \\
$\bullet$ si $\cal L$ est engendr\'e par une grammaire alors $L(z)$ est alg\'ebrique.

Rappelons qu'une fraction rationnelle est un quotient de deux polyn\^omes
et qu'une fonction $f$ est dite alg\'ebrique si elle peut \^etre annul\'ee par un polyn\^ome
(il existe une relation du genre $f(z)^{27}-456 f(z)^{13} +4/6 f(z) -1 =0$ ).

En compl\'ement du th\'eor\`eme, on a m\^eme une m\'ethode pour
trouver 
``explicitement'' $L(z)$ : 
si la grammaire est non-ambig\"ue, la transformation suivante
\begin{center}
\begin{tabular}{l c l}
$S\rightarrow aSbScS | dB | ac | \epsilon$ & $\Rightarrow$ & $S(z) = z^3 S(z)
^3 + z B(z) +z^2+1$\\
$B\rightarrow aBBc |  \epsilon$  & $\Rightarrow$ & $B(z) = z^2 B(z) ^2 +1$
\end{tabular}\end{center}
donne un syst\`eme d'\'equations  qui, si on le r\'esout, fournit une
formule pour $S(z)=L(z)$.


\subsection{} Une s\'equence de $n$ tirs \`a pile ou face donne $2^n$
mots de longueur $n$ possibles (codons ``pile face pile'' par ``010'',
etc.). Donner une expression {\em simple} de la s\'erie g\'en\'eratrice
$L(z)$ du langage $\cal L$ ``suites des tirs \`a pile 
ou face''.

Observation : puisque le langage peut \^etre engendr\'e par la
grammaire r\'eguliere 
$S \rightarrow 0S | 1S | \epsilon$, votre r\'esultat doit \^etre coh\'erent avec le th\'eor\`eme et vous devez obtenir une fraction rationnelle. 

\subsection{} Sur un quadrillage avec un rep\`ere, on part du point
$(0,0)$, puis on fait soit des pas $(+1,+1)$ montants en diagonale, ou
$(-1,-1)$ descendants en diagonale. On s'int\'eresse aux chemins
partant de (0,0) et atteignant au final l'axe $y=0$ sans jamais passer
en-dessous. En codant par $a$ les pas montants et par $b$ les pas descendants, les premiers chemins valides sont donc : $\epsilon, ab, abab, aabb, ababab, aabbab, abaabb, aababb$...
Les mots possibles sont appel\'es ``mots de Dyck'' ou encore ``chemins
de Dyck''.

\vskip 3cm

Trouvez une grammaire (non-ambig\"ue) qui engendre les mots
de Dyck, puis, en utilisant la m\'ethode de Sch\"utzenberger, donnez une expression
simple de la s\'erie g\'en\'eratrice $L(z)$ du langage $\cal L$ des mots de Dyck.
Quel est le rayon de convergence de cette s\'erie ?
Qu'en concluez-vous ? (penser au lien entre coefficients et rayon de convergence).


\subsection{} Prouvez \`a l'aide du th\'eor\`eme de
Chomsky-Sch\"utzenberger qu'un langage de la question 2.1 n'est pas r\'egulier.



\section{Automates et cha\^{\i}nes de Markov}
Une cha\^{\i}ne de Markov est un automate dont les transitions sont
``probabilis\'ees''.
\subsection{}
Dessinez la  cha\^{\i}ne de Markov qui correspond au jeu suivant~:
on tire \`a pile ou face et on s'arr\^ete (\'etat final~!) quand on a
obtenu  ``PPP''. 

\subsection{} Idem avec ``PFP''. Qu'en concluez-vous~?


\section{Compilation}

Pour chacune des phases suivantes, dire en une courte phrase en quoi
elle consiste : analyse lexicale,
analyse syntaxique,
analyse s\'emantique,
optimisation,
g\'en\'eration de code,
ex\'ecution.

\end{document}