summaryrefslogtreecommitdiffstats
path: root/notes-inf105.tex
blob: a8572db7947d2c0a1818b9fb34575d78dc0c6929 (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
737
738
739
740
741
742
743
744
745
746
747
748
749
750
751
752
753
754
755
756
757
758
759
760
761
762
763
764
765
766
767
768
769
770
771
772
773
774
775
776
777
778
779
780
781
782
783
784
785
786
787
788
789
790
791
792
793
794
795
796
797
798
799
800
801
802
803
804
805
806
807
808
809
810
811
812
813
814
815
816
817
818
819
820
821
822
823
824
825
826
827
828
829
830
831
832
833
834
835
836
837
838
839
840
841
842
843
844
845
846
847
848
849
850
851
852
853
854
855
856
857
858
859
860
861
862
863
864
865
866
867
868
869
870
871
872
873
874
875
876
877
878
879
880
881
882
883
884
885
886
887
888
889
890
891
892
893
894
895
%% 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}[subsection]
\newcommand\thingy{%
\refstepcounter{comcnt}\smallbreak\noindent\textbf{\thecomcnt.} }
\newtheorem{defn}[comcnt]{Définition}
\newtheorem{prop}[comcnt]{Proposition}
\newtheorem{lem}[comcnt]{Lemme}
\newtheorem{thm}[comcnt]{Théorème}
\newtheorem{cor}[comcnt]{Corollaire}
\newtheorem{scho}[comcnt]{Scholie}
\newtheorem{algo}[comcnt]{Algorithme}
\renewcommand{\qedsymbol}{\smiley}
%
\newcommand{\liff}{\mathrel{\Longleftrightarrow}\relax}
%
\DeclareUnicodeCharacter{00A0}{~}
%
\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}}
%
%
% NOTE: compile dot files with
% dot2tex --figonly -f tikz --tikzedgelabels --graphstyle=automaton file.dot  > file.tex
\tikzstyle{automaton}=[>=stealth',initial text={}]
\tikzstyle{state}=[]
\tikzstyle{final}=[accepting by arrow]
%
%
%
\begin{document}
\title{THL (Théorie des langages)\\Notes de cours \textcolor{red}{provisoires}}
\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


%
%
%

{\footnotesize
\tableofcontents
\par}

\bigbreak

\section{Alphabets, mots et langages}

\subsection{Introduction, alphabets, mots et longueur}

\thingy L'objet de ces notes, au confluent des mathématiques et de
l'informatique, est l'étude des \textbf{langages} : un langage étant
un ensemble de \textbf{mots}, eux-mêmes suites finies de
\textbf{lettres} choisies dans un \textbf{alphabet}, on va commencer
par définir ces différents termes avant de décrire plus précisément
l'objet de l'étude.

\thingy Le point de départ est donc ce que les mathématiciens
appelleront un \textbf{alphabet}, et qui correspond pour les
informaticiens à un \textbf{jeu de caractères}.  Il s'agit d'un
ensemble \emph{fini}, sans structure particulière, dont les éléments
s'appellent \textbf{lettres}, ou encore \textbf{caractères} dans une
terminologie plus informatique.

Les exemples mathématiques seront souvent donnés sur un alphabet tel
que l'alphabet à deux lettres $\{a,b\}$ ou à trois lettres
$\{a,b,c\}$.  On pourra aussi considérer l'alphabet $\{0,1\}$ appelé
\textbf{binaire} (puisque l'alphabet n'a pas de structure
particulière, cela ne fait guère de différence par rapport à n'importe
quel autre alphabet à deux lettres).  Dans un contexte informatique,
des jeux de caractères (=alphabets) souvent importants sont ASCII,
Latin-1 ou Unicode : en plus de former un ensemble, ces jeux de
caractère attribuent un numéro à chacun de leurs éléments (par
exemple, la lettre A majuscule porte le numéro 65 dans ces trois jeux
de caractères), mais cette structure supplémentaire ne nous
intéressera pas ici.  Dans tous les cas, il est important pour la
théorie que l'alphabet soit \emph{fini}.

L'alphabet sera généralement fixé une fois pour toutes dans la
discussion, et désigné par la lettre $\Sigma$ (sigma majuscule).

\thingy Un \textbf{mot} sur l'alphabet $\Sigma$ est une suite finie de
lettres (éléments de $\Sigma$) ; dans la terminologie informatique, on
parle plutôt de \textbf{chaîne de caractères}, qui est une suite finie
(=liste) de caractères.  Le mot est désigné en écrivant les lettres
les unes à la suite des autres : autrement dit, si $x_1,\ldots,x_n \in
\Sigma$ sont des lettres, le mot formé par la suite finie
$x_1,\ldots,x_n$ est simplement écrit $x_1\cdots x_n$.  À titre
d'exemple, $abbcab$ est un mot sur l'alphabet $\Sigma = \{a,b,c,d\}$,
et \texttt{foobar} est un mot (=chaîne de caractères) sur l'alphabet
ASCII.  (Dans un contexte informatique, il est fréquent d'utiliser une
sorte de guillemet pour délimiter les chaînes de caractères : on
écrira donc \texttt{\char`\"foobar\char`\"} pour parler du mot en
question.  Dans ces notes, nous utiliserons peu cette convention.)

L'ensemble des mots sur un alphabet $\Sigma$ est généralement
désigné $\Sigma^*$ (on verra que l'étoile fait partie d'un usage plus
général qui sera défini ci-dessous).  Par exemple, si $\Sigma =
\{0,1\}$, alors $\Sigma^*$ est l'ensemble (infini !) dont les éléments
sont toutes les suites finies binaires (=suites finies de $0$ et
de $1$).

\thingy Le nombre $n$ de lettres dans un mot $w \in \Sigma^*$ est
appelé la \textbf{longueur} du mot, et généralement notée $|w|$ ou
bien $\ell(w)$ : autrement dit, si $x_1,\ldots,x_n \in \Sigma$, alors
la longueur $\ell(x_1\cdots x_n)$ du mot $x_1\cdots x_n$, vaut $n$.
Ceci coïncide bien avec la notion usuelle de longueur d'une chaîne de
caractères en informatique.  À titre d'exemple, sur l'alphabet
$\Sigma=\{a,b,c,d\}$, la longueur du mot $abbcab$ vaut $6$ (on écrira
$|abbcab|=6$ ou bien $\ell(abbcab)=6$).

\thingy Quel que soit l'alphabet, il existe un unique mot de
longueur $0$, c'est-à-dire un unique mot n'ayant aucune lettre, appelé
le \textbf{mot vide} (ou la \textbf{chaîne [de caractères] vide}).
Étant donné qu'il n'est pas commode de désigner un objet par une
absence de symbole, on introduit un symbole spécial, généralement
$\varepsilon$, pour désigner ce mot vide : on a donc
$|\varepsilon|=0$.  On souligne que le symbole $\varepsilon$
\underline{ne fait pas partie} de l'alphabet $\Sigma$, c'est un
symbole \emph{spécial} qui a été introduit pour désigner le mot vide.
(Lorsque les mots sont délimités par des guillemets, comme il est
usage pour les chaînes de caractères en informatique, le mot vide n'a
pas besoin d'un symbole spécial : il s'écrit juste
\texttt{\char`\"\char`\"} — sans aucun caractère entre les
guillemets.)

{\footnotesize Lorsque l'alphabet $\Sigma$ est \emph{vide},
  c'est-à-dire $\Sigma=\varnothing$, alors le mot vide est le seul mot
  qui existe : on a $\Sigma^*=\{\varepsilon\}$ dans ce cas.  C'est la
  seule situation où l'ensemble $\Sigma^*$ des mots est un ensemble
  fini.  Dans la suite, nous négligerons parfois ce cas particulier,
  qu'on pourra oublier : c'est-à-dire que nous ferons parfois
  l'hypothèse tacite que $\Sigma \neq \varnothing$.\par}

La notation $\Sigma^+$ est parfois utilisée pour désigner l'ensemble
des mots \emph{non vides} sur l'alphabet $\Sigma$ (par opposition à
$\Sigma^*$ qui désigne l'ensemble de tous les mots, y compris le mot
vide).

\thingy\label{convention-on-words-of-length-one} Les mots d'une seule
lettre sont naturellement en correspondance avec les lettres
elles-mêmes : on identifiera souvent tacitement, quoique un peu
abusivement, une lettre $x\in\Sigma$ et le mot de longueur $1$ formé
de la seule lettre $x$.  (En informatique, cette identification entre
\emph{caractères} et \emph{chaînes de caractères de longueur $1$} est
faite par certains langages de programmation, mais pas par tous :
\textit{caveat programmator}.)  Ceci permet d'écrire par exemple
$\Sigma \subseteq \Sigma^*$ ou bien $|x|=1 \liff x\in\Sigma$.

\thingy\label{number-of-words-of-length-n} Si le cardinal de
l'alphabet $\Sigma$ vaut $\#\Sigma = N$, alors, pour chaque $n$, le
nombre de mots de longueur exactement $n$ est égal à $N^n$
(combinatoire classique).  Le nombre de mots de longueur $\leq n$ vaut
donc $1 + N + \cdots + N^n = \frac{N^{n+1}-1}{N-1}$ (somme d'une série
géométrique).


\subsection{Concaténation de mots, préfixes, suffixes, facteurs, sous-mots}

\thingy Si $u := x_1\cdots x_m$ et $v := y_1\cdots y_n$ sont deux
mots, de longueurs respectives $m$ et $n$, sur un même
alphabet $\Sigma$, alors on définit un mot $uv := x_1\cdots x_m
y_1\cdots y_n$ de longueur $m+n$, dont les lettres sont obtenues en
mettant bout à bout celles de $u$ puis celles de $v$ (dans cet ordre),
et on l'appelle \textbf{concaténation} (ou, si cela ne prête pas à
confusion, simplement \textbf{produit}) des mots $u$ et $v$.  (Dans un
contexte informatique, on parle de concaténation de chaînes de
caractères.)

\thingy Parmi les propriétés de la concaténation, signalons les faits
suivants :
\begin{itemize}
\item le mot vide $\varepsilon$ est « \textbf{neutre} » pour la
  concaténation, ce qui signifie par définition : $\varepsilon w = w
  \varepsilon = w$ quel que soit le mot $w \in \Sigma^*$ ;
\item la concaténation est « \textbf{associative} », ce qui signifie
  par définition : $u(vw) = (uv)w$ quels que soient les mots $u,v,w
  \in \Sigma^*$.
\end{itemize}

On peut traduire de façon savante ces deux propriétés en une phrase :
l'ensemble $\Sigma^*$ est un \textbf{monoïde}, d'élément
neutre $\varepsilon$, pour la concaténation (cela signifie exactement
ce qui vient d'être dit).

\thingy On a par ailleurs $|uv| = |u| + |v|$ (la longueur de la
concaténation de deux mots est la somme des concaténations), et on
rappelle par ailleurs que $|\varepsilon| = 0$ ; on peut traduire cela
de manière savante : la longueur est un \textbf{morphisme de monoïdes}
entre le monoïde $\Sigma^*$ des mots (pour la concaténation) et le
monoïde $\mathbb{N}$ des entiers naturels (pour l'addition) (cela
signifie exactement ce qui vient d'être dit).

{\footnotesize\thingy \textbf{Complément :} Le monoïde $\Sigma^*$
  possède la propriété suivante par rapport à l'ensemble $\Sigma$ : si
  $M$ est un monoïde quelconque (c'est-à-dire un ensemble muni d'une
  opération binaire associative $\cdot$ et d'un élément $e$ neutre
  pour cette opération), et si $\psi\colon \Sigma\to M$ est une
  application quelconque, alors il existe un unique morphisme de
  monoïdes $\hat\psi\colon \Sigma^* \to M$ (c'est-à-dire une
  application préservant le neutre et l'opération binaire) tel que
  $\hat\psi(x) = \psi(x)$ si $x\in\Sigma$.  (Démonstration : on a
  nécessairement $\hat\psi(x_1\cdots x_n) = \psi(x_1)\cdots
  \psi(x_n)$, or ceci définit bien un morphisme comme annoncé.)  On
  dit qu'il s'agit là d'une propriété « universelle », et plus
  précisément que $\Sigma^*$ est le \textbf{monoïde libre} sur
  l'ensemble $\Sigma$.  Par exemple, le morphisme « longueur »
  $\ell\colon\Sigma^*\to\mathbb{N}$ est le $\ell = \hat\psi$ obtenu en
  appliquant cette propriété à la fonction $\psi(x) = 1$ pour
  tout $x\in\Sigma$.\par}

\thingy\label{powers-of-a-word} Lorsque $w \in \Sigma^*$ et $r \in
\mathbb{N}$, on définit un mot $w^r$ comme la concaténation de $r$
facteurs tous égaux au mot $w$, autrement dit, comme la répétition $r$
fois du mot $w$.  Formellement, on définit par récurrence :
\begin{itemize}
\item $w^0 = \varepsilon$ (le mot vide),
\item $w^{r+1} = w^r w$.
\end{itemize}
(Ces définitions valent, d'ailleurs, dans n'importe quel monoïde.  On
peut constater que $w^r w^s = w^{r+s}$ quels que soient
$r,s\in\mathbb{N}$.)  On a bien sûr $|w^r| = r|w|$.

Cette définition sert notamment à désigner de façon concise les mots
comportant des répétitions d'une même lettre : par exemple, le mot
$aaaaa$ peut s'écrire tout simplement $a^5$, et le mot $aaabb$ peut
s'écrire $a^3 b^2$.  (De même que pour le mot vide, il faut souligner
que ces exposants ne font pas partie de l'alphabet.)

\thingy Lorsque $u,v,w \in \Sigma^*$ vérifient $w = uv$, autrement dit
lorsque le mot $w$ est la concaténation des deux mots $u$ et $v$, on
dira également :
\begin{itemize}
\item que $u$ est un \textbf{préfixe} de $w$, ou
\item que $v$ est un \textbf{suffixe} de $w$.
\end{itemize}

De façon équivalente, si $w = x_1\cdots x_n$ (où $x_1,\ldots,x_n \in
\Sigma$) est un mot de longueur $n$, et si $0\leq k\leq n$ est un
entier quelconque compris entre $0$ et $n$, on dira que $u :=
x_1\cdots x_k$ (c'est-à-dire, le mot formé des $k$ premières lettres
de $w$, dans le même ordre) est le \textbf{préfixe de longueur $k$}
de $w$, et que $v := x_{k+1}\cdots x_n$ (mot formé des $n-k$ dernières
lettres de $w$, dans le même ordre) est le \textbf{suffixe de
  longueur $n-k$} de $w$.  Il est clair qu'il s'agit bien là de
l'unique façon d'écrire $w = uv$ avec $|u|=k$ et $|v|=n-k$, ce qui
fait le lien avec la définition donnée au paragraphe précédent ;
parfois on dira que $v$ est le suffixe \textbf{correspondant} à $u$ ou
que $u$ est le préfixe correspondant à $v$ (dans le mot $w$).

Le mot vide est préfixe et suffixe de n'importe quel mot.  Le mot $w$
lui-même est aussi un préfixe et un suffixe de lui-même.  Entre les
deux, pour n'importe quelle longueur $k$ donnée, il existe un unique
préfixe et un unique suffixe de longueur $k$.  (Il peut tout à fait se
produire que le préfixe et le suffixe de longueur $k$ soient égaux
pour d'autres $k$ que $0$ et $|w|$, comme le montre l'exemple qui
suit.)

À titre d'exemple, le mot $abbcab$ sur l'alphabet $\Sigma=\{a,b,c,d\}$
a les sept préfixes suivants, rangés par ordre croissant de longueur :
$\varepsilon$ (le mot vide), $a$, $ab$, $abb$, $abbc$, $abbca$ et
$abbcab$ lui-même ; il a les sept suffixes suivants, rangés par ordre
croissant de longueur : $\varepsilon$ (le mot vide), $b$, $ab$, $cab$,
$bcab$, $bbcab$ et $abbcab$ lui-même.  Le suffixe correspondant au
préfixe $abb$ est $bcab$ puisque $abbcab = (abb)(bcab)$.

\thingy Comme généralisation à la fois de la notion de préfixe et de
celle de suffixe, on a la notion de facteur : si $u_0,v,u_1 \in
\Sigma^*$ sont trois mots quelconques sur un même alphabet $\Sigma$,
et si $w = u_0 v u_1$ est leur concaténation, on dira que $v$ est un
\textbf{facteur} de $w$.  Alors qu'un préfixe ou suffixe du mot $w$
est déterminé simplement par sa longueur, un facteur est déterminé par
sa longueur et l'emplacement à partir duquel il commence.

À titre d'exemple, les facteurs du mot $abbcab$ sont : $\varepsilon$
(le mot vide), $a$, $b$, $c$, $ab$, $bb$, $bc$, $ca$, $abb$, $bbc$,
$bca$, $cab$, $abbc$, $bbca$, $bcab$, $abbca$, $bbcab$ et $abbcab$
lui-même.

Dans un contexte informatique, ce que nous appelons ici « facteur »
est souvent appelé « sous-chaîne [de caractères] ».  Il ne faut
cependant pas confondre ce concept avec celui de sous-mot défini
ci-dessous.

\thingy\label{definition-subword} Si $u_0,\ldots,u_r$ et
$v_1,\ldots,v_r$ sont des mots sur un même alphabet $\Sigma$, on dira
que $v := v_1\cdots v_r$ est un \textbf{sous-mot} du mot $w := u_0 v_1
u_1 v_2 \cdots u_{r-1} v_r u_r$.  En plus clair, cela signifie que $v$
est obtenu en ne gardant que certaines lettres du mot $w$ (celles
des $v_i$), dans le même ordre, mais en en effaçant d'autres (celles
des $u_i$) ; à la différence du concept de facteur, celui de sous-mot
n'exige pas que les lettres gardées soient consécutives.

À titre d'exemple, le mot $acb$ est un sous-mot du mot $abbcab$
(obtenu en gardant les lettres soulignées ici :
$\underline{a}bb\underline{c}a\underline{b}$ ; pour se rattacher à la
définition ci-dessus, on pourra prendre $u_0 = \varepsilon$ et $v_1 =
a$ et $u_1 = bb$ et $v_2 = c$ et $u_2 = a$ et $v_3 = b$ et $u_3 =
\varepsilon$).

\thingy Si $w = x_1\cdots x_n$, où $x_1,\ldots,x_n \in \Sigma$, est un
mot de longueur $n$ sur un alphabet $\Sigma$, alors on définit son mot
\textbf{miroir} ou \textbf{transposé}, parfois noté $w^{\textsf{R}}$
ou $w^{\textsf{T}}$ (parfois les exposants sont écrits à gauche),
comme le mot $x_n\cdots x_1$ dont les lettres sont les mêmes que
celles de $w$ mais dans l'ordre inverse.  À titre d'exemple,
$(ababb)^{\textsf{R}} = bbaba$.  On remarquera que $(w_1
w_2)^{\textsf{R}} = w_2^{\textsf{R}} w_1^{\textsf{R}}$ si $w_1,w_2$
sont deux mots quelconques.

Un mot $w$ est dit \textbf{palindrome} lorsque $w = w^{\textsf{R}}$.


\subsection{Langages et opérations sur les langages}

\thingy Un \textbf{langage} $L$ sur l'alphabet $\Sigma$ est simplement
un ensemble de mots sur $\Sigma$.  Autrement dit, il s'agit d'un
sous-ensemble (=une partie) de l'ensemble $\Sigma^*$ de tous les mots
sur $\Sigma^*$ : en symboles, $L \subseteq \Sigma^*$.  On souligne
qu'on ne demande pas que $L$ soit fini (mais il peut l'être).

\thingy À titre d'exemple, l'ensemble $\{d,dc,dcc,dccc,dcccc,\ldots\}
= \{dc^r \colon r\in\mathbb{N}\}$ des mots formés d'un $d$ suivi d'un
nombre quelconque (éventuellement nul) de $c$ est un langage sur
l'alphabet $\Sigma = \{a,b,c,d\}$.  On verra plus loin que ce langage
est « rationnel » (et pourra être désigné par l'expression rationnelle
$dc*$).

Voici quelques autres exemples de langages :
\begin{itemize}
\item Le langage (fini) $\{foo,bar,baz\}$ formé des seuls trois mots
  $foo$, $bar$, $baz$ sur l'alphabet $\Sigma = \{a,b,f,o,r,z\}$.
\item Le langage (fini) formé des mots de longueur exactement $42$ sur
  l'alphabet $\Sigma = \{p,q,r\}$.  Comme on l'a vu
  en \ref{number-of-words-of-length-n}, cet ensemble a pour cardinal
  exactement $3^{42}$.
\item Le langage (fini) formé du seul mot vide (=mot de longueur
  exactement $0$) sur l'alphabet, disons, $\Sigma = \{p,q,r\}$.  Ce
  langage $\{\varepsilon\}$ a pour cardinal $1$ (ou $3^0$ si on veut).
  Il ne faut pas le confondre avec le suivant :
\item Le langage vide, qui ne contient aucun mot (sur un alphabet
  quelconque).  Ce langage a pour cardinal $0$.
\item Le langage formé des mots de une seule lettre sur un alphabet
  $\Sigma$, qu'on peut identifier à $\Sigma$ lui-même (en identifiant
  un mot de une lettre à la lettre en question).
\item Le langage sur l'alphabet $\Sigma=\{a,b\}$ formé des mots qui
  commencent par trois $a$ consécutifs : ou, si on préfère, qui ont le
  mot $aaa$ comme préfixe.
\item Le langage sur l'alphabet $\Sigma=\{a,b\}$ formé des mots qui
  contiennent trois $a$ consécutifs ; ou, si on préfère, qui ont $aaa$
  comme facteur.
\item Le langage sur l'alphabet $\Sigma=\{a,b\}$ formé des mots qui
  contiennent au moins trois $a$, non nécessairement consécutifs ; ou,
  si on préfère, qui ont $aaa$ comme sous-mot.
\item Le langage sur l'alphabet $\Sigma=\{a\}$ formé de tous les mots
  dont la longueur est un nombre premier ($L = \{aa, aaa, a^5, a^7,
  a^{11},\ldots\}$).  Ce langage est infini.
\item Le langage sur l'alphabet $\Sigma=\{0,1\}$ formé de tous les
  mots commençant par un $1$ et qui, interprétés comme un nombre écrit
  en binaire, désignent un nombre premier ($L = \{10, 11, 101, 111,
  1011, \ldots\}$).
\item Le langage sur l'alphabet Unicode formé de tous les mots qui
  constituent un document XML bien-formé d'après la spécification
  XML 1.0.
\end{itemize}

\thingy On pourrait aussi considérer un langage (sur
l'alphabet $\Sigma$) comme une \emph{propriété} des mots (sur
l'alphabet en question).  Précisément, si $P$ est une propriété qu'un
mot $w \in \Sigma^*$ peut ou ne pas avoir, on considère le langage
$L_P = \{w \in \Sigma^* : w \text{~a la propriété~} P\}$, et
inversement, si $L \subseteq \Sigma^*$ est un langage, on considère la
propriété « appartenir à $L$ » : en identifiant la propriété et le
langage qu'on vient d'associer l'un à l'autre (par exemple, le langage
des mots commençant par $a$ et la propriété « commencer par $a$ »), un
langage pourrait être considéré comme une propriété des mots.

{\footnotesize(Ceci n'a rien de spécifique aux langages : une partie
  d'un ensemble $E$ quelconque peut être identifiée à une propriété
  que les éléments de $E$ peuvent ou ne pas avoir, à savoir,
  appartenir à la partie en question.)\par}

On évitera de faire cette identification pour ne pas introduire de
confusion, mais il est utile de la garder à l'esprit : par exemple,
dans un langage de programmation fonctionnel, un « langage » au sens
de ces notes peut être considéré comme une fonction (pure,
c'est-à-dire, déterministe et sans effet de bord) prenant en entrée
une chaîne de caractères et renvoyant un booléen.

\thingy Si $L_1$ et $L_2$ sont deux langages sur un même
alphabet $\Sigma$ (autrement dit, $L_1,L_2 \subseteq \Sigma^*$), on
peut former les langages \textbf{union} $L_1\cup L_2$ et
\textbf{intersection} $L_1\cap L_2$ qui sont simplement les opérations
ensemblistes usuelles (entre parties de $\Sigma^*$).

Les opérations correspondantes sur les propriétés de mots sont
respectivement le « ou logique » (=disjonction) et le « et logique »
(=conjonction) : à titre d'exemple, sur $\Sigma = \{a,b\}$ si $L_1$
est le langage des mots commençant par $a$ et $L_2$ le langage des
mots finissant par $b$, alors $L_1 \cup L_2$ est le langage des mots
commençant par $a$ \emph{ou bien} finissant par $b$, tandis que $L_1
\cap L_2$ est le langage des mots commençant par $a$ \emph{et}
finissant par $b$.

\thingy Si $L$ est un langage sur l'alphabet $\Sigma$, autrement dit
$L \subseteq \Sigma^*$, on peut former le langage $\Sigma^*\setminus
L$, parfois noté simplement $\overline L$ si ce n'est pas ambigu, dit
\textbf{complémentaire} de $L$, et qui est simplement l'ensemble des
mots sur $\Sigma$ \emph{n'appartenant pas} à $L$.  L'opération
correspondante sur les propriétés de mots est la négation logique.

À titre d'exemple, sur $\Sigma=\{a,b\}$, si $L$ est le langage des
mots commençant par $a$, alors $\overline{L}$ est le langage des mots
ne commençant pas par $a$, c'est-à-dire, la réunion de
$\{\varepsilon\}$ et du langage des mots commençant par $b$ (car sur
$\Sigma=\{a,b\}$, un mot ne commençant pas par $a$ est vide ou bien
commence par $b$).

\thingy Si $L_1$ et $L_2$ sont deux langages sur un même
alphabet $\Sigma$ (autrement dit, $L_1,L_2 \subseteq \Sigma^*$), on
peut former le langage \textbf{concaténation} $L_1 L_2$ : il est
défini comme l'ensemble des mots $w$ qui peuvent s'écrire comme
concaténation d'un mot $w_1$ de $L_1$ et d'un mot $w_2$ de $L_2$, soit
\[
\begin{aligned}
L_1 L_2 &= \{w_1 w_2 : w_1 \in L_1,\, w_2 \in L_2\}\\
 &= \{w \in \Sigma^* : \exists w_1 \in L_1\, \exists w_2 \in L_2\,(w = w_1 w_2)\}\\
\end{aligned}
\]

À titre d'exemple, sur l'alphabet $\Sigma = \{a,b,c,d\}$, si on a $L_1
= \{a,bb\}$ et $L_2 = \{bc, cd\}$ alors $L_1 L_2 = \{abc, acd, bbbc,
bbcd\}$.

\thingy Si $L$ est un langage sur l'alphabet $\Sigma$, autrement dit
$L \subseteq \Sigma^*$, et si $r \in \mathbb{N}$, on peut définir un
langage $L^r$, par analogie avec \ref{powers-of-a-word}, comme le
langage $L^r = \{w_1\cdots w_r : w_1,\ldots,w_r \in L\}$ formé des
concaténation de $r$ mots appartenant à $L$, ou si on préfère, par
récurrence :
\begin{itemize}
\item $L^0 = \{\varepsilon\}$,
\item $L^{r+1} = L^r L$.
\end{itemize}

À titre d'exemple, sur l'alphabet $\Sigma = \{a,b,c,d\}$, si on a $L =
\{a,bb\}$, alors $L^2 = \{aa, abb, bba, bbbb\}$ et $L^3 = \{aaa, aabb,
abba, abbbb, \penalty-100 bbaa, bbabb, bbbba, bbbbbb\}$.

\emph{Attention}, $L^r$ n'est pas le langage $\{w^r : w\in L\}$ formé
des répétitions $r$ fois ($w^r$) des mots $w$ de $L$ : c'est le
langage des concaténations de $r$ mots appartenant à $L$ \emph{mais
  ces mots peuvent être différents}.  À titre d'exemple, si $L =
\{a,b\}$ alors $L^r$ est le langage formé des $2^r$ mots de longueur
exactement $r$ sur $\{a,b\}$, ce n'est pas l'ensemble à deux éléments
$\{a^r, b^r\}$ formé des seuls deux mots $a^r = aaa\cdots a$ et $b^r =
bbb\cdots b$.

\thingy Si $L$ est un langage sur l'alphabet $\Sigma$, on définit
enfin l'\textbf{étoile de Kleene} $L^*$ de $L$ comme le langage formé
des concaténations d'un nombre \emph{quelconque} de mots appartenant
à $L$, c'est-à-dire
\[
\begin{aligned}
L^* &= \bigcup_{r=0}^{+\infty} L^r = \bigcup_{r\in\mathbb{N}} L^r\\
&= \{w_1\cdots w_r : r\in\mathbb{N},\, w_1,\ldots,w_r\in L\}\\
\end{aligned}
\]

Comme ci-dessus, il faut souligner que les mots $w_1,\ldots,w_r$
concaténés n'ont pas à être égaux : notamment, $\{a,b\}^*$ est le
langage formé de tous les mots sur l'alphabet $\{a,b\}$, pas le
langage $\{a\}^* \cup \{b\}^*$ formé des mots obtenus en répétant la
lettre $a$ ou en répétant la lettre $b$.

On remarquera que la définition de $L^*$ ci-dessus redonne bien,
lorsqu'on l'applique à l'alphabet $\Sigma$ lui-même (considéré comme
langage des mots de longueur $1$), l'ensemble $\Sigma^*$ de tous les
mots : la notation $\Sigma^*$ est donc justifiée \textit{a
  posteriori}.

Le mot vide appartient toujours à $L^*$ (quel que soit $L$) puisque
$L^0 = \{\varepsilon\}$ et qu'on peut prendre $r=0$ ci-dessus
(autrement dit, le mot vide est la concaténation de zéro mots de $L$).

\thingy\label{kleene-plus} On introduit parfois la notation $L^+ =
\bigcup_{r=1}^{+\infty} L^r = \{w_1\cdots w_r : r>0,\penalty-100\,
w_1,\ldots,w_r\in L\}$ pour l'ensemble des mots formés par
concaténation d'un nombre \emph{non nul} de mots de $L$.  Lorsque le
mot vide $\varepsilon$ n'appartient pas déjà à $L$, ce langage $L^+$
diffère de $L^*$ seulement en ce qu'il ne contient pas $\varepsilon$ ;
tandis que si $\varepsilon$ appartient déjà à $L$, alors $L^+$ est
égal à $L^*$.  En toute généralité, on a $L^+ = LL^*$.


\subsection{Langages rationnels et expressions rationnelles}

\thingy Soit $\Sigma$ un alphabet.  On va considérer les langages
de base triviaux suivants :
\begin{itemize}
\item le langage vide $\varnothing$,
\item le langage formé du seul mot vide, $\{\varepsilon\}$, et
\item les langages formés d'un seul mot lui-même formé d'une seule
  lettre, $\{x\}$ pour chaque $x\in\Sigma$,
\end{itemize}
et on va les combiner par les opérations dites « rationnelles »
suivantes :
\begin{itemize}
\item la réunion $(L_1,L_2) \mapsto L_1 \cup L_2$,
\item la concaténation $(L_1,L_2) \mapsto L_1 L_2$, et
\item l'étoile de Kleene $L \mapsto L^*$.
\end{itemize}

On obtient ainsi une certaine famille de langages (cf. ci-dessous pour
une définition plus précise), qu'on appelle \textbf{langages
  rationnels} : les langages rationnels sont exactement ceux qui
peuvent s'obtenir à partir des langages de base énumérés ci-dessus par
application (un nombre fini de fois) des opérations qu'on vient de
dire (i.e., la réunion de deux langages rationnels, ou la
concaténation de deux langages rationnels, ou l'étoile de Kleene d'un
langage rationnel, sont rationnels, et les langages rationnels sont
exactement ceux qu'on obtient ainsi).

À titre d'exemple, sur l'alphabet $\{a,b,c,d\}$, comme le langage
$\{c\}$ (formé du seul mot $c$) est rationnel, son étoile de Kleene,
c'est-à-dire $\{c\}^* = \{\varepsilon, c, cc, ccc, cccc,\ldots\}$, est
rationnel, et comme $\{d\}$ l'est aussi, la concaténation
$\{d\}(\{c\}^*) = \{d, dc, dcc, dccc, \ldots\}$ est encore un langage
rationnel.

{\footnotesize\thingy Formellement, la définition des langages
  rationnelles est la suivante : un ensemble $\mathscr{C} \subseteq
  \mathscr{P}(\Sigma^*)$ de langages (où $\mathscr{P}(\Sigma^*)$ est
  l'ensemble des parties de $\Sigma^*$, i.e., l'ensemble de tous les
  langages sur $\Sigma$) est dit \emph{stable par opérations
    rationnelles} lorsqu'il est stable par les opérations de réunion,
  concaténation et étoile de Kleene, i.e., si $L_1,L_2 \in
  \mathscr{C}$ alors $L_1\cup L_2 \in \mathscr{C}$ et $L_1 L_2 \in
  \mathscr{C}$, et si $L \in \mathscr{C}$ alors $L^* \in
  \mathscr{C}$ ; le \emph{plus petit} (pour l'inclusion) ensemble de
  langages stable par opérations rationnelles et contenant les
  langages $\varnothing$, $\{\varepsilon\}$ et $\{x\}$ pour $x \in
  \Sigma$ (i.e. $\varnothing\in\mathscr{C}$, $\{\varepsilon\} \in
  \mathscr{C}$ et si $x\in\Sigma$ alors $\{x\}\in\mathscr{C}$), ou
  plus exactement, l'intersection de tous les ensembles $\mathscr{C}$
  vérifiant tous ces propriétés, est la classe $\mathscr{R}$ des
  langages rationnels. \par}

\thingy Pour décrire la manière dont un langage rationnel est fabriqué
(à partir des langages de base par les opérations rationnelles), comme
il est malcommode d'écrire quelque chose comme $\{d\}(\{c\}^*)$, on
introduit un nouvel objet, les \textbf{expressions rationnelles}
(certains préfèrent le terme d'\textbf{expressions régulières}), qui
sont des expressions servant à désigner un langage rationnel.  Par
exemple, plutôt que d'écrire « $\{d\}(\{c\}^*)$ », on parlera du
langage désigné par l'expression rationnelle $dc*$.

Plus exactement, une expression rationnelle (sur un alphabet $\Sigma$)
est un mot sur l'alphabet $\Sigma \cup \{\bot,
\underline{\varepsilon}, {(}, {)}, {|}, {*}\}$, où $\bot,
\underline{\varepsilon}, {(}, {)}, {|}, {*}$ sont de nouveaux
caractères \emph{n'appartenant pas} à l'alphabet $\Sigma$, appelés
\textbf{métacaractères}, et qui servent à marquer la manière dont est
formée l'expression rationnelle.  On définit simultanément la notion
d'expression rationnelle $r$ et de \textbf{langage désigné} $L_r$ par
l'expression $r$, de la manière suivante :
\begin{itemize}
\item $\bot$ est une expression rationnelle et son langage désigné
  est $L_\bot := \varnothing$,
\item $\underline{\varepsilon}$ est une expression rationnelle et son
  langage désigné est $L_{\underline{\varepsilon}} :=
  \{\varepsilon\}$,
\item si $x\in\Sigma$ est une lettre de l'alphabet $\Sigma$, alors le
  mot $x$ est une expression rationnelle et son langage désigné
  est $L_x := \{x\}$,
\item si $r_1,r_2$ sont deux expressions rationnelles et $L_1 =
  L_{r_1}$ et $L_2 = L_{r_2}$ les langages désignés correspondants,
  alors $r_1 r_2$ est une expression rationnelle et son langage
  désigné est $L_{r_1 r_2} := L_1 L_2$,
\item si $r_1,r_2$ sont deux expressions rationnelles et $L_1 =
  L_{r_1}$ et $L_2 = L_{r_2}$ les langages désignés correspondants,
  alors $(r_1|r_2)$ est une expression rationnelle et son langage
  désigné est $L_{(r_1|r_2)} := L_1\cup L_2$,
\item si $r$ est une expression rationnelle et $L = L_r$ les langage
  désigné correspondant, alors $(r)*$ est une expression rationnelle
  et son langage désigné est $L_{(r)*} := L^*$.
\end{itemize}

À titre d'exemple, sur l'alphabet $\Sigma = \{a,b,c,d\}$, $c$ est une
expression rationnelle qui désigne le langage $\{c\}$, donc $(c)*$ en
est une qui désigne le langage $\{c\}^* = \{\varepsilon, c, cc,
ccc,\ldots\}$, et enfin $d(c)*$ en est une qui désigne le langage $\{d,
dc, dcc, \ldots\}$ des mots formés d'un $d$ et d'une succession
quelconques de $c$.  Voici quelques autres exemples, toujours sur
$\Sigma = \{a,b,c,d\}$ :
\begin{itemize}
\item l'expression rationnelle $(a|b)$ désigne le langage $\{a\} \cup
  \{b\} = \{a,b\}$ formé des deux mots d'une seule lettre $a$ et $b$ ;
\item l'expression rationnelle $(a|b)c$ désigne le langage
  $\{a,b\}\{c\} = \{ac,bc\}$, de même que $(ac|bc)$ ;
\item l'expression rationnelle $(bc)*$ désigne le langage $\{bc\}^* =
  \{\varepsilon, bc, bcbc, bcbcbc, \ldots\}$ ;
\item l'expression rationnelle $(a|(bc)*)$ désigne le langage $\{a\}
  \cup \{bc\}^* = \{a, \varepsilon, bc, bcbc, bcbcbc, \ldots\}$ ;
\item l'expression rationnelle $(a|(bc)*)d$ désigne le langage $\{a, d,
  bcd, bcbcd, bcbcbcd, \ldots\}$.
\end{itemize}

Un langage rationnel est par construction la même chose qu'un langage
pour lequel il existe une expression rationnelle qui le désigne.

On dira qu'un mot $w$ \textbf{vérifie} une expression rationnelle $r$
lorsque ce mot appartient au langage qu'elle désigne (i.e., $w \in
L_r$).  Par exemple, $dccc$ vérifie l'expression rationnelle $d(c)*$.

La convention de parenthésage introduite ci-dessus est inambiguë mais
parfois inutilement lourde : on se permettra parfois de l'alléger, par
exemple d'écrire $(r_1|r_2|r_3)$ pour $((r_1|r_2)|r_3)$ (ou pour
$(r_1|(r_2|r_3))$, ce qui n'a guère d'importance vu qu'elles désignent
le même langage), ou encore $x*$ pour $(x)*$ lorsque $x$ est formé
d'un seul caractère.  La convention essentielle est que l'opération
d'étoile $*$ est la plus prioritaire ($ab*$ se lit comme $a(b)*$ et
non pas comme $(ab)*$), la concaténation vient après, et la barre de
disjonction $|$ est la moins prioritaire ($ab|cd$ se lit comme
$(ab|cd)$ et pas comme $a(b|c)d$).

{\footnotesize Les métacaractères $\bot$ et $\underline{\varepsilon}$
  sont introduits ici par souci de complétude mais font rarement
  utilisés dans les expressions rationnelles (le métacaractère
  $\underline{\varepsilon}$ a été souligné parce qu'il s'agit d'une
  vraie lettre et non pas du mot vide ; on peut ignorer cette
  subtilité qui n'a que très peu d'importance).\par}

La barre de disjonction que nous avons notée ${|}$ est souvent plutôt
notée $+$ par les mathématiciens.  Il y a ici un risque de confusion
lié au fait que, en informatique, le symbole \texttt{+} est utilisé
par de nombreux moteurs d'expressions régulières (par exemple,
\texttt{egrep}) pour désigner l'opération évoquée en \ref{kleene-plus}
(de sorte que $r+$ a le même sens que $rr*$).


\section{Automates finis}

\setcounter{comcnt}{0}

\thingy Les automates finis sont un modèle de calcul particulièrement
simple et particulièrement appropriés à l'étude et à l'analyse des
langages rationnels.  Il faut imaginer un automate fini comme une
machine disposant d'une quantité finie (et sous-entendu, très limitée)
de mémoire : la configuration complète de cette mémoire est décrite
par un \emph{état}, qui appartient à un ensemble fini d'états
possibles.  L'automate prendra une décision (passer dans un nouvel
état) en fonction de son état actuel et de la lettre qu'on lui donne à
consommer.

