\documentclass[12pt]{article}

\usepackage{latexsym,amsfonts,amsmath}
\usepackage[english,french]{babel}
\usepackage[utf8]{inputenc}
\usepackage[a4paper,text={16cm,23.7cm},centering]{geometry}
\usepackage{tikz}
\usepackage{shuffle}
\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\pair#1{[#1]}
\def\ppair#1{[\![#1]\!]}
\def\Nat{\mathrm{I\!N}}
\def\sm{\sqsubseteq}
\def\pk#1{\chi(#1)}
\def\pkinv#1{\chi^{-1}(#1)}

\def\A{\mathcal{A}}
\def\O{\mathcal{O}}
\def\L{\mathcal{L}}
\def\eps{\varepsilon}

\begin{document}

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

\begin{center}
{\Huge Langages Formels} \\[2ex]
{\LARGE Licence Informatique -- ENS Paris-Saclay} \\[1ex]
{\Large Partiel du 18 mars 2021}
\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{Automates et arithmétique}

Soit $\Sigma=\{0,1\}$. On interprète un mot $w\in\Sigma^*$ de longueur paire
comme une paire d'entiers, c'est à dire si $w=a_0b_0a_1b_1\cdots a_nb_n$,
on note $\pair{w}=\tup{a,b}$, où $a=\sum_{k=0}^na_k\cdot 2^k$ et $b$ analogue.
Par convention $\pair{\eps}=\tup{0,0}$. D'ailleurs on note $A(w)=a$ et $B(w)=b$
si $\pair{w}=\tup{a,b}$.

\begin{enumerate}
\item[(a)] Construire un automate quelconque pour
$$L:=\set{w\in\Sigma^{2n}}{n\ge0,\ A(w)+B(w)=0\pmod{2^n}}.$$

\paragraph{Solution:}
On construit un automate qui simule l'addition habituelle de $A(w)$ et $B(w)$.
Les états acceptants exigent que le nombre de lettres est pair et que
la somme donne $0$ sur les $n$ paires de positions évaluées.
Les états $r_0,r_1$ mémorisent la retenue après toute paire de chiffres,
en démarrant avec $r_0$. Les états $i_0,i_1,i_2$ mémorisent la
somme intermédiaire de la retenue et le prochain bit de $A(w)$.
Si la somme de la retenue et de deux bits est impaire, on utilise l'état
poubelle~$p$.

\begin{center}
\scalebox{1}{
\begin{tikzpicture}
\node[draw,circle,initial above,accepting] (0) at (6,4) {$r_0$};
\node[draw,circle,accepting] (1) at (3,4) {$r_1$};
\node[draw,circle] (0p) at (6,2) {$i_0$};
\node[draw,circle] (1p) at (3,2) {$i_1$};
\node[draw,circle] (2p) at (0,2) {$i_2$};
\node[draw,circle] (p) at (3,0) {$p$};
\draw[->]
        (0) edge[bend left] node[right] {$0$} (0p)
        (0) edge[style={pos=0.7}] node[below] {$1$} (1p)
        (1) edge[bend left] node[right] {$0$} (1p)
        (1) edge[bend left=10] node[right] {$1$} (2p)
        (0p) edge[bend left] node[left] {$0$} (0)
        (0p) edge node[right] {$1$} (p)
        (1p) edge node[right] {$0$} (p)
        (1p) edge[bend left] node[left] {$1$} (1)
        (2p) edge[bend left=10] node[left] {$0$} (1)
        (2p) edge node[left] {$1$} (p)
        (p) edge[loop below] node[below] {$0,1$} (p)
;
\end{tikzpicture}
}
\end{center}


\item[(b)] En construire l'automate déterministe complet minimal pour $L$
(ou bien justifier pourquoi votre automate dans (a) est cet automate).

\paragraph{Solution:} L'automate dans (a) est bien détermiste et complet,
et il est aussi minimal. Pour montrer ce dernier, on montre que tout état
tombe dans une classe différente de Nérode:
\begin{itemize}
\item $r_0$ est le seul état à accepter le mot $00$;
\item $r_1$ est le seul état à accepter le mot $10$;
\item $i_0$ est le seul état à accepter le mot $000$;
\item $i_1$ est le seul état à accepter le mot $1$;
\item $i_2$ est le seul état à accepter le mot $001$;
\item $p$ est le seul état à n'accepter aucun mot.
\end{itemize}


\item[(c)] Soient $k,\ell\in\Nat^+$. Montrer que le langage
$$L_{k,\ell}:=\set{w\in\Sigma^{2n}}{n\ge0,\ k\cdot A(w)+\ell\cdot B(w)=0\pmod{2^n}}$$
 est accepté par un automate avec au plus $3\cdot(k+\ell)$ états.

