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

\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 28/10/2002}
\end{center}

\begin{center}
{\large Automates \`a pile - Langages non reconnaissables}
\end{center}


\begin{center}

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

\end{center}

\medskip
%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%


\Exo Montrer que les langages suivant sont, ou ne sont pas, reconnaissables
\begin{itemize}
\item Les mots de la forme $a^n.b^n$
\item Les mots sur $\{a,b\}$ qui ont autant de $a$ que de $b$
\item Les mots dont la somme du nombre de $a$ et de $b$ est paire
\item Les mots dont la difference entre le nombre de $a$ et de $b$ est paire
\item Les mots dont la difference entre le nombre de $a$ et de $b$ est 2
\end{itemize}


\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 vu dans les TDs
passages de grammaire a automate...


\Exo
Donner un automate \`a pile qui reconna\^{\i}t le langage :
$$ L = \{ a^n b^p a^m \mid n,p,m > 0, 
\quad \mbox{et} \quad (p \leq n \quad \mbox{ou} \quad p \leq m)\}. $$
On pourra donner au choix un automate qui reconna\^{\i}t le langage
par pile vide ou un qui reconna\^{\i}t le langage
par \'etats d'acceptation.

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

\Exo Montrer que les langages suivants sont alg\'ebriques en donnant
une grammaire qui les g\'en\`ere, puis un automate \`a pile :
\begin{itemize}
\item $ L_1 = \{ a^n b^m \mid n \geq 6  \quad \mbox{et} \quad m \geq 2\}. $ 
\item $ L_2 = \mbox{expressions bien parenthes\'ees sur l'alphabet 
contenant les quatre parenth\`eses : (, ), [ et ]} . $

\item $ L_3 = \{ z \in \{a, b\}^* \mid z = xwy  \quad \mbox{avec} \quad
x,w,y \in \{a, b\}^*
\quad \mbox{et} \quad y = \tilde{x}\}. $
\item $ L_4 = \{ a^n b^m c^p  \mid n \leq p \leq n+m\}. $
\item $ L_5 = \{ a^n (b^{m_1}c)(b^{m_2}c)..(b^{m_n}c) \mid n \geq 0 \quad
\mbox{et} \quad \forall i,m_i \geq 0\}. $
\end{itemize}
%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%


\Exo
Un langage algebrique $L$ est {\em d\'eterministe} s'il existe un automate 
\`a pile d\'eterministe qui l'accepte \`a pile vide et \'etat final.

Soit $L_1=\{a^nb^pa^n\ :\ n,p > 0\}$ et $L_2=\{a^nb^pc^p\ :\ n,p > 0\}$.

Donner un APD qui accepte $L_1\bigcup L_2$.

\pagebreak


\Corr 
\begin{itemize}
\item non reconnaissable
\item non reconnaissable
\item reconnaissable
\item c'est le meme
\item non reconnaissable, prendre $a^N.b^{N+2}$
\end{itemize}

\Corr Pas d'erreurs ici, mais il faut leur faire remarquer en rouge la contradiction !
 Le langage a ete vu au TD1. Pour memoire il s'agit de :\\ $ S
\rightarrow a.S.b.S~|~b.S.a.S~|~\epsilon$


\Corr

\Corr

\Corr
Dans un premier etat, on empile un $A$ pour chaque $a$ lu, puis au
premier $b$ on change d'etat, et on empile un $B$ pour chaque $b$
lu. De la, on definit 2 autres etats, ou l'on va en depilant l'un pour
la lecture d'un $c$ disons $(p)$, l'autre pour la lecture d'un $a$,
disons $(q)$. Dans $(p)$, je depile un $B$ pour chaque $c$ lu, et si
la pile presente autre chose, je change d'etat avec un $\epsilon$. De
ce nouvel etat je vide la pile avec des $\epsilon$, puis je vais en
final a pile vide sur $Z0$.\\

Pour $(q)$, je vide tout les $B$ de la pile en lisant des $\epsilon$,
au premier $A$, encore avec un $\epsilon$ je vais en $(q')$ duquel je
consomme les $A$ pour chaque $a$, puis on sort avec $\epsilon,Z0$ dans
un etat final a pile vide.

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


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