El diccionario de la lengua francesa puede verse como un conjunto finito de palabras formadas por letras (mayúsculas, minúsculas, acentuadas). Las instrucciones de un lenguaje de programación se especifican en el manual de uso y son finitas. En cambio, los nombres de variables o funciones que puede manejar un programa informático son potencialmente infinitos. Las secuencias genéticas son palabras —a menudo muy largas— formadas por caracteres del conjunto {A, C, G, T} de los cuatro nucleótidos. Todos estos ámbitos comparten la noción de lenguaje.
El alfabeto: los rudimentos
-----------------------
Para escribir palabras hace falta un alfabeto (un conjunto finito de caracteres). Una palabra es una sucesión finita de caracteres de un alfabeto dado. Por ejemplo, con el alfabeto {a, b, c}, es posible formar las palabras bbca, aaa, bcbcbc, acbc…
Un lenguaje (abstracto) L sobre el alfabeto A es simplemente un conjunto —finito o infinito— de palabras formadas por caracteres de A. Así, por ejemplo, se puede manejar el lenguaje infinito de todas las palabras sobre el alfabeto {a, b} que contienen un número impar de a: {a, aaa, aaaaa… ba, ab, abaa, baaa, babbaa…}. Esta definición abstracta recoge las características de las situaciones informáticas, biológicas y lingüísticas mencionadas más arriba, además de muchas otras.
Para manejar automáticamente un lenguaje L, es fundamental disponer de un mecanismo que reciba una palabra y «diga» si esta pertenece o no a L. ¡Los autómatas finitos deterministas (AFD) se crearon precisamente para eso! Un objeto M de este tipo viene dado por varios elementos. En primer lugar, un alfabeto A. Después, un conjunto finito de estados, Q = {q0, q1… *qk}. En este conjunto se distingue q*0, el estado inicial de M. Es la «puerta de entrada» de M. También se distingue el subconjunto F de Q de los estados aceptores de M. Una palabra w = x1 x2… *xn procesada por M se escribe inicialmente en la cinta de M (su memoria de entrada, de solo lectura). Cada carácter xi de w ocupa una celda de la cinta. Al comienzo, un cabezal de lectura del autómata apunta al primer carácter, x*1, de w.
