summaryrefslogtreecommitdiffstats
path: root/exercices2.tex
blob: 6a0738f8283e1e3ab03007406d67d605c578001e (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
%% 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[hyperindex=false]{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}
%
\newcommand{\liff}{\mathrel{\Longleftrightarrow}\relax}
%
\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{TD langages algébriques — Corrigé}
\else
\title{TD langages algébriques}
\fi
\author{David A. Madore}
\maketitle

\centerline{\textbf{INF105}}

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



%
%
%

\exercice

Considérons le fragment simplifié suivant de la grammaire d'un langage
de programmation hypothétique :
\[
\begin{aligned}
\mathit{Instruction} &\rightarrow \mathtt{foo} \;|\; \mathtt{bar} \;|\; \mathtt{qux} \;|\; \mathit{Conditional}\\
|&\phantom{\rightarrow} \mathtt{begin}\ \mathit{InstrList}\ \mathtt{end}\\
\mathit{Conditional} &\rightarrow \mathtt{if}\ \mathit{Expression}\ \mathtt{then}\ \mathit{Instruction}\ \mathtt{else}\ \mathit{Instruction}\\
|&\phantom{\rightarrow} \mathtt{if}\ \mathit{Expression}\ \mathtt{then}\ \mathit{Instruction}\\
\mathit{InstrList} &\rightarrow \mathit{Instruction} \;|\; \mathit{Instruction}\ \mathit{InstrList}\\
\mathit{Expression} &\rightarrow \mathtt{true} \;|\; \mathtt{false} \;|\; \mathtt{happy} \;|\; \mathtt{trippy}\\
\end{aligned}
\]
(Ici, les « lettres » ou tokens ont été écrits comme des mots, par
exemple $\mathtt{foo}$ est une « lettre » : les terminaux sont écrits
en police à espacement fixe tandis que les nonterminaux sont en
italique et commencent par une majuscule.  On prendra
$\mathit{Instruction}$ pour axiome.)

(1) Donner l'arbre d'analyse de :
$\mathtt{if}\penalty0\ \mathtt{happy}\penalty0\ \mathtt{then}\penalty0\ \mathtt{if}\penalty0\ \mathtt{trippy}\penalty0\ \mathtt{then}\penalty0\ \mathtt{foo}\penalty0\ \mathtt{else}\penalty0\ \mathtt{bar}\penalty0\ \mathtt{else}\penalty0\ \mathtt{qux}$ ;
expliquer brièvement pourquoi il n'y en a qu'un.

(2) Donner deux arbres d'analyse distincts de :
$\mathtt{if}\penalty0\ \mathtt{happy}\penalty0\ \mathtt{then}\penalty0\ \mathtt{if}\penalty0\ \mathtt{trippy}\penalty0\ \mathtt{then}\penalty0\ \mathtt{foo}\penalty0\ \mathtt{else}\penalty0\ \mathtt{bar}$.
Que peut-on dire de la grammaire présentée ?

(3) En supposant que, dans ce langage,
$\mathtt{begin}\penalty0\ I\penalty0\ \penalty0\mathtt{end}$ (où $I$
est une instruction) a le même effet que $I$ seul, comment un
programmeur peut-il réécrire l'instruction considérée en (2) pour
obtenir un comportant équivalent à l'une ou l'autre des deux
interprétations ?

(4) Modifier légèrement la grammaire proposée de manière à obtenir une
grammaire faiblement équivalente dans laquelle seul l'un des arbres
d'analyse obtenus en (2) est possible (i.e., une grammaire qui force
cette interprétation-là par défaut) ; on pourra être amené à
introduire des nouveaux nonterminaux pour des variantes de
$\mathit{Instruction}$ et $\mathit{Conditional}$ qui interdisent
récursivement les conditionnelles sans $\mathtt{else}$.

