Le dictionnaire de la langue française peut être vu comme un ensemble fini de mots composés de lettres (majuscules, minuscules, accentuées). Les instructions d'un langage de programmation sont spécifiées dans le manuel d'utilisation et sont en nombre fini. Par contre, les noms de variables ou de fonctions qu'un programme informatique peut manipuler sont en nombre potentiellement infini. Les séquences génétiques sont des mots (souvent très longs) composés de caractères de l'ensemble {A, C, G, T} des quatre nucléotides. Un point commun à tous ces domaines est la notion de langage.
L'alphabet : le b.a.-ba
Pour écrire des mots, il faut un alphabet (un ensemble fini de caractères). Un mot est une suite finie de caractères d'un alphabet donné. Par exemple, avec l'alphabet {a, b, c}, il est possible de composer les mots bbca, aaa, bcbcbc, acbc…
Un langage (abstrait) L d'alphabet A est simplement un ensemble (fini ou infini) de mots composés de caractères de A. Il est ainsi possible de manipuler par exemple le langage (infini) de tous les mots sur l'alphabet {a, b} composés d'un nombre impair de a : {a, aaa, aaaaa… ba, ab, abaa, baaa, babbaa…}. Cette définition abstraite capture les caractéristiques des situations informatiques, biologiques, linguistiques évoquées plus ...
Lire la suite