Automatas

Introducción a la teoría de Autómatas

1

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áselegante 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 menosuno 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 unAutó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 noqueda en estado de aceptación, se dice que la cadena ha sido rechazada. Si la entrada es una cadena vacía (λ) 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, Σ, δ, ι, F) donde: a. S, es un conjunto finito de estados. b. Σ, es el alfabeto de la máquina. c. δ, es una función (función de transición) de S× Σa S. d. ι, (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 δ de un autómata finito determinista es que δ(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 paracada 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 Σ* como el conjunto de cadenas de longitud finita formadas por el alfabeto Σ. Un subconjunto de Σ se denomina lenguaje. Si M es un autómata finito determinista ( S, Σ, δ, ι,F), la colección de cadenas que acepta constituye un lenguaje con respecto al alfabeto Σ. 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 Σ no tendrá efecto alguno sobre el procesamiento de una cadena en Σ*, podemos considerar sólo las máquinas con alfabeto Σ. Sin embargo, la colección de autómatas finitos deterministas con alfabeto Σ es contable ya que podemos elaborar de forma sistemática una lista de todas lasmá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 Σ es incontable, ya que el conjunto infinito Σ* 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...