path: root/controle-20230615.tex

%% This is a LaTeX document.  Hey, Emacs, -*- latex -*- , get it?
\documentclass[12pt,a4paper]{article}
\usepackage[a4paper,margin=2.5cm]{geometry}
\usepackage[francais]{babel}
\usepackage[utf8]{inputenc}
\usepackage[T1]{fontenc}
%\usepackage{ucs}
\usepackage{times}
% A tribute to the worthy AMS:
\usepackage{amsmath}
\usepackage{amsfonts}
\usepackage{amssymb}
\usepackage{amsthm}
%
\usepackage{mathrsfs}
\usepackage{wasysym}
\usepackage{url}
%
\usepackage{graphics}
\usepackage[usenames,dvipsnames]{xcolor}
\usepackage{tikz}
\usetikzlibrary{arrows,automata,positioning}
\usepackage{hyperref}
%
\theoremstyle{definition}
\newtheorem{comcnt}{Tout}
\newcommand\thingy{%
\refstepcounter{comcnt}\smallskip\noindent\textbf{\thecomcnt.} }
\newcommand\exercice{%
\refstepcounter{comcnt}\bigskip\noindent\textbf{Exercice~\thecomcnt.}\par\nobreak}
\renewcommand{\qedsymbol}{\smiley}
%
\DeclareUnicodeCharacter{00A0}{~}
\DeclareUnicodeCharacter{03B5}{$\varepsilon$}
%
\DeclareMathSymbol{\tiret}{\mathord}{operators}{"7C}
\DeclareMathSymbol{\traitdunion}{\mathord}{operators}{"2D}
%
%
\DeclareFontFamily{U}{manual}{} 
\DeclareFontShape{U}{manual}{m}{n}{ <->  manfnt }{}
\newcommand{\manfntsymbol}[1]{%
    {\fontencoding{U}\fontfamily{manual}\selectfont\symbol{#1}}}
\newcommand{\dbend}{\manfntsymbol{127}}% Z-shaped
\newcommand{\danger}{\noindent\hangindent\parindent\hangafter=-2%
  \hbox to0pt{\hskip-\hangindent\dbend\hfill}}
%
\newcommand{\spaceout}{\hskip1emplus2emminus.5em}
\newif\ifcorrige
\corrigetrue
\newenvironment{corrige}%
{\ifcorrige\relax\else\setbox0=\vbox\bgroup\fi%
\smallbreak\noindent{\underbar{\textit{Corrigé.}}\quad}}
{{\hbox{}\nobreak\hfill\checkmark}%
\ifcorrige\par\smallbreak\else\egroup\par\fi}
\newenvironment{commentaire}%
{\ifcorrige\relax\else\setbox0=\vbox\bgroup\fi%
\smallbreak\noindent{\underbar{\textit{Commentaires.}}\quad}}
{{\hbox{}\nobreak\hfill\maltese}%
\ifcorrige\par\smallbreak\else\egroup\par\fi}
%
%
% NOTE: compile dot files with
% dot2tex --figonly -f tikz --tikzedgelabels --graphstyle=automaton file.dot  > file.tex
\tikzstyle{automaton}=[>=stealth',initial text={},thick,every loop/.style={min distance=7mm,looseness=5}]
\tikzstyle{state}=[]
\tikzstyle{final}=[accepting by arrow]
%
%
%
\begin{document}
\ifcorrige
\title{INF105\\Contrôle de connaissances — Corrigé\\{\normalsize Théorie des langages}}
\else
\title{INF105\\Contrôle de connaissances\\{\normalsize Théorie des langages}}
\fi
\author{}
\date{15 juin 2023}
\maketitle

\pretolerance=8000
\tolerance=50000

\vskip1truein\relax

\noindent\textbf{Consignes.}

Les exercices sont totalement indépendants.  Ils pourront être traités
dans un ordre quelconque, mais on demande de faire apparaître de façon
très visible dans les copies où commence chaque exercice.

\medbreak

L'usage de tous les documents (notes de cours manuscrites ou
imprimées, feuilles d'exercices, livres) est autorisé.

L'usage des appareils électroniques est interdit.

\medbreak

Durée : 1h30

Barème \emph{indicatif} : autant de points pour chaque exercice.

\ifcorrige
Ce corrigé comporte \textcolor{red}{XXX} pages (page de garde incluse).
\else
Cet énoncé comporte \textcolor{red}{XXX} pages (page de garde incluse).
\fi

\vfill

{\tiny\noindent
\immediate\write18{sh ./vc > vcline.tex}
Git: \input{vcline.tex}
\immediate\write18{echo ' (stale)' >> vcline.tex}
\par}

\pagebreak


%
%
%

\exercice

Dans cet exercice, on pose $\Sigma = \{a,b\}$.  On considère les huit
automates suivants
($A_{\mathrm{s}},A_{\mathrm{t}},A_{\mathrm{u}},A_{\mathrm{v}},A_{\mathrm{w}},A_{\mathrm{x}},A_{\mathrm{y}},A_{\mathrm{z}}$)
sur l'alphabet $\Sigma$ :

\begin{center}
\begin{tabular}{|c|c|}
\hline
$A_{\mathrm{s}}$\rule[-2ex]{0pt}{0pt}&
\scalebox{0.85}{%
\begin{tikzpicture}[>=latex,line join=bevel,automaton,baseline=(q0.base)]
\node (q0) at (0bp,0bp) [draw,circle,state,initial] {$0$};
\node (q1) at (60bp,0bp) [draw,circle,state] {$1$};
\node (q2) at (120bp,0bp) [draw,circle,state] {$2$};
\node (q3) at (180bp,0bp) [draw,circle,state] {$3$};
\node (q4) at (240bp,0bp) [draw,circle,state] {$4$};
\node (q5) at (300bp,0bp) [draw,circle,state,final] {$5$};
\draw[->] (q0) -- node[auto]{$a$} (q1);
\draw[->] (q1) -- node[auto]{$b$} (q2);
\draw[->] (q2) -- node[auto]{$a$} (q3);
\draw[->] (q3) -- node[auto]{$b$} (q4);
\draw[->] (q4) -- node[auto]{$b$} (q5);
\end{tikzpicture}
}\\
\hline
$A_{\mathrm{t}}$\rule[-2ex]{0pt}{0pt}&
\scalebox{0.85}{%
\begin{tikzpicture}[>=latex,line join=bevel,automaton,baseline=(q0.base)]
\node (q0) at (0bp,0bp) [draw,circle,state,initial] {$0$};
\node (q1) at (60bp,0bp) [draw,circle,state] {$1$};
\node (q2) at (120bp,0bp) [draw,circle,state] {$2$};
\node (q3) at (180bp,0bp) [draw,circle,state] {$3$};
\node (q4) at (240bp,0bp) [draw,circle,state] {$4$};
\node (q5) at (300bp,0bp) [draw,circle,state,final] {$5$};
\draw[->] (q0) -- node[auto]{$a$} (q1);
\draw[->] (q1) -- node[auto]{$b$} (q2);
\draw[->] (q2) -- node[auto]{$a$} (q3);
\draw[->] (q3) -- node[auto]{$b$} (q4);
\draw[->] (q4) -- node[auto]{$b$} (q5);
\draw[->] (q0) to[loop above] node[auto]{$a,b$} (q0);
\end{tikzpicture}
}\\
\hline
$A_{\mathrm{u}}$\rule[-2ex]{0pt}{0pt}&
\scalebox{0.85}{%
\begin{tikzpicture}[>=latex,line join=bevel,automaton,baseline=(q0.base)]
\node (q0) at (0bp,0bp) [draw,circle,state,initial] {$0$};
\node (q1) at (60bp,0bp) [draw,circle,state] {$1$};
\node (q2) at (120bp,0bp) [draw,circle,state] {$2$};
\node (q3) at (180bp,0bp) [draw,circle,state] {$3$};
\node (q4) at (240bp,0bp) [draw,circle,state] {$4$};
\node (q5) at (300bp,0bp) [draw,circle,state,final] {$5$};
\draw[->] (q0) -- node[auto]{$a$} (q1);
\draw[->] (q1) -- node[auto]{$b$} (q2);
\draw[->] (q2) -- node[auto]{$a$} (q3);
\draw[->] (q3) -- node[auto]{$b$} (q4);
\draw[->] (q4) -- node[auto]{$b$} (q5);
\draw[->] (q5) to[loop above] node[auto]{$a,b$} (q5);
\end{tikzpicture}
}\\
\hline
$A_{\mathrm{v}}$\rule[-2ex]{0pt}{0pt}&
\scalebox{0.85}{%
\begin{tikzpicture}[>=latex,line join=bevel,automaton,baseline=(q0.base)]
\node (q0) at (0bp,0bp) [draw,circle,state,initial] {$0$};
\node (q1) at (60bp,0bp) [draw,circle,state] {$1$};
\node (q2) at (120bp,0bp) [draw,circle,state] {$2$};
\node (q3) at (180bp,0bp) [draw,circle,state] {$3$};
\node (q4) at (240bp,0bp) [draw,circle,state] {$4$};
\node (q5) at (300bp,0bp) [draw,circle,state,final] {$5$};
\draw[->] (q0) -- node[auto]{$a$} (q1);
\draw[->] (q1) -- node[auto]{$b$} (q2);
\draw[->] (q2) -- node[auto]{$a$} (q3);
\draw[->] (q3) -- node[auto]{$b$} (q4);
\draw[->] (q4) -- node[auto]{$b$} (q5);
\draw[->] (q0) to[loop above] node[auto]{$a,b$} (q0);
\draw[->] (q5) to[loop above] node[auto]{$a,b$} (q5);
\end{tikzpicture}
}\\
\hline
$A_{\mathrm{w}}$\rule[-2ex]{0pt}{0pt}&
\scalebox{0.85}{%
\begin{tikzpicture}[>=latex,line join=bevel,automaton,baseline=(q0.base)]
\node (q0) at (0bp,0bp) [draw,circle,state,initial] {$0$};
\node (q1) at (60bp,0bp) [draw,circle,state] {$1$};
\node (q2) at (120bp,0bp) [draw,circle,state] {$2$};
\node (q3) at (180bp,0bp) [draw,circle,state] {$3$};
\node (q4) at (240bp,0bp) [draw,circle,state] {$4$};
\node (q5) at (300bp,0bp) [draw,circle,state,final] {$5$};
\draw[->] (q0) -- node[auto]{$a$} (q1);
\draw[->] (q1) -- node[auto]{$b$} (q2);
\draw[->] (q2) -- node[auto]{$a$} (q3);
\draw[->] (q3) -- node[auto]{$b$} (q4);
\draw[->] (q4) -- node[auto]{$b$} (q5);
\draw[->] (q0) to[loop above] node[auto]{$a,b$} (q0);
\draw[->] (q1) to[loop above] node[auto]{$a,b$} (q1);
\draw[->] (q2) to[loop above] node[auto]{$a,b$} (q2);
\draw[->] (q3) to[loop above] node[auto]{$a,b$} (q3);
\draw[->] (q4) to[loop above] node[auto]{$a,b$} (q4);
\draw[->] (q5) to[loop above] node[auto]{$a,b$} (q5);
\end{tikzpicture}
}\\
\hline
$A_{\mathrm{x}}$\rule[-2ex]{0pt}{0pt}&
\scalebox{0.85}{%
\begin{tikzpicture}[>=latex,line join=bevel,automaton,baseline=(q0.base)]
\node (q0) at (0bp,0bp) [draw,circle,state,initial,accepting below] {$0$};
\node (q1) at (60bp,0bp) [draw,circle,state,accepting below] {$1$};
\node (q2) at (120bp,0bp) [draw,circle,state,accepting below] {$2$};
\node (q3) at (180bp,0bp) [draw,circle,state,accepting below] {$3$};
\node (q4) at (240bp,0bp) [draw,circle,state,accepting below] {$4$};
\node (q5) at (300bp,0bp) [draw,circle,state,accepting below] {$5$};
\draw[->] (q0) -- node[auto]{$a$} (q1);
\draw[->] (q1) -- node[auto]{$b$} (q2);
\draw[->] (q2) -- node[auto]{$a$} (q3);
\draw[->] (q3) -- node[auto]{$b$} (q4);
\draw[->] (q4) -- node[auto]{$b$} (q5);
\end{tikzpicture}
}\\
\hline
$A_{\mathrm{y}}$\rule[-2ex]{0pt}{0pt}&
\scalebox{0.85}{%
\begin{tikzpicture}[>=latex,line join=bevel,automaton,baseline=(q0.base)]
\node (q0) at (0bp,0bp) [draw,circle,state,initial above] {$0$};
\node (q1) at (60bp,0bp) [draw,circle,state,initial above] {$1$};
\node (q2) at (120bp,0bp) [draw,circle,state,initial above] {$2$};
\node (q3) at (180bp,0bp) [draw,circle,state,initial above] {$3$};
\node (q4) at (240bp,0bp) [draw,circle,state,initial above] {$4$};
\node (q5) at (300bp,0bp) [draw,circle,state,initial above,final] {$5$};
\draw[->] (q0) -- node[auto]{$a$} (q1);
\draw[->] (q1) -- node[auto]{$b$} (q2);
\draw[->] (q2) -- node[auto]{$a$} (q3);
\draw[->] (q3) -- node[auto]{$b$} (q4);
\draw[->] (q4) -- node[auto]{$b$} (q5);
\end{tikzpicture}
}\\
\hline
$A_{\mathrm{z}}$\rule[-2ex]{0pt}{0pt}&
\scalebox{0.85}{%
\begin{tikzpicture}[>=latex,line join=bevel,automaton,baseline=(q0.base)]
\node (q0) at (0bp,0bp) [draw,circle,state,initial above,accepting below] {$0$};
\node (q1) at (60bp,0bp) [draw,circle,state,initial above,accepting below] {$1$};
\node (q2) at (120bp,0bp) [draw,circle,state,initial above,accepting below] {$2$};
\node (q3) at (180bp,0bp) [draw,circle,state,initial above,accepting below] {$3$};
\node (q4) at (240bp,0bp) [draw,circle,state,initial above,accepting below] {$4$};
\node (q5) at (300bp,0bp) [draw,circle,state,initial above,accepting below] {$5$};
\draw[->] (q0) -- node[auto]{$a$} (q1);
\draw[->] (q1) -- node[auto]{$b$} (q2);
\draw[->] (q2) -- node[auto]{$a$} (q3);
\draw[->] (q3) -- node[auto]{$b$} (q4);
\draw[->] (q4) -- node[auto]{$b$} (q5);
\end{tikzpicture}
}\\
\hline
\end{tabular}
\end{center}

On définit aussi les douze langages suivants, où $w_0$ désigne le
mot $ababb$ :
\begin{itemize}
\item $L_0 = \varnothing$ : le langage vide.
\item $L_1 = \{w_0\}$ : le langage constitué du seul mot $w_0$.
\item $L_2$ : le langage constitué des mots qui sont un sous-mot de
  $w_0$.
\item $L_3$ : le langage constitué des mots qui ont $w_0$ comme
  sous-mot.
\item $L_4$ : le langage constitué des mots qui sont un facteur de
  $w_0$.
\item $L_5$ : le langage constitué des mots qui ont $w_0$ comme
  facteur.
\item $L_6$ : le langage constitué des mots qui sont un préfixe de
  $w_0$.
\item $L_7$ : le langage constitué des mots qui ont $w_0$ comme
  préfixe.
\item $L_8$ : le langage constitué des mots qui sont un suffixe de
  $w_0$.
\item $L_9$ : le langage constitué des mots qui ont $w_0$ comme
  suffixe.
\item $L_{10} = \{w_0^i : i\in\mathbb{N}\}$ : le langage constitué des
  mots qui sont une répétition d'un nombre quelconque ($i$) de copies
  de $w_0$ (par exemple, $ababbababb$).
\item $L_{11} = \{b^i w_0 a^i : i\in\mathbb{N}\}$ : le langage
  constitué des mots obtenus en précédant $w_0$ d'un nombre
  quelconque ($i$) de copies de la lettre $b$ et en le suivant du même
  nombre de copies de la lettre $a$ (par exemple, $bbababbaa$).
\end{itemize}

\textbf{(a)} Pour chacun des huit automates $A \in \{A_{\mathrm{s}},
A_{\mathrm{t}}, A_{\mathrm{u}}, A_{\mathrm{v}}, A_{\mathrm{w}},
A_{\mathrm{x}}, A_{\mathrm{y}}, A_{\mathrm{z}}\}$, dire lequel ou
lesquels parmi les douze langages $L_0,\ldots,L_{11}$ est celui
reconnu par l'automate $A$.  On ne demande pas de justifier la
réponse.

\begin{corrige}
L'automate $A_{\mathrm{s}}$ reconnaît le langage $L_1 = \{w_0\}$.

L'automate $A_{\mathrm{t}}$ reconnaît le langage $L_9$ des mots ayant
$w_0$ comme suffixe (car un chemin dans $A_{\mathrm{t}}$ finit par un
chemin consommant $w_0$).

L'automate $A_{\mathrm{u}}$ reconnaît le langage $L_7$ des mots ayant
$w_0$ comme préfixe (car un chemin dans $A_{\mathrm{u}}$ commence
par un chemin consommant $w_0$).

L'automate $A_{\mathrm{v}}$ reconnaît le langage $L_5$ des mots ayant
$w_0$ comme facteur (car un chemin dans $A_{\mathrm{u}}$ passe par un
chemin consommant $w_0$).

L'automate $A_{\mathrm{w}}$ reconnaît le langage $L_3$ des mots ayant
$w_0$ comme sous-mot (car un chemin dans $A_{\mathrm{u}}$ consomme les
lettres $a,b,a,b,b$ dans cet ordre, intercalées par un nombre
quelconque de lettres quelconques).

L'automate $A_{\mathrm{x}}$ reconnaît le langage $L_6$ des préfixes
de $w_0$ (car un chemin dans $A_{\mathrm{x}}$ consomme le début
de $w_0$).

L'automate $A_{\mathrm{y}}$ reconnaît le langage $L_8$ des suffixes
de $w_0$ (car un chemin dans $A_{\mathrm{y}}$ consomme la fin
de $w_0$).

L'automate $A_{\mathrm{z}}$ reconnaît le langage $L_4$ des facteurs
de $w_0$ (car un chemin dans $A_{\mathrm{z}}$ consomme un intervalle
de lettres consécutives de $w_0$).

(Les justifications entre parenthèses n'étaient pas demandées.)
\end{corrige}

\textbf{(b)} Pour chacun des sept automates $A \in \{A_{\mathrm{s}},
A_{\mathrm{t}}, A_{\mathrm{u}}, A_{\mathrm{v}}, A_{\mathrm{w}},
A_{\mathrm{x}}, A_{\mathrm{y}}\}$ (cette question-ci n'est pas posée
pour $A_{\mathrm{z}}$), donner une expression rationnelle dénotant le
langage $L$ reconnu par $A$.  On ne demande pas de justifier la
réponse, et il n'est pas obligatoire d'appliquer un algorithme vu en
cours.

\begin{corrige}
L'automate $A_{\mathrm{s}}$ reconnaît le langage dénoté par $ababb$.

L'automate $A_{\mathrm{t}}$ reconnaît le langage dénoté
par $(a|b){*}ababb$.

L'automate $A_{\mathrm{u}}$ reconnaît le langage dénoté
par $ababb(a|b){*}$.

L'automate $A_{\mathrm{v}}$ reconnaît le langage dénoté
par $(a|b){*}ababb(a|b){*}$.

L'automate $A_{\mathrm{w}}$ reconnaît le langage dénoté
par $(a|b){*}a(a|b){*}b(a|b){*}a(a|b){*}b(a|b){*}b(a|b){*}$.

L'automate $A_{\mathrm{x}}$ reconnaît le langage dénoté
par $\underline{\varepsilon}|a|ab|aba|abab|ababb$ (simple énumération
de tous les préfixes de $w_0$) ou, si on préfère, par
$\underline{\varepsilon}|a(\underline{\varepsilon}|b(\underline{\varepsilon}|a(\underline{\varepsilon}|b(\underline{\varepsilon}|b))))$
(obtenue en éliminant les états de $A_{\mathrm{x}}$ dans
l'ordre $5,4,3,2,1,0$).

L'automate $A_{\mathrm{y}}$ reconnaît le langage dénoté
par $\underline{\varepsilon}|b|bb|abb|babb|ababb$ (simple énumération
de tous les suffixes de $w_0$) ou, si on préfère, par
$\underline{\varepsilon}|(\underline{\varepsilon}|(\underline{\varepsilon}|(\underline{\varepsilon}|(\underline{\varepsilon}|a)b)a)b)b$
(obtenue en éliminant les états de $A_{\mathrm{y}}$ dans
l'ordre $0,1,2,3,4,5$).
\end{corrige}

\textbf{(c)} Pour chacun des huit automates $A \in \{A_{\mathrm{s}},
A_{\mathrm{t}}, A_{\mathrm{u}}, A_{\mathrm{v}}, A_{\mathrm{w}},
A_{\mathrm{x}}, A_{\mathrm{y}}, A_{\mathrm{z}}\}$, dire de quel type
d'automate vu en cours (DFA complet, DFA à spécification incomplète,
NFA ou bien NFA à transitions spontanées) est l'automate $A$.  On
donnera à chaque fois le type le plus particulier applicable.

\begin{corrige}
L'automate $A_{\mathrm{s}}$ est un DFA à spécification incomplète (ou
DFAi).

L'automate $A_{\mathrm{t}}$ est un NFA (à cause de la double
transition étiquetée $a$ depuis l'état $0$).

L'automate $A_{\mathrm{u}}$ est un DFA à spécification incomplète (ou
DFAi).

L'automate $A_{\mathrm{v}}$ est un NFA.

L'automate $A_{\mathrm{w}}$ est un NFA.

L'automate $A_{\mathrm{x}}$ est un DFA à spécification incomplète (ou
DFAi).

L'automate $A_{\mathrm{y}}$ est un NFA (à cause des multiples états
initiaux).

L'automate $A_{\mathrm{z}}$ est un NFA.
\end{corrige}

\textbf{(d)} Pour chacun des cinq automates $A \in \{A_{\mathrm{s}},
A_{\mathrm{u}}, A_{\mathrm{v}}, A_{\mathrm{x}}, A_{\mathrm{z}}\}$
(cette question-ci n'est pas posée pour $A_{\mathrm{t}},
A_{\mathrm{w}}, A_{\mathrm{y}}$), donner un DFA complet sans état
inaccessible qui soit équivalent à $A$ (c'est-à-dire, reconnaissant le
langage $L$).  On appliquera un algorithme vu en cours en le nommant.

{\footnotesize Conseil sur la présentation graphique : pour s'éviter
  des maux de tête dans le placement des états (et en éviter aussi au
  correcteur), il est conseillé de commencer par placer
  horizontalement de gauche à droite les états successifs rencontrés
  lors de la consommation du mot $w_0 = ababb$ par l'automate
  construit, et d'ajouter ensuite les autres états éventuellement
  nécessaires.\par}

\begin{corrige}
S'agissant de $A_{\mathrm{s}}$, comme c'est un DFAi, il s'agit
simplement de lui ajouter un état « puits », noté $\bot$ ci-dessous,
où aboutissent toutes les transitions manquantes :
\begin{center}
\scalebox{0.85}{%
\begin{tikzpicture}[>=latex,line join=bevel,automaton,baseline=(q0.base)]
\node (q0) at (0bp,0bp) [draw,circle,state,initial] {$0$};
\node (q1) at (60bp,0bp) [draw,circle,state] {$1$};
\node (q2) at (120bp,0bp) [draw,circle,state] {$2$};
\node (q3) at (180bp,0bp) [draw,circle,state] {$3$};
\node (q4) at (240bp,0bp) [draw,circle,state] {$4$};
\node (q5) at (300bp,0bp) [draw,circle,state,final] {$5$};
\node (qbot) at (300bp,-60bp) [draw,circle,state] {$\bot$};
\draw[->] (q0) -- node[auto]{$a$} (q1);
\draw[->] (q1) -- node[auto]{$b$} (q2);
\draw[->] (q2) -- node[auto]{$a$} (q3);
\draw[->] (q3) -- node[auto]{$b$} (q4);
\draw[->] (q4) -- node[auto]{$b$} (q5);
\draw[->] (q0) to[out=270,in=240] node[auto]{$b$} (qbot);
\draw[->] (q1) to[out=270,in=210] node[auto]{$a$} (qbot);
\draw[->] (q2) to[out=270,in=180] node[auto]{$b$} (qbot);
\draw[->] (q3) to[out=270,in=150] node[auto]{$a$} (qbot);
\draw[->] (q4) to[out=270,in=120] node[auto]{$a$} (qbot);
\draw[->] (q5) to[out=270,in=90] node[auto]{$a,b$} (qbot);
\draw[->] (qbot) to[loop right] node[auto]{$a,b$} (qbot);
\end{tikzpicture}
}
\end{center}
\vskip0ptplus20ex\relax
La construction est analogue pour $A_{\mathrm{u}}$ :
\begin{center}
\scalebox{0.85}{%
\begin{tikzpicture}[>=latex,line join=bevel,automaton,baseline=(q0.base)]
\node (q0) at (0bp,0bp) [draw,circle,state,initial] {$0$};
\node (q1) at (60bp,0bp) [draw,circle,state] {$1$};
\node (q2) at (120bp,0bp) [draw,circle,state] {$2$};
\node (q3) at (180bp,0bp) [draw,circle,state] {$3$};
\node (q4) at (240bp,0bp) [draw,circle,state] {$4$};
\node (q5) at (300bp,0bp) [draw,circle,state,final] {$5$};
\node (qbot) at (300bp,-60bp) [draw,circle,state] {$\bot$};
\draw[->] (q0) -- node[auto]{$a$} (q1);
\draw[->] (q1) -- node[auto]{$b$} (q2);
\draw[->] (q2) -- node[auto]{$a$} (q3);
\draw[->] (q3) -- node[auto]{$b$} (q4);
\draw[->] (q4) -- node[auto]{$b$} (q5);
\draw[->] (q5) to[loop above] node[auto]{$a,b$} (q5);
\draw[->] (q0) to[out=270,in=240] node[auto]{$b$} (qbot);
\draw[->] (q1) to[out=270,in=210] node[auto]{$a$} (qbot);
\draw[->] (q2) to[out=270,in=180] node[auto]{$b$} (qbot);
\draw[->] (q3) to[out=270,in=150] node[auto]{$a$} (qbot);
\draw[->] (q4) to[out=270,in=120] node[auto]{$a$} (qbot);
\draw[->] (qbot) to[loop right] node[auto]{$a,b$} (qbot);
\end{tikzpicture}
}
\end{center}
\vskip0ptplus20ex\relax S'agissant de $A_{\mathrm{v}}$, on a affaire à
un « vrai » non-déterminisme et on applique donc l'algorithme de
déterminisation vu en cours, qui donne (en omettant les accolades dans
le nommage des états) :
\begin{center}
\scalebox{0.85}{%
\begin{tikzpicture}[>=latex,line join=bevel,automaton,baseline=(q0.base)]
\node (q0) at (0bp,0bp) [draw,circle,state,initial] {\small $0$};
\node (q1) at (60bp,0bp) [draw,circle,state] {\small $0,1$};
\node (q2) at (120bp,0bp) [draw,circle,state] {\small $0,2$};
\node (q3) at (180bp,0bp) [draw,circle,state] {\small $0,1,3$};
\node (q4) at (240bp,0bp) [draw,circle,state] {\small $0,2,4$};
\node (q5) at (300bp,0bp) [draw,circle,state,final] {\small $0,5$};
\draw[->] (q0) -- node[auto]{$a$} (q1);
\draw[->] (q1) -- node[auto]{$b$} (q2);
\draw[->] (q2) -- node[auto]{$a$} (q3);
\draw[->] (q3) -- node[auto]{$b$} (q4);
\draw[->] (q4) -- node[auto]{$b$} (q5);
\draw[->] (q0) to[loop below] node[auto]{$b$} (q0);
\draw[->] (q1) to[loop below] node[auto]{$a$} (q1);
\draw[->] (q2) to[out=120,in=60] node[auto,swap]{$b$} (q0);
\draw[->] (q3) to[out=120,in=60] node[auto,swap]{$a$} (q1);
\draw[->] (q4) to[out=120,in=60] node[auto,swap]{$a$} (q3);
\draw[->] (q5) to[loop above] node[auto]{$a,b$} (q5);
\end{tikzpicture}
}
\end{center}
\vskip0ptplus20ex\relax
La construction pour $A_{\mathrm{x}}$ est exactement comme pour
$A_{\mathrm{s}}$ sauf que les états $0$ à $5$ sont tous marqués
finaux :
\begin{center}
\scalebox{0.85}{%
\begin{tikzpicture}[>=latex,line join=bevel,automaton,baseline=(q0.base)]
\node (q0) at (0bp,0bp) [draw,circle,state,initial,accepting above] {$0$};
\node (q1) at (60bp,0bp) [draw,circle,state,accepting above] {$1$};
\node (q2) at (120bp,0bp) [draw,circle,state,accepting above] {$2$};
\node (q3) at (180bp,0bp) [draw,circle,state,accepting above] {$3$};
\node (q4) at (240bp,0bp) [draw,circle,state,accepting above] {$4$};
\node (q5) at (300bp,0bp) [draw,circle,state,accepting above] {$5$};
\node (qbot) at (300bp,-60bp) [draw,circle,state] {$\bot$};
\draw[->] (q0) -- node[auto]{$a$} (q1);
\draw[->] (q1) -- node[auto]{$b$} (q2);
\draw[->] (q2) -- node[auto]{$a$} (q3);
\draw[->] (q3) -- node[auto]{$b$} (q4);
\draw[->] (q4) -- node[auto]{$b$} (q5);
\draw[->] (q0) to[out=270,in=240] node[auto]{$b$} (qbot);
\draw[->] (q1) to[out=270,in=210] node[auto]{$a$} (qbot);
\draw[->] (q2) to[out=270,in=180] node[auto]{$b$} (qbot);
\draw[->] (q3) to[out=270,in=150] node[auto]{$a$} (qbot);
\draw[->] (q4) to[out=270,in=120] node[auto]{$a$} (qbot);
\draw[->] (q5) to[out=270,in=90] node[auto]{$a,b$} (qbot);
\draw[->] (qbot) to[loop right] node[auto]{$a,b$} (qbot);
\end{tikzpicture}
}
\end{center}
\vskip0ptplus20ex\relax
S'agissant de $A_{\mathrm{z}}$, on a de nouveau affaire à un « vrai »
non-déterminisme et on applique donc l'algorithme de déterminisation
vu en cours, qui donne (en omettant les accolades dans le nommage des
états) :
\begin{center}
\scalebox{0.85}{%
\begin{tikzpicture}[>=latex,line join=bevel,automaton,baseline=(qI.base)]
\node (qI) at (0bp,0bp) [draw,circle,state,initial,accepting above] {$I$};
\node (q1) at (60bp,0bp) [draw,circle,state,accepting above] {$1,3$};
\node (q2) at (120bp,0bp) [draw,circle,state,accepting above] {$2,4$};
\node (q3) at (180bp,0bp) [draw,circle,state,accepting above] {$3$};
\node (q4) at (240bp,0bp) [draw,circle,state,accepting above] {$4$};
\node (q5) at (300bp,0bp) [draw,circle,state,accepting above] {$5$};
\node (q245) at (120bp,-120bp) [draw,circle,state,accepting below] {\small $2,4,5$};
\node (qbot) at (300bp,-90bp) [draw,circle,state] {$\varnothing$};
\draw[->] (qI) -- node[auto]{$a$} (q1);
\draw[->] (q1) -- node[auto]{$b$} (q2);
\draw[->] (q2) -- node[auto]{$a$} (q3);
\draw[->] (q3) -- node[auto]{$b$} (q4);
\draw[->] (q4) -- node[auto]{$b$} (q5);
\draw[->] (qI) to[out=270,in=150] node[auto,swap]{$b$} (q245);
\draw[->] (q1) to[out=270,in=180] node[auto,near start]{$a$} (qbot);
\draw[->] (q2) to[out=60,in=120] node[auto]{$b$} (q5);
\draw[->] (q3) to[out=270,in=150] node[auto,near start]{$a$} (qbot);
\draw[->] (q4) to[out=270,in=120] node[auto,near start]{$a$} (qbot);
\draw[->] (q5) to[out=270,in=90] node[auto]{$a,b$} (qbot);
\draw[->] (q245) to[out=60,in=240] node[auto]{$a$} (q3);
\draw[->] (q245) to[out=30,in=240] node[auto,swap,very near end]{$b$} (q5);
\draw[->] (qbot) to[loop right] node[auto]{$a,b$} (qbot);
\end{tikzpicture}
}
\end{center}
où on a noté $I$ au lieu de $\{0,1,2,3,4,5\}$.
\end{corrige}

\textbf{(e)} Pour $A = A_{\mathrm{z}}$ (et seulement celui-ci),
minimiser le DFA trouvé à la question (d).

\begin{corrige}
On a affaire à un DFA complet sans état inaccessible : on va le
minimiser avec l'algorithme de Moore.

Dans une première étape, on fait deux classes d'état : celle des états
finaux, c'est-à-dire $I,\{1,3\},\{2,4\},\{2,4,5\},\{3\},\{4\},\{5\}$
et celle des états non-finaux, c'est-à-dire le seul
état $\varnothing$.

Séparons maintenant les états selon la cible de la transition
étiquetée par $a$ : la classe formée de
$I,\{1,3\},\{2,4\},\{2,4,5\},\{3\},\{4\},\{5\}$ se scinde en deux :
$I,\{2,4\},\{2,4,5\}$ d'une part, où elle mène à un état final, et
$\{1,3\},\{3\},\{4\},\{5\}$ d'autre part, où elle mène à un état
non-final.  La cible de la transition étiquetée par $b$, pour sa part,
sépare $\{5\}$ de tous les autres états (le seul où elle mène à un
état non-final).  À ce stade, on a quatre classes : la classe formée
de $I,\{2,4\},\{2,4,5\}$, celle de $\{1,3\},\{3\},\{4\}$, et deux
classes singleton, $\{5\}$ et $\varnothing$.

À l'étape suivante, la cible de la transition étiquetée par $a$ ne
sépare rien (les états de la première classe mènent à la seconde et
les états de la seconde mènent au puits).  La cible de la transition
étiquetée par $b$, en revanche, sépare la classe formée de
$I,\{2,4\},\{2,4,5\}$ en $I$ d'une part (qui mène à cette même classe)
et $\{2,4\},\{2,4,5\}$ de l'autre (qui mène à $\{5\}$) ; et elle
sépare la classe formée de $\{1,3\},\{3\},\{4\}$ en trois (puisque les
cibles sont dans trois classes distinctes).  À ce stade, les seuls
états qui n'ont pas été séparés sont $\{2,4\}$ et $\{2,4,5\}$.  Or
comme ils ont exactement les mêmes cibles de transitions étiquetées
par $a$ et $b$, ils ne sont pas séparés, donc l'algorithme s'applique
ici : il fusionne exactement deux états, à savoir
$\{2,4\}$ et $\{2,4,5\}$, en un seul, que nous noterons $B$ :
\begin{center}
\scalebox{0.85}{%
\begin{tikzpicture}[>=latex,line join=bevel,automaton,baseline=(qI.base)]
\node (qI) at (0bp,0bp) [draw,circle,state,initial,accepting above] {$I$};
\node (q1) at (60bp,0bp) [draw,circle,state,accepting above] {$1,3$};
\node (q2) at (120bp,0bp) [draw,circle,state,accepting above] {$B$};
\node (q3) at (180bp,0bp) [draw,circle,state,accepting above] {$3$};
\node (q4) at (240bp,0bp) [draw,circle,state,accepting above] {$4$};
\node (q5) at (300bp,0bp) [draw,circle,state,accepting above] {$5$};
\node (qbot) at (300bp,-60bp) [draw,circle,state] {$\varnothing$};
\draw[->] (qI) -- node[auto]{$a$} (q1);
\draw[->] (q1) -- node[auto]{$b$} (q2);
\draw[->] (q2) -- node[auto]{$a$} (q3);
\draw[->] (q3) -- node[auto]{$b$} (q4);
\draw[->] (q4) -- node[auto]{$b$} (q5);
\draw[->] (qI) to[out=60,in=120] node[auto]{$b$} (q2);
\draw[->] (q1) to[out=270,in=180] node[auto,near start]{$a$} (qbot);
\draw[->] (q2) to[out=60,in=120] node[auto]{$b$} (q5);
\draw[->] (q3) to[out=270,in=150] node[auto,near start]{$a$} (qbot);
\draw[->] (q4) to[out=270,in=120] node[auto]{$a$} (qbot);
\draw[->] (q5) to[out=270,in=90] node[auto]{$a,b$} (qbot);
\draw[->] (qbot) to[loop right] node[auto]{$a,b$} (qbot);
\end{tikzpicture}
}
\end{center}
\vskip-\baselineskip\vskip-1ex\strut
\end{corrige}

\textbf{(f)} Parmi les douze langages $L_0,\ldots,L_{11}$, lesquels
sont rationnels ?  Lesquels sont algébriques ?  Lesquels sont
décidables ?  Lesquels sont semi-décidables ?  On justifiera la
réponse à chaque fois (par exemple en donnant une expression
rationnelle, un automate, une grammaire hors-contexte, un algorithme,
ou n'importe quel autre type d'argument applicable permettant de
justifier la conclusion).

\begin{corrige}
Les langages $L_1,L_3,L_4,L_5,L_6,L_7,L_8,L_9$ sont rationnels car ils
sont reconnaissables : on a vu que les automates $A_{\mathrm{s}},
A_{\mathrm{w}}, A_{\mathrm{z}}, A_{\mathrm{v}}, A_{\mathrm{x}},
A_{\mathrm{u}}, A_{\mathrm{y}}, A_{\mathrm{t}}$ respectivement les
reconnaissent.  Il reste donc à traiter le cas de
$L_0,L_2,L_{10},L_{11}$.

Les langages $L_0$ et $L_2$ sont rationnels car ils sont finis (on
peut donner des expressions rationnelles pour les deux, à savoir
$\bot$ pour $L_0$ et, en énumérant systématiquement tous les
sous-mots, $\varepsilon | b | bb | a | ab | abb | bbb | ba | bab |
babb | aa | aab | aabb | abbb | aba | abab | ababb$ pour $L_2$, mais
ce n'est pas très intéressant et ce n'était pas demandé).

Le langage $L_{10} = \{w_0^i : i\in\mathbb{N}\} = L_1^*$ est rationnel
car il est l'étoile de Kleene d'un langage rationnel (si on préfère,
il est dénoté par l'expression rationnelle $(ababb){*}$).

Tous les langages $L_0$ à $L_{10}$ sont donc rationnels, et, en
particulier, algébriques, décidables et semi-décidables.

Reste à évoquer le cas du langage $L_{11} = \{b^i w_0 a^i :
i\in\mathbb{N}\}$.  Montrons qu'il n'est pas rationnel, et montrons
qu'il est algébrique.

Il n'est pas rationnel par le lemme de pompage.  En effet, supposons
par l'absurde que $\{b^i w_0 a^i : i\in\mathbb{N}\}$ soit rationnel,
et soit $k$ tel que donné par le lemme de pompage.  Considérons le mot
$t := b^k ababb a^k \in L_{11}$.  D'après la propriété de $k$, il
existe une factorisation $t = uvw$ vérifiant les propriétés garanties
par le lemme de pompage.  Le fait que $|uv|\leq k$, comme le préfixe
de longueur $k$ de $t$ est formé uniquement de la lettre $b$, assure
que $u = b^{\ell_1}$ et $v = b^{\ell_2}$ pour certains $\ell_1,\ell_2$
avec, de plus, $\ell_2 > 0$ (car $v\neq\varepsilon$) et
$\ell_1+\ell_2\leq k$.  On a alors $w = b^{k-\ell_1-\ell_2} ababb
a^k$, et $uv^iw = b^{k+(i-1)\ell_2} ababb a^k$.  Comme les mots de
$L_{11}$ ont la propriété nécessaire que leur nombre initial de $b$
(i.e., la longueur de leur plus long préfixe formé uniquement de la
lettre $b$) est égale à leur nombre final de $a$ (i.e., la longueur de
leur plus long suffixe formé uniquement de la lettre $a$), on devrait
avoir $k+(i-1)\ell_2 = k$, ce qui est une contradiction dès que $i\neq
1$.

En revanche, le langage $L_{11}$ est algébrique, car il est engendré
par la grammaire suivante d'axiome $S$ :
\[
S \rightarrow ababb \;|\; bSa
\]
Étant algébrique, le langage $L_{11}$ est décidable et semi-décidable.
(Au demeurant, il est facile de donner un algorithme qui décide si un
mot appartient à $L_{11}$ : on vérifie que son nombre initial de $b$
est égal à son nombre final de $a$ et, une fois ce fait vérifié, on
vérifie qu'une fois retiré le préfixe et le suffixe en question il
reste exactement le mot $ababb$.)

Pour résumer, tous les langages dont on a parlé sont algébriques,
décidables et semi-décidables, et tous sauf $L_{11}$ sont rationnels.
\end{corrige}



%
%
%
\end{document}