automatas

Universidad Autónoma de Sinaloa

Facultad de Informática

Matemáticas VI

Unidad 2

AUTOMATAS FINITOS
LENGUAJES REGULARES
La teoría de la computación comienza con una pregunta: ¿Qué es una computadora? tal vez sea una pregunta tonta, ya que
cualquiera sabe que es una computadora. Sin embargo, definir una computadora es realmente complicado, demasiado complicado,
Pero a la vez lascomputadoras nos permiten la creación de una teoría matemática manejable. Pero para ello se utiliza una
idealización de la computadora llamado modelo computacional.
Al igual que con cualquier modelo en la ciencia, un modelo computacional puede ser preciso en algunos aspectos, pero quizá no en
otros. Por lo tanto vamos a utilizar diferentes modelos computacionales, en función de las característicasque queremos enfocar.
Iniciaremos con el modelo más simple, llamado máquina de estados finitos o autómata finito.

AUTÓMATA FINITO DETERMINISTA
En esta asignatura se estudiarán distintos tipos de máquinas abstractas con diferente poder computacional. Cada uno de estos
tipos de máquinas permiten reconocer lenguajes de distintos tipos y su poder computacional está asociado al tipo de lenguajesque
pueden reconocer. El primer tipo de máquinas abstractas que se va a definir son los Autómatas Finitos , que permiten reconocer
cadenas pertenecientes a Lenguajes Regulares . Los Autómatas finitos son buenos modelos para computadoras con poca
memoria. ¿Qué puede hacer un equipo con poca memoria? ¡Muchas cosas útiles! Un ejemplo de las cosas que podría hacerse seria
el controlador de unapuerta automática de las que se encuentran en los supermercados en entradas y salidas, puertas
automáticas de detección de oscilación que se abren al acercarse una persona. Aunque es de señalarse que son los autómatas los
de menor poder computacional y que para reconocer los lenguajes sólo disponen de una cinta de entrada (en la que se escribe una
cadena), de un cabezal lector (que lee símbolos deuno en uno y de izquierda a derecha) y tiene un conjunto finito de reglas que
especifican cómo actuar ante cada símbolo leído en la cinta de entrada. Gráficamente se puede representar por medio de la
siguiente figura:

Figura: Modelo físico de un Autómata Finito.
®Lic. Roy Jonny Sida López

Teoría de la Computación

1

Universidad Autónoma de Sinaloa

Facultad de InformáticaMatemáticas VI

Un autómata finito tiene varias partes. Tiene un conjunto de estados y reglas para pasar de un estado a otro, dependiendo del
símbolo de entrada. Tiene un alfabeto de entrada que indica los símbolos permitidos. Tiene un estado de inicio y un conjunto de
estados de aceptación. La definición formal dice que un autómata finito es una lista de cinco objetos: conjunto de estados, elalfabeto de entrada, las reglas de traslado, el estado de inicio y los estados de aceptación. En el lenguaje matemático una
lista de cinco elementos se le denomina 5 − tupla .
Se utiliza una función de transición , que se denota por δ , para definir las reglas de traslado. La función de transición indica a
qué estado se va a pasar sabiendo cuál es el estado actual y el símbolo que se estáleyendo. Es importante notar que δ es una
función y no simplemente una relación; esto implica que para un estado y un símbolo del alfabeto dados, habrá uno y sólo un estado
siguiente. Esta característica, que permite saber siempre cuál será el siguiente estado, se llama determinismo .
Ejemplo:

Si el autómata finito tiene una flecha de un estado x a un estado y etiquetados con el símbolo de entrada1,
significa que, si el autómata se encuentra en el estado x cuando se lee un 1, entonces pasa al estado y . Esto
se puede indicar mediante la función de transición escribiendo δ ( x,1) = y .

La definición siguiente corresponde a los autómatas finitos deterministas, abreviado “AFD”
Definición.

Un autómata finito es una 5 − tupla ( Q, ∑, δ , q0 , F ) , donde:
1.

Q es un conjunto...