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

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

\begin{center}
{\large Automates \`a pile}
\end{center}


\begin{center}

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

\end{center}

\medskip



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

\Exo
Soit $M$ l' automate \`a pile donn\'e par\\
$M = (\{q_0,q_1\},\{a,b\},\{Z_0,X\},q_0,Z_0,\emptyset,\delta)$
avec

\begin{quote}
$\delta(q_0,a,Z_0) = \{(q_0,XZ_0)\}, 
 \delta(q_0,a,X) =\{(q_0,XX)\}$,\\
$\delta(q_0,b,X) = \{(q_1,X)\}, 
 \delta(q_0,\epsilon,Z_0) = \{(q_0,\epsilon)\}$\\
$\delta(q_1,a,X) = \{(q_1,\epsilon)\}, 
 \delta(q_1,b,Z_0) = \{(q_0,Z_0)\}$
\end{quote}
\begin{itemize}
\item Est-ce que cet automate est d\'eterministe ?
\item Quel est le langage reconnu par \'etats accepteurs ($L(M)$) ?
\item Quel est le langage reconnu par pile vide ($N(M)$)?
\end{itemize}

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

\Exo Soit $M$ l'automate \`a pile donn\'e par $M =
(Q,\Sigma,\Gamma,q_0,Z_0,F,\delta)$ avec $Q = \{q_0,q_1\}$, $\Sigma
=\{a,b\}$, $\Gamma = \{A,Z_0\}$, $F = \{q_1\}$ et

\begin{quote}
$\delta(q_0,a,Z_0) = \{(q_0,AZ_0)\},
\delta(q_0,b,A) = \{(q_1,AAA)\}$\\
$\delta(q_0,\epsilon,Z_0) = \{(q_1,Z_0)\},\delta(q_1,b,A)=
\{(q_1,\epsilon)\}$
\end{quote}

\begin{itemize}
\item Est-ce que $M$ est d\'eterministe ?
\item Quel est le langage reconnu avec \'etats accepteurs ?
\item Quel est le langage reconnu par pile vide ?
\end{itemize}

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

\Exo

Construire des automates \`a pile et des grammaires qui acceptent les
langages suivants:
\begin{itemize}
\item $\{a^mb^n : m \leq n \leq 2m\}$
\item $\{ w \in \{a,b\}^* : |w|_a=|w|_b\}$
\item $\{ w \in \{a,b\}^* : |w|_a=2|w|_b\}$
\end{itemize}

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

\end{document}
