\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]{TD4} % except the center
\fancyfoot{} % except the center
\fancyfoot[L]{louis.jachiet@ens.fr}
\fancyfoot[R]{19 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 % uncomment for tutors
}
\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}

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

\begin{document}
\pagestyle{fancy}


\section{Grammaires non contextuelles}


\begin{question}
  Donner une grammaire non contextuelle pour chacun des langages
  suivants (sans trop justifier) :
  \begin{enumerate}

  \item $\Lc_0 = \{ a^ib^jc^k \mid i\neq j \lor j\neq k \}$
  \item $\Lc_1 =  \{ w \in \{a,b\}^* \mid \norm{w}_a \geq \norm{w}_b\}$
  \item $\Lc_2 = \{  w\in\{ (, ), 0, 1, *, +\} \mid w \mbox{ correspond à une expression arithmétique valide}\}$
  \end{enumerate}
\end{question}

\begin{solution}
  \begin{enumerate}
  \item
    On découpe $i\neq j \lor j\neq k$ en $i<j\lor j>i \lor j<k \lor
    j>k$. Pour On introduit $(x,y)\in\{a,b,c\}^2$ $S_x\rightarrow x~
    S_x \mid \epsilon$ et $E_{x,y}\rightarrow x~ E_{x,y}~ y \mid
    \epsilon$ qui calculent les termes $x^n$ et $x^ny^n$ la règle est
    alors :
    $S\rightarrow S_a~ E_{b,c}~ c~ S_c \mid S_a~ b~ S_b~
    E_{b,c} \mid S_a~ a ~ E_{a,b} ~S_c \mid  E_{a,b}~ b~ S_b~ c $

  \item $S\rightarrow \epsilon \mid aS \mid SaSbS \mid SbSaS$. Montrons cela
    par récurrence sur la taille des mots. Si un mot est de taille $2$
    ou moins il est clair qu'il est généré par notre grammaire. Étant
    donné un mot $w_1\dots w_n\in\Ls$ on note $f(k) = \norm{w_1\dots w_k}_a-\norm{w_1\dots w_k}_b$.

    S'il existe $i$ tel que $f(i)=0$ et $1<i \leq n$ alors on prend le
    plus petit tel $i$ et on a $w=a w_2 \dots w_{i-1} b w_{i+1} w_n$
    ou $w=b w_2 \dots w_{i-1} a w_{i+1} w_n$ avec $w'=w_2 \dots
    w_{i-1}$ et $w'' = w_{i+1} w_n$ qui vérifient la propriété donc
    par récurrence $S\xrightarrow{*} w'$ et $S\xrightarrow{*} w''$
    soit $S\rightarrow SaSbS \mid SbSaS \xrightarrow{*} w$.

    Si un tel $i$ n'existe pas alors on a $f(0)=0$ et $f(n)> 0$. Soit
    $f$ est strictement croissante et $w=a^k$ (qui est généré par
    $S\rightarrow aS$) soit on a $1\leq i < j$ avec $f(i)=f(j)$ et
    $0\leq f(j) \leq f(n)$. Notez que $i+1<j$ car $f(i+1)\neq
    f(i)$. On coupe alors $w$ en $x=w_1\dots w_{i}$, $y=w_{i+2}\dots
    w_{j-1}$ et $z=w_{j+1}\dots w_n$. Ces trois bouts respectent la
    propriété car $\norm{x}_a-\norm{x}_b=f(i)$, $\norm{y}_a-\norm{y}_b=f(j)-f(i)$ et
    $\norm{z}_a-\norm{z}_b$.

    En prenant $i$ et $j$ minimal on a $w_{i+1}\neq w_j$. Dans le cas
    $w_{i+1}=a$ et $w_j=b$ (resp. $w_{i+1}=b$ et $w_j=a$) comme on a
    $S\xrightarrow{*} x$, $S\xrightarrow{*} y$, $S\xrightarrow{*} z$
    alors $S\rightarrow SaSbS \xrightarrow{*} x~a~y~b~z$
    (resp. $S\rightarrow SbSaS \xrightarrow{*} x~b~y~a~z$).
    
  \item $S\rightarrow S+S \mid S*S \mid 0 \mid 1 \mid (S) $
    
  \end{enumerate} 
  
\end{solution}

