Définition

Soit un alphabet $Σ$ on exprime $Σ *$ l’ensemble des mots sur $Σ$ . Un langage formel $L$ est un ensemble de mots sur $Σ$ càd $L \subseteq Σ *$

IMPORTANT

$Σ *$ inclut $ϵ$

Définir un langage formel

Langages définis en extension. $L_{a} = {ϵ, a, aa, aaa}$ $L_{i} = {a, b, aaa, aba}$ Langages définis en intention. $L_{a}^{'} = {m o t s d o n t t o u t es l es l e tt res so n t d es a}$ $L_{i}^{'} = {u \in Σ * t e l q u e \exists n \in N, ∣ u ∣ = 2 n + 1}$

Opérations sur les langages

Opération	Signification
Union	Mots appartenant $L_{1}$ ou $L_{2}$
Intersection	Mots appartenant $L_{1}$ et $L_{2}$
Produit	${u = v . w t e l q u e v d an s L_{1} w d an s L_{2}}$
Complément	$Σ * ∖ L$ ou $Σ * - L$
Exponentiation	Soit $n \in N$ $L^{0} = {ϵ}$ $L^{1} = L$ $L^{2} = L . L$

Propriétés

le produit et l’union sont associatif
le produit est asymétrique: $L_{1} . L_{2} \neq = L_{2} . l_{1}$ , mais l’union l’est
$L .\emptyset = \emptyset$ et $L \cup \emptyset = L$