Chapitre 1 TL : Introduction Flashcards
(Définition) Un vocabulaire
Un vocabulaire V est un ensemble fini de symboles (lettres).
Exemple : V = {0, 1} ou bien V = {a, b, …, z}.
a ∈ A
. La notation a ∈ A signifie que l’élément a appartient à l’ensemble A
B ⊆ A
la notation B ⊆ A signifie que B est un sous-ensemble de A.
∅
L’ensemble vide est noté ∅
A = B
La notation A = B signifie que quelques soit a, a appartient a A si et
seulement si a appartient a B, not ́e ∀a.(a ∈ A ⇔ a ∈ B).
dans la notation A = {a I P (a)} que veux dire P(a)
On dit alors que A est un ensemble de tous les éléments a pour lesquels P (a) est vrai.
union
A∪B
intersection
A∩B
différence
A\B
définir le produit cartésien des ensembles A et B
Le produit cartésien des ensembles A et B est défini comme suit.
A × B = {(a, b) I a ∈ A ∧ b ∈ B}
où (a, b) est un couple ordonné des éléments a et b.
cardinalité de l’ensemble A
|A|
L’ensemble de tous les sous-ensembles de
l’ensemble A.
2ᴱ
(définition) concaténation
La concaténation w1.w2 de deux mots w1 = a1.a2 . . . .an et w2 = b1.b2 . . . .bm
est définie par :
— Pour chaque i ∈ {1, 2}, ε.wi = wi
— Pour chaque i ∈ {1, 2}, wi.ε = wi
— w1.w2 = a1.a2 . . . .an.b1.b2 . . . .bm
(définition) Qu’est-ce qu’un langage
Un langage L sur un vocabulaire V est un sous-ensemble de V∗.
Les opérations sur les langages sont
- la concat ́enation L.L′ = {α.α′ | α ∈ L ∧ α′ ∈ L′} ;
- l’itération L∗ =⋃₍n≥0₎ Ln avec L0 = {ε} et Ln = L.Ln−1 ;
- l’union ∪, l’intersection ∩, le compl ́ementaire C de L dans V ∗ (op ́erations sur des
ensembles) ; - le miroir, etc
