Capitulo 1

La teoría de autómatas es el estudio de dispositivos de cálculo abstractos, es decir, de las “máquinas”. Antes de que existieran las computadoras, en la década de los años treinta, A. Turing estudió una máquina abstracta que tenía todas las capacidades de las computadoras de hoy día, al menos en lo que respecta a lo que podían calcular. El objetivo de Turing era describir de forma precisa los límites entre lo que una máquina de cálculo podía y no podía hacer; estas conclusiones no sólo se aplican a las máquinas abstractas de Turing, sino a todas las máquinas reales actuales.

En 1969, S. Cook amplió el estudio realizado por Turing sobre lo que se podía y no se podía calcular. Cook fue capaz de separar aquellos problemas que se podían resolver de forma eficiente mediante computadora de aquellos problemas que, en principio, pueden resolverse, pero que en la práctica consumen tanto tiempo que las computadoras resultan inútiles para todo excepto para casos muy simples del problema. Este último tipo de problemas se denominan “insolubles” o “NP-difíciles ”. Es extremadamente improbable que incluso la mejora de carácter exponencial en la velocidad de cálculo que el hardware de computadora ha experimentado (“Ley de Moore”) tenga un impacto significativo sobre nuestra capacidad para resolver casos complejos de problemas insolubles.

on varias las razones por las que el estudio de los autómatas y de la complejidad de cálculo constituyen una parte importante del núcleo de la Ciencias de la Computación. Esta sección presenta al lector estas razones, e introduce los temas más importantes que se cubren en este libro.

Introducción a los autómatas finitos

Los autómatas finitos constituyen un modelo útil para muchos tipos de hardware y software. A partir del Capítulo 2 veremos ejemplos de cómo se emplean estos conceptos. Por el momento, sólo enumeraremos algunos de los tipos más importantes:

1.Software para diseñar y probar el comportamiento de circuitos digitales.

2.El“analizadorléxico”deuncompiladortípico,esdecir,elcomponentedelcompiladorqueseparaeltexto de entrada en unidades lógicas, tal como identificadores, palabras clave y signos de puntuación.

3.Software para explorar cuerpos de texto largos, como colecciones de páginas web, o para determinar el número de apariciones de palabras, frases u otros patrones.

4.Software para verificar sistemas de todo tipo que tengan un número finito de estados diferentes, tales como protocolos de comunicaciones o protocolos para el intercambio seguro de información.

Aunque pronto veremos una definición precisa de los distintos tipos de autómatas, comenzaremos esta introducción informal con un boceto de lo que es y lo que hace un autómata finito. Existen muchos sistemas o componentes, como los que hemos enumerado anteriormente, que pueden encontrarse siempre en uno de una serie de “estados” finitos. El propósito de un estado es el de recordar la parte relevante del historial del sistema. Puesto que sólo existe un número finito de estados, generalmente, no es posible recordar el historial completo, por lo que el sistema debe diseñarse cuidadosamente, con el fin de recordar lo que es importante y olvidar lo que no lo es. La ventaja de disponer de sólo un número finito de estados es que podemos implementar el sistema mediante un conjunto fijo de recursos. Por ejemplo, podríamos implementarlo por hardware como un circuito, o como una forma simple de programa que puede tomar decisiones consultando sólo una cantidad limitada de datos o utilizando la posición del propio código para tomar la decisión.

Existen dos importantes notaciones que no son las utilizadas normalmente con los autómatas, pero que desem- peñan un importante papel en el estudio de los autómatas y sus aplicaciones.

5.Lasgramáticassonmodelosútileseneldiseñodesoftwarequesirveparaprocesardatosconunaestruc- tura recursiva. El ejemplo más conocido es el de un “analizador sintáctico” (parser), el componente de un compilador que se ocupa de las funciones anidadas recursivamente de los lenguajes de programación típicos, tales como expresiones aritméticas, condicionales, etc. Por ejemplo, una regla gramatical como E ⇒ E + E establece que una expresión puede formarse tomando cualesquiera dos expresiones y conec- tándolas mediante un signo más; esta regla es típica de cómo se forman las expresiones en los lenguajes reales de programación. En el Capítulo 5 se presentan las gramáticas independientes del contexto, nombre con el que se conoce este tipo de gramáticas.

6.Las expresiones regulares también especifican la estructura de los datos, especialmente de las cadenas de texto. Como veremos en el Capítulo 3, los patrones de cadenas de caracteres que pueden describir expresiones regulares son los mismos que pueden ser descritos por los autómatas finitos. El estilo de estas expresiones difiere significativamente del de las gramáticas. Veamos a continuación un ejemplo simple de esto. La expresión regular estilo UNIX ’[A-Z][a-z]*[ ][A-Z][A-Z]’ representa palabras que comienzan por una letra mayúscula seguida de un espacio y de dos letras mayúsculas.