\paragraph{Solution:} On généralise le principe de l'automate de (a), sauf
que les bits de $A(w),B(w)$ possèdent les poids $k,\ell$, respectivement.
Pour chaque pair de lettres, on calcule la somme $s$ de la retenue et ces deux
poids, on exige que $s$ soit paire, et la nouvelle retenue devient $s/2$.
La retenue est désormais entre $0$ et $k+\ell-1$, en effet, elle n'exède
jamais cette borne car $(k+\ell-1)+k+\ell < 2(k+\ell)$. $L_{k,\ell}$ est
donc accepté par l'automate DC $\A_{k,\ell}=\tup{R\cup I\cup\{p\},\delta,r_0,R}$, où
\begin{itemize}
\item $R=\{r_0,\ldots,r_{k+\ell-1}\}$;
\item $I=\{i_0,\ldots,i_{2k+\ell-1}\}$;
\item pour $b=0,1$, $j=0,\ldots,k+\ell-1$, $j'=0,\ldots,2k+\ell-1$:
\begin{itemize}
\item $\delta(r_j,b)=i_{j+kb}$;
\item $\delta(i_{j'},b)=\begin{cases}
i_{({j'}+\ell b)/2} & \hbox{si ${j'}+\ell b$ pair} \\
p & \hbox{sinon}\end{cases}$;
\item $\delta(p,b)=p$.
\end{itemize}
\end{itemize}
On vérifie que $\A_{k,\ell}$ possède $3k+2\ell+1\le 3(k+\ell)$ états
(avec $l\ge1$).
\end{enumerate}

Encore mots de longueur paire, 
si $w=a_0\cdots a_nb_0\cdots b_n$, notons
$\ppair{w}=\tup{a,b}$, avec $a,b$ comme avant,
et $A'(w)=a$, $B'(w)=b$ si $\ppair{w}=\tup{a,b}$.
On définit, pour $k\in\Nat$:
$$L':=\set{w\in\Sigma^{2n}}{n\ge0,\ A'(w)+B'(w)=0\pmod{2^n}}$$
$$L_{k}:=\set{w\in\Sigma^{2n}}{n\ge0,\ A'(w)+B'(w)=0\pmod{2^k}}$$

\begin{enumerate}
\item[(d)] $L'$, est-il reconnaissable ? Et $L_k$, pour $k$ quelconque ?

\paragraph{Solution:}
Supposons que $L'$ est reconnaissable, et soit $N$ la constante du lemme
de l'étoile. On considère $w=0^N10^N1$, alors $|w|=2(N+1)$ et $A'(w)=B'(w)=2^N$
et $A'(w)+B'(w)=0 \pmod{2^{N+1}}$, du coup $w\in L'$. Alors par le lemme de
l'étoile il existe un $k$ t.q.\ $w'=0^{N+k}10^N1\in L'$, et $k$ doit être pair.
Mais $A'(w')=0$ et $B'(w')>0$, alors $w'\notin L'$, ce qui est absurde.
Du coup, $L'$ n'est pas reconnaissable.

Certains ont remarqué que $L_0$ contient tous les mots de longueur paire,
ce qui est reconnaissable (j'aurais voulu écrire $k\in\Nat^+$ \ldots).

Sinon, par un raisonnement similaire, $L_k$ n'est pas reconnaissable pour
$k\ge1$. On considère $w=10^{k-1}0^N1^k0^N$, alors $A'(w)=1$, $B'(w)=2^k-1$,
du coup $w\in L_k$. Par le lemme de l'étoile il existe un $k$ (pair)
t.q.\ $w'=10^{k-1}0^{N+k}1^k0^N\in L_k$. Mais $A'(w')=1$ est impair
et $B'(w')$ est pair, du coup $w'\notin L_k$, ce qui est absurde.
\end{enumerate}

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

\section{Mélange de mots et monoïdes}

Soient $u,v\in\Sigma^*$, pour un alphabet $\Sigma$ quelconque, et 
$K,L\subseteq\Sigma^*$ des langages, et
$\phi\colon\Sigma^*\to M$, $\psi\colon\Sigma^*\to M'$
des morphismes reconnaissant $K$ resp.\ $L$.

Pour rappel, on dit que $u$ est \emph{sous-mot} de $v$, noté $u\sm v$,
si les lettres de $u$ apparaissent dans $v$ dans l'ordre,
c'est à dire
$v=v_0u_1v_1u_2\cdots u_nv_n$
    avec $u_i,v_i\in\Sigma^*$ et $u=u_1u_2\cdots u_n$.

\begin{enumerate}
\item[(a)] En construire un morphisme reconnaissant le langage
 $$K':=\set{v}{\exists u\in K: u\sm v}.$$

\paragraph{Solution:}
Pour $w\in\Sigma^*$, définissons $\ppair{w}:=\set{v}{v\sm w}$.
On voit bien que $\ppair{wa}=\ppair{w}\cup\set{va}{v\sm w}$,
pour $a\in\Sigma$.

On va montrer que $K'$ est accepté par le morphisme
$\phi':\Sigma^*\to2^M$ engendré par $\phi'(a)=\{\phi(\eps),\phi(a)\}$,
pour $a\in\Sigma$, avec l'opération $A\cdot B=\set{ab}{a\in A,b\in B}$.
Cette opération est bien associatif car l'opération sur $M$ l'est,
et son élément neutre est $\{\phi(\eps)\}=:\phi'(\eps)$.

On prouvera par récurrence que pour tout mot $w\in\Sigma^*$,
$\phi'(w)=\phi(\ppair{w})$.
Effectivement, c'est vrai pour tout mot de longueur $0$ ou $1$ par définition.
Soit alors $w$ un mot satisfaisant cette propriété. Alors 

\begin{center}
\begin{tabular}{rcl}
$\phi'(wa) = \phi'(w)\cdot\phi'(a)$ & $=$ &
	$\phi(\ppair{w})\cdot\{\phi(\eps),\phi(a)\}$ \\
& $=$ & $\phi(\ppair{w})\cup\set{\phi(va)}{v\sm w} = \phi(\ppair{wa})$
\end{tabular}
\end{center}

Pour conclure, montrons que $w\in K'$ ssi $\phi'(w)\cap\phi(K)\ne\emptyset$.
Effectivement, ceci est le cas ssi $\exists u\in\phi'(w)$ t.q. $\phi(u)\in\phi(K)$ ssi $u\sm w$ et $u\in K$.

\end{enumerate}

Le \emph{mélange} $u\shuffle v$ désigne l'ensemble des mots
qu'on obtient en intercalant $u$ et $v$:
$$u\shuffle v=\set{u_1v_1\cdots u_kv_k}{k\ge0,\ \forall i:u_i,v_i\in\Sigma^*,\ u_1\cdots u_k=u,\ v_1\cdots v_k=v}$$
On étend cette notion aux langages avec $K\shuffle L=\bigcup\set{u\shuffle v}{u\in K,\ v\in L}$.

\begin{enumerate}
\item[(b)] En construire un morphisme reconnaissant le langage $K\shuffle L$.

\paragraph{Solution:}
Le raisonnement est similaire à celui de (a) -- en effet on pourrait obtenir
le résultat de (a) comme un cas spécial de (b).

Définissons alors $\ppair{w}=\set{\tup{u,v}}{w\in u\shuffle v}$.
On voit bien $\ppair{\eps}=\{\tup{\eps,\eps}\}$ et
$\ppair{wa}=\set{\tup{ua,v},\tup{u,va}}{\tup{u,v}\in\ppair{w}}$.

Construisons $\chi:\Sigma^*\to2^{M\times M'}$ engendré par
$\chi(a):=\{\tup{\phi(a),\psi(\eps)},\tup{\phi(\eps),\psi(a)}\}$
avec l'opération $A\cdot B:=\set{\tup{ab,a'b'}}{\tup{a,a'}\in A,\tup{b,b'}\in B}$. De nouveau, l'associativité suit de celle de $M$ et $M'$, et son élément neutre est $\{\tup{\phi(\eps),\psi(\eps)}\}=:\chi(\eps)$.

Prouvons par récurrence que
$\chi(w)=\set{\tup{\phi(u),\psi(v)}}{\tup{u,v}\in\ppair{w}}$.
Encore c'est vrai par définition pour les motsde longueur au plus 1.
Soit $w$ un mot satisfaisant la propriété, alors

\begin{center}
\begin{tabular}{rcl}
$\chi(wa) = \chi(w)\cdot\chi(a)$ & $=$ &
	$\chi(w)\cdot\{\tup{\phi(a),\psi(\eps)}\}
	\cup \chi(w)\cdot\{\tup{\phi(\eps),\psi(a)}\}$ \\
& $=$ &
	$\set{\tup{\phi(ua),\psi(v)},\tup{\phi(u),\psi(va)}}{\tup{u,v}\in\ppair{w}}$\\
& $=$ &
	$\set{\tup{\phi(u'),\psi(v')}}{\tup{u',v'}\in\ppair{wa}}$.
\end{tabular}
\end{center}

Pour montrer que $\chi$ reconnait $K\shuffle L$, on montre que
$w\in K\shuffle L$ ssi $\chi(w)\cap (\phi(K)\times\psi(L))\ne\emptyset$.
Effectivement, ceci est le cas ssi
$\exists u,v$ t.q.\ $\tup{\phi(u),\psi(v)}\in\chi(w)$ et $u\in\phi(K),v\in\psi(L)$ ssi $w\in u\shuffle v$ et $u\in K$, $v\in L$.
\end{enumerate}

Si $\Sigma=\{a_1,\ldots,a_k\}$, on associe à un mot $u$ le $k$-vecteur indiquant
le nombre d'occurrences de toute lettre:
$$\pk{u}:=\tup{|u|_{a_1},\ldots,|u|_{a_k}}$$
Par exemple, $\pk{abad}=\tup{2,1,0,1}$ si $\Sigma=\{a,b,c,d\}$.
Pour un langage $K$, on note $\pk{K}=\set{\pk{u}}{u\in K}$.
On utilise l'addition et multiplication scalaire habituelle entre vecteurs.
Un vecteur de base est $1$ dans une seule dimension et $0$ dans les autres.

Un ensemble $S\subseteq\Nat^k$ de vecteurs est \emph{linéaire}
s'il existe des vecteurs $x_0,x_1,\ldots,x_n$ t.q.
$$S=\set{x_0+b_1x_1+\cdots+b_nx_n}{b_1,\ldots,b_n\in\Nat}$$
D'ailleurs, $S$ est \emph{ultralinéaire} si $x_0,x_1,\ldots,x_n$
sont des vecteurs de base et \emph{semilinéaire} si $S$ est une union
fini d'ensembles linéaires.

\begin{enumerate}
\item[(c)] Soit $S$ un ensemble (i) ultralinéaire (ii) linéaire (iii) semilinéaie. En général, $\pkinv{S}$ est-il reconnaissable ?

\paragraph{Solution:}
\begin{enumerate}
\item[(i)] Ultralinéaire: (J'aurais voulu écrire que $x_1,\ldots,x_n$ sont
des multiples de vecteurs de base, sans contrainte sur $x_0$, mais ma cervelle
ne fonctionnait plus. Heureusement, ce ne fait pas une grande différence.)

Soit alors $S$ ultralinéaire et
soient $a_{j_0},\ldots,a_{j_n}$ les lettres de $\Sigma$ que $x_i$ égale 1
dans sa $j_i$-ème dimension, pour $i=0,\ldots,n$. Alors tout mot dans
$\pkinv{S}$ contient au moins une occurrence de $a_{j_0}$ et des nombres
arbitraires des lettres das $\{a_{j_1},\ldots,a_{j_n}\}$ (le fait que plusieurs
lettres dans cet ensemble peuvent être identiques ne change rien).
Du coup $\pkinv{S}$ est le langage de l'expression régulière
$\sum_{i=1}^n a_{j_i}\cdot a_{j_0} \cdot \sum_{i=1}^n a_{j_i}$ et est
donc reconnaissable.

\item[(ii)] Linéaire: Considérons le cas $k=2$. L'ensemble
$S=\set{\tup{0,0}+b_1\cdot\tup{1,1}}{b_1\in\Nat}$ est linéaire,
et $\pkinv{S}\cap a^*b^*=\set{a^nb^n}{n\ge0}$. Comme ce dernier n'est
pas reconnaissable mais $a^*b^*$ l'est, alors $\pkinv{S}$ ne peut pas
être reconnaissable.

\item[(iii)] Les ensembles linéaires étant un cas spécial des semilinéaires,
le résultat négatif de (ii) s'étend à ce cas aussi.
\end{enumerate}

\item[(d)] Montrer que pour tout ensemble semilinéaire $S$ il existe
un langage reconnaissable $L$ tel que $\pk{L}=S$.

\paragraph{Solution:}
Pour un vecteur $x=\tup{x_1,\ldots,x_k}\in\Nat^k$, définissions le mot
$\alpha(x)=a_1^{x_1}\cdots a_k^{x_k}$. Regardons d'abord le cas où
$S$ est linéaire, de la forme
$S=\set{x_0+b_1x_1+\cdots+b_nx_n}{b_1,\ldots,b_n\in\Nat}$.
Soit $L:=\L(\alpha(x_0)\cdot\alpha(x_1)^*\cdots\alpha(x_n)^*)$,
alors $\pk{L}=S$.

Pour un ensemble semilinéaire, le résultat suit du fait que les langages
reconnaissables sont clos sous l'union fini.
\end{enumerate}

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

\end{document}