\subsection{Automates finis déterministes (=DFA)}

\thingy\label{definition-dfa} Un \textbf{automate fini déterministe},
ou en abrégé \textbf{DFA} (pour \textit{deterministic finite
  automaton}), sur un alphabet $\Sigma$ est la donnée
\begin{itemize}
\item d'un ensemble fini $Q$ dont les éléments sont appelés
  \textbf{états},
\item d'un état $q_0 \in Q$ appelé \textbf{état initial},
\item d'un ensemble $F \subseteq Q$ d'états appelés états
  \textbf{finaux}\footnote{Le pluriel de « final » est indifféremment
    « finaux » ou « finals ».} ou \textbf{acceptants},
\item d'une fonction $\delta \colon Q\times\Sigma \to Q$ appelée
  \textbf{fonction de transition}.
\end{itemize}

\thingy Graphiquement, on représente un DFA comme un graphe orienté
aux arêtes étiquetées par des éléments de $\Sigma$ : plus exactement,
on trace un nœud pour chaque élément $q \in Q$, et lorsque
$\delta(q,x) = q'$ on introduit une arête $q \to q'$ étiquetée par la
lettre $x$.  La condition sur $\delta$ (pour être un DFA) est alors
que, pour chaque état $q \in Q$ et chaque lettre $x \in \Sigma$, il
existe une unique arête partant de $q$ et étiquetée par $x$.  En
outre, on introduit une arête pointant de nulle part vers $q_0$, et
pour chaque $q\in F$ une arête pointant de $q$ vers nulle
part\footnote{Certains auteurs préfèrent d'autres conventions, par
  exemple celle consistant à entourer deux fois les états finaux.}.

