summaryrefslogtreecommitdiffstats
path: root/controle-20170207.tex
blob: 4606537119eb458667b526dbba2dbe208a4a36ef (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
648
649
650
651
652
653
654
655
656
657
658
659
660
661
662
663
664
665
666
667
668
669
670
671
672
673
674
675
676
677
678
679
680
681
682
683
684
685
686
687
688
689
690
691
692
693
694
695
696
697
698
699
700
701
702
703
704
705
706
707
708
709
710
711
712
713
714
715
716
717
718
719
720
721
722
723
724
725
726
727
728
729
730
731
732
733
734
735
736
%% 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}
%
%
% 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{7 février 2017}
\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

On considère l'automate fini $M$ sur l'alphabet $\Sigma = \{a,b\}$
représenté par la figure suivante :
\begin{center}
\begin{tikzpicture}[>=latex,line join=bevel,automaton]
\node (X) at (-80bp,0bp) [draw,circle,state,initial] {$X$};
\node (Y) at (80bp,0bp) [draw,circle,state,final] {$Y$};
\node (A1) at (-40bp,50bp) [draw,circle,state] {$A\phantom{'}$};
\node (A2) at (40bp,50bp) [draw,circle,state] {$A'$};
\node (B1) at (-40bp,-50bp) [draw,circle,state] {$B\phantom{'}$};
\node (B2) at (40bp,-50bp) [draw,circle,state] {$B'$};
\draw[->] (X) -- node[auto]{$\varepsilon$} (A1);
\draw[->] (X) -- node[auto,below left]{$\varepsilon$} (B1);
\draw[->] (A1) -- node[auto]{$a$} (A2);
\draw[->] (B1) -- node[auto]{$b$} (B2);
\draw[->] (A1) to[loop above] node[auto]{$b$} (A1);
\draw[->] (A2) to[loop above] node[auto]{$b$} (A2);
\draw[->] (B1) to[loop below] node[auto]{$a$} (B1);
\draw[->] (B2) to[loop below] node[auto]{$a$} (B2);
\draw[->] (A2) -- node[auto]{$\varepsilon$} (Y);
\draw[->] (B2) -- node[auto,below right]{$\varepsilon$} (Y);
\end{tikzpicture}
\end{center}

(0) De quelle sorte d'automate s'agit-il ?  (Autrement dit : est-il
déterministe ou non ? avec transitions spontanées ou non ?)

(1a) Décrire brièvement, en français, le langage $L$ reconnu
(=accepté) par l'automate $M$, puis donner une expression
rationnelle qui le dénote.  (On pourra préférer traiter la question
(1b) d'abord.)

(1b) Pour chacun des mots suivants, dire s'ils sont dans $L$ ou non :
$\varepsilon$, $a$, $b$, $ab$, $aa$, $aab$, $aabb$, $abab$, $ababa$.
(Note : il est recommandé de réutiliser ces mots pour vérifier
rapidement les réponses aux questions suivantes et ainsi détecter
d'éventuelles erreurs lors des transformations des automates.)

(2) Éliminer les transitions spontanées de l'automate $M$.  (On
supprimera les états devenus inutiles.)  On appellera $M_2$ l'automate
obtenu.

(3) Déterminiser l'automate $M_2$ obtenu en (2), si nécessaire.  (On
demande un automate déterministe complet.)  On appellera $M_3$
l'automate déterminisé.

Pour simplifier le travail du correcteur, on demande de représenter
$M_3$ de sorte que les transitions étiquetées par $a$ soient, dans la
mesure du possible, horizontales de la gauche vers la droite, et
celles étiquetées par $b$, verticales du haut vers le bas.

(4) Minimiser l'automate $M_3$ obtenu en (3), si nécessaire
(justifier).

(5) Donner un automate (de n'importe quelle sorte) qui reconnaît le
langage $\overline{L} = \Sigma^*\setminus L$ complémentaire de $L$.

(6) Décrire brièvement, en français, ce langage
complémentaire $\overline{L}$.

(7) (Question bonus, plus longue, à ne traiter qu'en dernier.)
Calculer une expression rationnelle qui dénote ce langage
complémentaire $\overline{L}$.  (Ne pas hésiter à introduire des
notations intermédiaires.)

\begin{corrige}
(0) L'automate $M$ est un automate fini non-déterministe à transitions
  spontanées, ou ε-NFA (le concept d'« automate déterministe à
  transitions spontanées » n'aurait tout simplement pas de sens).

\smallbreak

(1a) Le chemin par les états $X,A,A',Y$ accepte les mots exactement
un $a$, c'est-à-dire le langage dénoté par $b{*}ab{*}$.  Le chemin par
les états $X,B,B',Y$ accepte les mots comportant exactement un $b$,
c'est-à-dire le langage dénoté par $a{*}ba{*}$.  L'automate $M$ dans
son ensemble accepte les mots comportant exactement un $a$ ou
(inclusif) exactement un $b$ (i.e. $L = \{w\in\Sigma^* : |w|_a = 1
\penalty0\ \textrm{ou}\penalty0\ |w|_b = 1\}$ si $|w|_x$ désigne le
nombre total d'occurrences de la lettre $x$ dans le mot $w$).  C'est
le langage dénoté par l'expression rationnelle $b{*}ab{*} | a{*}ba{*}$
(nous notons ici et ailleurs $|$ pour la disjonction, qu'on peut aussi
noter $+$).

(1b) Parmi les mots proposés, $a$, $b$, $ab$ et $aab$ appartiennent à
$L$, tandis que $\varepsilon$, $aa$, $aabb$, $abab$ et $ababa$ n'y
appartiennent pas.

\smallbreak

(2) La ε-fermeture (arrière) de l'état $X$ est $\{X,A,B\}$ ; la
ε-fermeture de l'état $A'$ est $\{A',Y\}$ et celle de l'état $B'$ est
$\{B',Y\}$ ; les autres états sont leur propre ε-fermeture (i.e.,
celle-ci est un singleton).  L'élimination des transitions spontanées
conduit donc à l'automate $M_2$ suivant :
\begin{center}
\begin{tikzpicture}[>=latex,line join=bevel,automaton]
\node (X) at (-80bp,0bp) [draw,circle,state,initial] {$X$};
\node (A1) at (-40bp,50bp) [draw,circle,state] {$A\phantom{'}$};
\node (A2) at (40bp,50bp) [draw,circle,state,final] {$A'$};
\node (B1) at (-40bp,-50bp) [draw,circle,state] {$B\phantom{'}$};
\node (B2) at (40bp,-50bp) [draw,circle,state,final] {$B'$};
\draw[->] (X) -- node[auto]{$b$} (A1);
\draw[->] (X) -- node[auto,below left]{$a$} (B1);
\draw[->] (X) -- node[auto,below right]{$a$} (A2);
\draw[->] (X) -- node[auto,above right]{$b$} (B2);
\draw[->] (A1) -- node[auto]{$a$} (A2);
\draw[->] (B1) -- node[auto]{$b$} (B2);
\draw[->] (A1) to[loop above] node[auto]{$b$} (A1);
\draw[->] (A2) to[loop above] node[auto]{$b$} (A2);
\draw[->] (B1) to[loop below] node[auto]{$a$} (B1);
\draw[->] (B2) to[loop below] node[auto]{$a$} (B2);
\end{tikzpicture}
\end{center}
(On a supprimé l'état $Y$ qui est devenu inutile car aucune transition
non-spontanée n'y conduit.)

\smallbreak

(3) L'algorithme de déterminisation conduit à l'automate $M_3$ suivant
où, pour plus de lisibilité, les états finaux ont été marqués en les
entourant deux fois plutôt que par une flèche sortante :
\begin{center}
\begin{tikzpicture}[>=latex,line join=bevel,automaton]
\node (s00) at (0bp,0bp) [draw,rounded corners,state,initial] {$\{X\}$};
\node (s01) at (75bp,0bp) [draw,rounded corners,state,accepting by double] {$\{A',B\}$};
\node (s02) at (150bp,0bp) [draw,rounded corners,state] {$\{B\}$};
\node (s10) at (0bp,-50bp) [draw,rounded corners,state,accepting by double] {$\{A,B'\}$};
\node (s11) at (75bp,-50bp) [draw,rounded corners,state,accepting by double] {$\{A',B'\}$};
\node (s12) at (150bp,-50bp) [draw,rounded corners,state,accepting by double] {$\{B'\}$};
\node (s20) at (0bp,-100bp) [draw,rounded corners,state] {$\{A\}$};
\node (s21) at (75bp,-100bp) [draw,rounded corners,state,accepting by double] {$\{A'\}$};
\node (s22) at (150bp,-100bp) [draw,rounded corners,state] {$\varnothing$};
\draw[->] (s00) -- node[auto]{$a$} (s01);
\draw[->] (s01) -- node[auto]{$a$} (s02);
\draw[->] (s10) -- node[auto]{$a$} (s11);
\draw[->] (s11) -- node[auto]{$a$} (s12);
\draw[->] (s20) -- node[auto]{$a$} (s21);
\draw[->] (s21) -- node[auto]{$a$} (s22);
\draw[->] (s02) to[loop right] node[auto]{$a$} (s02);
\draw[->] (s12) to[loop right] node[auto]{$a$} (s12);
\draw[->] (s22) to[loop right] node[auto]{$a$} (s22);
\draw[->] (s00) -- node[auto]{$b$} (s10);
\draw[->] (s10) -- node[auto]{$b$} (s20);
\draw[->] (s01) -- node[auto]{$b$} (s11);
\draw[->] (s11) -- node[auto]{$b$} (s21);
\draw[->] (s02) -- node[auto]{$b$} (s12);
\draw[->] (s12) -- node[auto]{$b$} (s22);
\draw[->] (s20) to[loop below] node[auto]{$b$} (s20);
\draw[->] (s21) to[loop below] node[auto]{$b$} (s21);
\draw[->] (s22) to[loop below] node[auto]{$b$} (s22);
\end{tikzpicture}
\end{center}

Pour la commodité de la suite de la correction, on renomme les états
de cet automate $M_3$ de la façon suivante :
\begin{center}
\begin{tikzpicture}[>=latex,line join=bevel,automaton]
\node (s00) at (0bp,0bp) [draw,rounded corners,state,initial] {$00$};
\node (s01) at (75bp,0bp) [draw,rounded corners,state,accepting by double] {$01$};
\node (s02) at (150bp,0bp) [draw,rounded corners,state] {$02$};
\node (s10) at (0bp,-50bp) [draw,rounded corners,state,accepting by double] {$10$};
\node (s11) at (75bp,-50bp) [draw,rounded corners,state,accepting by double] {$11$};
\node (s12) at (150bp,-50bp) [draw,rounded corners,state,accepting by double] {$12$};
\node (s20) at (0bp,-100bp) [draw,rounded corners,state] {$20$};
\node (s21) at (75bp,-100bp) [draw,rounded corners,state,accepting by double] {$21$};
\node (s22) at (150bp,-100bp) [draw,rounded corners,state] {$22$};
\draw[->] (s00) -- node[auto]{$a$} (s01);
\draw[->] (s01) -- node[auto]{$a$} (s02);
\draw[->] (s10) -- node[auto]{$a$} (s11);
\draw[->] (s11) -- node[auto]{$a$} (s12);
\draw[->] (s20) -- node[auto]{$a$} (s21);
\draw[->] (s21) -- node[auto]{$a$} (s22);
\draw[->] (s02) to[loop right] node[auto]{$a$} (s02);
\draw[->] (s12) to[loop right] node[auto]{$a$} (s12);
\draw[->] (s22) to[loop right] node[auto]{$a$} (s22);
\draw[->] (s00) -- node[auto]{$b$} (s10);
\draw[->] (s10) -- node[auto]{$b$} (s20);
\draw[->] (s01) -- node[auto]{$b$} (s11);
\draw[->] (s11) -- node[auto]{$b$} (s21);
\draw[->] (s02) -- node[auto]{$b$} (s12);
\draw[->] (s12) -- node[auto]{$b$} (s22);
\draw[->] (s20) to[loop below] node[auto]{$b$} (s20);
\draw[->] (s21) to[loop below] node[auto]{$b$} (s21);
\draw[->] (s22) to[loop below] node[auto]{$b$} (s22);
\end{tikzpicture}
\end{center}
Ici, l'état $0\bullet$ signifie que l'automate n'a pas rencontré
de $a$, l'état $1\bullet$ qu'il en a rencontré exactement un, et
l'état $2\bullet$ qu'il en a rencontré au moins deux ; les états
$\bullet0$, $\bullet1$ et $\bullet2$ ont la même signification pour la
lettre $b$.

\smallbreak

(4) L'automate $M_3$ est déjà minimal.  En effet, l'algorithme de
minimisation commence par séparer les classes $\{01,10,11,12,21\}$
(états finaux) et $\{00,02,20,22\}$ (états non-finaux) ; ensuite, la
transition étiquetée par $a$ sépare la classe $\{01,10,11,12,21\}$ en
$\{01,21\}$ (qui vont vers un état non-final) et $\{10,11,12\}$ (qui
vont vers un état final), et la classe $\{00,02,20,22\}$ en
$\{00,20\}$ (qui vont vers un état final) et $\{02,22\}$ (qui vont
vers un non-final).  La transition étiquetée par $b$ sépare ensuite en
deux chacune des trois classes $\{00,20\}$, $\{01,21\}$ et $\{02,22\}$
(car le premier élément va dans la classe $\{10,11,12\}$ tandis que le
second reste dans la même classe) et sépare en trois la classe
$\{10,11,12\}$.  On a donc séparé chacun des états.

\smallbreak

(5) Pour reconnaître le complémentaire du langage reconnu par un
automate fini déterministe complet, il suffit d'échanger états finaux
et non-finaux : on peut donc prendre l'automate dessiné en (3) avec,
cette fois, la convention que les états simplement entourés sont
finaux (et les doublement entourés sont non-finaux).
Appelons-le $M_5$.

\emph{Attention :} échanger états finaux et non-finaux ne marche pas
pour reconnaître le complémentaire du langage reconnu par un automate
non-déterministe ou incomplet (car la négation de « il existe un
chemin qui va vers un état final » est « aucun chemin ne va vers un
état final » et pas « il existe un chemin qui va vers un état
non-final »).

\smallbreak

(6) Puisque $L$ est le langage formé des mots comportant exactement un
$a$ ou (inclusif) exactement un $b$, son complémentaire $\overline{L}$
est formé des mots ayant un nombre différent de $1$ de $a$ \emph{et}
un nombre différent de $1$ de $b$ ; si on préfère, il s'agit du
langage comportant ($0$ ou au moins $2$ fois la lettre $a$) \emph{et}
($0$ ou au moins $2$ fois la lettre $b$).

\smallbreak

(7) L'élimination des états n'est pas trop complexe car l'automate
$M_5$ a très peu de boucles.  Éliminons simultanément tous les états
non-finaux ($01$, $10$, $11$, $12$ et $21$), et profitons-en pour
créer un nouvel (et unique) état final $F$ :
\begin{center}
\begin{tikzpicture}[>=latex,line join=bevel,automaton]
\node (s00) at (0bp,0bp) [draw,rounded corners,state,initial] {$00$};
\node (s02) at (100bp,0bp) [draw,rounded corners,state] {$02$};
\node (s20) at (0bp,-60bp) [draw,rounded corners,state] {$20$};
\node (s22) at (100bp,-60bp) [draw,rounded corners,state] {$22$};
\node (F) at (160bp,-60bp) [draw,circle,state,final] {$F$};
\draw[->] (s00) -- node[auto]{$aa$} (s02);
\draw[->] (s20) -- node[auto]{$ab{*}a$} (s22);
\draw[->] (s02) to[loop above] node[auto]{$a$} (s02);
\draw[->] (s00) -- node[auto]{$bb$} (s20);
\draw[->] (s02) -- node[auto]{$ba{*}b$} (s22);
\draw[->] (s20) to[loop left] node[auto]{$b$} (s20);
\draw[->] (s22) to[loop below] node[auto]{$a|b$} (s22);
\draw[->] (s22) -- node[auto]{$\varepsilon$} (F);
\draw[->] (s00) -- node[auto]{$r$} (s22);
\draw[->,out=0,in=90] (s02) to node[auto]{$\varepsilon$} (F);
\draw[->,out=270,in=270] (s20) to node[auto,below]{$\varepsilon$} (F);
\draw[->] (s00) to[out=45,in=180] (100bp,40bp) to[out=0,in=45] node[auto,above]{$\varepsilon$} (F);
\end{tikzpicture}
\end{center}
où $r := abaa{*}b \,|\, abbb{*}a \,|\, baaa{*}b \,|\, babb{*}a$
(correspondant aux quatre façons de passer de $00$ à $22$ dans le
graphe ci-dessus).  Éliminons l'état $02$ et l'état $20$ :
\begin{center}
\begin{tikzpicture}[>=latex,line join=bevel,automaton]
\node (s00) at (0bp,0bp) [draw,rounded corners,state,initial] {$00$};
\node (s22) at (100bp,-60bp) [draw,rounded corners,state] {$22$};
\node (F) at (160bp,-60bp) [draw,circle,state,final] {$F$};
\draw[->] (s22) -- node[auto]{$\varepsilon$} (F);
\draw[->] (s22) to[loop above] node[auto]{$a|b$} (s22);
\draw[->] (s00) -- node[auto]{$r'$} (s22);
\draw[->,out=0,in=90] (s00) to node[auto]{$\varepsilon|aaa{*}|bbb{*}$} (F);
\end{tikzpicture}
\end{center}
où $r' := r \penalty0\,|\, aaa{*}ba{*}b \penalty0\,|\, bbb{*}ab{*}a =
abaa{*}b \penalty0\,|\, abbb{*}a \penalty0\,|\, baaa{*}b
\penalty0\,|\, babb{*}a \penalty0\,|\, aaa{*}ba{*}b \penalty0\,|\,
bbb{*}ab{*}a$.  On obtient finalement l'expression rationnelle
suivante pour $\overline{L}$ :
\[
\varepsilon\,|\,aaa{*}\,|\,bbb{*}\,|\,(abaa{*}b \,|\,
abbb{*}a \,|\, baaa{*}b \,|\, babb{*}a
\,|\, aaa{*}ba{*}b \,|\, bbb{*}ab{*}a)(a|b){*}
\]
Pour comprendre cette expression rationnelle, la disjonction de plus
haut niveau correspond aux quatre possibilités : (i) $0$ fois la
lettre $a$ et $0$ fois la lettre $b$, (ii) au moins $2$ fois la lettre
$a$ et $0$ fois la lettre $b$, (iii) $0$ fois la lettre $a$ et au
moins $2$ fois la lettre $b$, et (iv) au moins $2$ fois la lettre $a$
et au moins $2$ fois la lettre $b$.  Pour mieux comprendre
l'expression du cas (iv), on peut remarquer que $abaa{*}b
\penalty0\,|\, baaa{*}b \penalty0\,|\, aaa{*}ba{*}b$ dénote le langage
formé des mots comportant au moins deux $a$ et exactement deux $b$ et
qui finissent par un $b$, et symétriquement $abbb{*}a \penalty0\,|\,
babb{*}a \penalty0\,|\,bbb{*}ab{*}a$ dénote le langage formé des mots
comportant au moins deux $b$ et exactement deux $a$ et qui finissent
par un $a$ : l'expression du cas (iv) correspond donc à écrire un mot
ayant au moins deux $a$ et au moins deux $b$ comme le premier préfixe
qui vérifie cette propriété suivi d'un suffixe quelconque.  (On
pouvait utiliser directement ce raisonnement pour produire
l'expression.)
\end{corrige}


%
%
%

\exercice

Soit $\Sigma$ un alphabet (fini, non vide) fixé.  Les questions
suivantes sont indépendantes (mais on remarquera leur parallélisme).
Ne pas hésiter à décrire les algorithmes de façon succincte et
informelle.

(1) Expliquer, au moyen des résultats vus en cours, pourquoi il existe
un algorithme $A_1$ qui, étant donnée une expression rationnelle $r$
sur $\Sigma$, décide si le langage $L_r$ dénoté par $r$ est différent
du langage $\Sigma^*$ de tous les mots sur $\Sigma$.  (Autrement dit,
l'algorithme $A_1$ doit prendre en entrée une expression rationnelle
$r$, terminer en temps fini, et répondre « vrai » s'il existe un mot
$w\in\Sigma^*$ tel que $w\not\in L_r$ et « faux » si $L_r = \Sigma^*$.
On ne demande pas que l'algorithme soit efficace.)

(2) Expliquer pourquoi il existe un algorithme $A_2$ qui, étant donnée
une grammaire hors contexte $G$ sur $\Sigma$, « semi-décide » si le
langage $L_G$ engendré par $G$ est différent du langage $\Sigma^*$ de
tous les mots.  (« Semi-décider » signifie que l'algorithme $A_2$ doit
prendre en entrée une grammaire hors contexte $G$, terminer en temps
fini en répondant « vrai » s'il existe un mot $w\in\Sigma^*$ tel que
$w\not\in L_G$, et ne pas terminer\footnote{On peut admettre qu'il
  termine parfois en répondant « faux », mais ce ne sera pas utile.}
si $L_G = \Sigma^*$.)  Indication : on peut tester tous les mots
possibles.

(3) Expliquer pourquoi il existe un algorithme $A_3$ comme suit : on
lui fournit en entrée un algorithme $T$ qui décide un langage $L_T
\subseteq \Sigma^*$ (c'est-à-dire que $T$ termine toujours en temps
fini quand on lui présente un mot sur $\Sigma$, et répond « vrai » ou
« faux », et $L_T$ est le langage des mots sur lesquels il répond
« vrai »), et l'algorithme $A_3$ doit semi-décider si $L_T$ est
différent de $\Sigma^*$.  (C'est-à-dire que $A_3$ doit terminer en
répondant « vrai » s'il existe un mot $w\in\Sigma^*$ tel que $w\not\in
L_T$, et ne pas terminer si $L_T = \Sigma^*$.)  Indication : la même
approche permet de traiter les questions (2) et (3).

(4) Expliquer pourquoi il \emph{n'existe pas} d'algorithme $A_4$ qui,
dans les mêmes conditions que $A_3$, décide (au lieu de seulement
semi-décider) si $L_T$ est différent de $\Sigma^*$.  (C'est-à-dire que
$A_4$ est censé terminer toujours, et répondre « vrai » s'il existe un
mot $w\in\Sigma^*$ tel que $w\not\in L_T$, et « faux » si $L_T =
\Sigma^*$.)  Indication : expliquer comment on pourrait utiliser un
tel $A_4$ pour résoudre le problème de l'arrêt, en cherchant à
fabriquer un $T$ qui rejette un mot précisément si un programme donné
s'arrête.

\begin{corrige}
(1) Donnée une expression rationnelle $r$, on sait qu'on peut
  algorithmiquement fabriquer un automate fini non-déterministe à
  transitions spontanées qui reconnaît exactement le langage $L_r$
  dénoté par $r$, et ensuite éliminer les transitions spontanées et
  déterminiser l'automate pour obtenir un automate fini déterministe
  complet reconnaissant $L_r$.  Sur un tel automate, savoir si $L_r
  \neq \Sigma^*$ est trivial : dès lors qu'il existe un état $q$
  non-final accessible, il existe un mot rejeté par l'automate (i.e.,
  n'appartenant pas à $L_r$), à savoir le mot lu en suivant les
  étiquettes d'un chemin quelconque de l'état initial $q_0$
  jusqu'à $q$, et inversement, si tous les états sont finaux, il est
  trivial que l'automate accepte tous les mots.  (On pouvait aussi
  minimiser l'automate et le comparer à l'automate minimal trivial qui
  reconnaît le langage $\Sigma^*$.)

\smallbreak

(2) On sait qu'il existe un algorithme qui, donnée une grammaire
hors-contexte $G$ et un mot $w$, décide si $w \in L_G$.  Pour
semi-décider s'il existe un $w$ tel que $w \not\in L_G$, il suffit de
tester tous les mots possibles : plus exactement, on construit un
algorithme $A_2$ qui effectue une boucle infinie sur tous les
$w\in\Sigma^*$ (il est évidemment algorithmiquement faisable
d'énumérer tous les mots sur $\Sigma$) et, pour chacun, teste si $w
\in L_G$, et si ce n'est pas le cas, termine immédiatement en
répondant « vrai » (on a trouvé un $w$ n'appartenant pas à $L_G$),
tandis que si c'est le cas, l'algorithme $A_2$ ne terminera jamais.

\smallbreak

(3) On procède exactement comme en (2) : par hypothèse on dispose d'un
algorithme $T$ qui, donné un mot $w$, décide si $w \in L_T$.  Pour
semi-décider s'il existe un $w$ tel que $w \not\in L_T$, il suffit de
tester tous les mots possibles : plus exactement, on construit un
algorithme $A_3$ qui effectue une boucle infinie sur tous les
$w\in\Sigma^*$ et, pour chacun, teste si $w \in L_T$ (en lançant
l'algorithme $T$ qui, par hypothèse, termine toujours), et si ce n'est
pas le cas, termine immédiatement en répondant « vrai » (on a trouvé
un $w$ n'appartenant pas à $L_T$), tandis que si c'est le cas,
l'algorithme $A_3$ ne terminera jamais.

\smallbreak

(4) Supposons par l'absurde qu'on dispose d'un algorithme $A_4$ comme
on vient de dire, et montrons pour arriver à une contradiction qu'on
peut s'en servir pour résoudre le problème de l'arrêt.  On se donne
donc un algorithme $S$ et une entrée $x$ de $S$ et on cherche à savoir
(en utilisant $A_4$) si $S$ termine sur l'entrée $x$.  Pour cela, on
va construire un $T$ auquel appliquer $A_4$.

Voici une solution possible : donné un mot $w \in \Sigma^*$, le
programme $T$ ne considère que la longueur $|w|$ de $w$, et lance
(=simule) l'exécution de $S$ sur l'entrée $x$ pour au plus $|w|$
étapes : si l'exécution termine dans le temps imparti, alors $T$
rejette le mot $w$, sinon, il l'accepte (dans tous les cas, $T$
termine et répond « vrai » ou « faux », donc il est une entrée
légitime à $A_4$).  Cette construction fait que $L_T$ rejette au moins
un mot précisément lorsque $S$ termine sur $x$ : si au contraire $S$
ne termine pas sur $x$, alors $L_T = \Sigma^*$.  L'utilisation de
$A_4$ sur $T$ permet donc de savoir algorithmiquement si $S$ termine
sur $x$, ce qui contredit l'indécidabilité du problème de l'arrêt.

Variante de la même idée : on appelle « trace d'exécution » de $S$ sur
$x$ un mot $w$ qui code le calcul complet de l'exécution de $S$ sur
$x$ (par exemple, si on voit $S$ comme une machine de Turing, l'état
courant et le contenu du ruban à chaque étape), du début à l'arrêt.
Une telle trace d'exécution existe donc précisément si $S$ termine
sur $x$.  Or il est visiblement décidable de savoir si un mot $w$
donné est une trace d'exécution (il suffit de vérifier qu'à chaque
étape la machine a bien fait ce qu'elle devait faire).  On peut donc
écrire un algorithme $T$ qui termine toujours et accepte précisément
les mots qui \emph{ne sont pas} une trace d'exécution de $S$ sur $x$.
Le fait que $L_T$ soit différent de $\Sigma^*$ signifie alors
exactement qu'une trace d'exécution existe, donc que $S$ termine
sur $x$.  Ainsi l'utilisation de $A_4$ permet de savoir
algorithmiquement si $S$ termine sur $x$, ce qui contredit
l'indécidabilité du problème de l'arrêt.
\end{corrige}


%
%
%

\exercice

On considère la grammaire hors-contexte $G$ d'axiome $S$ et de
nonterminaux $N = \{S, T\}$ sur l'alphabet $\Sigma = \{a,b,c\}$
donnée par
\[
\begin{aligned}
S &\rightarrow TS \;|\; \varepsilon\\
T &\rightarrow aSbSc\\
\end{aligned}
\]
On notera $L(S) = L_G$ le langage qu'elle engendre, et $L(T)$ le
langage des mots qui dérivent de $T$ (c'est-à-dire, si on préfère, le
langage engendré par la grammaire identique à $G$ mais ayant $T$ pour
axiome).

(0) Donner quelques exemples de mots de $L(S)$ et de $L(T)$ (au
moins deux de chaque).

(1) Expliquer brièvement pourquoi $L(S)$ est l'ensemble des mots de la
forme $u_1\cdots u_k$ avec $u_i \in L(T)$, et pourquoi $L(T)$ est
l'ensemble des mots de la forme $awbw'c$ avec $w,w'\in L(S)$.  (Par
conséquent, $L(T)$ est l'ensemble des mots de la forme $a u_1 \cdots
u_k b u'_1\cdots u'_{\ell} c$ avec
$u_1,\ldots,u_k,u'_1,\ldots,u'_{\ell} \in L(T)$.)

(2) Comment exprimer $L(S)$ à partir de $L(T)$ au moyen d'une ou
plusieurs opérations rationnelles\footnote{C'est-à-dire : union,
  concaténation, étoile de Kleene.} ?  Y a-t-il inclusion de l'un dans
l'autre ?

(3) Montrer que tout mot $w$ appartenant à $L(S)$ ou à $L(T)$ a le
même nombre de $a$, de $b$ et de $c$, c'est-à-dire $|w|_a = |w|_b =
|w|_c$ où $|w|_x$ désigne le nombre total d'occurrences de la
lettre $x$ dans le mot $w$.

(4) Montrer par récurrence sur la longueur $|u|$ d'un mot $u\in
L(T)$ que si $v$ est un préfixe de $u$ de longueur $0<|v|<|u|$,
alors on a $|v|_c < |v|_a$.  Pour cela, on pourra écrire $u$ sous la
forme $a u_1 \cdots u_k b u'_1\cdots u'_{\ell} c$ obtenue en (1),
considérer un préfixe\footnote{\label{prefix-note}On signale à toutes
  fins utiles le fait évident suivant : un préfixe non vide de $t_1
  \cdots t_n$ où $t_1,\ldots,t_n \in\Sigma^*$ s'écrit sous la forme
  $t_1\cdots t_{i-1} y$ où $y\neq\varepsilon$ est un préfixe
  de $t_i$.} d'une telle expression, et appliquer la question (3) et
l'hypothèse de récurrence.

(5) Déduire des questions (3) et (4) que si $u \in L(T)$ et si $v$
est un préfixe de $u$ autre que $u$ lui-même, alors $u \not\in
L(T)$.  En déduire que $u\in L(T)$ et $z \in \Sigma^*$, alors $u$
est l'\emph{unique} préfixe du mot $w := uz$ qui appartienne
à $L(T)$ (autrement dit, aucun préfixe de $w$ de longueur ${<}|u|$
ni ${>}|u|$ n'appartient à $L(T)$).

(6) En déduire que si un mot $w$ s'écrit $w = u_1\cdots u_k$ avec
$u_1,\ldots,u_k \in L(T)$ alors cette factorisation est unique.
(Comment peut-on caractériser $u_1$ comme préfixe de $w$ ?)  Montrer
de même la conclusion analogue pour $u_1\cdots u_k b u'_1\cdots
u'_\ell$ (on pourra noter que $bz\not\in L(T)$ quel que
soit $z\in\Sigma^*$).

(7) En déduire que la grammaire $G$ est inambiguë.

\begin{corrige}
(0) Les mots $abc$ et $aabcbc$ et $ababcc$ appartiennent à $L(T)$.
  Les mots $\varepsilon$ et $abc$ et $abcabc$ appartiennent à $L(S)$.

\smallbreak

(1) En bref : il s'agit simplement d'une reformulation des règles de
  la grammaire.  En plus détaillé : si on considère un arbre d'analyse
  d'un mot $w$ de $L(S)$, soit il est la dérivation triviale du mot
  vide, soit sa racine a deux fils étiquetés $T$ et $S$, l'un dont
  descend un arbre d'analyse d'un mot $u_1$ de $L(T)$ et l'autre
  dont descend un arbre d'analyse d'un autre mot $w'$ de $L(S)$, avec
  $w = u_1 w'$ : en répétant cette remarque jusqu'à tomber sur le mot
  vide, on voit que $w = u_1 u_2 \cdots u_k$ pour des mots $u_i \in
  L(T)$ ; et réciproquement, tout mot de cette forme a un arbre
  d'analyse dans $G$ obtenu en mettant ensemble les arbres d'analyse
  des $u_i$ (en les associant deux par deux par la droite).  Le cas
  d'un mot $u$ de $L(T)$ est plus simple : son arbre d'analyse donne
  directement une écriture sous la forme $awbw'c$ avec $w,w'$ les mots
  analysés par les arbres qui descendent des deux fils étiquetés $S$
  de la racine (étiquetée $T$).

\smallbreak

(2) La description faite en (1) signifie notamment que $L(S) =
L(T)^*$ où « $*$ » est l'étoile de Kleene.  (Si on veut, la règle $S
\rightarrow TS \,|\, \varepsilon$ peut s'interpréter comme $S
\rightarrow T{*}$.)  En particulier, on a $L(T) \subseteq L(S)$.

\smallbreak

(3) La propriété $|\gamma|_a = |\gamma|_b = |\gamma|_c$ (ici $\gamma
\in (\Sigma\cup N)^*$) est vérifiée pour $\gamma = S$ et elle est
préservée par toute dérivation immédiate pour $G$ puisqu'elle est
préservée en remplaçant $S$ par $TS$ ou par le mot vide et en
remplaçant $T$ par $aSbSc$.  Elle est donc vérifiée pour tout mot de
$L(S)$ (et en particulier, pour tout mot de $L(T)$).

\smallbreak

(4) On procède par récurrence sur $|u|$, ce qui permet de supposer la
propriété déjà connue pour tout préfixe $v$ d'un mot de longueur
strictement plus courte que $u$.  Si $v$ est un préfixe d'un mot $u
\in L(T)$, qu'on peut écrire sous la forme $u = a u_1 \cdots u_k b
u'_1\cdots u'_{\ell} c$, et si $0<|v|<|u|$, on a soit $v = a u_1
\cdots u_{i-1} y$ où $y \neq \varepsilon$ est un préfixe de $u_i$,
soit $v = a u_1\cdots u_k b u'_1\cdots u'_{i-1} y$ où $y \neq
\varepsilon$ est un préfixe de $u'_i$.  Dans tous les cas, tous les
facteurs $t$ qui interviennent dans cette écriture vérifient $|t|_c
\leq |t|_a$ : c'est trivial pour $a$ et $b$, c'est le cas pour chaque
$u_j$ par la question (3), et pour $y$ cela découle soit de
l'hypothèse de récurrence (lorsque $|y|<|u_i|$ resp. $|y|<|u'_i|$)
soit par la question (3) (lorsque $y$ est en fait égal à $u_i$
resp. $u'_i$).  Comme par ailleurs $|a|_c = 0 < 1 = |a|_a$, une
égalité est stricte et on en déduit $|v|_c < |v|_a$, ce qui conclut la
récurrence.

\smallbreak

(5) Si $u \in L(T)$ et si $v$ est un préfixe de $u$ autre que $u$
lui-même, alors soit $v = \varepsilon$, qui n'appartient pas à
$L(T)$ (par exemple par la question (1)), soit $0<|v|<|u|$, auquel
cas la question (4) donne $|v|_c<|v|_a$, ce qui interdit $v\in L(T)$
d'après (3).  Dans tous les cas, $v\not\in L(T)$.

Si maintenant $u\in L(T)$ et $z\in\Sigma^*$, un préfixe de $w := uz$
est soit un préfixe de $u$ soit de la forme $uz'$ avec $z'$ un préfixe
non vide de $z$ (cf. la note \ref{prefix-note}).  Un préfixe de $w$ de
longueur ${<}|u|$ n'appartient pas à $L(T)$ d'après le paragraphe
précédent, et un mot de la forme $uz'$ ne peut pas y appartenir non
plus car c'est alors $u$ lui-même qui serait un préfixe strict de $uz'
\in L(T)$ appartenant à $L(T)$, ce qui contredit de nouveau le
paragraphe précédent.

\smallbreak

(6) D'après la question précédente, on peut définir $u_1$ comme
l'unique préfixe de $w$ qui appartient à $L(T)$ (tout préfixe
strictement plus court ou strictement plus long n'appartient pas à
$L(T)$).  Une fois que $u_1$ est défini, en appliquant le même
raisonnement au suffixe correspondant $u_2\cdots u_k$, on voit que
$u_2$ est défini de façon unique.  En procédant ainsi (par récurrence
sur $k$ si on veut), les $u_i$ sont définis de façon unique.

Le même raisonnement vaut pour $u_1\cdots u_k b u'_1\cdots u'_\ell$ :
on a une factorisation en mots de $L(T)\cup\{b\}$ et à chaque fois
le premier facteur est défini comme le seul préfixe possible
appartenant à $L(T)\cup\{b\}$.  (On utilise le fait que $bz\not\in
L(T)$, qui découle du (1), pour voir que $bu'_1\cdots bu'_\ell$ n'a
pas de préfixe dans $L(T)$.)

\smallbreak

(7) En reprenant l'analyse du (1), il s'agit de montrer que la
factorisation $u_1\cdots u_k$ d'un mot de $L(S)$ est unique et que la
factorisation $a u_1\cdots u_k b u'_1\cdots u'_\ell c$ d'un mot
de $L(T)$ l'est aussi.  La première partie est exactement une
conclusion du (6), et la seconde l'est aussi dès lors qu'on retire le
$a$ initial et le $c$ final.
\end{corrige}



%
%
%
\end{document}