\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}
\fancyhead[R]{\textsc{Langage formels, calculabilité et complexité}}
\fancyhead[L]{TD2} % except the center
\fancyfoot{} % except the center
\fancyfoot[L]{louis.jachiet@ens.fr}
\fancyfoot[R]{5 octobre 2017}
\newcommand{\A}{\mathcal{A}}
\newcommand{\B}{\mathcal{B}}
\newcommand{\X}{\mathcal{X}}
\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}}
\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}

\usepackage{tikz}
\usetikzlibrary{automata,positioning}

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

\begin{document}
\pagestyle{fancy}

\section{Lemme d'Arden}
\begin{question}
Soit ${\A}$, ${\B}$ des langages rationnels, montrez que si
$\epsilon\not\in {\A}$ alors ${\X}=\A\X\cup{\B}$ admet un unique langage $\X$
solution. Exprimez cette solution en fonction de $a$
(resp. $b$) une expression régulière qui reconnaît ${\A}$
(resp. ${\B}$).

\textit{Conseil pour aborder cet exercice :
\begin{enumerate}
\item trouvez une première solution et prouvez que c'en est bien une ;
\item prouvez que toute solution contient votre première solution ;
\item prouvez que votre première solution contient toute solution.
\end{enumerate}}
\end{question}

\begin{solution}
Nous allons montrer que l'unique solution est $\A^*\B =\{ a_1 \dots a_n b \mid
(a_i)\in {\A}^*, b\in {\B}\}$ ou en forme d'expression
régulière $a^*b$.

$\A^*\B$ est une solution : $\A\A^*\B \cup \B = \A^*\B$.

Montrons par récurrence sur la taille des mots de
${\X}$ que toute solution est incluse dans $a^*b$.
  
  Soit $x\in {\X}$ on a soit $x\in {\B}$ soit $x\in
  \mathcal{AX}$. Si $x\in B$, le résultat est clair. Si $x\in
  \mathcal{AX}$ nous avons $a\in{\A}$ et $x'\in {\X}$
  tels que $x=ax'$. Comme $|a|>0$, $|x'|<|x|$ et donc par récurrence
  on a $x'$ dans $a^*b$ donc $x$ aussi.

  Enfin toute solution ${\X}$ contient ${\B}$ et est
  stable par concaténation gauche de ${\A}$ donc $a^*b$ est
  contenue dans cette solution.
\end{solution}

