summaryrefslogtreecommitdiffstats
path: root/controle-20200123.tex
blob: 1ff6354db926f8f7dcd216918c96dee9e8827187 (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
556
557
558
559
560
561
562
563
564
565
566
567
568
569
570
571
572
573
574
575
576
577
578
579
580
581
582
583
584
585
586
587
588
589
590
591
592
593
594
595
596
597
598
599
600
601
602
603
604
605
606
607
608
609
610
611
612
613
614
615
616
617
618
619
620
621
622
623
624
625
626
627
628
629
630
631
632
633
634
635
636
637
638
639
640
641
642
643
644
645
646
647
%% 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{23 janvier 2020}
\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.

Dans l'exercice \ref{exercise-on-unary-languages}, les deux parties
peuvent en principe être traitées indépendamment, mais la première
donne un exemple aidant à comprendre la démarche de la seconde.

\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} : 2+(7+6)+5.

\ifcorrige
Ce corrigé comporte 9 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

Soit $\mathscr{A}$ l'automate fini suivant sur l'alphabet $\Sigma :=
\{a,b,c\}$ :

\begin{center}
\begin{tikzpicture}[>=latex,line join=bevel,automaton]
\node (S0) at (0bp,0bp) [draw,circle,state,initial] {$0$};
\node (S1) at (70bp,35bp) [draw,circle,state] {$1$};
\node (S2) at (70bp,-35bp) [draw,circle,state] {$2$};
\node (S3) at (140bp,0bp) [draw,circle,state,final] {$3$};
\draw [->] (S0) -- node[auto,near end] {$\varepsilon$} (S1);
\draw [->] (S0) -- node[auto,below] {$\varepsilon$} (S2);
\draw [->] (S1) to[out=225,in=135] node[auto,left] {$a$} (S2);
\draw [->] (S2) to[out=45,in=315] node[auto,right] {$b$} (S1);
\draw [->] (S2) to[loop below] node[auto] {$c$} (S2);
\draw [->] (S1) -- node[auto] {$\varepsilon$} (S3);
\draw [->] (S2) -- node[auto,below,near end] {$\varepsilon$} (S3);
\end{tikzpicture}
\end{center}

\vskip-\baselineskip\vskip-.5ex\noindent En lui appliquant la méthode
d'élimination des états, déterminer une expression rationnelle
dénotant le langage qu'il reconnaît.

