%% 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 dix langages suivants où $w_0$ désigne le
mot $ababb$ :
\begin{itemize}
\item $L_0$: le langage vide.
\item $L_1$: 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.
\end{itemize}

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}}\}$,
on pose les questions suivantes :

\textbf{(a)} Parmi les dix langages $L_0,\ldots,L_9$, lequel est le
langage $L$ reconnu par l'automate $A$ ?  On ne demande pas de
justifier la réponse.

\textbf{(b)} Donner une expression rationnelle reconnaissant le
langage $L$ en question.  On ne demande pas de justifier la réponse,
et il n'est pas obligatoire d'appliquer un algorithme vu en cours ;
par ailleurs, cette question-ci n'est pas posée pour
l'automate $A_{\mathrm{z}}$.

\textbf{(c)} De quel type d'automate vu en cours (DFA complet, DFA à
spécification incomplète, NFA ou bien NFA à transitions spontanées)
l'automate $A$ est-il ?  On donnera à chaque fois le type le plus
particulier applicable.

\textbf{(d)} Donner un DFA complet sans état inaccessible équivalent
à $A$ (c'est-à-dire, reconnaissant le langage $L$).  On ne traitera
que les cinq automates suivants :
$A_{\mathrm{s}},A_{\mathrm{u}},A_{\mathrm{v}},A_{\mathrm{x}},A_{\mathrm{z}}$
(c'est-à-dire que cette question-ci n'est pas posée pour
$A_{\mathrm{t}},A_{\mathrm{w}},A_{\mathrm{y}}$) ; on appliquera les
algorithmes vus en cours en les nommant.



%
%
%
\end{document}