diff options
| -rw-r--r-- | controle-20210618.tex | 268 |
1 files changed, 268 insertions, 0 deletions
diff --git a/controle-20210618.tex b/controle-20210618.tex new file mode 100644 index 0000000..4993f1d --- /dev/null +++ b/controle-20210618.tex @@ -0,0 +1,268 @@ +%% 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{18 juin 2021} +\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}{nnn} pages (page de garde incluse) +\else +Cet énoncé comporte \textcolor{red}{nnn} 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\}$. On considère +l'expression rationnelle $r := bb{*}a(a|b){*}$, et soit $L := L(r)$ le +langage qu'elle dénote (autrement dit, c'est le langage constitués des +mots qui commencent par un nombre $\geq 1$ de fois la lettre $b$, +immédiatement suivis par la lettre $a$, puis n'importe quoi). + +(0) Pour chacun des mots suivants, dire si oui ou non il appartient +à $L$ (c'est-à-dire s'il vérifie $r$) : $\varepsilon$ (le mot vide), +$a$, $b$, $ab$, $ba$, $bb$, $bab$, $bba$, $baba$. On ne demande pas +de justifier les réponses. + +\emph{Il est fortement conseillé, dans toutes les questions suivantes, + d'utiliser les mots qui viennent d'être listés pour vérifier les + automates successifs qu'on calculera.} (Par exemple, pour un +automate censé reconnaître le langage $L$, on vérifiera qu'il accepte +bien les mots qu'on a identifiés comme appartenant à $L$ et pas ceux +qu'on a identifiés comme n'appartement pas à $L$.) Les fautes pouvant +être détectées par cette vérification seront plus lourdement +sanctionnées. + +(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 fini $\mathscr{A}_1$. +À 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 en question. On rappelle qu'on attend ici +un automate fini \emph{déterministe complet}. + +(3) Minimiser l'automate $\mathscr{A}_2$. On appellera +$\mathscr{A}_3$ l'automate canonique du langage $L$ ainsi obtenu. + +(4) Déduire de $\mathscr{A}_3$ un automate fini déterministe complet +$\mathscr{A}_4$ reconnaissant le langage $M := \Sigma^*\setminus L$ +complémentaire de $L$. + +(5) En appliquant l'algorithme d'élimination des états, déduire +de $\mathscr{A}_4$ une expression rationnelle $s$ dénotant le +langage $M$ (c'est-à-dire vérifiée exactement par les mots qui ne +vérifient pas $r$). + + +% +% +% + +\exercice + +On considère la grammaire hors-contexte $G$ sur l'alphabet $\Sigma = +\{a,b,c\}$ ayant pour seul nonterminal son axiome $S$, et pour règles +\[ +S \rightarrow \varepsilon \;|\; aSbc \;|\; abSc +\] +On appellera « $0$ » la règle $S \rightarrow \varepsilon$, et +« $1$ » la règle $S \rightarrow aSbc$, et enfin « $2$ » la règle $S +\rightarrow abSc$. + +(1) Donner un arbre d'analyse (= de dérivation) du mot $abaabcbcc$ +selon cette grammaire $G$. (On pourra d'abord lire les questions +suivantes si on a du mal à trouver comment dériver ce mot.) + +On va maintenant montrer que $G$ est inambiguë. + +(2) Montrer que tout mot non-vide du langage $L := L(G)$ engendré +par $G$ a nécessairement $a$ pour préfixe (i.e., commence par la +lettre $a$). + +(3) Montrer que tout mot de $L$ dérivé en commençant +par\footnote{C'est-à-dire : tout mot $w$ possédant une dérivation + selon $G$ de la forme $S \Rightarrow aSc \mathrel{\Rightarrow^*} w$ + où $\mathrel{\Rightarrow^*}$ désigne une succession quelconque de + dérivations. Ou, ce qui revient au même (on pourra tenir ce point + pour acquis) : tout mot $w$ possédant un arbre d'analyse dont la + racine a trois fils étiquetés $a,S,b$ dans cet ordre.} la règle $1$ +a nécessairement $aa$ ou $ac$ comme préfixe. Montrer de même que tout +mot de $L$ dérivé en commençant par la règle $2$ a nécessairement $ab$ +comme préfixe. + +(4) En déduire comment, d'après la longueur d'un mot $w$ de $L$ et ses +deux premières lettres, on peut savoir par quelle règle commence +nécessairement une dérivation de $w$ selon $G$ (ou, ce qui revient au +même, quels sont les fils de la racine dans tout arbre d'analyse +de $w$). + +(5) Connaissant tous les arbres d'analyse d'un mot $w$ selon $G$, +expliquer comment trouver tous les arbres d'analyse du mot $awbc$ +d'une part, et du mot $abwc$ d'autre part. + +(6) En déduire que tout mot $w \in L$ possède un unique arbre +d'analyse selon $G$, et proposer (sur la base des questions +précédentes) un algorithme qui le calcule. + + +% +% +% + +\exercice + +(Les deux questions suivantes sont indépendantes.) + +\smallskip + +(1) Le langage $\{a^n b^n c^n : n\in\mathbb{N}\}$ n'est pas +algébrique\footnote{Ce fait est démontré dans le poly, dans la section + consacrée au lemme de pompage pour les langages algébriques et comme + illustration de ce dernier ; on ne demande bien sûr pas ici de le + redémontrer.}. Est-il rationnel ? Est-il décidable ? Est-il +semi-décidable ? On justifiera soigneusement les réponses. + +\smallskip + +(2) On rappelle la définition du problème de l'arrêt : c'est +l'ensemble $H$ 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}$ (ou bien de $\Sigma^*$ sur un alphabet + $\Sigma\neq\varnothing$ arbitraire). 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. On a vu en +cours que $H$ était semi-décidable mais non décidable. + +On considère l'ensemble $J$ des triplets $(e_1,e_2,x)$ tels que +$(e_1,x) \in H$ et $(e_2,x) \not\in H$. Autrement dit, le programme +$e_1$ termine en temps fini quand on l'exécute sur l'entrée $x$ mais +le programme $e_2$, lui, ne termine pas sur cette même entrée. +L'ensemble $J$ est-il décidable ? Semi-décidable ? On justifiera +soigneusement. + + +% +% +% +\end{document} |