\documentclass[12pt]{article}

\usepackage{latexsym,amsfonts,amsmath}
\usepackage[english,french]{babel}
\usepackage[utf8]{inputenc}
\usepackage[a4paper,text={16cm,23.7cm},centering]{geometry}
\usepackage{tikz}
\usetikzlibrary{automata, positioning, arrows}
\tikzset{->,
        >=stealth,
        node distance=2cm,
        every state/.style={thick},
        initial text=$ $
}

\parindent=0cm
\parskip=2ex

\def\diff#1{\marginpar{\raggedleft{\scriptsize [#1]}}}
\def\tup#1{\btup{}{#1}}
\def\bt#1{\btup{\big}{#1}}
\def\btup#1#2{#1\langle{#2}#1\rangle}
\def\set#1#2{\bset{}{\mathrel}{#1}{#2}}
\def\bigs#1#2{\bset{\big}{\bigm}{#1}{#2}}
\def\bset#1#2#3#4{#1\{\,#3 #2| #4\,#1\}}

\def\A{\mathcal{A}}
\def\O{\mathcal{O}}
\def\L{\mathcal{L}}
\def\sp#1{[#1]}
\def\eps{\varepsilon}
\def\cp#1{\overline{#1}}

\begin{document}

%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%

\begin{center}
{\Huge Langages Formels} \\[2ex]
{\LARGE Licence Informatique -- ENS Paris-Saclay} \\[1ex]
{\Large Contrôle du 20 mai 2020 -- partie 1}
\end{center}

\emph{Toutes les réponses devront être correctement justifiées.\\
Le chiffre en regard d’une question est une indication sur sa difficulté ou sa longueur.}

%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%

\section{Reconnaissance de suffixes}

La proposition suivante était donnée sans preuve pendant la présentation
sur l'analyse syntaxique:

\emph{Soit $w=a_1\cdots a_n\in\Sigma^*$.
L'automate déterministe minimal complet $\A_w$ reconnaissant
$\Sigma^*w$ possède $n+1$ états.}

\begin{enumerate}
\item[(a)] Prouver que $\A_w$ possède au moins $n+1$ états. \diff{2}

\item[(b)] Prouver que $\A_w$ possède au plus $n+1$ états. \diff{3}

\end{enumerate}

%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%

\paragraph{Solution:}

Notons $L:=\Sigma^*w$, et soit
$w_i$ le préfixe de $w$ de longueur $i$ et $w'_i$ le suffixe
de $w$ de longueur $n-i$ (donc à partir de $a_{i+1}$), pour $i=0,\ldots,n$.

\begin{enumerate}
\item[(a)]
Le mot le plus court de $L$ est bien $w$, avec $|w|=n$.
Supposons que $\A_w$ possède au plus $n$ états, alors on va prouver que
$\A_w$ accepte un mot plus court que $w$, une contradiction.
Deux variantes pour ce faire:

%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%

\textit{Preuve par théorie de graphes :}

Puisque $L$ n'est pas vide, $\A_w$ possède un état acceptant et accessible.
Cet état est accessible par un calcul de longueur au plus $n-1$, du coup
$w$ n'est pas le mot le plus court accepté.

%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%