\section{Lemme de pompage (ou lemme de l'étoile)}

\begin{question}
  Les langages suivants sont-ils réguliers ? Justifiez.
  \begin{enumerate}
  \item $\{a^nb^n \mid n\in\mathbb{N}\}$
  \item $\{a^mb^n \mid n \equiv m \pmod d\}$ pour un $d\in\mathbb{N}$ donné.
  \item $\{a^p \mid p \mbox{ premier }\}$
  \item $\{a^{P(n)} \mid n\in \mathbb{N}\}$ pour $P\in \mathbb{N}[X]$ donné.
  \end{enumerate}
\end{question}

\begin{solution}
  \begin{enumerate}
    \item Non, d'après le lemme de pompage pour $m$ suffisamment grand
      on a $a^mb^m$ qui se décomposerait en $uvw$ avec $uv^kw$ dans le
      langage. Si $v$ panache $a$ et $b$ alors le $uv^2w$ alterne $a$
      et $b$ et si $w$ ne contient que $a$ ou que $b$ il y a
      déséquilibre entre les nombres de $a$ et $b$.
      
    \item Oui, c'est l'union pour $k=0,\dots,d-1$ des langages  $L_k=(a^k(a^d)^*b^k(b^d)^*)$

      
    \item Non, si pour $p$ suffisamment  grand on a $a^p$ implique une
      décomposition $a^p=uvw$  avec $uv^xw$ dans le  langage pour tout
      $x$. Si $v=a^d$ on a $a^p+x\times d$ pour tout $d$ or $p+x\times
      d$ n'est pas premier pour $x=p$ ($p+pd=(d+1)p$).
      
    \item Par lemme de pompage on a pour $n$ assez grand $a^{P(n)}$
      décomposable en $uvw$ avec $|v|>0$ et $uv^kw$ dans le langage
      pour tout $k$. Donc il existe $k$ et $d$ tel que $a^{k\times x +
        d}$ pour tout $x$. Ce n'est pas vrai si $P$ est du second
      degré ou plus (l'écart $P(n+1)-P(n)$ tend vers l'infini). En
      revanche si $P$ est du premier degré ça marche, pour $P(X)=BX+C$
      on a l'expression $(a^B)*a^{(C\%B)}$.
  \end{enumerate}
\end{solution}

\section{Puzzles}

\begin{question}
  Soient $x$ et $y$ deux mots tels que $xy=yx$, que pouvez-vous dire
  de la forme de $x$ et $y$ ?
\end{question}


\begin{solution}
  Montrons par récurrence sur $|y|+|x|$ qu'il existe $w$ tel que
  $x=w^n$ et $y=w^m$ pour $(n,m)\in\mathbb{N}^2$.
  
  Si $|x|=|y|$, on a $x=y$ alors $w=x=y$ avec $n=m=1$ convient.

  Sinon on a $xy=yx$ donc on peut trouver $z$ tel que $y=xz$. On a
  alors $xxz=xzx$ et donc $xz=zx$. Par récurrence on obtient $x=w^n$,
  $z=w^m$ et donc $y=w^{m+n}$
  
\end{solution}

\begin{question}
  Soient $(p,q)\in \mathbb{N}^*$, et $\mathcal{L}$ un langage régulier
  est-ce que $\dfrac{p}{q}\mathcal{L} = \left\{ u \mid \exists v:
  uv\in\mathcal{L}\mbox{ et } |u|=\dfrac{p}{q}|uv|\right\}$ est
  nécessairement régulier ?
\end{question}

\begin{solution}
  Oui, nous allons présenter l'automate pour $p\leq q$ et $gcd(p,q)=1$ (les autres cas
sont triviaux).  L'idée c'est que $|u|=\dfrac{p}{q}|uv|$ est
équivalent à $q|u|=p|uv|$ ou $(q-p)|u|=p|v|$. De la même manière que pour
$\dfrac{1}{2}\mathcal{L}$ où à chaque fois que l'on lit une lettre, on
avance d'une lettre en partant de la fin (voir TD de la semaine
dernière), ici en lisant $p$ lettres de $u$ on note que l'on avance de
$q-p$ lettres dans l'automate en partant de la fin.

Soit $<\Sigma,\mathcal{Q},\delta,i,\mathcal{F}>$ un automate
déterministe qui reconnaît $\mathcal{L}$ notre automate est
:\\ $<\Sigma,\mathcal{Q}\times \{0,1,\dots,p-1\}\times
2^\mathcal{Q},\eta, (i,0,\mathcal{F}), \{(e,0,f) \mid
f\cap\mathcal{F}\neq \emptyset\}>$ Un état $(e,l,f)$ stocke l'état $e$
obtenu par l'automate initial, le nombre $l$ de lettres lues modulo
$q$ et les états $g\in f$ tels qu'il existe un mot de taille
$\lfloor\dfrac{p}{q}l\rfloor$ qui mène de $g$ à un état de
$\mathcal{F}$.

Les transitions sont donc $\eta((e,p-1,f),c) = (\delta(e,c),0,\{g\mid
\exists h\in f,v: |v|=p-q \mbox{ et } {\td}(h,v)=g\})$ et
$\eta((e,l,f),c) = (\delta(e,c),l+1,f)$ si $l<q-1$.
\end{solution}