\begin{corrige}
(1) L'arbre d'analyse de
  $\mathtt{if}\penalty0\ \mathtt{happy}\penalty0\ \mathtt{then}\penalty0\ \mathtt{if}\penalty0\ \mathtt{trippy}\penalty0\ \mathtt{then}\penalty0\ \mathtt{foo}\penalty0\ \mathtt{else}\penalty0\ \mathtt{bar}\penalty0\ \mathtt{else}\penalty0\ \mathtt{qux}$
  est le suivant (en notant $I$, $C$ et $E$ pour
  $\mathit{Instruction}$, $\mathit{Condition}$ et
  $\mathit{Expression}$ respectivement) :
\begin{center}
\tikzstyle{automaton}=[scale=0.4]
%%% begin ex2p1 %%%

\begin{tikzpicture}[>=latex,line join=bevel,automaton]
%%
\node (foo) at (279bp,18bp) [draw,draw=none] {$\mathtt{foo}$};
  \node (then1) at (207bp,90bp) [draw,draw=none] {$\mathtt{then}$};
  \node (if0) at (27bp,234bp) [draw,draw=none] {$\mathtt{if}$};
  \node (if1) at (63bp,90bp) [draw,draw=none] {$\mathtt{if}$};
  \node (bar) at (423bp,18bp) [draw,draw=none] {$\mathtt{bar}$};
  \node (I1) at (243bp,234bp) [draw,draw=none] {$I$};
  \node (I0) at (207bp,378bp) [draw,draw=none] {$I$};
  \node (I3) at (423bp,90bp) [draw,draw=none] {$I$};
  \node (I2) at (279bp,90bp) [draw,draw=none] {$I$};
  \node (I4) at (387bp,234bp) [draw,draw=none] {$I$};
  \node (trippy) at (135bp,18bp) [draw,draw=none] {$\mathtt{trippy}$};
  \node (else0) at (315bp,234bp) [draw,draw=none] {$\mathtt{else}$};
  \node (else1) at (351bp,90bp) [draw,draw=none] {$\mathtt{else}$};
  \node (qux) at (387bp,162bp) [draw,draw=none] {$\mathtt{qux}$};
  \node (C1) at (243bp,162bp) [draw,draw=none] {$C$};
  \node (then0) at (171bp,234bp) [draw,draw=none] {$\mathtt{then}$};
  \node (C0) at (207bp,306bp) [draw,draw=none] {$C$};
  \node (E1) at (135bp,90bp) [draw,draw=none] {$E$};
  \node (E0) at (99bp,234bp) [draw,draw=none] {$E$};
  \node (happy) at (99bp,162bp) [draw,draw=none] {$\mathtt{happy}$};
  \draw [] (I2) ..controls (279bp,60.846bp) and (279bp,46.917bp)  .. (foo);
  \draw [] (C0) ..controls (192.52bp,276.85bp) and (185.36bp,262.92bp)  .. (then0);
  \draw [] (I0) ..controls (207bp,348.85bp) and (207bp,334.92bp)  .. (C0);
  \draw [] (C0) ..controls (250.16bp,277.03bp) and (271.72bp,263.05bp)  .. (else0);
  \draw [] (C1) ..controls (286.16bp,133.03bp) and (307.72bp,119.05bp)  .. (else1);
  \draw [] (C1) ..controls (257.48bp,132.85bp) and (264.64bp,118.92bp)  .. (I2);
  \draw [] (E0) ..controls (99bp,204.85bp) and (99bp,190.92bp)  .. (happy);
  \draw [] (C1) ..controls (199.84bp,133.03bp) and (178.28bp,119.05bp)  .. (E1);
  \draw [] (C1) ..controls (228.52bp,132.85bp) and (221.36bp,118.92bp)  .. (then1);
  \draw [] (C0) ..controls (263.23bp,285.79bp) and (310.83bp,268.84bp)  .. (351bp,252bp) .. controls (353.93bp,250.77bp) and (356.97bp,249.43bp)  .. (I4);
  \draw [] (C1) ..controls (186.77bp,141.79bp) and (139.17bp,124.84bp)  .. (99bp,108bp) .. controls (96.068bp,106.77bp) and (93.027bp,105.43bp)  .. (if1);
  \draw [] (C0) ..controls (150.77bp,285.79bp) and (103.17bp,268.84bp)  .. (63bp,252bp) .. controls (60.068bp,250.77bp) and (57.027bp,249.43bp)  .. (if0);
  \draw [] (E1) ..controls (135bp,60.846bp) and (135bp,46.917bp)  .. (trippy);
  \draw [] (C1) ..controls (299.23bp,141.79bp) and (346.83bp,124.84bp)  .. (387bp,108bp) .. controls (389.93bp,106.77bp) and (392.97bp,105.43bp)  .. (I3);
  \draw [] (C0) ..controls (221.48bp,276.85bp) and (228.64bp,262.92bp)  .. (I1);
  \draw [] (I4) ..controls (387bp,204.85bp) and (387bp,190.92bp)  .. (qux);
  \draw [] (I1) ..controls (243bp,204.85bp) and (243bp,190.92bp)  .. (C1);
  \draw [] (I3) ..controls (423bp,60.846bp) and (423bp,46.917bp)  .. (bar);
  \draw [] (C0) ..controls (163.84bp,277.03bp) and (142.28bp,263.05bp)  .. (E0);
