Définitions usuelles

dénombrable | monoïde | alphabet | langage

Définition: Un ensemble E est dénombrable s'il est bijection avec l'ensemble N des entiers naturels.

Propriétés:

Toute partie d'un ensemble dénombrable est finie ou dénombrable.

Tout produit cartésien fini d'ensembles dénombrables est dénombrable.

N*N est dénombrable

Proposition: Soit E un ensemble et soit P(E) l'ensemble desparties de E. On a

|E| < |P(E)|

Définition: Un ensemble E muni d'une opération * associative est un semi-groupe. Si de plus E possède un élément neutre e pour * on dit que (E,*,e) est un monoïde. Si la loi * est commutative (resp. le monoïde) est dit commutatif.

Définition: Soit A un ensemble fini appelé alphabet et dont les éléments sont appelés lettres. Le monoïde libre sur A noté A*, est l'ensemble des mots écrits sur l'alphabet A. Un mot u est simplement une suite finie de lettres.

Définition: Soit A* un monoïde libre engendré par l'alphabet A. Un langage est une partie de A*.