\documentclass[a4paper]{article}
 
\usepackage[latin1]{inputenc}
\usepackage[francais]{babel}
\usepackage{amsmath,amssymb,xspace,a4wide}
 
\pagestyle{empty}
 
\newcounter{comptexo}
\newcommand{\debexo}[1][]{\refstepcounter{comptexo} \medskip
  \noindent{\bf Exercice \arabic{comptexo} : #1}\smallskip\newline\indent }
\newcommand{\finexo}{\medskip}
\newenvironment{exo}{\debexo}{\finexo}
 
\renewcommand{\epsilon}{\varepsilon}
\renewcommand{\leq}{\leqslant}
\renewcommand{\geq}{\geqslant}
 
 
\def\remarque#1{\vskip6pt\par\noindent{\em Remarque : {#1}}\par\vskip6pt}
\def\bar{\,|\,}
 
%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%
\begin{document}
%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%
 
\begin{center}
  {\large Grammaires et analyse -  Semaine du 18/11/2002}\smallskip\\
  {\large Formes Normales}\smallskip\\
  {\small Yan Jurski, Aurelian Lavric, Dominique Poulalhon}
\end{center}
 
%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%
\bigskip
%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%



\section{Forme normale de Chomsky}

On dit qu'une grammaire est sous {\em forme normale de Chomsky\/} (ou
{\em forme normale quadratique\/} si toutes les productions qu'elle
contient sont sous la forme
\[ V\rightarrow WX \]
ou
\[ V\rightarrow a \]
où $V$, $W$, $X$ sont des symboles non-terminaux, et $a$ est un
terminal.

Dans les grammaires suivantes, effectuez la suite de transformations
suivante: élimination des symboles inutiles, élimination des
$\epsilon$-productions, élimination des productions unaires, mise sous
forme normale de Chomsky.

\[
\begin{array}{cccc}
\begin{array}{l}
S\rightarrow aS \bar Sb \bar c\\
\end{array} &
\begin{array}{l}
S\rightarrow A\\
A\rightarrow b\bar c
\end{array} &
\begin{array}{l}
S\rightarrow abcdef
\end{array}
\begin{array}{l}
S\rightarrow aS \bar Ab\\
A\rightarrow cB \\
B\rightarrow dA \bar e
\end{array}&
\end{array}
\]
\[
\begin{array}{cc}
\begin{array}{l}
S\rightarrow aSAb\bar bSS\bar d\\
A\rightarrow cASaA\bar bcd
\end{array}
\begin{array}{l}
S\rightarrow x\bar lSr\bar SpS\bar SmS
\end{array}
\end{array}
\]

\section{Forme normale de Greibach}

Vérifiez que les grammaires suivantes sont sous forme normale de
Chomsky et mettez-les sous forme normale de Greibach.
\[
  \begin{array}{cc}
  \begin{array}{l}
  A_1\rightarrow A_2 A_3\\
  A_2\rightarrow a\bar A_1 A_2\\
  A_3\rightarrow b
  \end{array}
  \begin{array}{l}
  A_1\rightarrow A_2 A_3\\
  A_2\rightarrow a\bar A_1 A_3\\
  A_3\rightarrow b\bar A_2 A_3
  \end{array}
  \begin{array}{l}
  S\rightarrow a\bar AA\\
  A\rightarrow b\bar SS
  \end{array}
  \end{array}
\]


\section{Grammaires linéaires}

Une grammaire est dite {\em linéaire} si dans tout membre droit de
production il y a au plus un symbole non terminal.  Un langage est
linéaire lorsqu'il existe une grammaire linéaire qui l'engendre.

Montrez que le langage $\{a^nb^n\bar n\in\mathbf{N}\}$ est linéaire.
Qu'en est-il du langage $\{u\tilde{u}\bar u\in\{a,b\}^*\}$?

Et des langages reguliers ?

Vérifiez que toutes les transformations vues jusqu'ici (élimination
des symboles inutiles, élimination des $\epsilon$-productions,
élimination des productions unaires) préservent la linéarité.

\remarque{la classe des langages linéaires est close par intersection
et union avec un langage rationnel.  On peut montrer que le langage
$\{a^n b^n c^p d^p\bar n,p\}$ n'est pas linéaire.}


\section{Ambiguité}

On rappelle qu'une grammaire est ambigûe lorsqu'il existe deux arbres
de dérivation distincts pour un mot donné.

\paragraph{1.} Montrez que les grammaires suivantes sont ambigües:
\[
\begin{array}{cc}
\begin{array}{l}
S\rightarrow \epsilon \bar aSb\bar aaSb
\end{array} &
\begin{array}{l}
S\rightarrow x \bar SpS \bar SmS
\end{array}
\end{array}
\]

On dit qu'un langage est {\em intrinsuement ambigu\/} lorsque toute
grammaire qui le génère est ambigüe.

\paragraph{2.} Montrez que l'union de deux langages
non-intrinsèquement ambigus disjoints n'est pas intrinsèquement
ambigüe.

\paragraph{3.} Soit $G$ une grammaire dont toutes les productions
ont la forme
\[ U\rightarrow a\alpha \]
où $a$ est un terminal et $\alpha$ une suite de symboles (terminaux ou
non) telle que dès qu'on a 
\[ U\rightarrow a\alpha \]
et
\[ U\rightarrow a\alpha' \]
alors $\alpha = \alpha'$.  Montrez que $G$ n'est pas ambigüe.

\paragraph{3.} Montrez qu'un langage rationnel n'est pas
intrinsèquement ambigu.


\section{Automates à pile}
Construisez un automate à pile à un seul état qui reconnaît à pile
vide le langage engendré par la grammaire suivante :
\[
S\rightarrow +SS\bar \times SS\bar x
\]
Cet automate est-il déterministe ?

Même question pour les grammaires de l'exercice précédent.

\end{document}