%
\end{tikzpicture}

%%% end ex2p1 %%%
\end{center}

Il est le seul possible car une fois acquis que les deux $\mathtt{if}$
comportent chacun un $\mathtt{else}$, il se construit ensuite en
descendant de façon unique (l'instruction est forcément une condition,
qui s'analyse en $\mathtt{if}\ E\ \mathtt{then}\ I\ \mathtt{else}\ I$
de façon unique, et chacun des morceaux s'analyse de nouveau de façon
unique).

\vskip .5explus.1fil

(2) Un arbre d'analyse possible consiste à associer le
$\mathtt{else}\penalty0\ \mathtt{bar}$ avec
$\mathtt{if}\penalty0\ \mathtt{trippy}\penalty0\ \mathtt{then}\penalty0\ \mathtt{foo}$ :
\begin{center}
\tikzstyle{automaton}=[scale=0.4]
%%% begin ex2p1a %%%

\begin{tikzpicture}[>=latex,line join=bevel,automaton]
%%
\node (bar) at (423bp,18bp) [draw,draw=none] {$\mathtt{bar}$};
  \node (then1) at (207bp,90bp) [draw,draw=none] {$\mathtt{then}$};
  \node (if0) at (27bp,234bp) [draw,draw=none] {$\mathtt{if}$};
  \node (if1) at (63bp,90bp) [draw,draw=none] {$\mathtt{if}$};
  \node (I1) at (243bp,234bp) [draw,draw=none] {$I$};
  \node (I0) at (135bp,378bp) [draw,draw=none] {$I$};
  \node (I3) at (423bp,90bp) [draw,draw=none] {$I$};
  \node (I2) at (279bp,90bp) [draw,draw=none] {$I$};
  \node (trippy) at (135bp,18bp) [draw,draw=none] {$\mathtt{trippy}$};
  \node (else1) at (351bp,90bp) [draw,draw=none] {$\mathtt{else}$};
  \node (foo) at (279bp,18bp) [draw,draw=none] {$\mathtt{foo}$};
  \node (C1) at (243bp,162bp) [draw,draw=none] {$C$};
  \node (then0) at (171bp,234bp) [draw,draw=none] {$\mathtt{then}$};
  \node (C0) at (135bp,306bp) [draw,draw=none] {$C$};
  \node (E1) at (135bp,90bp) [draw,draw=none] {$E$};
  \node (E0) at (99bp,234bp) [draw,draw=none] {$E$};
  \node (happy) at (99bp,162bp) [draw,draw=none] {$\mathtt{happy}$};
  \draw [] (I2) ..controls (279bp,60.846bp) and (279bp,46.917bp)  .. (foo);
  \draw [] (C0) ..controls (149.48bp,276.85bp) and (156.64bp,262.92bp)  .. (then0);
  \draw [] (I0) ..controls (135bp,348.85bp) and (135bp,334.92bp)  .. (C0);
  \draw [] (C1) ..controls (228.52bp,132.85bp) and (221.36bp,118.92bp)  .. (then1);
  \draw [] (C1) ..controls (286.16bp,133.03bp) and (307.72bp,119.05bp)  .. (else1);
  \draw [] (I3) ..controls (423bp,60.846bp) and (423bp,46.917bp)  .. (bar);
  \draw [] (E0) ..controls (99bp,204.85bp) and (99bp,190.92bp)  .. (happy);
  \draw [] (C1) ..controls (199.84bp,133.03bp) and (178.28bp,119.05bp)  .. (E1);
  \draw [] (C1) ..controls (186.77bp,141.79bp) and (139.17bp,124.84bp)  .. (99bp,108bp) .. controls (96.068bp,106.77bp) and (93.027bp,105.43bp)  .. (if1);
  \draw [] (C0) ..controls (91.844bp,277.03bp) and (70.277bp,263.05bp)  .. (if0);
  \draw [] (E1) ..controls (135bp,60.846bp) and (135bp,46.917bp)  .. (trippy);
  \draw [] (C1) ..controls (299.23bp,141.79bp) and (346.83bp,124.84bp)  .. (387bp,108bp) .. controls (389.93bp,106.77bp) and (392.97bp,105.43bp)  .. (I3);
  \draw [] (C0) ..controls (178.16bp,277.03bp) and (199.72bp,263.05bp)  .. (I1);
  \draw [] (C1) ..controls (257.48bp,132.85bp) and (264.64bp,118.92bp)  .. (I2);
  \draw [] (I1) ..controls (243bp,204.85bp) and (243bp,190.92bp)  .. (C1);
  \draw [] (C0) ..controls (120.52bp,276.85bp) and (113.36bp,262.92bp)  .. (E0);