Lorsque plusieurs arêtes étiquetées par des symboles $x,y$ différents
relient les mêmes sommets $q,q'$ (i.e., lorsqu'on a à la fois
$\delta(q,x) = q'$ et $\delta(q,y) = q'$), on pourra écrire « $x,y$ »
ou « $x|y$ » sur l'arête en question (et ne la tracer qu'une seule
fois).  Voir \ref{discussion-example2} ci-dessous pour un exemple.

\thingy\label{discussion-example1} Pour donner un exemple simple,
l'automate sur $\Sigma = \{a,b\}$ représenté ci-dessous a $Q =
\{0,1\}$ et $q_0 = 0$ et $F = \{1\}$ et la fonction de transition
$\delta$ donnée par $\delta(0,a) = 0$ et $\delta(0,b) = 1$ et
$\delta(1,a) = 1$ et $\delta(1,b) = 0$.  On pourra se convaincre (une
fois lues les définitions plus loin) que cet automate accepte les mots
dont le nombre de $b$ est pair.

\begin{center}
%%% begin example1 %%%

\begin{tikzpicture}[>=latex,line join=bevel,automaton]
%%
\node (q1) at (98bp,20.306bp) [draw,circle,state,final] {$1$};
  \node (q0) at (18bp,20.306bp) [draw,circle,state,initial] {$0$};
  \draw [->] (q1) ..controls (75.212bp,3.6347bp) and (64.284bp,-1.3057bp)  .. (54bp,1.3057bp) .. controls (50.042bp,2.3107bp) and (46.047bp,3.8633bp)  .. node[auto] {$b$} (q0);
  \draw [->] (q0) ..controls (46.106bp,20.306bp) and (58.578bp,20.306bp)  .. node[auto] {$b$} (q1);
  \draw [->] (q1) ..controls (89.406bp,46.931bp) and (91.75bp,56.306bp)  .. (98bp,56.306bp) .. controls (102bp,56.306bp) and (104.4bp,52.458bp)  .. node[auto] {$a$} (q1);
  \draw [->] (q0) ..controls (9.4062bp,46.931bp) and (11.75bp,56.306bp)  .. (18bp,56.306bp) .. controls (22.004bp,56.306bp) and (24.405bp,52.458bp)  .. node[auto] {$a$} (q0);