\begin{question}
Il y a différentes manières de parser les expressions arithmétiques
valides. Trouver une grammaire non ambiguë et dans laquelle les arbres
de parsing donne la priorité à * par rapport à + (i.e. 2+3*4 est vue
comme l'expression qui vaut 14 et non 20).
\end{question}

\begin{solution}
  \[
  \begin{array}{lcr}
    S & \rightarrow & NoPlus \mid NoPlus + S \\
    NoPlus &  \rightarrow & NoPlusTimes*NoPlus \mid NoPlusTimes \\
    NoPlusTimes & \rightarrow & (S) \mid 0 \mid 1 \\
  \end{array}
  \]
\end{solution}


\begin{question}
Prouver que les grammaires définies par les symboles $S$ et $Balanced$
reconnaissent le même langage mais que l'une est ambiguë et pas
l'autre :
\[
\begin{array}{lcrclcr}
  Balanced & \rightarrow & (OneRight ~ Balanced \mid \epsilon & \hspace{10em} & S & \rightarrow &  SS \mid (S) \mid \epsilon\\
  OneRight & \rightarrow &  ) \mid  ( OneRight ~ OneRight \\
\end{array}
\]
\end{question}

\begin{solution}
Les deux reconnaissent les expressions bien parenthèsées. Pour $S$
c'est assez clair et pour $Begin$ il suffit de remarquer que $End$
reconnaît les expressions $e)$ tels que $e$ est bien parenthèsée.

$S\rightarrow SS$ est ambiguë, en effet $SSS$ peut être obtenue comme
$[SS]S$ ou $S[SS]$. Tandis que la grammaire introduite par $Begin$ est
non ambiguë (comme dérivation est imposée par le premier caractère).
  
\end{solution}

\section{Grammaires sensibles au contexte}

\begin{question}
  Considérons la grammaire suivante :
\[ %
\begin{array}{rclcrcl}
S & \rightarrow & aSBC \mid aBC & \hspace{5em} & bB & \rightarrow & bb \\
CB & \rightarrow & BC &                     & bC & \rightarrow & bc \\
aB & \rightarrow & ab &                     & cC & \rightarrow & cc \\
\end{array}%
\]

Quel langage reconnaît-elle ? Justifier.
\end{question}

\begin{solution}

  Nous allons montrer que $S\xrightarrow{*} w$ implique que $w$ est de
  la forme \fo{1}~$w=a^nb^ic^j\#(B^{n-i},C^{n-j})$ ou
  \fo{2}~$w=a^nS\#(B^n,C^n)$ pour des $n,i,j$ avec $\#(x,y)$
  l'entrelacement de mots $x$ et $y$.

  Nous procédons par récurrence sur la taille d'une dérivation. Pour
  la taille nulle on a $S$ de la forme \fo{2} ($S=a^0S\#(B^0,C^0)$)
  donc c'est bon.

  Sinon soit $w'$ respectant notre critère, regardons
  $S\xrightarrow{*} w' \rightarrow w$ on a selon la règle utilisé dans
  $w'\rightarrow w$:
  \begin{itemize}
  \item Si $S\rightarrow aSBC$ est la dernière règle alors $w'$ est de
    la forme \fo{2} et $w$ aussi.
  \item Si $S\rightarrow aBC$ est la dernière règle alors $w'$ est de
    la forme \fo{2} et $w$ de la forme \fo{1}.
  \item La règle $CB\rightarrow BC$ préserve les deux formes.
  \item Si la règle utilisée est $aB\rightarrow ab$ alors on avait
    $w'$ de la forme \fo{1} avec $w'=a^nb^0c^0\#(B^n,C^n)$ et on a
    $w=a^nb^1c^0\#(B^{n-1},C^n)$.
  \item Si la règle est $bB\rightarrow bb$, $cC\rightarrow CC$ ou
    $bC\rightarrow bc$ alors on reste bien dans la forme \fo{1} car un
    motif $cb$ ne peut pas apparaître.
  \end{itemize}

Finalement, si $w$ est complètement réduit alors $w$ est de la forme
$a^nb^nc^n$. Tous les mots de la forme $a^nb^nc^n$ peuvent être
obtenus pour $n\geq 1$: on applique $n-1$ la règle $S\rightarrow aSBC$
et une fois $S\rightarrow aBC$ on obtient $a^n(BC)^n$. On réordonne
$(BC)^n$ avec $CB\rightarrow BC$ pour obtenir $a^nB^nC^n$ puis en
appliquant une fois $aB\rightarrow ab$, $n-1$ fois $bB\rightarrow bb$,
une fois $bC\rightarrow bc$ puis $n-1$ fois $cC\rightarrow cc$ on
obtient bien $a^nb^nc^n$.
\end{solution}

\begin{question}
  Considérons la grammaire suivante :
\[ %
\begin{array}{rclcrcl}
S & \rightarrow & CD & \hspace{5em}         & Ab & \rightarrow & bA \\
 C & \rightarrow & aCA \mid bCB &                & Ba & \rightarrow & aB \\
AD & \rightarrow & aD &                     & Bb & \rightarrow & bB \\
BD & \rightarrow & bD &                     & C  & \rightarrow & \epsilon \\
Aa & \rightarrow & aA &                     & D & \rightarrow & \epsilon \\
\end{array}%
\]

Quel langage reconnaît-elle ? Justifier.
\end{question}

\begin{solution}
  On va montrer que les dérivations obtenues sont de la forme
  $wC^?\#(x,y)D^?$ avec $(x,w)\in (\{a,b\}^*)^2$, $y\in \{A,B\}^*$ et
  $w=x~ rev(lower(y))$ où $X^?$ indique que $X$ peut ou non être
  présent, $rev$ est la fonction qui retourne un mot et $lower$
  transforme les lettres $A$ en $a$ et les $B$ en $b$.

  Pour une dérivation de taille 1 on a $S\rightarrow CD$ donc c'est bon.

  Pour une dérivation de taille plus grande que 1 selon la dernière
  règle utilisée on a :
  \begin{itemize}
  \item Les règles $C\rightarrow \epsilon$ et $D\rightarrow \epsilon$
    qui préservent la forme.
  \item Les règles $C\rightarrow aCA$ et $C\rightarrow bCB$ préservent
    aussi la forme. Par exemple pour $C\rightarrow aCA$ alors $a$ va
    être ajoutée à la fin $w$ et $A$ au début de $y$ (et donc $a$ à la
    fin de $rev(lower(y))$).

  \item Les règles $Aa\rightarrow aA$, $Ba\rightarrow aB$,
    $Ab\rightarrow bA$ et $Bb\rightarrow bB$ préservent aussi la forme
    car elles ne ne déplacent pas l'ordre relatif des lettres dans $x$
    et $y$, juste l'entrelacement.

  \item Enfin les règles $AD\rightarrow aD$ et $BD\rightarrow bD$
    préservent aussi l'ordre car on avait $w=x~rev(lower(y))$ avec
    $y=y'A$ donc
    $x~rev(lower(y'A))=x~rev(lower(y')a)=x~a~rev(lower(y'))$ donc $w=
    (xa) rev(lower(y'))$.
    
  \end{itemize}

  Donc si un mot $m$ avec $S\xrightarrow{*} m$ complètement réduit on
  a $w\in\{a,b\}^*$ tel que $m=ww$.

  Tous les mots de cette forme sont bien accessibles car $S\rightarrow
  wCwD$ pour tout $w$~: c'est évident pour $w=\epsilon$ et par
  récurrence si $w'=wa$ alors on a $S\xrightarrow{*} wCwD
  \xrightarrow{} waCAwD \xrightarrow{*} waCwAD\rightarrow{} waCwaD$
  (on procède de même pour $w'=wb$).
\end{solution}

\begin{question}
  Considérons la grammaire suivante :
\[ S\rightarrow aS \mid aSbS \mid \epsilon \]

Quel langage reconnaît-elle ? Justifier.
\end{question}

\begin{solution}
Nous allons montrer qu'un mot est dans cette grammaire si et seulement
si tous ses préfixes contiennent au moins autant de $a$ que de $b$.

Montrons d'abord par récurrence sur la taille des mots que si un mot
est dans cette grammaire alors ses préfixes ont plus de $a$ que de
$b$. La propriété est clairement vraie après 0 dérivation. Et si elle
est vraie après $n$ dérivations alors elle est vraie après $n+1$
dérivations car $S\rightarrow \epsilon$ ne change pas les $a$ ou $b$ ;
$S\rightarrow aS$ ne peut qu'ajouter un $a$ et enfin une dérivation
$S\rightarrow aSbS$ n'ajoute un $b$ à un préfixe que si elle ajoute
aussi un $a$.

Montrons maintenant que tout mot avec notre propriété peut être obtenu
par récurrence sur la taille des mots. Soit $w$ un mot respectant la
propriété on a $w\epsilon$ et donc $S\rightarrow\epsilon$ ou
$w=aw'$. Si $w'$ respecte aussi la propriété alors on a
$S\xrightarrow{*}w'$ et $w$ peut être obtenu de la façon suivante
$S\rightarrow aS\xrightarrow{*} aw' =w$.

Maintenant si $w'$ ne respecte pas la propriété, on peut trouver $z$
le plus petit préfixe de $w'$ qui ne respecte pas la propriété. Par
mimimalité de $z$ on a $z=x~b$ avec $x$ respectant la propriété. On a
alors $w=a~x~b~y$ avec $a~x~b$ qui contient strictement autant de $a$
que de $b$. Comme $w$ respecte la propriété alors $y$ respecte aussi
la propriété (un préfixe $p$ de $y$ correspondant à un préfixe $axbp$
de $w$). Par récurrence on a donc $S\xrightarrow{*} x$ et
$S\xrightarrow{*} y$ donc $S\xrightarrow{*} aSbS \xrightarrow{*}
a~x~b~y = w$.
\end{solution}
\section{Myhill -- Nerode}

Soit $\Sigma$ un alphabet et $\Ls$ un langage dessus (pas
nécessairement régulier).

\begin{defi}
Soient deux mots $x,y\in {\Sigma^*}^2$ on définit la relation suivante
:

$$ x \sim_{\Ls} y ~~~\myeq~~~ \forall z\in\Sigma^* : xz\in\Ls \Leftrightarrow yz\in\Ls $$
\end{defi}

\begin{question}
  Montrer que cette relation est bien une relation d'équivalence
  (i.e. elle est réfléxive, symétrique et transitive).
\end{question}

\begin{solution}
C'est la relation d'équivalence induite par la fonction $f(x) = \{ z
\mid xz\in \Ls\}$ (i.e. $x\sim_\Lc y \Leftrightarrow f(x)=f(y)$).
\end{solution}

\begin{question}
  Soient $(x,y)\in{\Sigma^*}^2$ et $c\in\Sigma$ montrer que si
  $x\sim_\Ls y$ alors $xc\sim_\Ls yc$.
\end{question}

\begin{solution}
  Si $x (cz) \in\Ls$ alors $y (cz)\in\Ls$ et réciproquement.
\end{solution}

\begin{question}
  Montrer que si $\sim_\Ls$ a un nombre fini de classes
  d'équivalences, alors $\Ls$ est régulier.
\end{question}

\begin{solution}
Soient $x_1, \dots, x_n$ des représentants de chacune des classes
d'équivalence avec $x_1\sim_\Ls \epsilon$ et $\F=\{ x_i \mid x_i\in\Ls
\}$. D'après l'exercice précédent on peut définir $\delta(x_i,c)=x_j$
tel que $x_i c\sim_\Ls x_j$ et cela ne dépend pas du choix du
représentant $x_i$. On pose donc l'automate
$A=<\{x_1,\dots,x_n\},\Sigma,\delta,x_1,\F>$ et cet automate reconnaît
$\Ls$. En effet on voit par récurrence sur la taille de $w$ que
$\tilde{\delta}(x_1,w)\sim_\Ls w$ et donc $w\in\Ls \Leftrightarrow
\tilde{\delta}(x_1,w)\in \Ls \Leftrightarrow
\tilde{\delta}(x_1,w)\in\F $.
\end{solution}

\begin{question}
Montrer que si $\Ls$ est régulier alors $\sim_\Ls$ a un nombre fini de
classes d'équivalences.
\end{question}

\begin{solution}
  Soit $A=<\Q,\Sigma,\delta,i,\F>$ un automate déterministe complet
  qui reconnaît $\Ls$. Un mot $xz$ est dans $\Ls$ si et seulement
  $\tilde{\delta}(i,xz)\in \F $ et donc ssi
  $\tilde{\delta}(\tilde{\delta}(i,x),z)\in \F $. Donc pour deux mots
  $x$ et $y$ tels que $\tilde{\delta}(i,x)=\tilde{\delta}(i,y)$ on a
  $x\sim_\Ls y$. Si on a $n$ mots de $n$ classes distinctes, on a donc
  au moins $n$ états dans l'automate or le nombre d'états est fini
  donc le nombre de classes aussi.
\end{solution}

\section{Myhill -- Nerode : applications}

\begin{defi}
  Calculer les quotients à gauche d'un langage correspond à calculer
  les classes d'équivalences induites par la relation $\sim_\Ls$ vue
  plus haut.  Les quotients gauches de $\Ls$ sont les $\Lc_w$ pour
  $w\in\Sigma^*$ avec $\Lc_w = \{ x \mid wx\in\Ls \}$. D'après ce que
  nous avons vu plus haut les $\Lc_w$ sont en nombre fini puisque
  $x\sim_\Ls y \Leftrightarrow \Lc_x = \Lc_y$.
  
\end{defi}

\begin{question}
  Trouver les quotients à gauche et l'automate minimal pour chacun des
  langages suivants sur l'alphabet $\{a,b\}$:
  \begin{enumerate}
  \item $\Lc_3 = b(ba)^*$
  \item $\Lc_4 = \{ a^ib^j \mid i+j\mbox{ est pair}\}$
  \item $\Lc_5 = \{ w\in\{a,b\}^* \mid w \mbox{ contient exactement une fois
    le facteur } bb\}$
  \end{enumerate}

\end{question}

\begin{solution}
  \begin{enumerate}
  \item Les classes sont $\emptyset$, $b(ba)^*$, $(ba)^*$, $a(ba)^*$
    on a donc

  \begin{tikzpicture}[shorten >=1pt,node distance=3cm,on grid,auto]
    \node[state,initial] (q_1) {$b(ba)^*$};
    \node[state,right=of q_1] (q_0)   {$\emptyset$};
    \node[state,accepting] (q_2) [below=of q_1] {$(ba)^*$};
    \node[state](q_3) [right=of q_2] {$a(ba)^*$};
    \path[->]
    (q_1) edge  node {a} (q_0)
    (q_2) edge [bend left] node  {a} (q_0)
    (q_3) edge  node  {b} (q_0)
    (q_0) edge [loop above] node {a,b} ()
    (q_1) edge  node {b} (q_2)
    (q_2) edge [bend left] node {b} (q_3)
    (q_3) edge [bend left] node {a} (q_2);
    \end{tikzpicture}

\item les classes sont
  \fo{1}~$\emptyset$,
  \fo{2}~$\{ a^ib^j \mid i+j\mbox{ est pair}\}$,
  \fo{3}~$\{ a^ib^j \mid i+j\mbox{ est impair}\}$,
  \fo{4}~$\{ b^j \mid j\mbox{ est pair}\}$,
  \fo{5}~$\{ b^j \mid j\mbox{ est impair}\}$ l'automate
  est donc~:

   \begin{tikzpicture}[shorten >=1pt,node distance=4cm,on grid,auto]
    \node[state,initial,accepting] (q_2) {2};
    \node[state, below=of q_2] (q_3) {3};
    \node[state, below right = 2cm and 2cm of q_1] (q_0)   {$\emptyset$};
    \node[state,accepting] (q_4) [right=of q_3] {4};
    \node[state](q_5) [right=of q_2] {5};
    \path[->]
    (q_5) edge [bend right] node {a} (q_0)
    (q_4) edge [bend left] node {a} (q_0)
    (q_2) edge  node {b} (q_5)
    (q_3) edge  node {b} (q_4)
    (q_4) edge [bend left] node {b} (q_5)
    (q_5) edge [bend left] node {b} (q_4)
    (q_2) edge [bend left] node {a} (q_3)
    (q_3) edge [bend left] node {a} (q_2);
    \end{tikzpicture}
      
    \item  les classes sont
  \fo{0} $\emptyset$,
  \fo{1} $(b?a)^*bb(ab?)^*$,
  \fo{2} $b(ab?)^* | a(b?a)^*bb(ab?)^*$,
  \fo{3} $(ab?)^*$,
  \fo{4} $b?(ab?)^*$,
  l'automate
  est donc~:\\
   \begin{tikzpicture}[shorten >=1pt,node distance=4cm,on grid,auto]
    \node[state,initial] (q_1) {1};
    \node[state, right=of q_1] (q_2) {2};
    \node[state, accepting, below=of q_2] (q_3) {3};
    \node[state, accepting, left=of q_3] (q_4) {4};
    \node[state, below right = 2cm and 2cm of q_1] (q_0)   {$\emptyset$};

    \path[->]
    (q_1) edge [bend left] node {b} (q_2)
    (q_2) edge [bend left] node {b} (q_3)
    (q_3) edge [bend right] node {b} (q_0)
    (q_1) edge [bend right] node {a} (q_0)
    (q_2) edge [bend right] node {a} (q_0)
    (q_3) edge [bend left] node {a} (q_4)
    (q_4) edge [bend left] node {b} (q_3)
    (q_4) edge [loop above] node {a} (q_4);
    \end{tikzpicture}
      
\end{enumerate}
\end{solution}

\end{document}