%
\end{tikzpicture}

%%% end ex2p1a %%%
\end{center}
un autre consiste à associer le $\mathtt{else}\penalty0\ \mathtt{bar}$
avec
$\mathtt{if}\penalty0\ \mathtt{happy}\penalty0\ \mathtt{then}\penalty0\ ...$ :
\begin{center}
\tikzstyle{automaton}=[scale=0.4]
%%% begin ex2p1b %%%

\begin{tikzpicture}[>=latex,line join=bevel,automaton]
%%
\node (bar) at (387bp,162bp) [draw,draw=none] {$\mathtt{bar}$};
  \node (then1) at (279bp,90bp) [draw,draw=none] {$\mathtt{then}$};
  \node (if0) at (27bp,234bp) [draw,draw=none] {$\mathtt{if}$};
  \node (if1) at (135bp,90bp) [draw,draw=none] {$\mathtt{if}$};
  \node (I1) at (243bp,234bp) [draw,draw=none] {$I$};
  \node (I0) at (207bp,378bp) [draw,draw=none] {$I$};
  \node (I2) at (351bp,90bp) [draw,draw=none] {$I$};
  \node (I4) at (387bp,234bp) [draw,draw=none] {$I$};
  \node (trippy) at (207bp,18bp) [draw,draw=none] {$\mathtt{trippy}$};
  \node (else0) at (315bp,234bp) [draw,draw=none] {$\mathtt{else}$};
  \node (foo) at (351bp,18bp) [draw,draw=none] {$\mathtt{foo}$};
  \node (C1) at (243bp,162bp) [draw,draw=none] {$C$};
  \node (then0) at (171bp,234bp) [draw,draw=none] {$\mathtt{then}$};
  \node (C0) at (207bp,306bp) [draw,draw=none] {$C$};
  \node (E1) at (207bp,90bp) [draw,draw=none] {$E$};
  \node (E0) at (99bp,234bp) [draw,draw=none] {$E$};
  \node (happy) at (99bp,162bp) [draw,draw=none] {$\mathtt{happy}$};
  \draw [] (I2) ..controls (351bp,60.846bp) and (351bp,46.917bp)  .. (foo);
  \draw [] (C0) ..controls (192.52bp,276.85bp) and (185.36bp,262.92bp)  .. (then0);
  \draw [] (I0) ..controls (207bp,348.85bp) and (207bp,334.92bp)  .. (C0);
  \draw [] (C0) ..controls (250.16bp,277.03bp) and (271.72bp,263.05bp)  .. (else0);
  \draw [] (C1) ..controls (286.16bp,133.03bp) and (307.72bp,119.05bp)  .. (I2);
  \draw [] (I4) ..controls (387bp,204.85bp) and (387bp,190.92bp)  .. (bar);
  \draw [] (E0) ..controls (99bp,204.85bp) and (99bp,190.92bp)  .. (happy);
  \draw [] (C1) ..controls (228.52bp,132.85bp) and (221.36bp,118.92bp)  .. (E1);
  \draw [] (C0) ..controls (263.23bp,285.79bp) and (310.83bp,268.84bp)  .. (351bp,252bp) .. controls (353.93bp,250.77bp) and (356.97bp,249.43bp)  .. (I4);
  \draw [] (C1) ..controls (199.84bp,133.03bp) and (178.28bp,119.05bp)  .. (if1);
  \draw [] (C0) ..controls (150.77bp,285.79bp) and (103.17bp,268.84bp)  .. (63bp,252bp) .. controls (60.068bp,250.77bp) and (57.027bp,249.43bp)  .. (if0);
  \draw [] (E1) ..controls (207bp,60.846bp) and (207bp,46.917bp)  .. (trippy);
  \draw [] (C0) ..controls (221.48bp,276.85bp) and (228.64bp,262.92bp)  .. (I1);
  \draw [] (C1) ..controls (257.48bp,132.85bp) and (264.64bp,118.92bp)  .. (then1);
  \draw [] (I1) ..controls (243bp,204.85bp) and (243bp,190.92bp)  .. (C1);
  \draw [] (C0) ..controls (163.84bp,277.03bp) and (142.28bp,263.05bp)  .. (E0);
