diff options
| -rw-r--r-- | controle-20230615.tex | 340 |
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} |