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}
{\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\}.}
- avoir une souscription active sur mathprepa
- et être connecté au site
- revenir à la page d'accueil
- ou tester la page d'extraits libres