summaryrefslogtreecommitdiffstats
path: root/controle-20210618.tex
blob: 4993f1d49f377052df477d63f6e27d990d42ef38 (plain)
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94
95
96
97
98
99
100
101
102
103
104
105
106
107
108
109
110
111
112
113
114
115
116
117
118
119
120
121
122
123
124
125
126
127
128
129
130
131
132
133
134
135
136
137
138
139
140
141
142
143
144
145
146
147
148
149
150
151
152
153
154
155
156
157
158
159
160
161
162
163
164
165
166
167
168
169
170
171
172
173
174
175
176
177
178
179
180
181
182
183
184
185
186
187
188
189
190
191
192
193
194
195
196
197
198
199
200
201
202
203
204
205
206
207
208
209
210
211
212
213
214
215
216
217
218
219
220
221
222
223
224
225
226
227
228
229
230
231
232
233
234
235
236
237
238
239
240
241
242
243
244
245
246
247
248
249
250
251
252
253
254
255
256
257
258
259
260
261
262
263
264
265
266
267
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}