\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]{TD3} % except the center
\fancyfoot{} % except the center
\fancyfoot[L]{louis.jachiet@ens.fr}
\fancyfoot[R]{12 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}}
\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{TD3 : Langages formels, calculabilité et complexité}

\begin{document}
\pagestyle{fancy}

\section{Rappels : les langages suivants sont-ils rationnels~? (Justifiez)}

\begin{question}
  $\Lc_0=\{ w\in\{a,b, c\}^* \mid (|w|_a=0) \Rightarrow (|w|_b=0)\}$
\end{question}
\begin{solution}
  $c*+(b+c)*a(a+b+c)*$
\end{solution}

\begin{question}
  $\Lc_2=\{ w\in\{a,b\}^* \mid |w|_a< |w|_b \}$
\end{question}

\begin{solution}
  Non. Sinon on aurait un $n$ de pompage et sur le mot $a^nb^{2n}$ on
  aurait $a^{n+kx}b^{2n}$ dans le langage pour $k>0$ et tout $x$. Or
  $kx+n > 2n$ pour $x$ grand.
\end{solution}

\begin{question}
  $\Lc_1=\{ w\in\{a,b\}^* \mid 7 \mbox{ divise } |w|_a, 3 \mbox{
    divise } |w|_b, \}$
\end{question}

\begin{solution}
Oui, c'est l'intersection de $b^*((ab^*)^7)^*$ et de $a^*((ba^*)^3)^*$
\end{solution}

\begin{question}
  $\Lc_3=\{ w\in\{(,)\}^* \mid w \mbox{ est bien parenthèsé} \}$
\end{question}

\begin{solution}
 Non. Sinon on aurait un $n$ de pompage et sur le mot $(^n)^n$ on
 aurait $(^{n+kx})^n$ pour $k>0$ et tout $x$ dans le langage.
\end{solution}

\section{Non équivalence des lemmes de pompages}

Voici trois lemmes de pompage pour un langage $\Lc$~:
\[
\begin{array}{lrcl}
1&\exists n\in \mathbb{N}, \forall u\in\Lc : |u|\geq n & \Rightarrow & \exists v,t,w \in \Sigma^* \hspace{1em} u=vtw \hspace{1em} |t|>0  \hspace{1em} \forall m\in\mathbb{N}\hspace{1em} vt^mw\in\Lc \\
2&\exists n\in \mathbb{N}, \forall rus\in\Lc : |u|\geq n & \Rightarrow & \exists v,t,w \in \Sigma^* \hspace{1em} u=vtw \hspace{1em} |t|>0  \hspace{1em} \forall m\in\mathbb{N}\hspace{1em} rvt^mws\in\Lc \\
3&\exists n\in \mathbb{N}, \forall ru_1\dots u_ns\in\Lc, \forall i : |u_i|\geq 1 &\Rightarrow & \exists 1\leq i<j\leq n \hspace{1em} \forall m\in\mathbb{N}\hspace{1em} ru_1\dots u_{i-1}(u_i\dots u_j)^mu_{j+1}\dots u_ns \in \Lc \\
\end{array}
\]

\begin{question}
  Montrer que $\Lc=\{ w\in\{a,b\}^* \mid |w|_a = |w|_b \}$ vérifie le
  lemme 1 mais pas le lemme 2.
\end{question}

\begin{solution}
  Pour tout mot de taille supérieure à $1$ on peut trouver une
  alternance $a,b$ et on peut la répéter.

  Supposons qu'il existe $n$, on pose $r=a^n$, $s=\epsilon$, $u=b^n$
  et alors $u$ ne peut pas être découpé comme il faudrait.
\end{solution}

\begin{question}
  Montrer que $\Lc=\{ (ab)^n(cd)^n \mid n\in\mathbb{N} \}\cup \Sigma^*
  (aa+bb+cc+dd+ac+bd)\Sigma^* $ vérifie le lemme 2 mais pas le lemme
  3.
\end{question}

