Teoría sobre autómatas

Teoría sobre autómatas


Introducción a la teoría de Autómatas 1
José M. Godoy Giménez
1. AUTOMATAS FINITOS Y LENGUAJES REGULARES.
1.1 Análisis léxico.
Los diagramas de transiciones se pueden emplear como herramienta de diseño para producir rutinas de
análisis léxico. No obstante, el código generado directamente a partir de un diagrama de transiciones no siempre
representa la mejor solución al problema; se obtiene una solución más elegante si se emplean tablas de
transiciones. Una tabla de transición es un arreglo bidimensional cuyos elementos proporcionan el resumen de un
diagrama de transiciones correspondiente.
1.2 Autómatas finitos deterministas.
Un Autómata Finito Determinista consiste en un dispositivo que puede estar en cualquier estado entre un
número finito, uno de los cuales es el estado inicial y por lo menos uno es un estado de aceptación. A este
dispositivo está unido un flujo de entrada por medio del cual llegan en secuencia los símbolos de un alfabeto
determinado. La máquina tiene capacidad para detectar los símbolos conforme llegan y, basándose en el estado
actual y el símbolo recibido, ejecutar una transición consistente en cambiar a otro estado o la permanencia en el
mismo. El programa de un Autómata Finito Determinista no debe contener ambigüedades (para un estado un
determinado símbolo sólo puede producir una determinada acción).
Se dice que un Autómata Finito Determinista acepta su cadena de entrada si, después de comenzar sus
cálculos en el estado inicial la máquina cambia a un estado de aceptación después de leer el último símbolo de la
cadena. Si después de leer el último símbolo no queda en estado de aceptación, se dice que la cadena ha sido
rechazada. Si la entrada es una cadena vacía (l) será aceptada si y sólo si el estado inicial es también un estado de
aceptación. Un Autómata Finito Determinista consiste en una quíntupla ( S, S, d, i, F) donde:
a. S, es un conjunto finito de estados.
b. S, es el alfabeto de la máquina.
c. d, es una función (función de transición) de S× S a S.
d. i, (un elemento de S) es el estado inicial.
e. F (un subconjunto de S) es el conjunto de estados de aceptación.
La interpretación de la función de transición d de un autómata finito determinista es que d(p,x)=q sí y sólo
sí la máquina puede pasar de un estado p a un estado q al leer el símbolo x.
El diagrama de transición determinista sólo debe tener un arco que sale de un estado para cada símbolo
del alfabeto. Además, dicho diagrama está completamente definido, es decir, debe existir un arco para cada
símbolo del alfabeto.
1.3 Límites de los autómatas finitos deterministas.
LENGUAJES REGULARES
Se define S* como el conjunto de cadenas de longitud finita formadas por el alfabeto S. Un subconjunto
de S * se denomina lenguaje. Si M es un autómata finito determinista ( S, S, d, i, F), la colección de cadenas que
acepta constituye un lenguaje con respecto al alfabeto S. Este leguaje se representa como L(M), que es el lenguaje
que acepta el autómata M. Un lenguaje de la forma L(M) para un autómata finito M se denomina lenguaje regular.
TEOREMA 1.1.
Para cualquier alfabeto S, existe un lenguaje que no es igual a L(M) para cualquier
autómata finito determinista M.
Demostración.
Puesto que cualquier arco de un autómata finito determinista que esté rotulado con un símbolo que no
pertenece a S no tendrá efecto alguno sobre el procesamiento de una cadena en S*, podemos considerar sólo las
máquinas con alfabeto S. Sin embargo, la colección de autómatas finitos deterministas con alfabeto S es contable
ya que podemos elaborar de forma sistemática una lista de todas las máquinas posibles con un estado, seguidas por
todas las máquinas con dos estados, luego las de tres estados, etc. Por otra parte, el número de lenguajes con
respecto al alfabeto S es incontable, ya que el conjunto infinito S* tiene un número incontable de subconjuntos. Por
lo tanto hay más lenguajes que autómatas finitos deterministas, por lo que deben existir lenguajes que no son
aceptados por este tipo de máquinas.
Introducción a la teoría de Autómatas 2
José M. Godoy Giménez
LENGUAJES NO REGULARES
TEOREMA 1.2
Si un lenguaje regular contiene cadenas de la forma xnyn para enteros arbitrariamente
grandes, entonces debe contener cadenas de la forma xmyn, donde m y n no son iguales.
Demostración.
Suponiendo que M es un autómata finito determinista tal que L(M) contiene xnyn para un n
arbitrariamente grande. Entonces, debe existir un entero positivo k mayor que el número de estados en M y tal que
xkyk se encuentre en L(M). Puesto que existen más símbolos en xk que estados en M, el proceso de aceptación de
xkyk dará como resultado que se recorra más de una vez alguno de los estados de M antes de llegar a alguna de las y
de la cadena. Es decir, durante la lectura de algunas x se recorrerá una ruta circular del diagrama de transiciones
de la máquina. Si j es el número de x leídas al recorrer esta ruta, entonces la máquina [ Página siguiente >>> ]

1 2 3 4 5 6 7 8 9 10 11 12 13