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 haut, et bien d'autres.
Afin de manipuler automatiquement un langage L, il est essentiel d'avoir un mécanisme qui prend en entrée un mot et qui « dit » si ce mot fait, ou non, partie de L. Les automates finis déterministes (AFD) ont justement été créés pour ça ! Un tel objet M est la donnée de plusieurs éléments. Tout d'abord, un alphabet A. Ensuite, un ensemble fini d' états, Q = {q0, q1… *qk}. Dans cet ensemble, on distingue q*0, l' état initial de M. C'est la « porte d'entrée » de M. On distingue aussi le sous-ensemble F de Q des états accepteurs de M. Un mot w = x1 x2… *xn traité par M est initialement écrit sur le ruban de M (c'est la mémoire d'entrée, en lecture seule). Chaque caractère xi de w occupe une case du ruban. Une tête de lecture de l'automate pointe, au départ, sur le premier caractère, x*1, de w.