\begin{solution}
  Soit $rus\in \Ls$ avec $|u|\geq 5$.

  Soit $rus\in \Sigma^* aa + bb + cc + dd + ac + bd\Sigma^*$ et $rus =
  wxyv$ avec $w,v$ des mots et $x,y$ une paire de lettre de
  $aa+bb+cc+dd+ac+bd$. Comme $|u|\geq 3$ alors $u$ contient une lettre
  qui n'est pas $x$ ou $y$ et peut être retirée ou multipliée.

  Soit $rus =(ab)^k(cd)^k$ et donc $u$ contient $bab$ ou $cdc$ en
  prenant $t=a$ ou $t=d$ on obtient le résultat attendu car on a, soit
  un symbole $bb$ ou $cc$ quand $m=0$, soit le mot original quand
  $m=1$ soit $aa$ ou $dd$ quand $m\geq 2$.


  
  Soit $n\in \mathbb{N*}$. On pose $r=\epsilon$, $u_i=(ab)$ et
  $s=(cd)^n$ et le lemme 3 ne tient plus, car $(ab)^{n+(j-i-1)\times
    k}(cd)^n$ n'appartient pas au language pour $k\neq 1$.
\end{solution}
  
\section{Algorithme de Brzozowski}

Soit $\Ls$ un langage régulier sur l'alphabet $\Sigma$ et soit
$\A=<\Q,\Sigma,\delta,i,\F>$ un automate déterministe qui reconnaît
$\Ls$ tel que tous les états de $\A$ soient accessibles depuis $i$.

\begin{question}
Montrer que $Rev(\Ls)=\{ a_n \dots a_1 \mid a_1\dots a_n \in\Ls \}$
est reconnu par l'automate (non déterministe)
$Rev(\A)=<\Q,\Sigma,\delta',\F,\{i\}>$ où $v\in\delta'(q,c) \Leftrightarrow \delta(v,c)=q$.
\end{question}

\begin{solution}
Étant donné un mot $v_1\dots v_n$, tout parcours $q_1, q_2, \dots q_n$
dans l'automate $\A$ est équivalent à un parcours inversé $q_n, \dots, q_2, q_1$
dans $\A'$ (i.e. $\tilde{\delta}(q_1,v_1\dots v_i)=q_i \Leftrightarrow
\tilde{\delta'}(q_i,v_i\dots v_1)=q_1$).
Un parcours est acceptant dans $\A$ si et seulement si son renversé
est acceptant dans $\A'$ ($q_1=i$ et $q_n\in\F$). Donc $Rev(\A)$
accepte bien $Rev(\Ls)$.
\end{solution}

\begin{defi}
Étant donné un automate non déterministe  $\B=<\Q_\B,\Sigma,\delta_\B,\I_\B,\F_\B>$ On
note $Det(\B)$ l'automate obtenu par la construction par sous-ensemble.
On a $Det(\B)=<2^{\Q_{\B}},\Sigma,2^{\delta_\B},\I_\B,\{ q\in2^{\Q_\B} \mid q\cap
\F_\B\neq\emptyset\}>$) avec $2^{\delta_\B}(e,v)=\bigcup_{q\in e}\delta_\B(q,v)$.
\end{defi}

\begin{question}
\label{lem:det}
  Montrer que dans $Det(\B)=<2^{\Q_\B},\Sigma,2^{\delta_\B},\I_\B,\{ q\in2^{\Q_\B} \mid
q\cap \F_\B\neq\emptyset\}>$ on a~: $q\in \tilde{2^{\delta_\B}}(\I_\B,w_1\dots w_n)$
 équivalent à l'existence de $q_1, \dots ,q_n,q_{n+1}$ avec
$q_1\in\I_\B$, $q_{n+1}=q$ et $q_{i+1}\in \delta_\B(q_i,w_i)$.
\end{question}

\begin{solution}
  Par récurrence sur $n$, montrons l'existence de $q_1\dots q_{n+1}$~:
  \begin{itemize}
  \item pour $n=0$, $q_1=q$ convient;
  \item pour $n>0$ on a $q\in\tilde{2^{\delta_\B}}({\I_\B},w_1\dots w_n
    w_{n+1})$ qui nous donne par définition de $2^{\delta_\B}$, $q_{n+1}\in
    \tilde{2^{\delta_\B}}({\I_\B},w_1\dots w_n)$ tel que
    $q\in{\delta_\B}(q_{n+1},w_{n+1})$. On trouve alors $q_1\dots q_{n+1}$
    par récurrence et $q_1\dots q_{n+1}q_{n+2}$ avec $q_{n+2}=q$
    convient.
  \end{itemize}

  Maintenant s'il existe $q_1\dots q_{n+1}$, alors par itération sur
  $i$ que $q_{i+1}\in\tilde{2^{\delta_\B}}(I,w_1\dots w_{i})$on a~:
