Start writing exam: an exercise on finite automata.

1 files changed, 174 insertions, 0 deletions

diff --git a/controle-20200123.tex b/controle-20200123.tex
new file mode 100644
index 0000000..e0c0c1f
--- /dev/null
+++ b/controle-20200123.tex
@@ -0,0 +1,174 @@
+%% This is a LaTeX document.  Hey, Emacs, -*- latex -*- , get it?
+\documentclass[12pt,a4paper]{article}
+\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{23 janvier 2020}
+\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} : \textcolor{red}{(à remplir)}.
+
+\ifcorrige
+Ce corrigé comporte \textcolor{red}{(à remplir)} pages (page de garde incluse)
+\else
+Cet énoncé comporte \textcolor{red}{(à remplir)} 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\}$ (alphabet à une seule lettre).
+
+On considère l'expression rationnelle $r$ suivante : $(aaa|aaaaa){*}$
+(sur l'alphabet $\Sigma$).  On appelle $L := L(r)$ le langage qu'elle
+dénote et $M := \Sigma^* \setminus L$ son complémentaire.
+
+(1) Traiter l'une \emph{ou} l'autre des questions suivantes :
+(i) construire l'automate de Glushkov $\mathscr{A}_1$ de $r$ ;
+(ii) construire l'automate de Thompson de $r$, puis éliminer les
+transitions spontanées (= $\varepsilon$-transitions) de ce dernier (on
+retirera les états devenus inutiles) : on appellera $\mathscr{A}_1$
+l'automate ainsi obtenu.
+
+(Dans les deux cas, on obtient le même automate $\mathscr{A}_1$, ayant
+$9$ états.  À défaut de donner l'automate de Glushkov ou de Thompson,
+donner un NFA reconnaissant $L$ pourra apporter une partie des
+points.)
+
+(2) Déterminiser l'automate $\mathscr{A}_1$.  On appellera
+$\mathscr{A}_2$ l'automate (déterministe complet) en question.
+
+(On obtient un automate $\mathscr{A}_2$ ayant $14$ états.  On
+n'hésitera pas à introduire des notations simplificatrices si on le
+juge utile ; il pourra être judicieux de réfléchir au préalable à une
+façon de nommer les états de $\mathscr{A}_1$ qui rend la construction
+de $\mathscr{A}_2$ plus facile à mener sans se tromper.)
+
+Pour simplifier les questions suivantes (ainsi que le travail du
+correcteur), on renommera si nécessaire les états de $\mathscr{A}_2$
+de façon que, autant que possible, l'état résultant de la lecture du
+mot $a^k$ par l'automate soit numéroté $k$.
+
+(3) Minimiser l'automate $\mathscr{A}_2$.  On appellera
+$\mathscr{A}_3$ l'automate canonique ainsi obtenu.
+
+(On obtient un automate ayant $9$ états.)
+
+(4) Construire un automate $\mathscr{A}_4$ reconnaissant le langage $M
+:= \Sigma^*\setminus L$ complémentaire de $L$.  Ce langage $M$ est
+fini : énumérer exhaustivement les mots qu'il contient.
+
+(5) Quels sont les entiers naturels ne pouvant pas s'écrire sous la
+forme $3m+5n$ avec $m,n\in\mathbb{N}$ ?
+
+%
+%
+%
+\end{document}