diff options
| -rw-r--r-- | controle-20180322.tex | 147 |
1 files changed, 147 insertions, 0 deletions
diff --git a/controle-20180322.tex b/controle-20180322.tex new file mode 100644 index 0000000..516cd07 --- /dev/null +++ b/controle-20180322.tex @@ -0,0 +1,147 @@ +%% 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.}} +\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{22 mars 2018} +\maketitle + +%% {\footnotesize +%% \immediate\write18{sh ./vc > vcline.tex} +%% \begin{center} +%% Git: \input{vcline.tex} +%% \end{center} +%% \immediate\write18{echo ' (stale)' >> vcline.tex} +%% \par} + +\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 + +\pagebreak + + +% +% +% + +\exercice + +Dans cet exercice, on pose $\Sigma = \{a,b,c\}$. On appelle $L$ le +langage des mots sur $\Sigma$ qui ont $abc$ comme sous-mot, +c'est-à-dire, qui contiennent un $a$, un $b$ et un $c$ dans cet ordre +mais non nécessairement consécutivement (à titre d'exemple, $abac \in +L$). + +(1) Proposer un automate non-déterministe (NFA), sans transition +spontanée, $\mathscr{A}_1$ qui reconnaît le langage $L$. On +justifiera rapidement pourquoi l'automate proposé convient. + +(2) Déterminiser (si nécessaire) l'automate $\mathscr{A}_1$ trouvé +en (1) ; on appellera $\mathscr{A}_2$ l'automate résultant. + +(3) Minimiser (si nécessaire) l'automate $\mathscr{A}_2$ obtenu +en (2) ; on appellera $\mathscr{A}_3$ l'automate minimal (=canonique) +résultant. + +(4) Construire un automate $\mathscr{A}_4$ reconnaissant le langage $M +:= \Sigma^*\setminus L$ complémentaire de $L$. + +(5) En appliquant à $\mathscr{A}_4$ la méthode d'élimination des +états, déterminer une expression rationnelle dénotant le langage $M$. + + + +% +% +% +\end{document} |