\section{Lemme d'Arden généralisé}

\begin{defi}
  Un monoïde est une structure algébrique $(E,\bigodot,e)$ telle que :
  \begin{itemize}
    \item[(loi interne)] Pour $x,y\in E^2$, $x\bigodot y\in E$
    \item[(associative)] Pour $x,y,z\in E^3$, $(x\bigodot y)\bigodot z=x\bigodot (y\bigodot z)$
    \item[(élément neutre)] Pour $x\in E$, $x\bigodot e=e\bigodot x = x$
  \end{itemize}
\end{defi}

\begin{defi}
  Un demi-anneau est une structure algébrique $(E,+,\times,0,1)$ telle que :
  \begin{itemize}
  \item $(E,+,0)$ est un monoïde commutatif ($a+b=b+a$);
  \item $(E,\times,1)$ est un monoïde;
  \item $\times$ est distributif pour $+$ ($a\times (b+c)=a\times b + a \times c$ et $ (b+c)\times a=b\times a + c \times a$);
  \item $0$ est absorbant pour $\times$ (i.e. $0\times a=a\times 0=0$)
  \end{itemize}
\end{defi}

\begin{question}
  Remarquez que $({\Ls},\cup,/,\emptyset,\epsilon)$ est un demi-anneau où:
  \begin{itemize}
  \item ${\Ls}$ est l'ensemble des langages réguliers
    sur l'alphabet fini $\Sigma$;
  \item $/$ est la concaténation $X/Y=\{xy \mid x\in X, y\in Y\}$;
  \item $\cup$ est l'union;
  \item $\emptyset$ est le langage vide;
  \item $\epsilon$ est le langage contenant uniquement le mot vide.
  \end{itemize}

  
  Soit $(\Mn{},+,\times,0,1)$ l'ensemble des
  matrices carrés de taille $n$ sur le demi-anneau
  $({\Ls},/,\cup,\emptyset,\epsilon)$ avec
  \begin{itemize}
    \item $(M+N)_{i,j}=M_{i,j}\cup N_{i,j}$;
    \item $(M\times N)_{i,j}= \displaystyle{\bigcup_{1\leq k \leq n} M_{i,k} /  N_{k,j}}$;
    \item $0_{i,j}=\emptyset$
    \item $1_{i,j}=\begin{cases}\epsilon & i=j \\ \emptyset & \mbox{sinon}\end{cases}$
    \item $M^*=\sum_{i\in\mathbb{N}} M^i $
      
  \end{itemize}

  Remarquez que $(\Mn,+,\times,0,1)$ est aussi un
  demi-anneau.

  \textit{Note : Tout demi-anneau peut se transformer de la même manière en
    un demi-anneau de matrices}.
\end{question}

\begin{question}
  Soit ${\A} \in \Mn$ avec $\forall i,j ~
  \epsilon \not\in A_{i,j}$ et ${\B}\in
  M_{n,1}({\Ls})$ un vecteur de taille $n$ montrez qu'il
  n'existe qu'une unique solution ${\X}\in
  M_{n,1}({\Ls})$ à ${\X}=\mathcal{AX}\cup
  {\B}$ (i.e. $\forall i: {\X}_i = \left( \bigcup_j ~
  {\A}_{i,j} / {\X}_j \right) \cup {\B}_i$).
\end{question}

\begin{solution}

  L'unique solution est $\mathcal{A^*B}=\bigcup_n {\A}^n
  {\B}$. En effet, c'est une solution, et toutes les solutions
  doivent contenir ${\B}$ et être stables par concaténation
  gauche de ${\A}$ donc toutes les solutions contiennent
  $\mathcal{A^*B}$ et par conséquence pour tout $j$, une solution
  ${\X}$ est telle que $(\mathcal{A^*B})_j\subseteq
  {\X}_j$.

  Maintenant soit ${\X}$ une solution avec ${\X}\neq
  \mathcal{A^*B}$, soient $j$ et $(x_1,\dots,x_n)\in {\X}$ tels
  que $|x_j|$ est minimal et $x_j\in{\X}_j\setminus
  (\mathcal{A^*B})_j$. ${\X}=\mathcal{AX}\cup {\B}$ donc
  comme par définition ${\B}_j\subseteq {\X}_j$ il
  existe $a_{j,i}x_i$ et $x_i\in {\X}_i$. Comme $|x_j|$ est
  minimal et $|a_{i,j}|>0$ on a $x_i\in \mathcal{A^*B}$ mais alors
  $x_j\in(\mathcal{A^*B})_j$ ce qui est contradictoire. 

\end{solution}

\begin{question}\emph{(Pivot de Gauss)}
Étant donné ${\A}\in \Mn$ et
${\B}\in M_{n,1}({\Ls})$ montrez que si $n>1$ les
langages $(\mathcal{A^*B})_i$ pour $i\in \{1, \dots, n-1\}$ peuvent
s'exprimer sous la forme $\mathcal{A'^*B'}$ pour $\mathcal{A'}\in
M_{n}({\Ls}), {\B}'\in
M_{n,1}({\Ls})$.
\end{question}

\begin{solution}
On a ${\X}_n= \bigcup_i {\A}_{n,i} \X_i \cup {\B}_n$ donc $\X_n=
\bigcup_j \A_{n,i}\X_i\left(\A_{n,n}\X_n \cup \B_n\right)$ donc
$\X_n=\A_{n,n}^* \left(\B_n\bigcup_j \A_{n,i}\X_i\right)$.