%
\end{tikzpicture}

%%% end example1 %%%
\end{center}

\thingy Il faut comprendre le fonctionnement d'un DFA de la manière
suivante : initialement, l'automate est dans l'état initial $q_0$.  On
va lui présenter un mot $w \in \Sigma^*$, lettre par lettre, de la
gauche vers la droite : i.e., si $w = x_1\cdots x_n$ on va faire
consommer à l'automate les lettres $x_1,x_2,\ldots,x_n$ dans cet
ordre.  Le fait de consommer une lettre $x$ fait passer l'automate de
l'état $q$ à l'état $\delta(q,x)$ (autrement dit, l'automate passe
successivement dans les états $q_0$ puis $q_1 := \delta(q_0,x_1)$ puis
$q_2 := \delta(q_1,x_2)$, et ainsi de suite jusqu'à $q_n :=
\delta(q_{n-1},x_n)$).  Si $q_n$ est l'état dans lequel se trouve
l'automate une fois qu'il a consommé le mot $w$, on dira que
l'automate \emph{acepte} ou \emph{rejette} le mot selon que $q_n \in
F$ ou que $q_n \not\in F$.

Graphiquement, on peut présenter la procédure de la manière suivante :
on part de l'état $q_0$ (sommet du graphe représentant l'automate)
indiqué par la flèche entrante (pointant de nulle part), et pour
chaque lettre du mot $w = x_1\cdots x_n$ considéré, on suit l'arête
portant ce symbole (et partant de l'état où on se trouve
actuellement).  Si à la fin l'état $q_n$ est acceptant (représenté par
une flèche pointant vers nulle part), le mot $w$ est accepté, sinon il
est rejeté.