%
\end{tikzpicture}

%%% end ex2p1b %%%
\end{center}
La grammaire présentée est donc ambiguë.

\vskip .5explus.1fil

(3) Pour forcer la première interprétation (le
$\mathtt{else}\penalty0\ \mathtt{bar}$ se rapporte au
$\mathtt{if}\penalty0\ \mathtt{trippy}$), on peut écrire :
$\mathtt{if}\penalty0\ \mathtt{happy}\penalty0\ \mathtt{then}\penalty0\ \mathtt{begin}\penalty0\ \mathtt{if}\penalty0\ \mathtt{trippy}\penalty0\ \mathtt{then}\penalty0\ \mathtt{foo}\penalty0\ \mathtt{else}\penalty0\ \mathtt{bar}\penalty0\ \mathtt{end}$.

Pour forcer la seconde interprétation (le
$\mathtt{else}\penalty0\ \mathtt{bar}$ se rapporte au
$\mathtt{if}\penalty0\ \mathtt{happy}$), on peut écrire :
$\mathtt{if}\penalty0\ \mathtt{happy}\penalty0\ \mathtt{then}\penalty0\ \mathtt{begin}\penalty0\ \mathtt{if}\penalty0\ \mathtt{trippy}\penalty0\ \mathtt{then}\penalty0\ \mathtt{foo}\penalty0\ \mathtt{end}\penalty0\ \mathtt{else}\penalty0\ \mathtt{bar}$.

\vskip .5explus.1fil