On avait $\X_i = \bigcup_j \A_{i,j} \X_j$ on a $\X_i = \bigcup_{j<n}
\A_{i,j} \X_j \cup \A_{i,n}(\A_{n,n}^*\B_n \cup \bigcup \A_{n,n}^*A_{n,j}X_j)
\cup \B_i$ donc nous avons $\X_i = \bigcup_{j<n} (\A_{i,j} \cup
\A_{i,n}\A_{n,n}^*\A_{n,j}) \X_j \cup (\B_i\cup A_{i,n}A_{n,n}^*\B_n)$.

En posant $\A'_{i,j} = \A_{i,j} \cup \A_{i,n}\A_{n,n}^*\A_{n,j}$ et $\B'_i = B_i
\cup A_{i,n}A_{n,n}^*\B_n$ nous avons bien le résultat escompté.
\end{solution}

\begin{question}
En déduire un algorithme permettant de retrouver une expression
régulière à partir d'un automate.
\end{question}

\begin{solution}
Un automate $<\Sigma,\mathcal{Q},\delta,i,\mathcal{F}>$ peut être vu
comme un système d'équations avec $A_{i,j}= c_1 | \dots | c_k$ où les
$c_l$ sont tels que $q_j\in\delta(q_i,c_l)$ et
$B_i=\begin{cases}\epsilon & q_i\in\mathcal{F} \\ \emptyset &
\mbox{sinon} \end{cases}$. À partir de là on applique simplement le
pivot de Gauss jusqu'à obtenir une seule équation correspond à l'état
initial $\X=\A\X\cup \B$ et la solution est $\A^*\B$.
\end{solution}

\begin{question}
  Donner l'expression régulière pour l'automate suivant :

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

\begin{solution}
\[
\begin{array}{|cccc|l|}
  \hline
(a|b)  &   a  & \emptyset & \emptyset & \emptyset \\
\emptyset  &   \emptyset  & b & a & \emptyset \\
\emptyset  &   \emptyset  & \emptyset & a & \epsilon \\
\emptyset  &   \emptyset  & a & b & \emptyset \\
\hline
\end{array}
\hspace{1em}%
\begin{array}{|ccc|l|}
  \hline
(a|b)  &   a  & \emptyset &  \emptyset \\
\emptyset  &   \emptyset  & b|(ab^*a)  & \emptyset \\
\emptyset  &   \emptyset  & ab^*a & \epsilon \\
\hline
\end{array}
\hspace{1em}%
\begin{array}{|cc|l|}
  \hline
(a|b)  &   a  &  \emptyset \\
\emptyset  &   \emptyset  & (b|(ab^*a))(ab^*a)^*  \\
\hline
\end{array}
\hspace{1em}%
\begin{array}{|c|l|}
  \hline
(a|b)   &  a(b|(ab^*a))(ab^*a)^* \\
\hline
\end{array}
\]

Le langage est donc $(a|b)^*a(b|(ab^*a))(ab^*a)^*$
\end{solution}


