Alphabets, lettres, mots

Définition (alphabets, lettres, mots)

  • Un alphabet est un ensemble fini {\Sigma ,} dont les éléments sont appelés les lettres.
  • Un mot de {\Sigma} est une suite finie (éventuellement vide{)w=(w_{i})_{0\le i\lt n}\quad ,} notée {w=w_{0}w_{1}...w_{n-1}} de lettres de {\Sigma .}

Avec ces notations, on note {|w|=n} la longueur du mot {w.} Le mot vide est noté {\epsilon (}ainsi {|\epsilon |=0).}

  • On note {\Sigma} l’ensemble des mots de longueur {n.} Ainsi {\Sigma^{0}=\left\{\epsilon \right\}} et {\Sigma^{1}=\Sigma .} {n}
  • On note {\Sigma} l’ensemble de tous les mots sur {\Sigma .} En d’autres termes{,\Sigma}Formule du chapitre 14, page 1 {\Sigma .} {\star} {n}

On note {\Sigma^{+}=\Sigma \setminus \left\{\epsilon \right\}} l’ensemble des mots non vides sur {\Sigma .}

Quelques remarques très simples :

  • si {\Sigma =\varnothing ,} alors {\Sigma^{0}=\left\{\epsilon \right\}} et {\Sigma^{n}=\varnothing} pour {n\ge 1,} donc {\Sigma^{\star}=\left\{\epsilon \right\}.}
  • si card {\Sigma =\alpha \ge 1,} alors card {\Sigma^{n}=\alpha^{n}} pour tout {n\ge 0,} et l’ensemble {\Sigma} est infini dénombrable. {\star}
  • si par exemple {\Sigma =\left\{0,1\right\},} alors {\Sigma^{3}=\left\{000,001,010,011,100,101,110,111\right\}.}
  • si par exemple {\Sigma =\left\{a\right\},} alors {\Sigma^{\star}=\left\{\epsilon ,a,aa,aaa,aaaa,...\right\}.}
Pour voir la suite de ce contenu, vous devez : Pour poursuivre votre exploration, vous pouvez :