summaryrefslogtreecommitdiffstats
path: root/controle-20210618.tex
blob: 7cea2b229440462300d3936cdc9c74d8b974ea24 (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
269
270
271
272
273
274
275
276
277
278
279
280
281
282
283
284
285
286
287
288
289
290
291
292
293
294
295
296
297
298
299
300
301
302
303
304
305
306
307
308
309
310
311
312
313
314
315
316
317
318
319
320
321
322
323
324
325
326
327
328
329
330
331
332
333
334
335
336
337
338
339
340
341
342
343
344
345
346
347
348
349
350
351
352
353
354
355
356
357
358
359
360
361
362
363
364
365
366
367
368
369
370
371
372
373
374
375
376
377
378
379
380
381
382
383
384
385
386
387
388
389
390
391
392
393
394
395
396
397
398
399
400
401
402
403
404
405
406
407
408
409
410
411
412
413
414
415
416
417
418
419
420
421
422
423
424
425
426
427
428
429
430
431
432
433
434
435
436
437
438
439
440
441
442
443
444
445
446
447
448
449
450
451
452
453
454
455
456
457
458
459
460
461
462
463
464
465
466
467
468
469
470
471
472
473
474
475
476
477
478
479
480
481
482
483
484
485
486
487
488
489
490
491
492
493
494
495
496
497
498
499
500
501
502
503
504
505
506
507
508
509
510
511
512
513
514
515
516
517
518
519
520
521
522
523
524
525
526
527
528
529
530
531
532
533
534
535
536
537
538
539
540
541
542
543
544
545
546
547
548
549
550
551
552
553
554
555
%% 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} : 8+7+5.

\ifcorrige
Ce corrigé comporte \textcolor{red}{nnn} pages (page de garde incluse).
\else
Cet énoncé comporte 3 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é 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.

\begin{corrige}
Les mots $\varepsilon$, $a$, $b$, $ab$ et $bb$ n'appartiennent pas
à $L$ ; les mots $ba$, $bab$, $bba$ et $baba$ appartiennent à $L$.
\end{corrige}

\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 qui
auraient dû être détectées par cette vérification pourront être 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.)

\begin{corrige}
L'automate $\mathscr{A}_1$ trouvé est le suivant :
\begin{center}
\begin{tikzpicture}[>=latex,line join=bevel,automaton]
\node (q0) at (0bp,0bp) [draw,circle,state,initial] {$0$};
\node (q1) at (60bp,0bp) [draw,circle,state] {$1$};
\node (q2) at (120bp,0bp) [draw,circle,state] {$2$};
\node (q3) at (180bp,0bp) [draw,circle,state,final,accepting below] {$3$};
\node (q4) at (240bp,30bp) [draw,circle,state,final] {$4$};
\node (q5) at (240bp,-30bp) [draw,circle,state,final] {$5$};
\draw[->] (q0) -- node[auto]{$b$} (q1);
\draw[->] (q1) -- node[auto]{$b$} (q2);
\draw[->] (q2) to[loop above] node[auto]{$b$} (q2);
\draw[->] (q2) -- node[auto]{$a$} (q3);
\draw[->] (q1) to[out=330,in=210] node[auto,below]{$a$} (q3);
\draw[->] (q3) -- node[auto]{$a$} (q4);
\draw[->] (q3) -- node[auto,below]{$b$} (q5);
\draw[->] (q4) to[loop above] node[auto]{$a$} (q4);
\draw[->] (q4) to[out=240,in=120] node[auto,swap]{$b$} (q5);
\draw[->] (q5) to[out=60,in=300] node[auto,swap]{$a$} (q4);
\draw[->] (q5) to[loop below] node[auto]{$b$} (q5);
\end{tikzpicture}
\end{center}
\vskip-\baselineskip\vskip-1ex\strut
\end{corrige}

(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}.

