Teoría de Autómatas

Teoría de Autómatas

1.1 -Autómatas finitos y lenguajes regulares:

Nombres de variables válidos: Todos aquellos que comienzan con una letra, no llevan espacios y están formados por una combinación de letras y números finita y arbitraria. Las marcas de fin de cadena son los espacios, puntos, comas o retornos de carro.

Diagramas de transiciones: Es una colección finita de círculos rotulados, con flechas (arcos) que representan la cadena de entrada que se analiza. Un círculo doble es la 'salida', o sea, que la cadena es aceptada.

Tablas de transiciones: en una matriz bidimensional cuyos elementos dan el diagrama de transiciones correspondiente. Si no hay arco entre dos estados, la casilla se marca como error. El fin de cadena se designa por FDC... Ej:

Letra Dígito FDC
1 3 2 Error
2 Error Error Error
3 3 3 Aceptar


1.2.- Autómatas finitos deterministas (AFD):

Las cadenas están formadas por símbolos. Existe un conjunto de símbolos a partir del cual se construyen las cadenas que se analizarán. Este conjunto se llama 'alfabeto'.

Flujo de entrada: cadena o secuencia de símbolos que se analizan a la entrada del proceso de reconocimiento.

Autómata finito determinista (AFD): Dispositivo que puede estar en un número variable de estados, en los que uno es el estado inicial y al menos uno un estado de aceptación. Tiene la capacidad de analizar los símbolos según llegan y determinar su siguiente estado dependiendo del símbolo a analizar y el estado actual. Esta determinación se toma por un mecanismo de control de la máquina programado previamente para hallar el estado correspondiente a la situación actual. Se dice que un AFD acepta una cadena de entrada si después de analizarla completamente la máquina se queda en un estado de aceptación, si no es así, la cadena ha sido rechazada. Si la máquina llega al final de la entrada antes de leer la cadena (esto es, la cadena comienza con un carácter de fin de cadena) decimos que la cadena está vacía(, y esta es válida sólo si su estado inicial es un estado de aceptación.
Definición formal: Un autómata finito determinista consiste en una quíntupla (S,,,i,F) dónde:
S es un conjunto finito de estados,
es el alfabeto de la máquina,
es una función (función de transición) de S x  a S,
i (un subconjunto de S) es el estado inicial,
F (un subconjunto de S) es el conjunto de estados de aceptación.

Diagramas de transiciones deterministas: Los requisitos que debe cumplir un diagrama de transiciones para cumplir el determinismo, son que de cada uno de los estados sólo puede salir un arco para cada símbolo del alfabeto, no puede tener un mismo símbolo dos caminos posibles. Además ha de estar completamente definido, es decir,debe haber un arco para cada símbolo del alfabeto, de lo contrario, la máquina podría quedarse parada.

1.3.- Límites de los autómatas finitos deterministas:

Un autómata finito determinista se puede considerar como un agrupador de las cadenas que son aceptables y las que no lo son.

Denominamos * a todas las cadenas que es posible formar con los caracteres del alfabeto de la máquina y de longitud finita. ( Si  es {a,b} * sería {,a,b,ab,ba,aab,aaab,aa,...}). De esta manera, se define un lenguaje (del alfabeto como un subconjunto de *.

Si M es un AFD (S,,,i,F), la colección de todas las cadenas que acepta constituye un lenguaje con respecto al alfabeto , y se representa por L(M). Un lenguaje de forma L(M) para un autómata finito M se denomina lenguaje regular. Un par de lenguajes regulares especiales, son la colección de todas las cadenas de longitud finita de un lenguaje que se representó por  y el lenguaje vacío ().

Teorema 1.1.- Para cualquier alfabeto  existe un lenguaje regular que
no es igual a L(M) para cualquier autómata finito determinista M.

Este teorema nos dice que existen conjuntos de cadenas que no pueden ser identificados por los autómatas finitos deterministas, y por lo tanto nuestras técnicas de análisis léxico no pueden reconocerlos.

Lenguaje no regular: Un ejemplo de un lenguaje que no cumple las 'normas' para ser regular. Es, por ejemplo, las expresiones matemáticas con paréntesis, ya que nuestro autómata es incapaz de saber si ha cerrado todos los paréntesis que se han abierto, lo que daría una fórmula erronea.



1.4.- Autómatas finitos no deterministas (AFND).

Un autómata finito no determinista, surge como ampliación al concepto de autómata finito determinista, al encontrarnos con tipos de lenguajes que no pueden ser aceptados por éste. Son similares a los anteriores, ya que parten de un alfabeto finito y un numero de estados, de los que solo uno es de aceptación, pero la diferencia está en que la transición que se ejecuta en una etapa dada puede ser incierta. Esto viene porque puede ser que sea posible aplicar más de una transición, o que ninguna de las disponibles sea adecuada al caso particular.
En el análisis de un AFND, una cadena se acepta cuando es posible analizarla (cuando es posible que su análisis deje al autómata en un estado de aceptación). No tiene que cumplir la condición de que deje a la máquina en un estado de aceptación, ya que puede que se encuentre sin salida o con varias opciones posibles.
Al igual que en los deterministas, el conjunto de todas las cadenas aceptadas por un AFND M es un lenguaje representado por L(M). La definición formal de un AFND es la siguiente:
Definición formal: Un autómata finito no determinista consiste en una quíntupla (S,,,i,F) dónde:
S es un conjunto finito de estados,
es el alfabeto de la máquina,
es un subconjunto de S x  x S,
i (un elemento de S) es el estado inicial,
F (un subconjunto de S) es el conjunto de estados de aceptación.
Aqui  representa las posibles transiciones de la máquina.

Teorema 1.3.- Para cada autómata finito no determinista, existe un
autómata finito determinista que acepta exáctamente el mismo lenguaje.

Lo que de aqui se desprende es que partiendo de unAFND se puede construir siempre uno equivalente que cumpla el determinismo, evitando ramificaciones y retrocesos, pero lo que no se puede es mejorar las técnicas basadas en AFD.

Teorema 1.4.- Para cualquier alfabeto , {L(M) es un AFD con
alfabeto L(M) es un AFND con alfabeto 

Por este teorema, lo que se deduce es que no hay diferencia entre un AFD y un AFND en cuanto a aceptación de lenguajes, por lo que es común referirse a ellos simplemente como autómatas finitos.

1.5.- Gramáticas regulares:

Una gramática se compone de terminales, no terminales, símbolos de inicio y reglas de reescritura. A una gramática con estas características se le denomina gramática estructurada por frases.
De manera más formal, es una cuádrupla (V,T,S,R) en la que:
 V- Conjunto finito de no terminales.
 T - Conjunto finito de terminales.
 S - (un elemento de N) es el símbolo inicial.
 R - es un conjunto finito de reglas de reescritura.

En general, los lados derecho e izquierdo de las reglas de reescritura pueden ser cualquier combinación de terminales y no terminales siempre que el lado izquierdo contenga por lo menos un no terminal. Además el lado derecho puede ser una cadena vacía. En este caso se denomina a la regla 'regla ' . Nosotros denotaremos terminales con letras minúsculas y no terminales con mayúsculas.

De esta manera se dice que una gramática genera una cadena de terminales si al comenzar con el símbolo de inicio, se puede producir esa cadena sustituyendo sucesivamente los patrones que se encuentran en el lado izquierdo de las reglas de reescritura con su correspondiente en el lado derecho hasta que sólo queden terminales.

Así, se define una gramática regular como aquella cuyas reglas cumplen que el lado izquierdo de cualquier regla debe consistir de un sólo no terminal, mientras que el derecho debe ser un terminal seguido por un no terminal, un sólo terminal o la cadena vacía.

Teorema 1.5.- Para cada alfabeto {L(G):G es una gramática regular
de L:M es un autómata finito de 

1.6.- Expresiones regulares:

La base para la construcción de los elementos más simples de una gramática, ha de incluir a {y a {.La operación básica para la construcción de lenguajes es la unión de subconjuntos. De hecho, la unión de dos lenguajes regulares cualesquiera también es regular.

Otra operación para combinar lenguajes es la concatenación de cadenas (no conmutativa, por cierto). La concatenación de dos lenguajes regulares también es regular.

La última operación a considerar es la estrella de Kleene (*), en la que sólo se amplia un lenguaje en vez de dos. Consiste en formar concatenaciones de cero o más cadenas del lenguaje que se está ampliando. Aqui conseguimos insertar  como elemento del lenguaje, ya que (={.Para modificar un diagrama de transiciones para que este acepte la estrella de Kleene, lo que hay que hacer es añadir un nuevo estado inicial y unir este a cada uno de los estados a los que estaba conectado el estado inicial anterior. De aqui se deduce que la estrella de Kleene de cualquier lenguaje regular es regular.
Una expresión regular (para un alfabeto ) se define:
es una expresión regular
Cada miembro de es una expresión regular
Si p y q son expresiones regulares, tambien lo es p U q.
Si p y q son expresiones regulares, también lo es p o q.
Si p es una expresión regular, entonces también lo es p*.

Teorema 1.6.- Dado un alfabeto  los lenguajes regulares de son
exáctamente los lenguajes representados por las expresiones regulares de 

Del teorema y la definición se deduce otra forma de caracterizar los lenguajes regulares, son los lenguajes aceptados por autómatas finitos deterministas, no deterministas, lenguajes generados por gramáticas regulares y lenguajes aceptados por expresiones regulares. La ventaja de las expresiones regulares, es que basta con una sóla expresión para describir un lenguaje, frente a tablas de transiciones o reglas de reescritura.

Tesis y Monografías