Esta expresión representa patrones de texto que podrían corresponderse con el nombre de una ciudad y un estado, por ejemplo Ithaca NY. En cambio no reconocería nombres de ciudades formados por varias palabras, como por ejemplo Palo Alto CA, que sí podría ser reconocida por la expresión más compleja ’[A-Z][a-z]*([ ][A-Z][a-z]*)*[ ][A-Z][A-Z]’ Al interpretar dichas expresiones, sólo necesitamos saber que [A-Z] representa el rango de caracteres comprendido entre las letras mayúsculas “A” y “Z” (es decir, todas las letras mayúsculas) y que [ ] se utiliza para representar un único carácter en blanco. Además, el símbolo de asterisco (*) representa “cualquier número de” apariciones de la expresión anterior. Los paréntesis se emplean para agrupar componentes de la expresión; no representan caracteres del texto que se describe.

Capitulo 2

un autómata finito tiene un conjunto de estados y su “control” pasa de un estado a otro en respuesta a las “entradas” externas. Una de las diferencias fundamentales entre las clases de autómatas finitos es si dicho control es “determinista”, lo que quiere decir que el autómata no puede encontrarse en más de un estado a un mismo tiempo, o “no determinista”, lo que significa que sí puede estar en varios estados a la vez. Comprobaremos que añadir el no determinismo no nos permite definir ningún lenguaje que no pueda ser definido mediante un autómata finito determinista, aunque se obtiene una eficacia sustancial al describir una aplicación utilizando un autómata no determinista. En efecto, el no determinismo nos permite “programar” soluciones para los problemas utilizando un lenguaje de alto nivel. Entonces el autómata finito no determinista se “compila” mediante un algoritmo, en un autómata determinista que puede “ejecutarse” en una computadora convencional.

Notaciones más simples para los AFD

. Hay disponibles dos notaciones más cómodas para describir los autómatas:

Un diagrama de transiciones,

Una tabla de transiciones, que es una ordenación tabular de la función , la cual especifica el conjunto de estados y el alfabeto de entrada.

Diagramas de transiciones

Un diagrama de transiciones de un AFD A = (Q,,,q0,F) es un grafo definido como sigue:

a)  Para cada estado de Q, existe un nodo.

b)  Para cada estado q de Q y cada símbolo de entrada a de , sea (q, a) = p. Entonces, el diagrama de transiciones tiene un arco desde el nodo q hasta el nodo p, etiquetado como a. Si existen varios símbolos de entrada que dan lugar a transiciones desde q hasta p, entonces el diagrama de transiciones puede tener un único arco etiquetado con la lista de estos símbolos.

c)  Existe un flecha dirigida al estado inicial q0,etiquetada como Inicio. Esta flecha no tiene origenen nningún nodo.

d)  Lo nodos correspondientes a los estados de aceptación (los que pertenecen a F) están marcados con un doble círculo. Los estados que no pertenecen a F tienen un círculo simple.

Definición de autómata finito determinista

Un autómata finito determinista consta de:

Un conjunto finito de estados, a menudo designado como Q.

Un conjunto finito de símbolos de entrada, a menudo designado como .

Una función de transición que toma como argumentos un estado y un símbolo de entrada y devuelve un estado. La función de transición se designa habitualmente como . En nuestra representación gráfica informal del autómata, se ha representa mediante arcos entre los estados y las etiquetas sobre los arcos. Si q es un estado y a es un símbolo de entrada, entonces (q,a) es el estado p tal que existe un arco etiquetado a que va desde q hasta p.2

Un estado inicial, uno de los estados de Q.

Un conjunto de estados finales o de aceptación F. El conjunto F es un subconjunto de Q.

Definición de autómata finito no determinista

A continuación presentamos las nociones formales asociadas con los autómatas finitos no deterministas e indicamos las diferencias entre los AFD y AFN. Un AFN se representa esencialmente como un AFD:

A = (Q,,,q0,F)

donde:

Q es un conjunto finito de estados.

es un conjunto finito de símbolos de entrada.

q0, un elemento de Q, es el estado inicial.

F, un subconjunto de Q, es el conjunto de estados finales (o de aceptación).

, la función de transición, es una función que toma como argumentos un estado de Q y un símbolo de entrada de y devuelve un subconjunto de Q. Observe que la única diferencia entre un AFN y un AFD se encuentra en el tipo de valor que devuelve : un conjunto de estados en el caso de un AFN y un único estado en el caso de un AFD.