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

\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
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.
\begin{itemize}
\item Prouver la proposition suivante:

Si $L$ est un langage algebrique, $v,w\in L$  et $v$ est un prefixe de $w$,
alors $v=w$.
\item Pour $i\in N$, soit $L_i=\{a^jb^j\ :\ j\geq i\}$
\begin{itemize}

\item  Quel est l'ensemble $N_{det}=\{ i\ :\  L_i$ est d\'eterministe$\}$.
\item Decrire, en fonction de $j\in N_{det}$, un automate \`a pile
d\'eterministe qui accepte $L_j$.

\end{itemize}
\end{itemize}


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

\Exo
Soit $L_1=\{a^nb^pa^n\ :\ n,p > 0\}$ et $L_2=\{a^nb^pc^p\ :\ n,p > 0\}$.
\begin{itemize}
\item Donner des automates \`a pile pour $L_1$ et $L_2$.
En d\'eduire un automate \`a pile non d\'eterministe pour $L_1\bigcup L_2$.
\item Prouver que la classe des langages accept\'es par des
 APND est ferm\'ee par union (g\'en\'eraliser la construction pr\'ec\'edente).
Ceci est-il vrai pour la classe des langages accept\'es par des APD?
\item Donner un APD qui accepte $L_1\bigcup L_2$.
\end{itemize}

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

\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}

\pagebreak

\Corr 
\begin{itemize}
	\item S'il est deterministe, le calcul de A sur v est unique,
	on arrive a pile vide, alors il n'y a pas de transition
	possible.

	\item On trouve un automate pour $i\geq 2$, puis pour $i=1$.\\
	On utilise des symboles de pile $X_p$ pour $p \in [1..i]$ pour
	reconnaitre les premiers $a$, puis un autre $A$ pour tout les
	$a$ supplementaires. Quand on lis un $b$, on change d'etat, et
	on efface le $A$, puis on continue ou on fait decroitre
	l'indice de $X_p$. Sur $X_1$ avec un $b$ on va en etat
	terminal.\\ Dominique a une solution plus claire, c'est de
	faire des chemin de longueur $i$, si on a le temps on peut
	donc montrer les 2 solutions.

	Il faut montrer qu'il n'y en a pas pour $i=0$, on utilise la propriete
	precedente. On supose $L_0$ deterministe, puisque $\epsilon
	\in L_0$ est prefixe de tout autre $w$ de $L_0$, alors $L_0$
	devrait etre reduit a $\epsilon$, ce qui est absurde.
\end{itemize}

\Corr
\begin{itemize}

\item
\item Non, prendre $\{a\}$ et $\{ab\}$, l'union n'est pas APD d'apres
la propriete de l'exo 1
\item Rq que ca marche parce que $L_1$ fini par $a$, et $L_2$ par
$c$.\\

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{itemize}


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

\end{document}