\begin{corrige}
L'automate $\mathscr{A}_1$ est déjà déterministe, mais incomplet :
pour le transformer en automate déterministe complet, on se contente
de lui ajouter un puits pour obtenir l'automate $\mathscr{A}_2$ :
\begin{center}
\begin{tikzpicture}[>=latex,line join=bevel,automaton]
\node (q0) at (0bp,0bp) [draw,circle,state,initial] {$0$};
\node (q1) at (60bp,0bp) [draw,circle,state] {$1$};
\node (q2) at (120bp,0bp) [draw,circle,state] {$2$};
\node (q3) at (180bp,0bp) [draw,circle,state,final,accepting below] {$3$};
\node (q4) at (240bp,30bp) [draw,circle,state,final] {$4$};
\node (q5) at (240bp,-30bp) [draw,circle,state,final] {$5$};
\node (Sink) at (0bp,-50bp) [draw,circle] {$\bot$};
\draw[->] (q0) -- node[auto]{$b$} (q1);
\draw[->] (q1) -- node[auto]{$b$} (q2);
\draw[->] (q2) to[loop above] node[auto]{$b$} (q2);
\draw[->] (q2) -- node[auto]{$a$} (q3);
\draw[->] (q1) to[out=330,in=210] node[auto,below]{$a$} (q3);
\draw[->] (q3) -- node[auto]{$a$} (q4);
\draw[->] (q3) -- node[auto,below]{$b$} (q5);
\draw[->] (q4) to[loop above] node[auto]{$a$} (q4);
\draw[->] (q4) to[out=240,in=120] node[auto,swap]{$b$} (q5);
\draw[->] (q5) to[out=60,in=300] node[auto,swap]{$a$} (q4);
\draw[->] (q5) to[loop below] node[auto]{$b$} (q5);
\draw[->] (q0) -- node[auto,swap]{$a$} (Sink);
\draw[->] (Sink) to[loop left] node[auto]{$a,b$} (Sink);
\end{tikzpicture}
\end{center}
\vskip-\baselineskip\vskip-1ex\strut
\end{corrige}

(3) Minimiser l'automate $\mathscr{A}_2$.  On appellera
$\mathscr{A}_3$ l'automate minimal ainsi obtenu (automate canonique du
langage $L$).

\begin{corrige}
L'automate $\mathscr{A}_2$ est déterministe complet sans état
inaccessible.  On commence l'algorithme de minimisation en séparant
les états finaux $\{3,4,5\}$ et non-finaux $\{0,1,2,\bot\}$.  On
sépare ensuite ces derniers en deux classes, $\{1,2\}$ et $\{0,\bot\}$
selon que la transition étiquetée $a$ conduit à un état final.  Enfin,
la transition étiquetée $b$ sépare la classe $\{0,\bot\}$ en deux.
Finalement, on aboutit aux classes suivantes : $\{0\}$, $\{1,2\}$,
$\{3,4,5\}$ et $\{\bot\}$, et à l'automate minimal $\mathscr{A}_3$
suivant :
\begin{center}
\begin{tikzpicture}[>=latex,line join=bevel,automaton]
\node (q0) at (0bp,0bp) [draw,circle,state,initial] {$0$};
\node (q1) at (60bp,0bp) [draw,circle,state] {$1$};
\node (q3) at (120bp,0bp) [draw,circle,state,final] {$3$};
\node (Sink) at (0bp,-50bp) [draw,circle] {$\bot$};
\draw[->] (q0) -- node[auto]{$b$} (q1);
\draw[->] (q1) to[loop above] node[auto]{$b$} (q1);
\draw[->] (q1) -- node[auto]{$a$} (q3);
\draw[->] (q3) to[loop above] node[auto]{$a,b$} (q3);
\draw[->] (q0) -- node[auto,swap]{$a$} (Sink);
\draw[->] (Sink) to[loop left] node[auto]{$a,b$} (Sink);
\end{tikzpicture}
\end{center}
\vskip-\baselineskip\vskip-1ex\strut
\end{corrige}