\textit{Preuve par lemme d'étoile / principe de tiroirs :}

Le calcul unique et acceptant pour $w$ dans $\A_w$ comporte $n+1$ états.
Il existent alors $w_i,w_j$, $i<j$ tels que les calculs de $w_i$ et $w_j$
mènent au même état. Du coup,
$\A_w$ accepte aussi $w_iw'_j$, alors que ce mot est plus court que $w$.

%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%

\item[(b)]
Pour tout mot $u\in\Sigma^*$, notons $\sp u$ le plus long suffixe
de $u$ qui est aussi un préfixe de $w$. Puisque le mot vide est préfixe
et suffixe de tout autre mot, un tel suffixe existe pour tout $u$.
La longueur de $\sp u$ est alors entre 0 et $n$, et $u\in L$
ssi $\sp u=w$.

%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%

\textit{Preuve par résidu :}

Soient $u,v\in\Sigma^*$ tels que $\sp u=\sp v=:x$, il existent alors
$u',v'$ avec $u=u'x$ et $v=v'x$.
On montre l'inclusion de $u^{-1}L$ dans $v^{-1}L$,
l'autre sens étant symmétrique :
Soit donc $y\in u^{-1}L$, alors $uy=u'xy\in L$. Dans ce cas, $w$ doit être
suffixe de $xy$, sinon $u$ posséderait un suffixe plus long que $x$ qui
serait préfixe de $w$. Mais si $w$ est suffixe de $xy$, il l'est aussi
de $vy=v'xy$, alors $y\in v^{-1}L$. 

Le residu de tout mot $u$ est donc déterminé par $\sp u$. Le nombre
de résidus de $L$ est donc borné par $n+1$. Puisque $\A_w$ est identique
aux automates des résidus, cela conclut la preuve.

%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%

\textit{Preuve par construction d'un automate :}

Une autre possibilité pour la preuve consiste en définissant un automate
déterministe complet avec $n+1$ états : $\A:=\tup{\Sigma,\{w_0,\ldots,w_n\},\delta,\eps,\{w\}}$ avec $\delta(w_i,a)=\sp{w_i a}$. On montre 
que cet automate accepte $L$ en prouvant que $\A$ satisfait
$\forall u:\delta(\eps,u)=\sp u$, par récurrence sur $|u|$.
\begin{itemize}
\item Le cas $|u|=0$ est trivial: $\delta(\eps,\eps)=\eps=\sp\eps$.
\item Supposons que l'hypothèse tient pour $u\in\Sigma^*$, et soit $a\in\Sigma$,
 on souhaite alors prouver $\delta(\eps,ua)=\sp{ua}$.
 En appliquant l'hypothèse, on a
  $$\delta(\eps,ua)=\delta(\delta(\eps,u),a)=\delta(\sp u,a)=\sp{\sp{u}a}.$$
 Il reste à prouver $x:=\sp{ua}=\sp{\sp{u}a}=:y$, il suffit d'en comparer
 la longueur.
\begin{itemize}
\item $\sp{u}$ est suffixe de $u$, alors tout suffixe de $\sp{u}a$ est aussi
  suffixe de $ua$, ce qui implique $|y|\le|x|$.
\item Si $\sp{ua}=\eps$, alors $|x|\le|y|$ suit trivialement. Si $\sp{ua}=u'a$,
 alors $u'$ est suffixe de $u$ et préfixe de $w$.
  Par définition $|u'|\le|\sp u|$, du coup $u'a$ est aussi suffixe de $\sp ua$,
  alors $|x|\le |y|$.
\end{itemize}
\end{itemize}
\end{enumerate}

%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%

\section{Reconnaissable ou pas ?}

Soit $\Sigma=\{0,1\}$. Pour $w\in\Sigma^*$, définissons $\cp{w}$
comme le mot où tous les 0 ont été remplacés par des 1 et l'inverse,
p.ex.\ $\cp{01011}=10100$.

Les propositions suivantes, sont-elles vraies en général ?

%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%

\begin{enumerate}
\item[(a)] Si $L\subseteq\Sigma^*$ est réconnaissable, alors 
	\diff{4}
	$L_1:=\set{w}{\cp{w}w\in L}$ est reconnaissable.

\paragraph{Solution :}

$L_1$ est bien reconnaissable.

%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%

\textit{Preuve par construction d'automate :}

Soit $\A=\tup{\Sigma,Q,\delta,q_0,F}$ un automate déterministe complet
qui reconnait $L$.
On construit un automate $\A'$ qui, avant de lire
un mot $w$, devine un état~$q$ que $\A$ attendrait après avoir lu $\cp w$.
Il fait ensuite, en parallèle, le calcul de $\cp w$ depuis un état initial
et de $w$ depuis $q$. À la fin, il vérifie que le premier calcul a effectivement
atteint $q$ et que le deuxième a atteint un état final (dans quel cas il existe
bien un calcul acceptant pour $\cp ww$ dans $\A$). $\A'$ est non-déterministe
car il possède plusieurs états d'entrée, mais ses transitions sont
déterministes et complètes.  Formellement,

$$\A'=\tup{\Sigma,Q^3,\eta,I,G}$$
$$I=\set{\tup{q_0,q,q}}{q\in Q}$$
$$\eta(\tup{q_1,q,q_2},a)=\tup{\delta(q_1,\cp{a}),q,\delta(q_2,a)}$$
$$G=\set{\tup{q,q,q_f}}{q\in Q,q_f\in F}$$

%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%

\textit{Construction directe d'un automate déterministe :}

Soit $\A=\tup{\Sigma,Q,\delta,q_0,F}$ un automate déterministe complet
qui reconnait $L$. L'idée est similaire à celle d'avant, mais au lieu
de deviner un état `au milieu', on les traque tous, sous forme d'un
endomorphisme. On obtient donc

$$\A''=\tup{\Sigma,Q\times Q^Q,\theta,\tup{q_0,\mathbf{id}_Q},H}$$
$$H=\set{\tup{q,f}}{q\in Q, f(q)\in F}$$
$$\theta(\tup{q,f},a)=\tup{\delta(q,\cp a),f'}
	\hbox{\quad avec $f'(q'):=\delta(f(q'),a)$ pour tout $q'\in Q$}$$

%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%

\textit{Preuve par monoïde :}

Soit $\tup{M,\cdot,e}$ un monoïde reconnaissant $L$ avec homomorphisme $f$
et que $f(L)=M'\subseteq M$. On a $u\in L_1$ ssi $f(\cp u)\cdot f(u)\in M'$.
On construit donc un monoïde et homomorphisme qui associe $u$ à
$\tup{f(\cp u),f(u)}$. Concrètement $\tup{M^2,\circ,\tup{e,e}}$
avec $\tup{m_1,m_2}\circ\tup{m'_1,m'_2}=\tup{m_1\cdot m'_1,m_2\cdot m'_2}$
et $f'(a)=\tup{f(\cp a),f(a)}$, pour $a\in\Sigma$. Notons
$M'':=\set{\tup{m_1,m_2}\in M^2}{m_1\cdot m_2\in M'}$.
Alors $f'(w)\in M''$ ss'il existent $m_1,m_2\in M$ t.q. $f(\cp w)=m_1$,
$f(w)=m_2$ et $f(\cp ww)=m_1\cdot m_2\in M'$ ssi
$\cp ww\in L$.

\bigskip

%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%

\item[(b)] Si $L\subseteq\Sigma^*$ est réconnaissable, alors
	\diff{2}
	$L_2:=\set{\overline{w}w}{w\in L}$ est reconnaissable.

%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%

\paragraph{Solution :}

L'affirmation est fausse. P.ex., si $L=1^*=\set{1^n}{n\ge0}$,
alors $L_2=\set{0^n1^n}{n\ge0}$, un langage connu comme non-reconnaissable.

\end{enumerate}

\bigskip

%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%

Par $w[i]$ on note la $i$-ème lettre de $w$.
%
Pour un $d\ge1$ fixé, soit $$L_3:=\bigs{uv\in\Sigma^*}{|u|=|v|=d\land \exists i:1\le i\le d\land u[i]=v[i]}.$$
\begin{enumerate}
\item[(c)] Montrer qu'il existe un automate non-déterministe reconnaissant
 \diff{2}
 $L_3$ avec $\O(d^2)$ états.

%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%

\paragraph{Solution :} \ 

\textit{Dessin d'un automate partiel :}

Notons $L'_i:=\set{uv\in\Sigma^*}{|u|=|v|=d\land u[i]=v[i]}$.
Clairement, $L_3=\bigcup_{i=1}^d L'_i$. Il suffit alors de construire
un automate pour $L'_i$ de taille $\O(d)$, comme suite :

\bigskip

\begin{tikzpicture}
\node[state, initial] (q0) {$q_0$};
\node[state, right of=q0] (q1) {$q_1$};
\node[state, right of=q1] (qi) {$q_{i-1}$};
\node[state, above right of=qi] (r1) {$r_1$};
\node[state, below right of=qi] (s1) {$s_1$};
\node[state, right of=r1] (r2) {$r_2$};
\node[state, right of=s1] (s2) {$s_2$};
\node[state, right of=r2] (rd) {$r_d$};
\node[state, right of=s2] (sd) {$s_d$};
\node[state, below right of=rd] (ti) {$t_{i}$};
\node[state, accepting, right of=ti] (td) {$t_d$};

\draw   
	(q0) edge[above] node{$\Sigma$} (q1)
	(q1) edge[above,dashed] node{$\Sigma$} (qi)
	(qi) edge[above] node{$0$} (r1)
	(qi) edge[below] node{$1$} (s1)
	(r1) edge[above] node{$\Sigma$} (r2)
	(s1) edge[below] node{$\Sigma$} (s2)
	(r2) edge[above,dashed] node{$\Sigma$} (rd)
	(s2) edge[above,dashed] node{$\Sigma$} (sd)
	(rd) edge[above] node{$0$} (ti) 
	(sd) edge[below] node{$1$} (ti) 
	(ti) edge[above,dashed] node{$\Sigma$} (td)
	;
\end{tikzpicture}

\newpage

%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%

\textit{Construction directe formelle :}

Notons $D:=\{1,\ldots,d\}$, $D':=D\setminus\{d\}$.\\
On construit un automate $\A=\tup{\Sigma,Q,T_1\cup T_2\cup T_3,q_0,\{t_d\}}$, avec :

$$Q=\set{q_{i-1},t_i}{i\in D}
	\cup \set{\tup{i,j,a}}{i,j\in D,\ a\in\Sigma}$$

$$T_1=\bigs{\tup{q_{i-1},a,q_i},\ \tup{t_i,a,t_{i+1}}}{i\in D',\ a\in\Sigma}$$
$$T_2=\bigs{\bt{q_{i-1},a,\tup{i,1,a}},\ \bt{\tup{i,d,a},a,t_i}}{i\in D,\ a\in\Sigma}$$
$$T_3=\bigs{\bt{\tup{i,j,a},b,\tup{i,j+1,a}}}{i\in D,\ j\in D',\ a,b\in\Sigma}$$

Par rapport à la solution précédente, cet automate implémente directement
l'union des
automates pour tous les $L'_i$, où les états de la forme $\tup{i,j,0},\tup{i,j,1}$ jouent les rôles de $r_j$ resp $s_j$ dans l'automate pour $L'_i$.

%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%

\item[(d)] Montrer que tout automate déterministe reconnaissant $L_3$
  \diff{3}
  possède au moins $2^d$ états.

%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%

\paragraph{Solution :} \ 

\textit{Non-existence d'un automate plus petit :}

Par contradiction, soit $\A$ un automate déterministe 
reconnaissant $L_3$ avec moins de $2^d$ états. Cet automate
possède un calcul pour tout mot $u\in\Sigma^d$ car $uu\in L_3$.
Par principe de
tiroirs, il existe donc deux mots différents $u,v\in\Sigma^d$
dont le calcul dans $\A$ mène au même état~$q$, et soit $j$ une
position qui distingue $u$ et $v$ : $u[j]\ne v[j]$.

On constate que $u\cp v\in L_3$ car $u[j]=\cp v[j]$. Du coup, $\A$
accepte $\cp v$ depuis $q$, alors $\A$ accepte aussi $v\cp v$.
Or, $v\cp v\notin L_3$.

%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%

\textit{Preuve par résiduel :}

Le raisonnement ci-dessus prouve en effet que $u$ et $v$ n'ont
pas le même résidu. On peut s'en servir directement :

Soient $u,v\in\Sigma^d$ deux mots distincts, on prouve que
$u^{-1}L_3\ne v^{-1}L_3$. En effet, $\cp v\in u^{-1}L_3\setminus v^{-1}L_3$
car il existe un $j$ tel que $u[j]\ne v[j]$, donc $u\cp v\in L_3$
et $v\cp v\notin L_3$. Du coup $L_3$ possède
au moins $|\Sigma^d|=2^d$ résidus non-vides distincts,
ce qui implique le résultat.

\end{enumerate}

\end{document}
