
\documentclass[a4paper,10pt]{article}

\newtheorem{exercice}{Exercice}

\pagestyle{empty}

\begin{document}
\newcommand{\lra}{\longrightarrow}
\newcommand{\ra}{\rightarrow}
\medskip

\begin{center}
{\large Grammaires et analyse -  Semaine du 7/10/2000}
\end{center}

\begin{center}

{\large Langages alg\'ebriques}\\
\end{center}

\begin{center}

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

\end{center}

\medskip



\begin{exercice}
\rm
Soit $G = (N,\Sigma,P,S)$ la  grammaire donn\'ee par 
$N = \{S,A\}, \Sigma = \{a,b\}$ et
$P = \{S \ra AA, A \ra AAA, A \ra a, A \ra bA, A \ra Ab\}$.
\begin{itemize}
\item Quel sont les mots de $L(G)$ qu'on peut produire avec
des d\'erivations de longueur $4$ ou moins ?
\item Donner au minimum 4 d\'erivations diff\'erentes du mot $babbab$,
\item Pour $m,n,p > 0$ d\'ecrire une d\'erivation dans $G$ du mots
$b^mab^nab^p$.
\end{itemize}
\end{exercice}






\begin{exercice}
\rm
Consid\'erer la grammaire 
\[ S \ra S + S \;|\; S * S \;|\; (S) \;|\; x \;|\; y\]
\begin{itemize}
\item Connaissez vous le langage engendr\'e par cette grammaire ?
\item Consid\'erer le mot $x + y * y$.
Donner deux arbres de d\'erivation diff\'erents pour ce mot.
Quel est celui ``normalement'' pr\'ef\'er\'e ?
\end{itemize}
\end{exercice}


\begin{exercice}
\rm
Montrer que les langages suivants sont alg\'ebriques:
\begin{itemize}
\item $L_1 = \{a^mb^n\;:\; m \leq 2n\}$
\item $L_2 = \{a^mb^n \; : \; m \geq n\}$
\item $L_3 = \{a^mb^nc^pd^q\; : \; m+n = p+q\}$
\item $L_4 = \{uawb \; : \; u,w \in \{a,b\}^*$ et $|u| = |w|\}$
\end{itemize}
\end{exercice}


\begin{exercice}
\rm
Consid\'erer la grammaire
\[ S \ra aSbS \;|\; bSaS \;|\; \epsilon \]
\begin{itemize}
\item Montrer que cette grammaire est ambigu\"e en donnant
deux d\'erivations gauches du mot $abab$.
\item Donner les deux d\'erivations droites correspondantes
\item Donner les deux arbres de d\'erivation correspondants
\item Quel est le langage g\'en\'er\'e par cette grammaire?
\end{itemize}
\end{exercice}


\begin{exercice}
\rm
Montrer que le langage $L = \{w\in \{a,b\}^*: |w|_a=|w|_b\}$ n'est pas
reconnaissable. Meme question avec le langage decrit dans l'exercice
2.
\end{exercice}
\pagebreak
\section*{Correction}
Les 3 premiers exos se resolvent sans preuves.

pour l'exo 3 : L3 je commencerai comme ca :

$S -> S1 | S2$ , avec pour S1 : moins de m que de q, pour S2 plus de m
que de q

je ne vais faire que S1

$S1 -> a S1 d | T1$    on consomme tout les a avec des d, puis dans T1 il n'y aura plus de a

$T1 -> b T1 d \mbox{~(on consomme les b tant qu'il y a des d)~}  | U1 \mbox{~(plus de d)~} $

$U1 -> b U1 c | \epsilon $


c'est  presque pareil pour S2


Pour l'exo 4, 4eme, ce sont les mots qui contiennent autant de a que
de b, faire la preuve.

L'exo 5 va prendre du temps, a defaut rapeller le lemme d'iteration et
le laisser pour la prochaine fois. Peut etre qu'on fera un TD special
non reconnaissable, non algebrique.




Pour l'exo 5 :
le lemme est qq chose du genre :

si L est reconnaissable alors il existe N tel que pour tout mot w de L
de longueur $> N$, on peut decomposer w en $w1.u.w2$, de sorte que
$w1.u$ soit de longueur $< N$, u non nul !!, et tout les $w1.(u^i).w2$
seront aussi dans L. (i est un entier eventuellement nul).

Et on raisonne toujours par l'absurde : on supose L reconnaissable, ce
qui nous permet de supposer N fixe.  On considere un mot du langage,
ici $w=a^N.b^N$ la decomposition du lemme nous donne un u qui n'a que
des a.  on le suprime ou on l'itere (i=0 ou plus de 1) et on a un mot
$w'=a^{N-|u|}.b^{N}$ qui d'apres le lemme doit etre un mot du
langage. Ce qui est absurde si on reprend la definition $->$ il est
faux de dire que L est reconnaissable.

Pour l'autre langage, c'est pareil : les mots doivent etre bien
parentheses, et on pourrait en construire un qui ne le serai pas.

\end{document}









