Start writing test for 2023.

1 files changed, 340 insertions, 0 deletions

diff --git a/controle-20230615.tex b/controle-20230615.tex
new file mode 100644
index 0000000..358cab2
--- /dev/null
+++ b/controle-20230615.tex
@@ -0,0 +1,340 @@
+%% 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}