\thingy Formellement : si $A = (Q,q_0,F,\delta)$ est un DFA sur
l'alphabet $\Sigma$, on définit une fonction $\delta^* \colon
Q\times\Sigma^* \to Q$ par $\delta^*(q,x_1\cdots x_n) =
\delta(\cdots\delta(\delta(q,x_1),x_2)\cdots,x_n)$ ou, ce qui revient
au même (par récurrence sur la longueur du second argument) :
\begin{itemize}
\item $\delta^*(q,\varepsilon) = q$ quel que soit $q\in Q$ (où
  $\varepsilon$ désigne le mot vide),
\item $\delta^*(q,wx) = \delta(\delta^*(q,w),x)$ quels que soient
  $q\in Q$, $w\in\Sigma^*$ et $x\in\Sigma$,
\end{itemize}
(en particulier, $\delta^*(q,x) = \delta(q,x)$ si $x\in\Sigma$, donc
avec la convention faite en \ref{convention-on-words-of-length-one},
on peut dire que $\delta^*$ prolonge $\delta$).

Cette fonction $\delta^*$ étant définie, on dira que l'automate $A$
\textbf{accepte} ou \textbf{reconnaît} un mot $w$ lorsque
$\delta^*(q_0,w) =: q_n \in F$ ; dans le cas contraire, on dira qu'il
\textbf{rejette} le mot $w$.