\begin{corrige}
L'élimination de l'état $1$ conduit à l'automate suivant :
\begin{center}
\begin{tikzpicture}[>=latex,line join=bevel,automaton]
\node (S0) at (0bp,0bp) [draw,circle,state,initial] {$0$};
\node (S2) at (70bp,0bp) [draw,circle,state] {$2$};
\node (S3) at (140bp,0bp) [draw,circle,state,final] {$3$};
\draw [->] (S0) -- node[auto,below] {$\varepsilon|a$} (S2);
\draw [->] (S2) to[loop below] node[auto] {$c|ba$} (S2);
\draw [->] (S2) -- node[auto,below] {$\varepsilon|b$} (S3);
\draw [->] (S0) to[out=90,in=180] (60bp,35bp) -- node[auto] {$\varepsilon$} (80bp,35bp) to[out=0,in=90] (S3);
\end{tikzpicture}
\end{center}
\vskip-\baselineskip\vskip-.5ex\noindent — et l'élimination de
l'état $2$ conduit alors à l'expression rationnelle suivante :
$\varepsilon\;|\;(\varepsilon|a)\,(c|ba){*}\,(\varepsilon|b)$ (il se
trouve que le premier terme est inutile et que cette expression
rationnelle est équivalente à
simplement $(\varepsilon|a)\,(c|ba){*}\,(\varepsilon|b)$, mais la
méthode d'élimination proprement menée conduit à ce qui a été dit).

Si on élimine d'abord l'état $2$, on aboutit à l'automate suivant :
\begin{center}
\begin{tikzpicture}[>=latex,line join=bevel,automaton]
\node (S0) at (0bp,0bp) [draw,circle,state,initial] {$0$};
\node (S1) at (70bp,0bp) [draw,circle,state] {$1$};
\node (S3) at (140bp,0bp) [draw,circle,state,final] {$3$};
\draw [->] (S0) -- node[auto,below] {$\varepsilon|c{*}b$} (S1);
\draw [->] (S1) to[loop below] node[auto] {$ac{*}b$} (S1);
\draw [->] (S1) -- node[auto,below] {$\varepsilon|ac{*}$} (S3);
\draw [->] (S0) to[out=90,in=180] (60bp,35bp) -- node[auto] {$c{*}$} (80bp,35bp) to[out=0,in=90] (S3);
\end{tikzpicture}
\end{center}
\vskip-\baselineskip\vskip-.5ex\noindent — et à l'expression
rationnelle suivante :
$c{*}\;|\;(\varepsilon|c{*}b)\,(ac{*}b){*}\,(\varepsilon|ac{*})$.
Elle est, bien sûr, équivalente à celle obtenue avec l'autre ordre
d'élimination.
\end{corrige}


%
%
%

\exercice\label{exercise-on-unary-languages}

Dans cet exercice, on pose $\Sigma := \{a\}$ (alphabet à une seule
lettre), de sorte que $\Sigma^* = \{a^n : n\in\mathbb{N}\}$ ; on va
appliquer les automates finis à un problème arithmétique.

\medskip

\textbf{Première partie : étude d'un cas particulier.}

\nobreak

Dans cette partie, on considère l'expression rationnelle $r$
suivante : $(aaa|aaaaa){*}$ (sur l'alphabet $\Sigma$).  On appelle $L
:= L(r)$ le langage qu'elle dénote et $M := \Sigma^* \setminus L$ son
complémentaire.

(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 $\mathscr{A}_1$, ayant
$9$ états.  À 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$ obtenu est le suivant :
\begin{center}
\begin{tikzpicture}[>=latex,line join=bevel,automaton]
\node (S0) at (0bp,0bp) [draw,circle,state,initial,final,accepting below] {$0$};
\node (S1) at (60bp,35bp) [draw,circle,state] {$1$};
\node (S2) at (120bp,35bp) [draw,circle,state] {$2$};
\node (S3) at (180bp,35bp) [draw,circle,state,final] {$3$};
\node (S1p) at (60bp,-35bp) [draw,circle,state] {\vbox to0pt{\vss\hbox to0pt{$1'$\hss}}\phantom{$1$}};
\node (S2p) at (120bp,-35bp) [draw,circle,state] {\vbox to0pt{\vss\hbox to0pt{$2'$\hss}}\phantom{$2$}};
\node (S3p) at (180bp,-35bp) [draw,circle,state] {\vbox to0pt{\vss\hbox to0pt{$3'$\hss}}\phantom{$3$}};
\node (S4p) at (240bp,-35bp) [draw,circle,state] {\vbox to0pt{\vss\hbox to0pt{$4'$\hss}}\phantom{$4$}};
\node (S5p) at (300bp,-35bp) [draw,circle,state,final] {\vbox to0pt{\vss\hbox to0pt{$5'$\hss}}\phantom{$5$}};
\draw [->] (S0) -- node[auto] {$a$} (S1);
\draw [->] (S1) -- node[auto] {$a$} (S2);
\draw [->] (S2) -- node[auto] {$a$} (S3);
\draw [->] (S0) -- node[auto,below] {$a$} (S1p);
\draw [->] (S1p) -- node[auto,below] {$a$} (S2p);
\draw [->] (S2p) -- node[auto,below] {$a$} (S3p);
\draw [->] (S3p) -- node[auto,below] {$a$} (S4p);
\draw [->] (S4p) -- node[auto,below] {$a$} (S5p);
\draw [->] (S3) -- node[auto,above,near end] {$a$} (S1p);
\draw [->] (S5p) -- node[auto,below,very near end] {$a$} (S1);
\draw [->] (S3) to[out=90,in=0] (130bp,70bp) -- node[auto,below] {$a$} (110bp,70bp) to[out=180,in=90] (S1);
\draw [->] (S5p) to[out=210,in=0] (190bp,-70bp) -- node[auto,above] {$a$} (170bp,-70bp) to[out=180,in=330] (S1p);
\end{tikzpicture}
\end{center}
C'est l'automate de Glushkov.  Si on commence par construire
l'automate de Thompson, celui-ci a $20$ états, et l'élimination des
transitions spontanées conduit à l'automate $\mathscr{A}_1$ qu'on
vient d'écrire.
\end{corrige}

(2) Déterminiser l'automate $\mathscr{A}_1$.  On appellera
$\mathscr{A}_2$ l'automate (déterministe complet) en question.  (On
obtient un automate $\mathscr{A}_2$ ayant $14$ états.  On n'hésitera
pas à introduire des notations allégées si on le juge utile ; il
pourra être judicieux de réfléchir au préalable à une façon de nommer
les états de $\mathscr{A}_1$ qui rend la construction
de $\mathscr{A}_2$ plus facile à mener sans se tromper.)

Pour simplifier les questions suivantes (ainsi que le travail du
correcteur), on renommera si nécessaire les états de $\mathscr{A}_2$
de façon que, autant que possible, l'état résultant de la lecture du
mot $a^i$ par l'automate soit numéroté $i$.

\begin{corrige}
On travaille sur des ensembles d'états en suivant l'algorithme de
déterminisation : partant de l'ensemble $\{0\}$ des états initiaux de
l'automate $\mathscr{A}_1$, il n'y a à chaque fois qu'une seule
transition (étiquetée par $a$) à considérer, ce qui construit
successivement les états suivants (colonne du milieu de la table) :
\begin{center}
\begin{tabular}{c|l|c}
$0$&$\{0\}$&F\\\hline
$1$&$\{1,1'\}$&\\\hline
$2$&$\{2,2'\}$&\\\hline
$3$&$\{3,3'\}$&F\\\hline
$4$&$\{1,1',4'\}$&\\\hline
$5$&$\{2,2',5'\}$&F\\\hline
$6$&$\{1,1',3,3'\}$&F\\\hline
$7$&$\{1,1',2,2',4'\}$&\\\hline
$8$&$\{2,2',3,3',5'\}$&F\\\hline
$9$&$\{1,1',3,3',4'\}$&F\\\hline
$10$&$\{1,1',2,2',4',5'\}$&F\\\hline
$11$&$\{1,1',2,2',3,3',5'\}$&F\\\hline
$12$&$\{1,1',2,2',3,3',4'\}$&F\\\hline
$13$&$\{1,1',2,2',3,3',4',5'\}$&F\\
\end{tabular}
\end{center}
Le procédé de calcul de la table est le suivant : à chaque ligne à
partir de la deuxième, on incrémente tous les numéros avec et sans
prime, sauf que $3$ ou $5'$ deviennent $1,1'$ (les deux à la fois,
puisqu'il y a des transitions de $3$ et $5'$ vers $1$ et $1'$
dans $\mathscr{A}_1$).  Ceci permet de ne pas se tromper (d'où
l'intérêt d'avoir judicieusement étiqueté les états
de $\mathscr{A}_1$).  L'unique transition de l'automate (évidemment
étiquetée $a$) conduit de chaque ligne à la ligne suivante, sauf la
dernière ligne qui boucle sur elle-même.  Les états finaux sont ceux
qui contiennent un des états finaux de $\mathscr{A}_1$, c'est-à-dire
$0$ ou $3$ ou $5'$ (ou encore, les lignes qui précèdent une ligne
avec $1,1'$), on les a marqués par un F dans la colonne de droite de
la table ci-dessus.

On peut bien sûr préférer tracer graphiquement l'automate comme
d'habitude : c'est juste une ligne de $14$ états, toutes les
transitions étant étiquetées $a$, menant de chaque état vers le
suivant, sauf du dernier sur lui-même, certains états étant finaux
comme on vient de le dire.

On renumérote alors les états comme selon la colonne de gauche de la
table, c'est-à-dire en suivant l'ordre des lignes.  La transition
étiquetée $a$ mène alors de l'état $i$ vers l'état $i+1$ sauf pour
$i=13$ où elle mène vers lui-même.  L'ensemble des états finaux est $F
= \{0,3,5,6,8,9,10,11,12,13\}$ comme indiqué par la table.
(Dans la notation introduite à la question (6) plus bas, l'automate
$\mathscr{A}_2$ est décrit par $j_2 = 14$, $j_1 = 13$ et $F =
\{0,3,5,6,8,9,10,11,12,13\}$.)
\end{corrige}

(3) Minimiser l'automate $\mathscr{A}_2$.  On appellera
$\mathscr{A}_3$ l'automate canonique ainsi obtenu.
(On obtient un automate ayant $9$ états.)

\begin{corrige}
On a bien affaire pour commencer à un automate $\mathscr{A}_2$
déterministe complet sans état inaccessible.

L'algorithme de minimisation commence par partitionner l'ensemble
$\{0,\ldots,13\}$ des états en deux classes, les finaux
$\{0,3,5,6,8,9,10,11,12,13\}$ et les non-finaux $\{1,2,4,7\}$.  Une
première itération sépare les finaux en $\{5,8,9,10,11,12,13\}$ et
$\{0,3,6\}$ (selon que l'état vers lequel aboutit l'unique transition
est lui-même final ou non) et les non-finaux en $\{2,4,7\}$ et $\{1\}$
(idem).  La seconde itération sépare chacun de $0$, $2$ et $5$ des
autres états de leur classe respective : les classes sont alors
$\{0\}$, $\{1\}$, $\{2\}$, $\{3,6\}$, $\{4,7\}$ et
$\{8,9,10,11,12,13\}$.  La troisième itération sépare $4$ et $7$
tandis que la quatrième sépare $3$ et $6$.  Finalement, on obtient un
automate $\mathscr{A}_3$ canonique ayant $9$ états : un pour chaque
état de l'automate $\mathscr{A}_2$ entre $0$ et $7$ inclus, et un pour
tous les états de $8$ à $13$ inclus.

On pouvait aussi arguër de manière plus abstraite : il est clair que
tous les états $8$ à $13$ devront être fusionnés puisqu'ils sont
finaux et que leurs transitions arbitrairement itérées ne conduisent
qu'à des états finaux, tandis que les états $0$ à $7$ inclus devront
être tous séparés puisqu'ils sont distingués par le nombre de
transitions à partir desquelles on n'arrive plus qu'à des états
finaux.

On peut bien sûr tracer graphiquement l'automate $\mathscr{A}_3$ comme
d'habitude : c'est juste une ligne de $9$ états, toutes les
transitions étant étiquetées $a$, menant de chaque état vers le
suivant, sauf du dernier sur lui-même, les états finaux étant ceux
numérotés $0,3,5,6,8$ si on numérote les états de $0$ à $8$ dans
l'ordre des transitions.  (Dans la notation introduite à la
question (6) plus bas, l'automate $\mathscr{A}_3$ est décrit par
$j_2 = 9$, $j_1 = 8$ et $F = \{0,3,5,6,8\}$.)
\end{corrige}

(4) Construire un automate fini déterministe complet $\mathscr{A}_4$
reconnaissant le langage $M := \Sigma^*\setminus L$ complémentaire
de $L$.  Ce langage $M$ est fini : énumérer exhaustivement les mots
qu'il contient.

\begin{corrige}
Il suffit d'échanger états finaux et non-finaux dans un automate
déterministe complet quelconque reconnaissant $L$, disons l'automate
$\mathscr{A}_3$ (on pouvait aussi utiliser $\mathscr{A}_2$ si on n'a
pas réussi à calculer $\mathscr{A}_3$).  On peut bien sûr tracer
graphiquement l'automate $\mathscr{A}_4$ comme d'habitude : c'est
juste une ligne de $9$ états, toutes les transitions étant
étiquetées $a$, menant de chaque état vers le suivant, sauf du dernier
sur lui-même, les états finaux étant ceux numérotés $1,2,4,7$ si on
numérote les états de $0$ à $8$ dans l'ordre des transitions.  (Dans
la notation introduite à la question (6) plus bas, l'automate
$\mathscr{A}_3$ est décrit par $j_2 = 9$, $j_1 = 8$ et $F =
\{1,2,4,7\}$.)

L'état $8$ (i.e., le dernier) étant un puits dans
l'automate $\mathscr{A}_4$, les seuls mots acceptés le sont avant le
puits, et ce sont les mots $a$, $aa$, $aaaa = a^4$ et $aaaaaaa = a^7$
comme donnés par les états finaux de $\mathscr{A}_4$.
\end{corrige}

(5) En utilisant la question précédente, dire quels sont les (quatre)
entiers naturels ne pouvant pas s'écrire sous la forme $3m+5m'$ avec
$m,m'\in\mathbb{N}$.

\begin{corrige}
Si $n = 3m+5m'$ alors le mot $a^n = (aaa)^m(aaaaa)^{m'}$ appartient
à $L$, c'est-à-dire qu'il vérifie $r$ puisqu'il est manifestement
concaténation de mots de la forme $aaa$ ou $aaaaa$.  Réciproquement,
si le mot $a^n$ appartient à $L$, c'est-à-dire vérifie $r$, i.e.,
concaténation de mots de la forme $aaa$ et de la forme $aaaaa$, disons
$m$ de l'un et $m'$ de l'autre (en tout), il a pour longueur $n =
3m+5m'$.  Bref, les mots de $L$ sont exactement les $a^n$ avec $n$ de
la forme $3m+5m'$ ; et les mots qui ne sont pas dans $L$ (i.e., sont
dans $M$) sont exactement les $a^n$ avec $n$ ne pouvant pas s'écrire
de la forme $3m+5m'$ : on a vu que ce sont $a$, $aa$, $aaaa = a^4$ et
$aaaaaaa = a^7$.  Ainsi, les quatre entiers naturels ne pouvant pas
s'écrire sous la forme $3m+5m'$ avec $m,m'\in\mathbb{N}$ sont : $1$,
$2$, $4$ et $7$.
\end{corrige}

\medbreak

\textbf{Seconde partie : considérations générales.}

\nobreak

(6) Expliquer rapidement pourquoi un automate fini déterministe
complet sans état inaccessible $\mathscr{A}$ sur $\Sigma = \{a\}$
prend nécessairement la forme suivante : si on note $j_2$ son nombre
d'états, on peut numéroter ces états de $0$ à $j_2-1$, avec $0$ l'état
initial, et de façon qu'il y ait une unique transition étiquetée $a$
de l'état $i$ vers l'état $i+1$ pour chaque $0\leq i<j_2-1$, ainsi
qu'une transition étiquetée $a$ de l'état $j_2-1$ vers l'état $j_1$
pour un certain $0\leq j_1<j_2$.  Remarquer que l'automate
$\mathscr{A}$ est alors complètement décrit par les entiers $0\leq
j_1<j_2$ et par le sous-ensemble $F$ de $\{0,\ldots,j_2-1\}$ formé des
états finaux.

\begin{corrige}
Appelons $q_0$ l'état initial de $\mathscr{A}$, et par récurrence
sur $i$, posons $q_{i+1} = \delta(q_i,a)$ l'état vers lequel pointe la
transition sortante depuis l'état $q_i$ étiquetée par la lettre $a$
(cette transition étant unique puisqu'on a affaire à un automate
déterministe complet) ; ou, pour dire les choses autrement, appelons
$q_i = \delta^*(q_0, a^i)$ (pour tout $i\in \mathbb{N}$) l'état
résultant de la lecture du mot $a^i$ par l'automate.  L'automate
$\mathscr{A}$ étant fini, les états $q_0,q_1,q_2,\ldots$ ne peuvent
pas être tous distincts : il existe $j_1\neq j_2$ tels que $q_{j_1} =
q_{j_2}$ ; appelons $j_2$ l'indice de la première répétition, i.e., le
plus petit entier tel que $q_{j_2}$ coïncide avec un état $q_{j_1}$
avec $0\leq j_1<j_2$.  Alors (puisque $j_2$ est l'indice de la
première répétition) les états $q_0,\ldots,q_{j_2-1}$ sont tous
distincts.  En nommant simplement $i$ l'état $q_i$ (pour $0\leq i<j_2$
uniquement), on a, par construction, $\delta(i,a) = i+1$ pour $0\leq
i<j_2-1$ tandis que $\delta(j_2-1,a) = j_1$, comme annoncé.  De plus,
les états $0,\ldots,j_2-1$ étant tous ceux qu'on peut atteindre en
partant de $0$ et en suivant les transitions, ce sont tous les états
de l'automate (car on l'a supposé sans état inaccessible), donc $j_2$
est le nombre d'états, et l'automate a bien la forme demandée.

(Les notations choisies sont censées rappeler la démonstration du
lemme de pompage, qui utilise la même idée.  Aussi dans le même ordre
d'idées, il est utile pour la question suivante de remarquer que $q_i
= q_{i+(j_2-j_1)}$ dès que $i\geq j_1$, et donc plus généralement $q_i
= q_{i+k(j_2-j_1)}$ pour tout $k\in\mathbb{N}$.)
\end{corrige}

(7) Une fois un automate déterministe complet sur $\Sigma$ présenté
comme décrit à la question (6), à quelle condition nécessaire et
suffisante (sur $j_1,j_2,F$) le langage qu'il reconnaît est-il fini ?

\begin{corrige}
Les états $i$ tels que $j_1\leq i<j_2$ avec la notation introduite
en (6) sont des états résultat de la lecture d'un nombre infini de
mots distincts (à savoir $a^i$, $a^{i+(j_2-j_1)}$, et plus
généralement $a^{i+k(j_2-j_1)}$ pour tout $k\in\mathbb{N}$).  Si l'un
quelconque de ces états est acceptant (=final), le langage reconnu par
l'automate est infini.  À l'inverse, si aucun de ces états n'est
acceptant, le langage est fini et égal à $\{a^i : i\in F\}$.

Bref, la condition nécessaire et suffisante de finitude du langage
reconnu par $\mathscr{A}$ est que $F \cap \{j_1,\ldots,j_2-1\} =
\varnothing$, et le cas échéant, le langage est constitué des $a^i$
pour $i\in F$ (et $i<j_1$).
\end{corrige}

(8) Déduire de l'ensemble de cet exercice que le problème suivant est
calculable algorithmiquement\footnote{Autrement dit, montrer qu'il
  existe un algorithme qui, prenant en entrée $\ell_1,\ldots,\ell_r
  \in \mathbb{N}$, termine toujours en temps fini et répond au
  problème posé.} : donné des entiers naturels $\ell_1,\ldots,\ell_r
\in \mathbb{N}$, décider si l'ensemble\footnote{Autrement dit, il
  s'agit de l'ensemble $\mathbb{N} \setminus \{\ell_1 m_1 + \cdots +
  \ell_r m_r : (m_1,\ldots,m_r)\in \mathbb{N}^r\}$ complémentaire de
  l'image de $\mathbb{N}^r \to \mathbb{N},\penalty0\; (m_1,\ldots,m_r)
  \mapsto \ell_1 m_1 + \cdots + \ell_r m_r$.} des entiers naturels qui
ne peuvent pas s'écrire sous la forme $\ell_1 m_1 + \cdots + \ell_r
m_r$ avec $m_1,\ldots,m_r \in \mathbb{N}$ est fini, et, le cas
échéant, les énumérer.

\begin{corrige}
Il suffit d'appliquer la même méthode qui a été utilisée dans les
questions précédentes : donnés $\ell_1,\ldots,\ell_r \in \mathbb{N}$,
on fabrique l'expression rationnelle
$(a^{\ell_1}|\cdots|a^{\ell_r}){*}$ sur $\Sigma$, on construit son
automate de Glushkov (ou de Thompson dont on élimine ensuite les
transitions spontanées), on le déterminise, on peut éventuellement le
minimiser même si ce n'est pas nécessaire pour cette question, on
échange états finaux et non-finaux pour obtenir un automate
reconnaissant le langage complémentaire, et enfin on utilise le
critère trouvé en (7) pour savoir si ce langage est fini et, le cas
échéant, l'énumérer.  Par le même raisonnement qu'en (5), ceci donne
exactement les $a^n$ pour les $n$ qui ne peuvent pas s'écrire sous la
forme $\ell_1 m_1 + \cdots + \ell_r m_r$ avec $m_1,\ldots,m_r \in
\mathbb{N}$.

\emph{Remarque :} En fait, il s'avère que l'ensemble $\mathbb{N}
\setminus \{\ell_1 m_1 + \cdots + \ell_r m_r : (m_1,\ldots,m_r)\in
\mathbb{N}^r\}$ est fini si et seulement si le pgcd de
$\ell_1,\ldots,\ell_r$ vaut $1$ (i.e., si et seulement si ces nombres
sont premiers entre eux dans leur ensemble), ce qui est aussi testable
algorithmiquement ; mais ce n'était pas demandé ici, et ceci ne résout
pas la question d'énumérer explicitement l'ensemble.
\end{corrige}


%
%
%

\exercice

On considère la grammaire hors-contexte $G$ d'axiome $S$ et de
nonterminaux $N = \{S, T, U\}$ sur l'alphabet $\Sigma = \{a,b,c\}$
donnée par
\[
\begin{aligned}
S &\rightarrow T \;|\; TaS\\
T &\rightarrow U \;|\; UbT\\
U &\rightarrow c\\
\end{aligned}
\]
(La grammaire en question est inambiguë : on ne demande pas de le
démontrer.)

(1) Donner les arbres d'analyse (= de dérivation) des mots suivants :
$cacbcac$ et $cbcacbc$.

\begin{corrige}
On obtient les arbres d'analyse suivants :

\hbox to\hsize{
% S<T<U<c.>>a.S<T<U<c.>b.T<U<c.>>>a.S<T<U<c.>>>>>
\begin{tikzpicture}[line join=bevel,baseline=(S0.base)]
\node (S0) at (37.778bp,0.000bp) [draw=none] {$S$};
\node (T0) at (0.000bp,-30.000bp) [draw=none] {$T$};  \draw (S0) -- (T0);
\node (U0) at (0.000bp,-50.000bp) [draw=none] {$U$};  \draw (T0) -- (U0);
\node (c0) at (0.000bp,-70.000bp) [draw=none] {$c$};  \draw (U0) -- (c0);
\node (a0) at (20.000bp,-30.000bp) [draw=none] {$a$};  \draw (S0) -- (a0);
\node (S1) at (93.333bp,-30.000bp) [draw=none] {$S$};  \draw (S0) -- (S1);
\node (T1) at (60.000bp,-60.000bp) [draw=none] {$T$};  \draw (S1) -- (T1);
\node (U1) at (40.000bp,-90.000bp) [draw=none] {$U$};  \draw (T1) -- (U1);
\node (c1) at (40.000bp,-110.000bp) [draw=none] {$c$};  \draw (U1) -- (c1);
\node (b0) at (60.000bp,-90.000bp) [draw=none] {$b$};  \draw (T1) -- (b0);
\node (T2) at (80.000bp,-90.000bp) [draw=none] {$T$};  \draw (T1) -- (T2);
\node (U2) at (80.000bp,-110.000bp) [draw=none] {$U$};  \draw (T2) -- (U2);
\node (c2) at (80.000bp,-130.000bp) [draw=none] {$c$};  \draw (U2) -- (c2);
\node (a1) at (100.000bp,-60.000bp) [draw=none] {$a$};  \draw (S1) -- (a1);
\node (S2) at (120.000bp,-60.000bp) [draw=none] {$S$};  \draw (S1) -- (S2);
\node (T3) at (120.000bp,-80.000bp) [draw=none] {$T$};  \draw (S2) -- (T3);
\node (U3) at (120.000bp,-100.000bp) [draw=none] {$U$};  \draw (T3) -- (U3);
\node (c3) at (120.000bp,-120.000bp) [draw=none] {$c$};  \draw (U3) -- (c3);
\end{tikzpicture}
\hss et\hss
% S<T<U<c.>b.T<U<c.>>>a.S<T<U<c.>b.T<U<c.>>>>>
\begin{tikzpicture}[line join=bevel,baseline=(S0.base)]
\node (S0) at (60.000bp,0.000bp) [draw=none] {$S$};
\node (T0) at (20.000bp,-30.000bp) [draw=none] {$T$};  \draw (S0) -- (T0);
\node (U0) at (0.000bp,-60.000bp) [draw=none] {$U$};  \draw (T0) -- (U0);
\node (c0) at (0.000bp,-80.000bp) [draw=none] {$c$};  \draw (U0) -- (c0);
\node (b0) at (20.000bp,-60.000bp) [draw=none] {$b$};  \draw (T0) -- (b0);
\node (T1) at (40.000bp,-60.000bp) [draw=none] {$T$};  \draw (T0) -- (T1);
\node (U1) at (40.000bp,-80.000bp) [draw=none] {$U$};  \draw (T1) -- (U1);
\node (c1) at (40.000bp,-100.000bp) [draw=none] {$c$};  \draw (U1) -- (c1);
\node (a0) at (60.000bp,-30.000bp) [draw=none] {$a$};  \draw (S0) -- (a0);
\node (S1) at (100.000bp,-30.000bp) [draw=none] {$S$};  \draw (S0) -- (S1);
\node (T2) at (100.000bp,-50.000bp) [draw=none] {$T$};  \draw (S1) -- (T2);
\node (U2) at (80.000bp,-80.000bp) [draw=none] {$U$};  \draw (T2) -- (U2);
\node (c2) at (80.000bp,-100.000bp) [draw=none] {$c$};  \draw (U2) -- (c2);
\node (b1) at (100.000bp,-80.000bp) [draw=none] {$b$};  \draw (T2) -- (b1);
\node (T3) at (120.000bp,-80.000bp) [draw=none] {$T$};  \draw (T2) -- (T3);
\node (U3) at (120.000bp,-100.000bp) [draw=none] {$U$};  \draw (T3) -- (U3);
\node (c3) at (120.000bp,-120.000bp) [draw=none] {$c$};  \draw (U3) -- (c3);
\end{tikzpicture}
}

(On les trouve plus facilement si on se convainc d'abord que la
grammaire peut être vue comme décrivant une expression de termes $c$
reliés par deux opérations binaires $a$ et $b$, toutes les deux
associatives à droite, et l'opération $b$ étant prioritaire sur $a$.
Autrement dit, l'expression dérivant de $S$ est coupée d'abord au
niveau des $a$ en des sous-expressions dérivant de $T$, elles-mêmes
coupées au niveau des $b$.)
\end{corrige}

(2) Le langage $L := L(G)$ engendré par $G$ est, en fait, rationnel :
expliquer brièvement pourquoi, et donner une expression rationnelle
qui le dénote.  (On pourra commencer par décrire le langage $L' :=
L(G,T) := \{w \in \Sigma^* : T \mathrel{\Rightarrow^*_G} w\}$ des mots
qui dérivent de $T$ selon $G$.)

\begin{corrige}
Le langage $L' = L(G,T)$ est celui décrit par la grammaire $T
\rightarrow c \;|\; cbT$ d'axiome $T$ (le nonterminal $U$ est
visiblement inutile et peut être directement remplacé par $c$ pour y
voir plus clair).  Il s'agit visiblement du langage dénoté par
l'expression rationnelle $(cb){*}c$ (ceci se démontre par exemple en
remarquant que ses dérivations sont toutes de la forme $T \Rightarrow
cbT \Rightarrow \cdots \Rightarrow (cb)^k T \Rightarrow (cb)^k c$, ou
en raisonnant sur les arbres d'analyse qui sont formés en empilant des
$T$ ayant pour fils gauche $c$ et $b$ et pour fils droite un autre $T$
jusqu'à un dernier $T$ qui a pour seul fils $c$ ; on peut aussi
remarquer qu'il s'agit essentiellement d'une grammaire régulière) : si
on préfère, $L'$ est le plus petit langage tel que $L' = \{c\} \cup
(\{c\}\{b\}L')$, ce que dénote justement $(cb){*}c$.  Bref, un mot de
$L'$ est une succession de $c$ séparés par des $b$, ce que dénote
justement $(cb){*}c$.

Le langage $L = L(G,S)$ est construit selon exactement le même modèle
à partir de $L'$ que $L'$ à partir de $c$ : si on préfère, $L$ est le
plus petit langage tel que $L = L' \cup (L'\{a\}L)$, donc on s'attend
à avoir ce qu'il soit dénoté par $((cb){*}ca){*}(cb){*}c$.  On peut
par exemple raisonner sur les arbres d'analyse : ils sont formés en
empilant des $S$ ayant pour fils gauche $T$ et $a$ et pour fils droite
un autre $S$ jusqu'à un dernier $S$ qui a pour seul fils $T$, et enfin
en insérant un arbre d'analyse d'un mot de $L'$ comme descendance de
chaque $T$.  Bref, un mot de $L$ est une succession de mots de $L'$
séparés par des $a$, ce que dénote justement $((cb){*}ca){*}(cb){*}c$.

Tout ceci étant dit, en fait, le langage $L$ peut aussi être dénoté
par une expression rationnelle plus simple, à savoir $(c(a|b)){*}c$
(ou encore $c((a|b)c){*}$ ou encore $c(ac|bc){*}$ ou toutes sortes
d'autres variantes), puisqu'il s'agit d'une succession de $c$ séparés
indifféremment par des $a$ ou des $b$.  Cette expression rationnelle
perd le découpage en deux niveaux (d'abord par $a$ puis par $b$)
effectué par la grammaire $G$, mais est correcte comme description du
langage.
\end{corrige}


%
%
%
\end{document}