\begin{itemize}
\item $q_1\in I$ et donc $q_1\in\tilde{2^{\delta_\B}}({\I_\B},\epsilon)$
\item  $\tilde{2^{\delta_\B}}({\I_\B},w_1\dots w_{i+1}) =
  \bigcup_{e\in\tilde{2^{\delta_\B}}({\I_\B},w_1\dots w_{i})} {\delta_\B}(e,w_{i+1})$ or $q_i\in\tilde{2^{\delta_\B}}({\I_\B},w_1\dots w_{i})$ donc $q_{i+1}\in\tilde{2^{\delta_\B}}({\I_\B},w_1\dots w_{i+1})$
\end{itemize}
  
\end{solution}

\begin{defi}
On pose $leftEquiv(x,y) = \forall z : (zx\in\Ls)\Leftrightarrow (zy\in\Ls)$ 
\end{defi}

\begin{question}
Soit $Det(Rev(\A))=<\Q_d,\Sigma,\delta_d,i_d,\F_d>$. Montrer que pour
tout $x,y\in (\Sigma^*)^2$ on a~: $$LeftEquiv(x,y) \Rightarrow (
\tilde{\delta_d}(i_d,rev(x))=\tilde{\delta_d}(i_d,rev(y)) )$$
\end{question}

\begin{solution}
  
  Soient $x$ et $y$ tels que $Q_x=\delta_d(i_d,x)\neq
  \delta_d(i_d,y)=Q_y$. On a $Q_x\setminus Q_y\neq \emptyset$ ou
  $Q_y\setminus Q_x\neq \emptyset$ et donc par symétrie entre $x$ et
  $y$ on peut choisir $q\in Q_x\setminus Q_y$.
  Comme tous les états de $\A$ sont accessibles, on a $z$ tel que
  $\tilde{\delta}(i,z)=q$.

  Soit $w\in\{x,y\}$ avec $w=w_1\dots w_n$.  Un mot $zw = zw_1\dots
  w_l$ est dans $\Ls$ quand
  $\tilde{\delta}(i,zw)=\tilde{\delta}(q,w)\in \F$ et donc il existe
  $q_1,\dots, q_{l+1}$ avec $q_1=q$, $q_{l+1}\in \F$ et
  $q_i=\tilde{\delta}(q,w_1\dots w_i)$. D'après
  l'exercice~\ref{lem:det}, un tel parcours n'existe que pour $x$ car
  il correspondrait à un parcours renversé dans $Det(Rev(\Ls))$.
 

\end{solution}

\begin{question}
En déduire à l'aide du théorème de Myhill--Nerode que $Det(Rev(\Ls))$
est l'automate minimal reconnaissant $Rev(\Ls)$.

\emph{Rappel : Étant donné un langage $\Lc$ on peut regarder la relation
  d'équivalence $RightEquiv(x,y) = \forall z: xz \in \Lc \Leftrightarrow
  yz \in \Lc$. Le théorème de Myhill--Nerode dit que tout automate
  reconnaissant le langage contient au moins autant d'états que le
  nombre de classes d'équivalence.}
\end{question}

\begin{question}
En déduire une construction de l'automate minimal reconnaissant $\Ls$.
\end{question}

\begin{solution}
  $Det(Rev(Det(Rev(A))))$ est minimal et reconnaît
  $Rev(Rev(\Ls))=\Ls$.
\end{solution}
  
\begin{question}
  Quelle est la complexité de cette construction ?
\end{question}
\begin{solution}
  L'automate minimal résultant est forcément plus petit que l'automate
  mais la taille de l'automate déterministe (minimal) du langage
  renversé peut exploser (au pire $2^n$). Par exemple pour~:

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

 
\end{solution}

\end{document}
