From 7bbb8c184c6861d15fe4737e9da6eeefadbbc3ce Mon Sep 17 00:00:00 2001 From: "David A. Madore" Date: Thu, 25 Jan 2018 16:53:12 +0100 Subject: Possible exam for 2018-02-06. --- controle-20180206.tex | 288 ++++++++++++++++++++++++++++++++++++++++++++++++++ 1 file changed, 288 insertions(+) create mode 100644 controle-20180206.tex diff --git a/controle-20180206.tex b/controle-20180206.tex new file mode 100644 index 0000000..c18064b --- /dev/null +++ b/controle-20180206.tex @@ -0,0 +1,288 @@ +%% 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}\smallbreak\noindent\textbf{\thecomcnt.} } +\newcommand\exercice{% +\refstepcounter{comcnt}\bigbreak\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\relax\else\egroup\fi\par} +\newenvironment{commentaire}% +{\ifcorrige\relax\else\setbox0=\vbox\bgroup\fi% +\smallbreak\noindent{\underbar{\textit{Commentaires.}}\quad}} +{{\hbox{}\nobreak\hfill\maltese}% +\ifcorrige\relax\else\egroup\fi\par} +% +% +% 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{6 février 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 + +Le sujet étant long pour le temps imparti, il ne sera pas nécessaire +de traiter toutes les questions pour obtenir la totalité des points. + +\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} : 8 points par exercices + +\ifcorrige +%Ce corrigé comporte 10 pages (page de garde incluse) +\else +%Cet énoncé comporte 4 pages (page de garde incluse) +\fi + +\pagebreak + + +% +% +% + +\exercice + +Dans cet exercice, on pose $\Sigma = \{a,b\}$. On s'intéresse au +langage $L$ formé des mots (éléments de $\Sigma^*$) ayant $aa$ ou $bb$ +comme facteur (c'est-à-dire contenant deux $a$ consécutifs, ou bien +deux $b$ consécutifs, ou bien deux $c$ consécutifs), ainsi qu'à son +complémentaire $M := \Sigma^* \setminus L$. + +(1) Donner une expression rationnelle dénotant $L$. + +(2) Indépendamment de la question (1), expliquer brièvement pourquoi +l'automate $\mathscr{A}_2$ suivant reconnaît le langage $L$ : + +\begin{center} +\begin{tikzpicture}[>=latex,line join=bevel,automaton] +\node (S) at (0bp,0bp) [draw,circle,state,initial] {$S$}; +\node (A) at (70bp,35bp) [draw,circle,state] {$A$}; +\node (B) at (70bp,-35bp) [draw,circle,state] {$B$}; +\node (T) at (140bp,0bp) [draw,circle,state,final] {$T$}; +\draw [->] (S) to[loop above] node[auto] {$a,b$} (S); +\draw [->] (S) -- node[auto,near end] {$a$} (A); +\draw [->] (S) -- node[auto] {$b$} (B); +\draw [->] (T) to[loop above] node[auto] {$a,b$} (T); +\draw [->] (A) -- node[auto,near start] {$a$} (T); +\draw [->] (B) -- node[auto] {$b$} (T); +\end{tikzpicture} +\end{center} + +De quelle sorte d'automate s'agit-il ? + +(3) Déterminiser (si nécessaire) l'automate $\mathscr{A}_2$ représenté +en (2) ; on appellera $\mathscr{A}_3$ l'automate résultant. + +(4) Minimiser (si nécessaire) l'automate $\mathscr{A}_3$ obtenu +en (3) ; on appellera $\mathscr{A}_4$ l'automate résultant. + +(5) Construire un automate $\mathscr{A}_5$ reconnaissant le +langage $M$ complémentaire de $L$. + +(6) En appliquant à $\mathscr{A}_5$ la méthode d'élimination des +états, déterminer une expression rationnelle dénotant le langage $M$. + + + +% +% +% + +\exercice + +On considère la grammaire hors-contexte $G$ d'axiome $S$ et de +nonterminaux $N = \{S, T, U, V\}$ sur l'alphabet $\Sigma = +\{{\#},{@},{(},{)}, x, y, z\}$ (soit $7$ lettres) donnée par +\[ +\begin{aligned} +S &\rightarrow T \;|\; S\mathbin{\#}T\\ +T &\rightarrow U \;|\; U\mathbin{@}T\\ +U &\rightarrow V \;|\; (\,S\,)\\ +V &\rightarrow x \;|\; y \;|\; z\\ +\end{aligned} +\] +(On pourra imaginer que $\#$ et $@$ sont deux opérations binaires, les +parenthèses servent comme on s'y attend, et $x,y,z$ sont trois choses +auxquelles on peut vouloir appliquer ces opérations.) + +La grammaire en question est inambiguë (on ne demande pas de le +démontrer). + +(1) Donner les arbres d'analyse des mots suivants : +(a) $x\mathbin{\#}y\mathbin{\#}z$, (b) $x\mathbin{\#}y\mathbin{@}z$, +(c) $x\mathbin{@}y\mathbin{\#}z$, (d) $x\mathbin{@}y\mathbin{@}z$, +(e) $(x\mathbin{\#}y)\mathbin{@}z$. + +(2) En considérant que $(w)$ a le même effet / la même valeur +que $w$ : (a) Quelle opération parmi $\#$ et $@$ est +prioritaire\footnote{On dit qu'une opération binaire $\boxtimes$ est + \emph{prioritaire} sur $\boxplus$ lorsque « $u\boxtimes v\boxplus + w$ » se comprend comme « $(u\boxtimes v)\boxplus w$ » et + « $u\boxplus v\boxtimes w$ » comme « $u\boxplus (v\boxtimes w)$ ».} +sur l'autre ? (b) L'opération $\#$ s'associe-t-elle\footnote{On dit + qu'une opération binaire $\boxdot$ \emph{s'associe à gauche} lorsque + « $u\boxdot v\boxdot w$ » se comprend comme « $(u\boxdot v)\boxdot + w$ », et \emph{s'associe à droite} lorsque « $u\boxdot v\boxdot w$ » + se comprend comme « $u\boxdot (v\boxdot w)$ ».} à gauche ou à +droite ? (c) L'opération $@$ s'associe-t-elle à gauche ou à droite ? + + +% +% +% + +\exercice + +(On pourra si on le souhaite remplacer $\mathbb{N}$ partout dans cet +exercice par l'ensemble $\Sigma^*$ des mots sur un alphabet $\Sigma$ +[fini] non vide fixé quelconque.) + +Dans cet exercice, on appelle « langage » une partie de $\mathbb{N}$ +(cf. le paragraphe précédent). On dira que deux langages $L,M$ +disjoints (c'est-à-dire $L\cap M = \varnothing$) sont +\emph{calculablement séparables} lorsqu'il existe un $E$ décidable tel +que $L \subseteq E$ et $M \subseteq (\mathbb{N}\setminus E)$ (où +$\mathbb{N}\setminus E$ désigne le complémentaire de $E$) ; dans le +cas contraire, on les dit \emph{calculablement inséparables}. + +(1) Expliquer pourquoi deux langages $L,M$ disjoints sont +calculablement séparables si et seulement si il existe un algorithme +qui, prenant en entrée un élément $x$ de $\mathbb{N}$ : +\begin{itemize} +\item termine toujours en temps fini, +\item répond « vrai » si $x\in L$ et « faux » si $x \in M$ (rien n'est + imposé si $x\not\in L\cup M$). +\end{itemize} + +(2) Expliquer pourquoi deux langages $L,M$ disjoints sont +calculablement séparables si et seulement si il existe deux langages +$E,F$ \emph{décidables disjoints} tels que $L \subseteq E$ et $M +\subseteq F$. + +(3) Deux langages décidables disjoints peuvent-ils être calculablement +inséparables ? + +On cherche maintenant à montrer qu'il existe deux langages $L,M$ +\emph{semi-décidables} disjoints et calculablement inséparables. + +Pour cela, appelle $L$ l'ensemble des couples\footnote{Pour être + rigoureux, on a fixé un codage permettant de représenter les + programmes $e$, les entrées $x$ à ces programmes, et les couples + $(e,x)$ comme des éléments de $\mathbb{N}$. Il n'est pas nécessaire + de faire apparaître ce codage dans la description des algorithmes + proposés, qui peut rester informelle.} $(e,x)$ formés d'un programme +(=algorithme) $e$ et d'une entrée $x$, tels que l'exécution du +programme $e$ sur l'entrée $x$ termine en temps fini et renvoie la +valeur $1$ (ce qui peut se noter $\varphi_e(x) = 1$) ; et $M$ le +langage défini de la même manière mais avec la valeur $2$, +i.e., $\varphi_e(x) = 2$. (Ici, $1$ et $2$ peuvent être remplacés +deux éléments distincts quelconques de $\mathbb{N}$ : si on a souhaité +remplacer $\mathbb{N}$ par $\Sigma^*$, on peut prendre deux mots +distincts quelconques, par exemple $a$ et $aa$.) + +(4) Pourquoi $L$ et $M$ sont-ils disjoints ? + +(5) Pourquoi $L$ et $M$ sont-ils semi-décidables ? + +(6) En calquant la démonstration du théorème de Turing sur +l'indécidabilité du problème de l'arrêt, montrer qu'il n'existe aucun +algorithme qui, prenant en entrée un couple $(e,x)$, termine toujours +en temps fini et répond « vrai » si $(e,x)\in L$ et « faux » si $(e,x) +\in M$ (indication : si un tel algorithme existait, on pourrait s'en +servir pour faire le contraire de ce qu'il prédit). + +(7) Conclure. + + + +% +% +% +\end{document} -- cgit v1.2.3