\documentclass [a4paper,twoside] {article}

\usepackage {epic,eepic,amstex,amssymb,latexsym,epsfig,delarray,graphics,graphpap,alltt,graphicx}
%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%
\newtheorem {exercice} {Exercice \rm 6.\hspace {-.1cm}}
%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%
\newcommand {\meta} [1] {$\blacklozenge$-\texttt #1}
%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%
\begin{document}

%\headsep=+50pt
%\oddsidemargin=10pt
%\textwidth=430pt
\topmargin=0pt
%\textheight=700pt
\oddsidemargin=+60pt
\evensidemargin=+60pt
%\footskip=+10pt

\title{\textbf {Eléments d' informatique théorique} \\
                  S\'erie 6 \\
         \textsl {Lemme du Pompage et Automates à pile}}
\date {}
\vspace {-100 mm}
\maketitle









\begin{exercice}{\bf }\rm
Dites si les langages suivants sont réguliers ou non. Si vous pensez que non, utilisez le lemme du pompage, si vous pensez 
oui, exhibez un modèle de votre convenance qui engendre, génère ou accepte le langage.
 \begin{enumerate}
  \item Le langage engendré par l'expression régulière $r=1(0+1)^*$.
  \item Le langage sur $\{0,1\}$ définit par $L=\{0^nx\, |\, x\in\ r \text{ et } |x|\geqslant n\}$.
  \item Le langage engendré par la grammaire $\langle \{a,1\} , \{S,Z\}, \{S\rightarrow aSZ\, | \,\epsilon, Z\rightarrow 1\}, S\rangle$.
  \item Le langage sur $\{a,b,c\}$ définit par $L=\{a^nb^mc^p\, |\,n+m=p\}$.
  \item Le langage sur $\Sigma$ définit par $L=\Sigma^* \smallsetminus L$ où $L$ est un langage fini.
  \item Le langage définit par $L=\{ \omega\in\{0,1\}^*\,|\,\omega \text{ est un palindrome}\}$.
  \item Le langage $L$ définit sur $\{a,b\}$ tel que pour tout $\omega\in L$, $\omega$ vérifie
        \begin{itemize}
         \item la valeur absolue de la différence entre le nombre de $a$ et le nombre de $b$ de $\omega$ est 
               strictement inférieure à $4$.
         \item tout préfixe de $\omega$ est dans $L$, c'est-à-dire, $\forall\, \omega_1\omega_2\in L$ alors $\omega_1\in L$.
        \end{itemize}
 \end{enumerate}
\end{exercice}

\begin{exercice}{\bf }\rm
Le langage résultant de l'union d'un langage fini et d'un langage non-régulier est-il régulier? Si vous pensez que oui, donnez 
une démonstration, si vous pensez que non trouver un contre-exemple ou une démonstration. Que dire de l'intersection?
\end{exercice}

\begin{exercice}{\bf }\rm
  Construire les automates à pile acceptant les languages
\begin{enumerate}
 \item $\{  a^n b^{2n} \mid n\geq0\}$.
 \item $L=\{ a^n b^m a^m b^n \mid n,m \geq 1\}$,
 \item $L^*$.
 \item $\{ww^r \mid w \in \{{\rm a},{\rm b}\}^*\}$.
 \item $\{ a^n b^m a^m b^n \mid n,m \geq 1\}$.
 \item les expressions régulières sur l'aphabet $\{ a, b\}$.
\end{enumerate}
\end{exercice}
    
\begin{exercice}{\bf }\rm
Appliquer le lemme de pompage pour prouver que le langage des
expressions régulières sur $\{ a, b\}$ n'est pas régulier. 
\end{exercice}

\begin{exercice}{\bf }\rm
  La grammaire suivante est-elle ambiguë ($I$ représente une
  instruction d'un langage de programmation et $E$ une expression
  booléène) ?
  \begin{eqnarray*}
  \it I &\to& {\bf si\ } E\  {\bf alors\ } I \mid
  {\bf si\ } E\  {\bf alors\ } I\  
                 {\bf sinon\ } I \mid s_1 \mid s_2\mid  \ldots\mid s_n \\
  \it E &\to& e_1 \mid e_2\mid \ldots\mid e_n
  \end{eqnarray*}
\end{exercice}

%\begin{exercice}{\bf }\rm
%  Mettre la grammaire
%  \[
%  (\{A_1,A_2,A_3\},\{ a, b\},P,A_1) \mbox{ où } P=\{A_1\to A_2
%  A_3, A_2 \to A_3A_1\mid{b}, A_3 \to A_1A_2 \mid  a \})
%  \]
%  sous forme normale de Greibach.
%  
%  \medskip\noindent\underline{Indication} : Une production de la forme
%  $A \to A\alpha \mid \beta$ possède une récursion gauche. On peut
%  éliminer cette récursion gauche en ajoutant une nouvelle production
%  \begin{eqnarray*}
%    A & \to & \beta D\\
%    D & \to &\alpha D \mid \epsilon
%  \end{eqnarray*}
%  ou sans utiliser d'$\epsilon$-production
%  \begin{eqnarray*}
%    A & \to & \beta D \mid \beta \\
%    D & \to & \alpha D \mid \alpha
%  \end{eqnarray*}
%\end{exercice}


\end {document}


\begin{center}
\begin{figure}[htbp]
\centering \includegraphics[width=4cm]{Nom de la figure.ps}
\end{figure}
\end{center}

\begin{figure}[ht]
\begin{center}
\input{Nom de la figure.pstex_t}
\end{center}
\caption{Commentaire du dessin.}
\end{figure}