(4) Pour forcer la première interprétation (le $\mathtt{else}$ se
rapporte au $\mathtt{if}$ le plus proche possible), on peut modifier
la grammaire comme suit :
\[
\begin{aligned}
\mathit{Instruction} &\rightarrow \mathtt{foo} \;|\; \mathtt{bar} \;|\; \mathtt{qux} \;|\; \mathit{Conditional}\\
|&\phantom{\rightarrow} \mathtt{begin}\ \mathit{InstrList}\ \mathtt{end}\\
\mathit{InstrNoSC} &\rightarrow \mathtt{foo} \;|\; \mathtt{bar} \;|\; \mathtt{qux} \;|\; \mathit{CondNoSC}\\
|&\phantom{\rightarrow} \mathtt{begin}\ \mathit{InstrList}\ \mathtt{end}\\
\mathit{Conditional} &\rightarrow \mathtt{if}\ \mathit{Expression}\ \mathtt{then}\ \mathit{InstrNoSC}\ \mathtt{else}\ \mathit{Instruction}\\
|&\phantom{\rightarrow} \mathtt{if}\ \mathit{Expression}\ \mathtt{then}\ \mathit{Instruction}\\
\mathit{CondNoSC} &\rightarrow \mathtt{if}\ \mathit{Expression}\ \mathtt{then}\ \mathit{InstrNoSC}\ \mathtt{else}\ \mathit{InstrNoSC}\\
\mathit{InstrList} &\rightarrow \mathit{Instruction} \;|\; \mathit{Instruction}\ \mathit{InstrList}\\
\mathit{Expression} &\rightarrow \mathtt{true} \;|\; \mathtt{false} \;|\; \mathtt{happy} \;|\; \mathtt{trippy}\\
\end{aligned}
\]
L'idée est d'obliger une instruction conditionnelle qui apparaîtrait
après le $\mathtt{then}$ d'une conditionnelle complète à être
elle-même complète (elle ne peut pas être courte, car alors le
$\mathtt{else}$ devrait se rattacher à elle), et ce, récursivement.
On peut montrer que la grammaire ci-dessus est inambiguë et faiblement
équivalente à celle de départ.

On peut aussi fabriquer une grammaire inambiguë, faiblement
équivalente à celle de départ, qui force l'autre interprétation (le
$\mathtt{else}$ se rapporte au $\mathtt{if}$ le plus lointain
possible), mais c'est nettement plus complexe (l'idée générale pour
apparier un $\mathtt{else}$ avec un $\mathtt{if}...\mathtt{else}$ dans
cette logique est de demander que \emph{soit} le $\mathtt{else}$ n'est
suivi d'aucun autre $\mathtt{else}$, \emph{soit} toute instruction
conditionnelle entre le $\mathtt{then}$ et le $\mathtt{else}$ est
elle-même complète).  Contrairement à la grammaire précédente, cette
grammaire, bien qu'inambiguë, est probablement impossible à analyser
avec un analyseur LR (ou même, déterministe).
\end{corrige}


%
%
%

\exercice\label{non-square-words-is-algebraic}

