automatas finitos

Sintaxis y Semántica del Lenguaje UTN FRSF – Apunte Nro. 2

AUTÓMATAS FINITOS

Autómatas Finitos
1

Autómatas Finitos (AF)
Por qué estudiar autómatas finitos

Hay varias razones por las que el estudio de los autómatas y de la complejidad es una parte
importante del núcleo de las ciencias de la computación. Los AF constituyen un modelo útil para
muchos tipos importantes de hardware ysoftware, como:
a) Software para el diseño y la verificación del comportamiento de circuitos digitales.
b) El “analizador léxico” de un compilador típico, esto es, la componente del compilador que
descompone el texto original en unidades lógicas tales como identificadores, palabras
reservadas y signos de puntuación.
c) Software para explorar grandes corpus de texto, como conjuntos de páginasweb, o para
descubrir las apariciones de ciertas palabras, frases u otros patrones.
d) Software para comprobar la corrección de cualquier tipo de sistemas que tengan un
número finito de estados diferentes, como los protocolos de comunicación o los protocolos
de intercambio seguro de información.
Hay muchos sistemas o componentes, como los enumerados anteriormente, de los que se puede
decir entodo momento que están en cierto “estado”, entre un número finito de ellos. El objetivo de
un estado es recordar la parte significativa de la historia del sistema. Dado que solo disponemos
de un número finito de estados, normalmente no es posible recordar la historia completa, por lo
que el sistema ha de ser diseñado cuidadosamente para que sea posible recordar los aspectos
importantes yolvidar los que no lo sean.
Definición informal
Un AF es una máquina “reconocedora”, ya que a partir de una cadena de entrada, solo dice “si” o
“no”. Lo cual indica si esa cadena pertenece o no al lenguaje reconocido o aceptado por la
máquina.
A partir de una gramática se puede construir una máquina reconocedora o aceptadora del
lenguaje generado por esa gramática, de tal forma que cuando recibaa su entrada una
determinada cadena de símbolos, el autómata indicará si dicha cadena pertenece o no al
lenguaje. Una máquina reconoce un lenguaje L si es capaz de reconocer todas las sentencias
pertenecientes a L y de no reconocer ninguna sentencia que no pertenezca a L. Los lenguajes
regulares pueden describirse por medio de un AF.
Un AF tiene un conjunto de estados y su control se muevede estado en estado, en respuesta a
entradas externas. Estas entradas forman las cadenas a ser analizadas. Los estados de un AF,
son de tres tipos: estado inicial, que permite empezar la ejecución del autómata; estados finales o
estados “de aceptación” que permiten realizar la salida de aceptación de la cadena de entrada
en el caso de que no haya más símbolos en la entrada, y estadosintermedios, que son los que
permiten pasar del estado inicial a algún estado final.
Los AF se dividen en diversas clases, dependiendo de si su control es “determinista” (lo que
significa que el autómata no puede estar en más de un estado simultáneamente) o “no
determinista” (lo que significa que el autómata puede estar en varios estados al mismo tiempo).

Año: 2009

pág. 1

Sintaxis y Semánticadel Lenguaje UTN FRSF – Apunte Nro. 2

AUTÓMATAS FINITOS

2

Autómatas Finitos Deterministas
Definición formal

El autómata finito determinista (AFD) siempre está en un solo estado después de leer cualquier
secuencia de entrada. El término “determinista” hace referencia al hecho de que, para cada
entrada, existe un único estado al que el autómata pueda llegar partiendo del estadoactual.
Un AFD se denota con la quíntupla:
A = (Σ, Q, f, q0, F)
donde:
•

Σ es el alfabeto (conjunto finito) de símbolos de entrada.

•

Q es el conjunto finito de estados.

•

q0 ∈ Q es el estado inicial.

•

f, es 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 estado.

•

F ⊆ Q, es el conjunto de...