\section{Monoïde d'un langage}

\begin{defi}
Étant donné un alphabet ambiant $\Sigma$ et un langage $\mathcal{L}$
(pas nécessairement régulier) on note $\ml$ le morphisme syntaxique de $\mathcal{L}$ 
définit ainsi :
$\ml (u) = \{ (x,y) \in {\Sigma^*}^2 \mid xuy \in \Lc \}$.
\end{defi}

\begin{question}
    Montrer que $\ml$ est compatible avec la concaténation c'est à
    dire $\forall u,v,w : \ml (v)=\ml (w) \Rightarrow \left( \ml(vu)=\ml(wu)\right)
    \land \left(\ml(uv)=\ml(uw)\right)$.
\end{question}

\begin{solution}
  Soient $u,v,w$ avec $\ml(w)=\ml(v)$ on a $(x,y)\in\ml(vu)$
  équivalent $xvuy \in \Lc$ donc $(x,uy)\in\ml(v)=\ml(w)$ donc
  $(x,y)\in ml(wu)$ et donc $\ml(vu)\subseteq \ml(wu)$.  Tous les
  autres cas sont parfaitement symétriques donc on obtient le résultat
  voulu.
\end{solution}

\begin{question}
  Pour chaque élément $e\in\ml(\Sigma^*)$ on choisit un représentant
  $r(e)$ tel que $\ml(r(e))=e$, et on définit $u\odot v = \ml(r(u))
  \odot \ml(r(v))=\ml(r(u)r(v))$.

  Justifier que :
  \begin{itemize}
    \item $\odot$ ne dépend pas du choix de $r$.
    \item la structure  $(\ml(\Sigma^*),\odot,\ml(\epsilon))$ induite par $\ml$ est bien un monoïde
  \end{itemize}
et donc $\ml$ est bien un morphisme entre le monoïde libre sur
$\Sigma$ et le monoïde induit par $\ml$.


  \textit{Note : tout monoïde $(M,\odot,e)$ compatible avec une
    fonction $\mu$ induit une structure de monoïde sur $\mu(M)$}.
\end{question}

\begin{solution}
  \begin{itemize}
  \item Soient $r$ et $r'$, d'après la question précédente on a:
    $u\odot_r v=\mu(r(u))\odot_r \mu(r(v)) = \mu(r(u)r(v)) =
    \mu(r'(u)r(v)) = \mu(r'(u)r'(v)) = u\odot_{r'} v$

  \item $\odot$ est bien une loi interne, montrons son associativité :
    $(x\odot y)\odot z = (r(x)\odot r(y)) \odot r(z) = \ml(r(\ml(xy))
    r(z))$ mais $\ml(r(\ml(xy))z)=\ml(xyz)$ car
    $\ml(xy)=\ml(r(\ml(xy))$. De la même manière on a $x\odot(y\odot
    z)=\ml(xyz)$. Enfin $\ml(r(x) r(\ml(\epsilon)))=\ml(r(x))=\ml(
    r(\ml(\epsilon)) r(x))$ donc $\ml(\epsilon)$ est bien associatif.
  \end{itemize}

\end{solution}


\begin{question}
  Montrer que $\ml(\Sigma^*)$ est fini quand $\Lc$ est régulier.
\end{question}

\begin{solution}
  Si $\Lc$ est régulier, il existe un automate déterministe fini
  complet $<\Sigma,\mathcal{Q},\delta,i,\mathcal{F}>$ qui reconnaît
  $\Lc$. Pour un $u$ donné on pose $t(u)=\{ (p,\td(p,u))\in
  \mathcal{Q}^2 \mid q\in{\td}(p,u)\}$ montrons que $t(u)=t(v)$
  implique $\ml(u)=\ml(v)$. Par symétrie, montrons juste que
  $\ml(u)\subseteq \ml(v)$.

  Soient $u,v,x,y\in {\Sigma^*}^2$ et $(x,y)\in \ml(u)$ on a $xuy\in
  Lc$ donc $\td(i,xuy)\in \mathcal{F}$ mais ${\td}(i,xuy) = \td(
  q_x,uy )$ avec $q_x=\td(i,x)$.  Donc $\td(i,xuy)= \td(\td(q_x,u),y)
  = \td(\td(q_x,v),y)=\td(i,xvy)$ et donc $xvy\in\Lc$. 
\end{solution}

\begin{question}
  Montrer que si $\ml(\Sigma^*)$ est fini alors $\Lc$ est régulier.
\end{question}

\begin{solution}
Si $\ml(\Sigma^*) = \{ q_1 , \dots, q_n\}$ on pose $i=\ml(\epsilon)$,
$\delta(q_i,c)=q_i\odot \ml(c)$ et $\mathcal{F}=\{ q\in\ml(\Sigma^*)
\mid (\epsilon,\epsilon)\in q\}$ et alors
$<\Sigma,\ml(\Sigma^*),\delta,i,\mathcal{F}>$ est un automate qui
reconnaît $\Lc$.
\end{solution}

\begin{question}
À quoi ressemble le monoïde syntaxique des mots bien parenthèsés ?
\end{question}

\begin{solution}
À $\mathbb{Z}^2$ : un mot est envoyé sur $(x,y)\in \mathbb{Z}^2$ quand
il ferme $x$ parenthèses ouvertes avant lui et laisse ouvertes $y$
parenthèses et on a la loi $(x,y)\odot (w,z) = (x+max(w-y,0),z+max(y-w,0))$.
\end{solution}
\end{document}