Soit $\Sigma = \{a,b\}$.  On considère le langage $M$ des mots qui
\emph{ne s'écrivent pas} sous la forme $ww$ avec $w\in\Sigma^*$
(c'est-à-dire sous la forme d'un carré ; autrement dit, le langage $M$
est le \emph{complémentaire} du langage $Q$ des carrés considéré dans
l'exercice \ref{square-words-not-algebraic}) : par exemple, $M$
contient les mots $a$, $b$, $ab$, $aab$ et $aabb$ mais pas
$\varepsilon$, $aa$, $abab$ ni $abaaba$.

(0) Expliquer pourquoi tout mot sur $\Sigma$ de longueur impaire est
dans $M$, et pourquoi un mot $x_1\cdots x_{2n}$ de longueur paire $2n$
est dans $M$ si et seulement si il existe $i$ tel que $x_i \neq
x_{n+i}$.

On considère par ailleurs la grammaire hors contexte $G$
(d'axiome $S$)
\[
\begin{aligned}
S &\rightarrow A \;|\; B \;|\; AB \;|\; BA\\
A &\rightarrow a \;|\; aAa \;|\; aAb \;|\; bAa \;|\; bAb\\
B &\rightarrow b \;|\; aBa \;|\; aBb \;|\; bBa \;|\; bBb\\
\end{aligned}
\]

(1) Décrire le langage $L(G,A)$ des mots dérivant de $A$ dans la
grammaire $G$ (autrement dit, le langage engendré par la grammaire
identique à $G$ mais ayant pour axiome $A$).  Décrire de même
$L(G,B)$.

(2) Montrer que tout mot de longueur impaire est dans le
langage $L(G)$ engendré par $G$.

(3) Montrer que tout mot $t \in M$ de longueur paire est dans $L(G)$.
(Indication : si $t = x_1\cdots x_{2n}$ est de longueur paire $2n$ et
que $x_i \neq x_{n+i}$, on peut considérer la factorisation de $t$ en
$x_1\cdots x_{2i-1}$ et $x_{2i}\cdots x_{2n}$.)

(4) Montrer que tout mot de $L(G)$ de longueur paire est dans $M$.

(5) En déduire que $M$ est algébrique.

\begin{corrige}
(0) En remarquant que si $n = |w|$ alors $|ww| = 2n$, on constate que
  tout mot de la forme $ww$ est de longueur paire, et de plus, que
  pour un mot de longueur $2n$, être de la forme $ww$ signifie que son
  préfixe de longueur $n$ soit égal à son suffixe de longueur $n$ ;
  c'est-à-dire, si $t = x_1\cdots x_{2n}$, que $x_1\cdots x_n =
  x_{n+1}\cdots x_{2n}$, ce qui signifie exactement $x_i = x_{n+i}$
  pour tout $1\leq i\leq n$.

(1) La règle $A \rightarrow a \,|\, aAa \,|\, aAb \,|\, bAa \,|\, bAb$
  permet de faire à partir de $A$ une dérivation qui ajoute un nombre
  quelconque de fois une lettre ($a$ ou $b$) de chaque part de $A$, et
  finalement remplace ce $A$ par $a$.  On obtient donc ainsi
  exactement les mots de longueur impaire ayant un $a$ comme lettre
  centrale : $L(G,A) = \{w_1aw_2 : |w_1|=|w_2|\}$.  De même, $L(G,B) =
  \{w_1bw_2 : |w_1|=|w_2|\}$.

(2) Tout mot de longueur impaire est soit dans $L(G,A)$ soit dans
  $L(G,B)$ selon que sa lettre centrale est un $a$ ou un $b$.  Il est
  donc dans $L(G)$ en vertu des règles $S\rightarrow A$ et
  $S\rightarrow B$.

(3) Soit $t = x_1\cdots x_{2n}$ un mot de $M$ de longueur paire $2n$ :
  d'après (0), il existe $i$ tel que $x_i \neq x_{n+i}$.  Posons alors
  $u = x_1\cdots x_{2i-1}$ et $v = x_{2i}\cdots x_{2n}$.  Chacun de
  $u$ et de $v$ est de longueur impaire.  De plus, leurs lettres
  centrales sont respectivement $x_i$ et $x_{n+i}$, et elles sont
  différentes : l'une est donc un $a$ et l'autre un $b$ ; mettons sans
  perte de généralité que $x_i = a$ et $x_{n+i} = b$.  Alors $u \in
  L(G,A)$ d'après (1) et $v \in L(G,B)$ : le mot $t = uv$ s'obtient
  donc par la règle $S \rightarrow AB$ (suivie de dérivations de $u$ à
  partir de $A$ et de $v$ a partir de $B$) : ceci montre bien $t \in
  L(G)$.

(4) On a vu en (1) que tout mot dérivant de $A$ ou de $B$ est de
  longueur impaire.  Un mot $t$ de $L(G)$ de longueur paire $2n$
  dérive donc forcément de $AB$ ou de $BA$.  Sans perte de généralité,
  supposons qu'il dérive de $AB$, et on veut montrer qu'il appartient
  à $M$.  Appelons $u$ le facteur de $t$ qui dérive de $A$ et $v$ le
  facteur de $t$ qui dérive de $B$ : on sait alors (toujours
  d'après (1)) que $u$ s'écrit sous la forme $x_1\cdots x_{2i-1}$ où
  la lettre centrale $x_i$ vaut $a$, et que $v$ s'écrit sous la forme
  (quitte à continuer la numérotation des indices) $x_{2i}\cdots
  x_{2n}$ où la lettre centrale $x_{n+i}$ vaut $b$.  Alors $x_{n+i}
  \neq x_i$ donc le mot $t$ est dans $M$ d'après (0).

(5) On a $M = L(G)$ car d'après les questions précédentes, tout mot de
  longueur impaire est dans les deux et qu'un mot de longueur paire
  est dans l'un si et seulement si il est dans l'autre.  On a donc
  montré que $M$ est algébrique.
\end{corrige}


%
%
%

\exercice\label{square-words-not-algebraic}

Soit $\Sigma = \{a,b\}$.  Montrer que le langage $Q := \{ww :
w\in\Sigma^*\}$ constitué des mots de la forme $ww$ (autrement dit,
des carrés ; par exemple, $\varepsilon$, $aa$, $abab$, $abaaba$ ou
encore $aabbaabb$ sont dans $Q$) n'est pas algébrique.  On pourra pour
cela considérer son intersection avec le langage $L_0$ dénoté par
l'expression rationnelle $a{*}b{*}a{*}b{*}$ et appliquer le lemme de
pompage.

\begin{corrige}
Supposons par l'absurde que $Q$ soit algébrique : alors son
intersection avec le langage rationnel $L_0 = \{a^m b^n a^{m'} b^{n'} :
m,n,m',n' \in \mathbb{N}\}$ est encore algébrique.  Or $Q \cap L_0 =
\{a^m b^n a^m b^n : m,n \in \mathbb{N}\}$.  On va maintenant utiliser
le lemme de pompage pour arriver à une contradiction.

Appliquons le lemme de pompage pour les langages algébriques au
langage $Q \cap L_0 = \{a^m b^n a^m b^n : m,n \in \mathbb{N}\}$
considéré : appelons $k$ l'entier dont le lemme de pompage garantit
l'existence.  Considérons le mot $t := a^k b^k a^k b^k$ : dans la
suite de cette démonstration, on appellera « bloc » de $t$ un des
quatre facteurs $a^k$, $b^k$, $a^k$ et $b^k$.  D'après la propriété de
$k$ garantie par le lemme de pompage, il doit exister une
factorisation $t = uvwxy$ pour laquelle on a (i) $|vx|\geq 1$,
(ii) $|vwx|\leq k$ et (iii) $uv^iwx^iy \in Q \cap L_0$ pour
tout $i\geq 0$.

Chacun de $v$ et de $x$ doit être contenu dans un seul bloc, i.e.,
doit être de la forme $a^\ell$ ou $b^\ell$, sinon sa répétition ($v^i$
ou $x^i$ pour $i\geq 2$, qui appartient à $L_0$ d'après (iii)) ferait
apparaître plus d'alternations entre $a$ et $b$ que le langage $L_0$
ne le permet.  Par ailleurs, la propriété (ii) assure que le facteur
$vwx$ ne peut rencontrer qu'un ou deux blocs de $t$ (pas plus).
Autrement dit, $v$ et $x$ sont contenus dans deux blocs de $t$ qui
sont identiques ou bien consécutifs\footnote{La formulation est
  choisie pour avoir un sens même si $v$ ou $x$ est le mot vide (ce
  qui est possible \textit{a priori}).}.

D'après la propriété (i), au moins l'un de $v$ et de $x$ n'est pas le
mot vide.  Si ce facteur non trivial est dans le premier bloc $a^k$,
l'autre ne peut pas être dans l'autre bloc $a^k$ d'après ce qui vient
d'être dit : donc $uv^iwx^iy$ est de la forme $a^{k'} b^n a^k b^k$
avec $k'>k$ si $i>1$, qui n'appartient pas à $Q\cap L_0$, une
contradiction.  De même, le facteur non trivial est dans le premier
bloc $b^k$, l'autre ne peut pas être dans l'autre bloc $b^k$ : donc
$uv^iwx^iy$ est de la forme $a^m b^{k'} a^{m'} b^k$ avec $k'>k$ si
$i>1$, qui n'appartient pas à $Q\cap L_0$, de nouveau une
contradiction.  Les deux autres cas sont analogues.
\end{corrige}

\textbf{Remarque :} Les exercices \ref{non-square-words-is-algebraic}
et \ref{square-words-not-algebraic} mis ensemble donnent un exemple
explicite d'un langage $M$ algébrique dont le complémentaire $Q$ n'est
pas algébrique.


%
%
%
\end{document}