En informatique, un alphabet est un ensemble fini et non vide. Les éléments d'un alphabet sont appelés les lettres ou les symboles de l'alphabet.
Un exemple d'alphabet est { - , ⋅ } {\displaystyle \{-,\cdot \}}
qui peut être utilisé pour le code Morse ou {begin, if, else, for, while} qui peuvent être les mots clés d'un langage de programmation.
L'ensemble des nombres naturels n'est pas un alphabet car il n'est pas fini.
L'alphabet le plus utilisé en informatique est le {0,1}. On l'appelle l'alphabet binaire car il contient deux symboles. Un alphabet peut être utilisé pour former une chaîne de caractères (ou un mot). Il s'agit d'une séquence finie de lettres de l'alphabet. Par exemple, une chaîne de longueur 5 sur {0,1} est 01101.
La chaîne vide est celle qui ne contient pas de lettres (elle est souvent écrite comme λ {\displaystyle \lambda }
). La chaîne vide est une chaîne de caractères placée au-dessus de n'importe quel alphabet.
Si nous avons un alphabet appelé Σ {\displaystyle \Sigma }
. Ensuite, nous écrivons l'ensemble de toutes les chaînes qui peuvent être faites à partir de Σ {\displaystyle \Sigma } comme Σ ∗ {\displaystyle \Sigma ^{*}}
. C'est ce qu'on appelle l'étoile de Kleene (ou la fermeture de Kleene) de Σ {\displaystyle \Sigma } . Elle porte le nom du mathématicien Stephen Cole Kleene.
L'étoile de Kleene de l'alphabet binaire est { λ , 0 , 1 , 00 , 01 , 10 , 11 , 000 , 001 , ... } {\displaystyle \{\1}lambda ,0,1,00,01,10,11,000,001,...\}
. Les trois points après 001, montrent que nous ne pouvons pas écrire l'étoile de Kleene d'un alphabet en entier parce que c'est un ensemble infini.
Les alphabets sont importants car ils sont utilisés dans l'étude des langues formelles, des automates finis et des questions très difficiles en informatique sur ce qui peut être calculé et ce qui ne peut pas l'être.