\documentclass{scrartcl}
\usepackage[margin=1in, left=0.5in, right=0.5in]{geometry}
\usepackage[utf8]{inputenc}
\usepackage[francais]{babel}
\usepackage{amsmath}
\usepackage{amsfonts}
\usepackage{amssymb}
\usepackage{amsthm}
\usepackage{fancyhdr}
\usepackage{mathtools}
\fancyhead[R]{\textsc{Langage formels, calculabilité et complexité}}
\fancyhead[L]{TD5} % except the center
\fancyfoot{} % except the center
\fancyfoot[L]{louis.jachiet@ens.fr}
\fancyfoot[C]{https://louis.jachiet.com/tps.html}
\fancyfoot[R]{26 octobre 2017}
\newcommand{\A}{\mathcal{A}}
\newcommand{\Q}{\mathcal{Q}}
\newcommand{\B}{\mathcal{B}}
\newcommand{\X}{\mathcal{X}}
\newcommand{\I}{\mathcal{I}}
\newcommand{\F}{\mathcal{F}}
\newcommand{\R}{\mathcal{R}}
\newcommand{\Ls}{{\mathcal{L}_\Sigma}}
\newcommand{\Lc}{{\mathcal{L}}}
\newcommand{\ml}{\mu_{\mathcal{L}}}
\newcommand{\Mn}{M_n(\Ls)}
\newcommand{\Vn}{{M_{n,1}(\Ls)}}
\newcommand{\td}{\tilde{\delta}}
\newcommand{\norm}[1]{\left\lvert#1\right\rvert}
\renewcommand{\headrulewidth}{0.4pt}
\renewcommand{\footrulewidth}{0.4pt}
\usepackage{exsheets}[2014/09/14] % v0.16 or newer
\SetupExSheets{
  headings = runin ,
  headings-format = \large\bfseries\sffamily ,
  subtitle-format = \large\bfseries\sffamily ,
%  counter-within = section ,
%  counter-format = se.qu\IfQuestionSubtitleT{:} ,
%solution/print = true
}
\newtheorem{defi}{Definition}

\newcommand\myeq{\stackrel{\mathclap{\normalfont\mbox{def}}}{=}}

\newcommand*\fo[1]{\tikz[baseline=(char.base)]{
                \node[shape=circle,draw,inner sep=2pt] (char) {#1};}}
\usepackage{tikz}
\usetikzlibrary{automata,positioning,trees}

\author{}
%\date{}
\title{TD5 : Langages formels, calculabilité et complexité}

\begin{document}
\pagestyle{fancy}


\section{Grammaires non contextuelles}


\begin{question}
  Considérons la grammaire suivante sur l'alphabet $\{x,y,+,-,*\}$:
$$ E \rightarrow + EE \mid * EE \mid - EE \mid x \mid y$$

  \begin{enumerate}
    \item Trouver les dérivations gauches (\emph{leftmost}) et droites
      (\emph{rightmost}) ainsi qu'un arbre de dérivation pour la
      chaîne $+*-xyxy$.

    \item Prouver que cette grammaire est non-ambiguë.

    \item Trouver un automate à pile pour cette grammaire.
  \end{enumerate}
\end{question}

\begin{solution}

Voici les dérivations gauche et droite avec l'arbre induit noté par
des parenthèses :
  
  \[
  \begin{array}{cccccccccccccccccccccccccccc}
    E & \rightarrow &
    +EE & \rightarrow &
    +(*EE)E & \rightarrow &
    +(*(-EE)E)E \\ & \rightarrow &
    +(*(-xE)E)E & \rightarrow &
    +(*(-xy)E)E & \rightarrow &
    +(*(-xy)x)E \\ & \rightarrow &
    +(*(-xy)x)y \\
    \\
    E & \rightarrow &
    +EE & \rightarrow &
    +Ey & \rightarrow &
    +(*EE)y \\ & \rightarrow &
    +(*Ex)y & \rightarrow &
    +(*(-EE)x)y & \rightarrow &
    +(*(-Ey)x)y\\ & \rightarrow &
    +(*(-xy)x)y
  \end{array}
  \]

Si la grammaire est ambiguë alors il existe deux dérivations
gauches. Mais toutes les règles transformant $E$ insèrent un symbole
terminal à gauche et toutes les règles ont des symboles différents
donc les dérivations gauches sont forcées par la chaîne à atteindre
(et donc la $i$-ème dérivation est $E\rightarrow \lambda EE$ si
$\lambda\in\{+,-,*\}$ est le $i$-ème caractère ou $E\rightarrow z$ si
$z\in\{x,y\}$ est le $i$-ème caractère).


Notre automate est
$(\{E,OK\},\{+,*,-,x,y\},\{\epsilon,E\},\delta,E,\epsilon,\{OK\})$
avec pour $\lambda\in \{+,*,-\}$ et $z\in\{x,y\}$ on a
$\delta(E,\lambda,S)=(E,SE)$, $\delta(E,z,E)=(E,\epsilon)$,
$\delta(E,z,\epsilon)=(OK,\epsilon)$.

\end{solution}

\begin{question}
En utilisant le lemme d'Ogden ou le lemme de pompage, montrer que les
langages suivants ne sont pas algébriques~:
\begin{enumerate}
\item $\Lc_0 = \{ a^i b^j c^k \mid i<j<k \}$  
\item $\Lc_1 = \{ a^n b^n c^m \mid n \leq m \leq 2n \}$  
\item $\Lc_2 = \{ a^{2^n} \mid n\in\mathbb{N} \}$  
\item $\Lc_3 = \{ a^{n^2} \mid n\in\mathbb{N} \}$  
\end{enumerate}
\end{question}

\begin{solution}
  Soit $n$ de pompage, on a :
\begin{enumerate}
\item $u=a^nb^{n+1}c^{n+2} \in \Lc_0$ donc on peut décomposer en
  $u=xvywz$ tel que $xw^iyw^iz$ est dans le langage pour tout $i$ avec
  $|vw|\geq 1$.

  Comme c'est vrai pour $i=0$ on a $vw$ qui contient plus de $a$ que
  de $b$ que de $c$ mais comme c'est vrai pour $i=2$ on a que $vw$
  contient plus de $c$ que de $b$ que $a$ donc $vw$ en contient autant
  de chaque et au moins un mais $v$ et $w$ ne peuvent chacun contenir
  qu'une lettre (sinon le motif $a^*b^*c^*$ est brisé).

\item $a^nb^nc^{2n}\in \Lc_1$ peut être décomposé en $u=xvywz$ avec
  $xv^iyw^iz$ dans le langage avec $|vw|\geq 1$ mais alors les $v$ et
  $w$ ne peut contenir qu'une lettre (sinon le motif $a^*b^*c^*$).
  selon $v$ et $w$ on voit que le ratio entre $a$, $b$ et $c$ va être
  brisé pour $i=2n$.

\item $a^{2^n}\in\Lc_2$ donc on a comme pour le cas rationnel
  $u=xvywz$ et $xv^iyw^iz$ dans le langage donc $a^{2^n+i\times k}$
  dans le langage pour tout $i$ et $k> 0$ ce qui est contradictoire
  car les puissances de deux ne sont pas séparés de $k$.

\item $a^{n^2}\in\Lc_2$ donc on a comme pour le cas rationnel
  $u=xvywz$ et $xv^iyw^iz$ dans le langage donc $a^{n^2+i\times k}$
  dans le langage pour tout $i$ et $k> 0$ ce qui est contradictoire
  car les carrés sont séparés d'un nombre qui tend vers l'infini.

  
\end{enumerate}
\end{solution}



\section{Forme Normale de Chomsky (CNF)}

\begin{defi}
  On rappelle qu'une grammaire est sous forme normale de Chomsky quand
  toutes ses productions sont de la forme :
  \[
  \begin{array}{lcccr}
    A\rightarrow BC & \mbox{ ou } & A\rightarrow a& \mbox{ ou } & S\rightarrow \epsilon
  \end{array}
  \]
avec $B\neq S$ et $C\neq S$ où $S$ est le symbole initial.
\end{defi}

\begin{question}
  Soit $G=(\Sigma,N,P,S)$ un grammaire algébrique. On suppose que $S$
  n'apparaît jamais à droite d'une règle de production, comment
  éliminer toutes les transitions $A\rightarrow \epsilon$ (sauf
  éventuellement $S\rightarrow \epsilon$) d'une grammaire ?
\end{question}

\begin{solution}
  On calcule jusqu'à atteindre un point fixe l'ensemble
  $\mathcal{E}_{n}=\mathcal{E}_n\cup\{ A \mid A\rightarrow \epsilon
  \in P_n\}$ où $\mathcal{E}_0=\emptyset$, $P_0=P$ où l'on a gardé que
  les règles sans symboles non-terminaux et $P_{n+1}=P_n$ où on a
  remplacé dans les règles de production de $P_n$ les symboles de
  $\mathcal{E}_n$ par $\epsilon$.

  On ajoute alors pour chaque règle $A\rightarrow \alpha_1 \dots
  \alpha_n$ toutes les règles obtenables en supprimant des
  $\alpha_i\in \mathcal{E}$ puis enfin on supprime toutes les règles
  de production d'$\epsilon$ sauf éventuellement $S\rightarrow
  \epsilon$.
\end{solution}

\begin{question}
  Proposer des règles pour transformer les productions suivantes en
  CNF (on suppose que $S$ n'apparaît pas) :
  \begin{enumerate}
    \item $A\rightarrow bC$
    \item $A\rightarrow Bc$
    \item $A\rightarrow bc$
    \item $A\rightarrow BCD$
    \item $A\rightarrow \alpha_1\alpha_2\alpha_3$ avec $\alpha_i\in \Sigma \cup N$
    \item $A\rightarrow \alpha_1\dots\alpha_p$ avec $p\geq 3$
    \item $A\rightarrow B$
  \end{enumerate}
\end{question}

\begin{solution}
  \begin{enumerate}
  \item Pour $A\rightarrow bC$ on introduit un nouvel symbole $B$ et
      notre règle devient $A\rightarrow BC$ et $B\rightarrow b$;
    \item pour $A\rightarrow Bc$ de même, on introduit $C$ et notre
      règle devient  $A\rightarrow BC$ et $C\rightarrow c$;
    \item pour $A\rightarrow bc$ on introduit $B$ et $C$ et notre
      règle devient $A\rightarrow BC$, $B\rightarrow b$ et
      $C\rightarrow c$;
    \item pour $A\rightarrow BCD$ on introduit $E$ et notre règle devient
      $A\rightarrow BE$ et $E\rightarrow CD$;
    \item pour $A\rightarrow \alpha_1\alpha_2\alpha_3$ avec
      $\alpha_i\in \Sigma \cup N$ on introduit $B$ puis $A\rightarrow
      \alpha_1 B$ et $B\rightarrow \alpha_2 \alpha_3$ et on selon les
      cas on ré-applique les règles plus-haut;
    \item $A\rightarrow \alpha_1\dots\alpha_p$ avec $p\geq 3$ on
      introduit $B$ et on remplace la règle par $A\rightarrow \alpha_1
      B$ et $B\rightarrow \alpha_2\dots \alpha_p$ puis on procède par
      récurrence sur $B$.
  \item Pour $A\rightarrow B$ on ajoute des règles, pour chaque règle
    $X\rightarrow AA$ on ajoute $X\rightarrow AB$,$X\rightarrow BA$
    et$X\rightarrow BB$, pour chaque règle $X\rightarrow AZ$ on ajoute
    $X\rightarrow BZ$, pour chaque règle $X\rightarrow AZ$ on ajoute
    $X\rightarrow ZB$ puis on supprime $A\rightarrow B$.
  \end{enumerate}

\end{solution}

\begin{question}
  Proposer une grammaire CNF équivalente à la grammaire suivante :

  \[
  \begin{array}{rcrcl}
    S &~~ \rightarrow ~~& CSC & \mid & aB \\
    C & \rightarrow & B & \mid & S \\
    B & \rightarrow & b & \mid & \epsilon \\

  \end{array}
  \]
    
\end{question}

\begin{solution}
D'abord on ajoute un symbole initial $S_0\rightarrow S$ et on élimine
les règles à trois membres à droite :

  \[
  \begin{array}{rclcrcl}
    S_0 & \rightarrow & CD \mid aB &\hspace{6em} &
    D & \rightarrow & SC \\
    S & \rightarrow & CD \mid AB  &\hspace{6em} &
    C & \rightarrow & B \mid S  \\
    B & \rightarrow & b \mid \epsilon &&
    A & \rightarrow & a  \\
  \end{array}
  \]  

  Ensuite on note que le non terminal $C$ se transforme en $\epsilon$,
  alors $S\rightarrow D$ et $D\rightarrow S$ et donc on remplace $D$
  en $S$ :

  \[
  \begin{array}{rclcrcl}
    S_0 & \rightarrow & CS \mid AB \mid SB &\hspace{6em} &
    S & \rightarrow & SC \\
    S & \rightarrow & CS \mid AB  &\hspace{6em} &
    C & \rightarrow & B \mid S  \\
    B & \rightarrow & b \mid \epsilon &&
    A & \rightarrow & a  \\
  \end{array}
  \]  

  On élimine le non-terminal $C$ en le remplaçant par ses
  deux possibles productions~:
  
  \[
  \begin{array}{rclcrcl}
    S_0 & \rightarrow & SS \mid BS \mid AB \mid SB &\hspace{6em} &
    S & \rightarrow &  SS \mid BS \mid AB \mid SB \\
    B & \rightarrow & b \mid \epsilon &&
    A & \rightarrow & a  \\
  \end{array}
  \]  

On élimine $B\rightarrow \epsilon$ :
  \[
  \begin{array}{rclcrcl}
    S_0 & \rightarrow & S &\hspace{6em} &
    S & \rightarrow &  SS \mid BS \mid AB \mid SB \mid A \\
    B & \rightarrow & b &&
    A & \rightarrow & a  \\
  \end{array}
  \]  

On élimine $S\rightarrow A$ (en utilisant $A\rightarrow a$):
  \[
  \begin{array}{rclcrcl}
    S_0 & \rightarrow & S &\hspace{6em} &
    S & \rightarrow &  SS \mid BS \mid AB \mid SB \mid a \\
    B & \rightarrow & b &&
    A & \rightarrow & a  \\
  \end{array}
  \]
On remarque que la grammaire est celle des mots contenant au moins un $a$.
\end{solution}

\begin{question}
Proposer un algorithme de temps polynomial (en la taille cumulée du
mot et de la grammaire) qui reconnaît si un mot appartient à une
grammaire CNF.
\end{question}

\begin{solution}
Soit $u=u_1\dots u_n$, $A_1, \dots, A_k$ pour chaque paire $1\leq
i\leq j \leq n$ on va calculer $T(i,j,k)$ qui vaut vrai si $u_i\dots
u_j$ peut être transformé en le symbole $A_k$.

$$T(i,j,k) = \bigvee_{ {i\leq l < j }\atop {A_k\rightarrow A_xA_y\in G}} T(i,l,x) \land
T(l+1,j,y) $$ when $i\neq j$ and $T(i,i,k)=(A_k\rightarrow u_i\in G)$.

On est bien polynomial car le vecteur $T(i,j)$ peut être calculé
par une boucle sur $l$ et une itération sur les règles de $G$.
\end{solution}



\end{document}
