diff options
| -rw-r--r-- | controle-20190328.tex | 193 |
1 files changed, 193 insertions, 0 deletions
diff --git a/controle-20190328.tex b/controle-20190328.tex new file mode 100644 index 0000000..e3e1391 --- /dev/null +++ b/controle-20190328.tex @@ -0,0 +1,193 @@ +%% 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 rattrapage — Corrigé\\{\normalsize Théorie des langages}} +\else +\title{INF105\\Contrôle de rattrapage\\{\normalsize Théorie des langages}} +\fi +\author{} +\date{28 mars 2019} +\maketitle + +\pretolerance=8000 +\tolerance=50000 + +\vskip1truein\relax + +\noindent\textbf{Consignes.} + +\textcolor{red}{À remplir} + +\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}{xxx}. + +\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\}$. + +(1) Soit $L_1$ le langage formé des mots de $\Sigma^*$ ayant $a$ comme +première lettre (c'est-à-dire, comme préfixe).\quad(a) Donner une +expression rationnelle $r_1$ dénotant le langage $L_1$.\quad(b) Donner +l'automate fini déterministe complet minimal $\mathscr{A}_1$ +reconnaissant $L_1$ (on pourra préalablement passer par d'autres +sortes d'automates comme étapes intermédiaires ; pour obtenir la +totalité des points, on passera impérativement par des constructions +vues en cours, qu'on précisera). + +\emph{Information :} L'automate $\mathscr{A}_1$ correct a trois états. +Il est fortement conseillé de vérifier soigneusement qu'on a bien +obtenu un automate déterministe complet ayant le bon nombre états et +qu'il se comporte comme attendu sur quelques mots courts (par exemple +$\varepsilon$, $a$, $b$, $aa$, $ab$, $ba$ et $bb$). + +\medskip + +(2) Soit $L_2$ le langage formé des mots de $\Sigma^*$ ayant $a$ comme +dernière lettre (c'est-à-dire, comme suffixe).\quad(a) Donner une +expression rationnelle $r_2$ dénotant le langage $L_2$.\quad(b) Donner +l'automate fini déterministe complet minimal $\mathscr{A}_2$ +reconnaissant $L_2$ (mêmes remarques que ci-dessus). + +\emph{Information :} L'automate $\mathscr{A}_2$ correct a deux états. +Même conseil que ci-dessus. + +\medskip + +(3) Soit $L_3 = L_2^{\mathsf{R}} = \{w^{\mathsf{R}} : w \in L_2\}$ le +langage miroir de $L_2$, c'est-à-dire le langage formé des mots +miroirs des mots de $L_2$ (on rappelle que le mot « moir » +$w^{\mathsf{R}}$ d'un mot $w$ s'obtient en inversant l'ordre de ses +lettres).\quad(a) Déduire de $\mathscr{A}_2$ un automate fini +$\mathscr{A}_3$ reconnaissant $L_3$.\quad(b) Quel est le rapport entre +les langages $L_1$ et $L_3$ ?\quad(c) Faire un commentaire quant au +rapport entre $\mathscr{A}_1$ et $\mathscr{A}_3$ ; notamment, on +expliquera en quoi l'existence de $\mathscr{A}_3$ ne contredit pas la +minimalité de $\mathscr{A}_1$. + +\medskip + +(4) Soit $L_4 = L_1\cap L_2$.\quad(a) Déduire des automates +$\mathscr{A}_1$ et $\mathscr{A}_2$ un automate fini +$\mathscr{A}_{4\mathrm{a}}$ ayant six états +reconnaissant $L_4$.\quad(b) Donner l'automate fini déterministe +complet minimal $\mathscr{A}_{4\mathrm{b}}$ reconnaissant $L_4$. + +\emph{Information :} L'automate $\mathscr{A}_4$ correct a quatre +états. Même conseil que pour la question (1). + +\medskip + +(5) En appliquant l'algorithme d'élimination des états, déduire +de $\mathscr{A}_{4\mathrm{b}}$ une expression rationnelle $r_5$ +dénotant le langage $L_4$. + +\medskip + +(6) Sans raisonner sur les automates, proposer une expression +rationnelle $r_6$ différente de celle trouvée en $r_5$ et qui dénote +aussi le langage $L_4$ (dont on donnera au préalable une description +en français). + +% +% +% +\end{document} |