Il dizionario della lingua francese può essere visto come un insieme finito di parole composte da lettere (maiuscole, minuscole, accentate). Le istruzioni di un linguaggio di programmazione sono specificate nel manuale d’uso e sono in numero finito. Al contrario, i nomi delle variabili o delle funzioni che un programma informatico può manipolare sono potenzialmente infiniti. Le sequenze genetiche sono parole (spesso molto lunghe) composte da caratteri dell’insieme {A, C, G, T} dei quattro nucleotidi. Un elemento comune a tutti questi ambiti è la nozione di linguaggio.
L’alfabeto: le basi -----------------------
Per scrivere parole occorre un alfabeto (un insieme finito di caratteri). Una parola è una successione finita di caratteri di un dato alfabeto. Per esempio, con l’alfabeto {a, b, c}, è possibile comporre le parole bbca, aaa, bcbcbc, acbc…
Un linguaggio (astratto) L sull’alfabeto A è semplicemente un insieme (finito o infinito) di parole composte da caratteri di A. Si può così manipolare, per esempio, il linguaggio (infinito) di tutte le parole sull’alfabeto {a, b} composte da un numero dispari di a: {a, aaa, aaaaa… ba, ab, abaa, baaa, babbaa…}. Questa definizione astratta coglie le caratteristiche delle situazioni informatiche, biologiche e linguistiche evocate più sopra, e di molte altre.
Per manipolare automaticamente un linguaggio L, è essenziale disporre di un meccanismo che riceva in ingresso una parola e «dica» se essa appartiene o no a L. Gli automi finiti deterministici (AFD) sono stati creati proprio a questo scopo! Un oggetto M di questo tipo è costituito da vari elementi. Anzitutto un alfabeto A. Poi un insieme finito di stati, Q = {q0, q1… *qk}. In questo insieme si distingue q*0, lo stato iniziale di M. È la «porta d’ingresso» di M. Si distingue inoltre il sottoinsieme F di Q degli stati accettanti di M. Una parola w = x1 x2… *xn elaborata da M viene inizialmente scritta sul nastro di M (la memoria di ingresso, in sola lettura). Ogni carattere xi di w occupa una casella del nastro. Una testina di lettura dell’automa punta inizialmente al primo carattere, x*1, di w.