From 0b8df8c4f5753f1ae66a81f5cc0b3f576e88d613 Mon Sep 17 00:00:00 2001 From: "David A. Madore" Date: Mon, 20 Jan 2020 22:24:20 +0100 Subject: Start writing exam: an exercise on finite automata. --- controle-20200123.tex | 174 ++++++++++++++++++++++++++++++++++++++++++++++++++ 1 file changed, 174 insertions(+) create mode 100644 controle-20200123.tex 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} -- cgit v1.2.3