(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$.

\begin{corrige}
Il suffit d'échanger les états finaux et non-finaux
dans $\mathscr{A}_3$, ce qui donne l'automate $\mathscr{A}_4$
suivant :
\begin{center}
\begin{tikzpicture}[>=latex,line join=bevel,automaton]
\node (q0) at (0bp,0bp) [draw,circle,state,initial,final,accepting above] {$0$};
\node (q1) at (60bp,0bp) [draw,circle,state,final,accepting below] {$1$};
\node (q3) at (120bp,0bp) [draw,circle,state] {$3$};
\node (qZ) at (0bp,-50bp) [draw,circle,final] {$Z$};
\draw[->] (q0) -- node[auto]{$b$} (q1);
\draw[->] (q1) to[loop above] node[auto]{$b$} (q1);
\draw[->] (q1) -- node[auto]{$a$} (q3);
\draw[->] (q3) to[loop above] node[auto]{$a,b$} (q3);
\draw[->] (q0) -- node[auto,swap]{$a$} (qZ);
\draw[->] (qZ) to[loop left] node[auto]{$a,b$} (qZ);
\end{tikzpicture}
\end{center}
(On a renommé l'état $\bot$ en $Z$ vu que ce n'est plus un puits sur
ce nouvel automate, en revanche $3$ en est un.  Ces nom sont, bien
sûr, sans aucun impact sur le fonctionnement de l'automate.)
\end{corrige}

(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$).
\begin{corrige}
Pour procéder à l'algorithme d'élimination des états, on commence par
donner à l'automate un unique état final sans aucune transition qui en
part, appelons-le $\infty$.  On peut aussi d'ores et déjà éliminer
l'état $3$ qui est maintenant inutile, et remplacer les deux
transitions $Z\to Z$ étiquetées $a$ et $b$ par une seule
étiquetée $a|b$ (ce qui, dans un RNFA, revient au même) :
\begin{center}
\begin{tikzpicture}[>=latex,line join=bevel,automaton]
\node (q0) at (0bp,0bp) [draw,circle,state,initial] {$0$};
\node (q1) at (60bp,0bp) [draw,circle,state] {$1$};
\node (qZ) at (0bp,-50bp) [draw,circle] {$Z$};
\node (final) at (60bp,-50bp) [draw,circle,final] {$\infty$};
\draw[->] (q0) -- node[auto]{$b$} (q1);
\draw[->] (q1) to[loop above] node[auto]{$b$} (q1);
\draw[->] (q0) -- node[auto,swap]{$a$} (qZ);
\draw[->] (qZ) to[loop left] node[auto]{$a|b$} (qZ);
\draw[->] (q0) -- node[auto]{$\varepsilon$} (final);
\draw[->] (q1) -- node[auto]{$\varepsilon$} (final);
\draw[->] (qZ) -- node[auto,below]{$\varepsilon$} (final);
\end{tikzpicture}
\end{center}
L'élimination de l'état $1$ conduit à remplacer la transition
$0\to\infty$ étiquetée $\varepsilon$ par $\varepsilon | bb{*}$, et
l'élimination de l'état $Z$ conduit à y ajouter $a(a|b){*}$.
Finalement, on a affaire à un automate ayant les seuls états $0$
(initial) et $\infty$ (final) avec la seule transition $0\to\infty$
étiquetée par l'expression rationnelle $s$ recherchée :
\[
\varepsilon \,|\, bb{*} \,|\, a(a|b){*}
\]
qui dénote le langage $M$ complémentaire de $L$.  (Autrement dit : un
mot qui \emph{n'est pas} un nombre $\geq 1$ de $b$ suivi d'un $a$
suivi de n'importe quoi, c'est la même chose qu'un mot soit vide, soit
formé uniquement d'un nombre $\geq 1$ de $b$, soit d'un $a$ suivi de
n'importe quoi.)
\end{corrige}


%
%
%

\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 abc \;|\; aSbc \;|\; abSc
\]
On appellera « $0$ » la règle $S \rightarrow abc$, 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.)

\begin{corrige}
L'arbre d'analyse est le suivant :
% S<a.b.S<a.S<a.b.c.>b.c.>c.>
\begin{center}
\begin{tikzpicture}[line join=bevel,baseline=(S0.base)]
\node (S0) at (68.750bp,0.000bp) [draw=none] {$S$};
\node (a0) at (0.000bp,-30.000bp) [draw=none] {$a$};  \draw (S0) -- (a0);
\node (b0) at (20.000bp,-30.000bp) [draw=none] {$b$};  \draw (S0) -- (b0);
\node (S1) at (95.000bp,-30.000bp) [draw=none] {$S$};  \draw (S0) -- (S1);
\node (a1) at (40.000bp,-60.000bp) [draw=none] {$a$};  \draw (S1) -- (a1);
\node (S2) at (80.000bp,-60.000bp) [draw=none] {$S$};  \draw (S1) -- (S2);
\node (a2) at (60.000bp,-90.000bp) [draw=none] {$a$};  \draw (S2) -- (a2);
\node (b1) at (80.000bp,-90.000bp) [draw=none] {$b$};  \draw (S2) -- (b1);
\node (c0) at (100.000bp,-90.000bp) [draw=none] {$c$};  \draw (S2) -- (c0);
\node (b2) at (120.000bp,-60.000bp) [draw=none] {$b$};  \draw (S1) -- (b2);
\node (c1) at (140.000bp,-60.000bp) [draw=none] {$c$};  \draw (S1) -- (c1);
\node (c2) at (160.000bp,-30.000bp) [draw=none] {$c$};  \draw (S0) -- (c2);
\end{tikzpicture}
\end{center}
\vskip-\baselineskip\vskip-1ex\strut
\end{corrige}

On va maintenant montrer que $G$ est inambiguë.

(2) Expliquer pourquoi 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$).

\begin{corrige}
Les trois règles $0,1,2$ ont toutes le terminal $a$ comme premier
symbole de leur membre de droite.  Le fils le plus à gauche de la
racine (étiquetée $S$) dans n'importe quel arbre d'analyse selon $G$
est nécessairement étiqueté $a$, et le mot analysé commence donc
nécessairement par $a$.  (Si on préfère, toute dérivation selon $G$
commence par une règle produisant $a$ comme symbole le plus à gauche,
qui ne peut ensuite jamais être effacé ni réécrit puisqu'il s'agit
d'un terminal.)
\end{corrige}

(3) Montrer que tout mot de $L$ dérivé en démarrant
par\footnote{C'est-à-dire : tout mot $w$ possédant une dérivation
  selon $G$ de la forme $S \Rightarrow aSbc \mathrel{\Rightarrow^*} w$
  où $\mathrel{\Rightarrow^*}$ désigne une succession quelconque de
  dérivations immédiates.  Ou, ce qui revient au même (et on pourra
  tenir ce point pour acquis) : tout mot $w$ possédant un arbre
  d'analyse dont la racine a quatre fils étiquetés $a,S,b,c$ dans cet
  ordre.} la règle $1$ a nécessairement $aa$ comme préfixe.  Montrer
de même que tout mot de $L$ dérivé en démarrant par la règle $2$ a
nécessairement $aba$ comme préfixe.

\begin{corrige}
Si dans un arbre d'analyse $\mathscr{T}$ selon $G$ la racine
(étiquetée $S$) a quatre fils étiquetés $a,S,b,c$ dans cet ordre
(i.e., en démarrant par la règle $1$), les descendants du deuxième
fils (celui étiqueté $S$) forment eux-mêmes un arbre d'analyse
$\mathscr{T}'$ selon $G$, dont le mot analysé $w'$ (d'après la
question précédente) commence par $a$, si bien que le mot $w = aw'bc$
analysé par $\mathscr{T}$ commence par $aa$.  (Si on préfère : une
dérivation de la forme $S \buildrel 1\over\Rightarrow aSbc
\mathrel{\Rightarrow^*} w$ a nécessairement $w = aw'bc$ où $w'$ est le
mot obtenu en appliquant les mêmes règles à $S$, qui commence donc
par $a$, si bien que $w$ commence par $aa$.)

Un raisonnement analogue conduit à conclure que tout mot dérivé en
démarrant par la règle $2$ a la forme $abw'c$ où $w'\in L$ donc
commence par $a$, si bien que le mot commence par $aba$.
\end{corrige}

(4) En déduire comment, d'après les premières lettres d'un mot $w$
de $L$, on peut savoir par quelle règle démarre 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$).

\begin{corrige}
Si on appelle $L_0,L_1,L_2$ les parties de $L$ constituées des mots
ayant une dérivation selon $G$ démarrant par les règles $0,1,2$
respectivement, on a trivialement $L_0 = \{abc\}$ et on vient de voir
que les mots de $L_1$ ont $aa$ comme préfixe et ceux de $L_2$ ont
$aba$ comme préfixe.  Notamment :
\begin{itemize}
\item $L_0,L_1,L_2$ sont disjoints (i.e., la règle par laquelle
  démarre une dérivation de $w$ est déterminée par $w$), et
\item on peut savoir si un mot $w \in L$ appartient à $L_0$, $L_1$
  ou $L_2$ en regardant s'il commence par $abc$, $aa$ ou $aba$.
\end{itemize}
Ce qui répond à la question posée.
\end{corrige}

(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.

\begin{corrige}
Si $\mathscr{T}$ est un arbre d'analyse de $w$ selon $G$, on obtient
un arbre d'analyse $\mathscr{T}^\sharp$ de $w^\sharp := awbc$ de la
façon suivante : les quatre fils de la racine (étiquetée $S$) de
$\mathscr{T}^\sharp$ sont étiquetés $a,S,b,c$ respectivement (i.e., on
démarre par la règle $1$), et le second fils (celui étiqueté $S$) a
pour descendance une copie de $\mathscr{T}$ : ceci forme manifestement
un arbre d'analyse selon $G$, dont le mot analysé est $w^\sharp :=
awbc$.  \emph{Réciproquement}, comme $w^\sharp := awbc$ commence
par $aa$ (i.e., a $aa$ pour préfixe), on vient de voir que toute
dérivation de ce mot selon $G$ démarre nécessairement par la
règle $1$, donc a la forme qu'on vient de décrire.  (Autrement dit :
$\mathscr{T} \mapsto \mathscr{T}^\sharp$ définit une bijection entre
les arbres d'analyse de $w$ et ceux de $awbc$.)

Les mêmes considérations valent, \textit{mutatis mutandis} pour les
mots de la forme $w^\flat := abwc$ en commençant par la règle $2$.
\end{corrige}

(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.

\begin{corrige}
D'après les questions suivantes, tout mot de $L$ est dans un et un
seul des trois cas suivants : soit c'est le mot $abc$ produit par la
règle $abc$, soit il commence par $aa$ et c'est un mot de la forme
$awbc$ produit par une dérivation démarrant par la règle $1$ puis en
suivant une dérivation de $w$, soit il commence par $aba$ et c'est un
mot de la forme $abwc$ produit par une dérivation démarrant par la
règle $2$ puis en suivant une dérivation de $w$.  (Si on veut, $L$ est
réunion disjointe de $L_0,L_1,L_2$ où $L_0 = \{abc\}$ et $w \mapsto
awbc$ est une bijection $L \to L_1$ et $w \mapsto abwc$ est une
bijection $L \to L_2$.)

Il résulte par récurrence sur la longueur de $w \in L$ que $w$ a un
unique arbre d'analyse selon $G$ : en effet, il est soit de la forme
$abc$, soit de la forme $aw'bc$, soit de la forme $abw'c$ avec dans
les deux derniers cas $|w'| < |w|$ (précisément $|w'| = |w|-3$), donc
$w'$ a un unique arbre d'anayse selon $G$ par récurrence, d'où il
résulte que $w$ a un unique arbre d'analyse (qui s'obtient à partir de
celui de $w'$ en mettant la règle $1$ ou $2$ au sommet comme expliqué
dans la question (5)).

Cette démonstration est constructive, c'est-à-dire qu'on a
l'algorithme suivant qui analyse un mot $w$ :
\begin{itemize}
\item si le mot $w$ à analyser est $abc$, renvoyer l'arbre de la
  règle $0$ (c'est-à-dire ayant une racine étiquetée $S$ avec trois
  fils, tous des feuilles, étiquetés $a,b,c$ respectivement) ;
\item sinon, si $w$ commence par $aa$, vérifier qu'il termine par $bc$
  (sinon terminer avec une erreur d'analyse), appeler $w'$ le mot
  obtenu en effaçant le $a$ initial et le $bc$ final, appliquer
  récursivement l'algorithme qu'on est en train de définir au
  mot $w'$, il retourne un arbre d'analyse $\mathscr{T}'$, et renvoyer
  l'arbre d'analyse $\mathscr{T}$ fabriqué à partir de la règle $1$ et
  de l'arbre $\mathscr{T}'$ (i.e., les quatre fils de la racine
  étiquetée $S$ de $\mathscr{T}$ sont étiquetés $a,S,b,c$
  respectivement, et le second fils a pour descendance une copie
  de $\mathscr{T}'$) ;
\item sinon, si $w$ commence par $aba$, vérifier qu'il termine par $c$
  (sinon terminer avec une erreur d'analyse), appeler $w'$ le mot
  obtenu en effaçant le $ab$ initial et le $c$ final, appliquer
  récursivement l'algorithme qu'on est en train de définir au
  mot $w'$, il retourne un arbre d'analyse $\mathscr{T}'$, et renvoyer
  l'arbre d'analyse $\mathscr{T}$ fabriqué à partir de la règle $2$ et
  de l'arbre $\mathscr{T}'$ (i.e., les quatre fils de la racine
  étiquetée $S$ de $\mathscr{T}$ sont étiquetés $a,b,S,c$
  respectivement, et le troisième fils a pour descendance une copie
  de $\mathscr{T}'$) ;
\item dans tout autre cas (i.e., si $w$ n'est pas $abc$ et commence
  par autre chose que $aa$ ou $aba$), terminer avec une erreur
  d'analyse.
\end{itemize}
\vskip-\baselineskip\strut
\end{corrige}


%
%
%

\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}