L'ensemble $L_A$ des mots acceptés par l'automate $A$ s'appelle
\textbf{langage accepté}, ou \textbf{reconnu}, ou \textbf{défini}, par
l'automate $A$.

\textbf Un langage $L \subseteq \Sigma^*$ qui peut s'écrire sous la
forme du langage $L_A$ accepté par un DFA $A$ s'appelle
\textbf{reconnaissable} (sous-entendu : par automate déterministe
fini).

On dit que deux DFA $A,A'$ sont \textbf{équivalents} lorsqu'ils
reconnaissent le même langage, i.e., $L_A = L_{A'}$.

\thingy\label{discussion-example2} L'automate fini ci-dessous sur
$\Sigma := \{a,b,c\}$ a trois états, $Q = \{0,1,2\}$.  On peut en
faire la description informelle suivante : l'automate commence dans
l'état $0$, où il reste jusqu'à rencontrer un $a$ qui le fait passer
dans l'état $1$, où il reste ensuite jusqu'à rencontrer un $b$ qui le
fait passer dans l'état $2$, où il reste définitivement et qui
constitue un état acceptant.

\begin{center}
%%% begin example2 %%%

\begin{tikzpicture}[>=latex,line join=bevel,automaton]
%%
\node (q1) at (98bp,18bp) [draw,circle,state] {$1$};
  \node (q0) at (18bp,18bp) [draw,circle,state,initial] {$0$};
  \node (q2) at (178bp,18bp) [draw,circle,state,final] {$2$};
  \draw [->] (q0) ..controls (46.106bp,18bp) and (58.578bp,18bp)  .. node[auto] {$a$} (q1);
  \draw [->] (q1) ..controls (89.406bp,44.625bp) and (91.75bp,54bp)  .. (98bp,54bp) .. controls (102bp,54bp) and (104.4bp,50.152bp)  .. node[auto] {$a,c$} (q1);
  \draw [->] (q1) ..controls (126.11bp,18bp) and (138.58bp,18bp)  .. node[auto] {$b$} (q2);
  \draw [->] (q0) ..controls (9.4062bp,44.625bp) and (11.75bp,54bp)  .. (18bp,54bp) .. controls (22.004bp,54bp) and (24.405bp,50.152bp)  .. node[auto] {$b,c$} (q0);
  \draw [->] (q2) ..controls (169.41bp,44.625bp) and (171.75bp,54bp)  .. (178bp,54bp) .. controls (182bp,54bp) and (184.4bp,50.152bp)  .. node[auto] {$a,b,c$} (q2);
%
\end{tikzpicture}

%%% end example2 %%%
\end{center}

Cette description rend claire le fait que l'automate en question
accepte exactement les mots contenant un $a$ suivi, pas forcément
immédiatement, d'un $b$ ; autrement dit, les mots dont $ab$ est un
sous-mot (cf. \ref{definition-subword}).  Ce langage est donc
reconnaissable.

\thingy Un état $q$ d'un DFA $A$ est dit \textbf{accessible} lorsqu'il
existe un mot $w \in \Sigma^*$ tel que $q = \delta(q_0,w)$, autrement
dit, graphiquement, lorsqu'il existe un chemin orienté
$q_0,q_1,\ldots,q_n=q$ reliant l'état initial $q_0$ à l'état $q$
considéré.  Dans le cas contraire, il est dit \textbf{inaccessible}.
Il est évident qu'ajouter ou retirer (ou modifier) les états
inaccessibles dans un DFA ne change rien au langage reconnu au sens
où on obtient des langages équivalents.

Par exemple, dans le DFA qui suit, l'état $2$ est inaccessible
(l'automate est donc équivalent à celui représenté
en \ref{discussion-example1}).  On remarquera qu'il ne change rien que
cet état soit final ou non.

\begin{center}
%%% begin example1b %%%

\begin{tikzpicture}[>=latex,line join=bevel,automaton]
%%
\node (q1) at (98bp,20.306bp) [draw,circle,state,final] {$1$};
  \node (q0) at (18bp,20.306bp) [draw,circle,state,initial] {$0$};
  \node (q2) at (172bp,20.306bp) [draw,circle,state,final] {$2$};
  \draw [->] (q1) ..controls (75.212bp,3.6347bp) and (64.284bp,-1.3057bp)  .. (54bp,1.3057bp) .. controls (50.042bp,2.3107bp) and (46.047bp,3.8633bp)  .. node[auto] {$b$} (q0);
  \draw [->] (q0) ..controls (46.106bp,20.306bp) and (58.578bp,20.306bp)  .. node[auto] {$b$} (q1);
  \draw [->] (q1) ..controls (90.319bp,47.164bp) and (92.445bp,56.306bp)  .. (98bp,56.306bp) .. controls (101.47bp,56.306bp) and (103.6bp,52.735bp)  .. node[auto] {$a$} (q1);
  \draw [->] (q0) ..controls (9.4062bp,46.931bp) and (11.75bp,56.306bp)  .. (18bp,56.306bp) .. controls (22.004bp,56.306bp) and (24.405bp,52.458bp)  .. node[auto] {$a$} (q0);
%
\end{tikzpicture}

%%% end example1b %%%
\end{center}

\thingy On va maintenant introduire différentes variations sur le
thème des automates finis, c'est-à-dire différentes généralisations de
la définition faite en \ref{definition-dfa} correspondant à des types
d'automates finis plus puissants que les DFA mais dont on va montrer,
à chaque fois, qu'ils peuvent se ramener à des DFA au sens où pour
chacun de ces automates généralisés on pourra construire
algorithmiquement un DFA qui reconnaît le même langage (si bien que la
classe des langages reconnaissables par n'importe laquelle de ces
sortes d'automates sera toujours la même).  Les plus simples sont les
automates déterministes finis incomplets et on va donc commencer par
eux.


%
%
%
\end{document}