En este capítulo estudiaremos un tipo de máquinas abstractas
de computación en donde la entrada consiste de una cadena de un
determinado alfabeto, y la salida o resultado de la computación
es la aceptación o no de la cadena de entrada. El conjunto de
cadenas aceptadas por la máquina es el lenguaje reconocido por
la máquina. De esta forma, asociamos lenguajes y máquinas, los
dos tópicos principales de esta materia.
2.1 Autómatas Finítos Determinísticos (AFD)
Un AFD es un quintuple M = (Q, ∑, δ, q0, F), donde Q es una máquina de estados finita, ∑ es el alfabeto, q0 es el estado inicial, F es el estado(s) final(es) y δ es una función de Q x ∑ a Q llamada la función de transición.
Ejemplo: El siguiente AFD acepta el conjunto de cadenas que contienen la subcadena bb y donde ∑={a,b}. Esto quiere decir que L(M) = (a|b)*bb(a|b)* .
M: Q = {q0, q1, q2 }
∑ = {a, b}
F = {q2}
La función de transición d es dada en forma tabular y llamada tabla de transición.
Para las cadenas abba y abab tenemos las siguientes
operaciones (computaciones) en la tabla:
[q0, abba] [q0, abab]
-[q0, bba] -[q0, bab]
-[q1, ba] -[q1, ab]
-[q2, a] -[q0, b]
-[q2, λ] -[q1, λ]
acepta rechazado
La cadena abba es aceptada ya que la computación se
para (halts) en estado q2.
Una cadena de entrada es aceptada si existe una computación que procesa toda la cadena de entrada y para en un estado final o aceptador.
Diagramas de Estado
El diagrama de estado de un AFD es un grafo dirigido-etiquetado
en el cual los nodos representan los estados de la máquina y los
arcos son obtenidos de la función de transición.
Otra definición es la siguiente:
2.2 Autómatas Finitos No determinísticos (AFN)
La diferencia es el no determinismo de esta clase de autómatas. Esto se manifiesta en la función de transición que en los AFD significa moverse de un estado a otro bajo un símbolo de entrada. En un AFN la función de transición también contempla lo anterior, pero además contempla otras dos transiciones: moverse de un estado a varios estados bajo una sola entrada o símbolo; y moverse de un estado a otro bajo no entrada o símbolo. Estas tres transiciones se dan como
La relación entre AFD y AFN se sumariza con la siguiente frase: “Cada AFD es AFN”. La función de transición de un AFD especifica exactamente que con una entrada solo se puede ir a un estado. Mientras en un AFN con una entrada se puede ir a cero, uno o mas estados. Esto quiere decir que la familia de AFDs es un subconjunto de los AFN.
Una cadena de entrada para un AFN puede generar distintas computaciones. En unos casos el automata para (halt) sin aceptar la cadena, en otros la rechaza o las acepta.
Ejemplo: El AFN M para la cadena ababb con tres diferentes computaciones.
M: Q = {q0, q1, q2 }
∑ = {a, b}
F = {q2}
La primera computación procesa toda la entrada y para en un estado de rechazar. La segunda computación, para (halt) después de ejecutar tres instrucciones ya que no existe acción cuando la máquina esta en estado q1 y leyendo una a. Por último, la tercera computación acepta la entrada.
Una cadena de entrada es aceptada si existe una computación que procesa toda la cadena de entrada y para en un estado final o aceptador. Una cadena de entrada está en el lenguaje de un AFN si existe una computación que lo acepte. El lenguaje de un AFN M, denotado L(M), es el conjunto de cadenas aceptadas por M.
El diagrama de estados para el AFN del ejemplo anterior es el siguiente:
El diagrama aceptado por este último AFN es (a | b)*bb
Es AFN porqué existen dos transiciones de q0 a q0 y de q0 a q1 ante una misma entrada: b
El siguiente diagrama de estados para un AFN acepta el lenguaje expresado por (ab)* | a*
Es AFN porqué existen dos transiciones de q0 a q1 y de q0 a q3 ante una misma entrada: a
Transiciones Lambda
Las transiciones de estado a estado en AFD y AFN se llevan a cabo al procesar o leer un símbolo de entrada. Podemos también redefinir a un AFN de tal manera que admita transiciones de estado a estado sin leer un símbolo de entrada.
Una transición de esta forma es llamada transición lambda.
A este tipo de máquinas se les llama AFN- λ.
Por medio de movimientos lambda se puede construir máquinas complejas a partir de máquinas mas simples.
La definición de halting (cuando parar) se extiende para incluir la posibilidad que una computación puede continuar usando transiciones lambda después de que toda la cadena de entrada ha sido leída. También se pide, al igual que en los anteriores autómatas, que termine en un estado final, esto para finalizar el AFN-λ con éxito.
Ejemplo: Sea M1 y M2 las siguientes máquinas que aceptan los lenguajes descritos por (a | b)*bb (a | b)*
y (b | ab)* (a | l).
Podemos construír máquinas compuestas combinando los doagramas de estado M1 y M2.
El lenguaje del AFN-λ M es L(M1) U L(M2)
Una computación en la máquina M comienza siguiendo un arco lambda a un estado inicial de M1 o M2.
Ejemplo: Un AFN-λ M que acepta L(M1) L(M2), la concatenación de dos lenguajes se construye juntando las dos máquinas con un arco lambda.
Una cadena de entrada es aceptada solo si consiste de una cadena de L(M1) seguido de una cadena de L(M2)
2.3 Equivalencia de AFN y AFD
Tres clases de autómatas finitos se han estudiado. En esta sección demostraremos que los tres tipos de autómatas aceptan el mismo tipo de lenguajes; mejor dicho, el lenguaje aceptado por un AFN- l es aceptado por un equivalente AFN y también por un equivalente AFD. Demostraremos como a un AFN- l y aun AFN le podemos quitar su no determinismo mediante la construcción de un AFD equivalente.
En la figura anterior las transiciones de el estado q1 ante entrada α son el conjunto {q2, q3, q5, q6}. Esto debido a que podemos alcanzar o llegar a esos estados desde el estado q1 y solo leyendo α. Al estado q4 llegamos leyendo solo λ.
La función de transición t de un NFA- λ es una función un poco diferente a la función de transición δ de un AFD o un AFN. En la función t, las transiciones ante λ son válidas para moverse de un estado a otro y juntándola con una entrada del alfabeto.
Ejemplo: Las tablas de transición siguientes ejemplifican las funciones de transición δ y t para el siguiente AFN- λ(diagrama de estado M). El lenguaje de M es a+c*b*.
La función de transición t es usada para construir un autómata finito deterministico equivalente. El procedimiento usa el diagrama de estados de el AFN- λ para construir el diagrama de estados de el equivalente AFD.
Ejemplo: Construir un AFD equivalente para el siguiente AFN- λ.
Su correspondiente diagrama de estados:
Se crean tres nuevos estados a los cuales se les aplica el mismo procedimiento para obtener hacia que estados se moverá. Este procedimiento termina hasta que no hay no se genere un nuevo estado.
A partir del diagrama de estados se puede construir el AFD equivalente.
El AFN M acepta el lenguaje a+ b+. Procedemos a convertirlo a un equivalente AFD.
2.4 Propiedades de los Lenguajes aceptados por un Autómata Finito.
Cada autómata finito con alfabeto ∑ acepta un lenguaje para ∑. Podemos probar que la familia de lenguajes aceptados por un autómata finito consiste precisamente de los conjuntos o lenguajes regulares para ∑.
Primero demostramos que cada conjunto o lenguaje regular es aceptado por algún AFN- λ. La demostración va de acuerdo a una definición recursiva. Los lenguajes o conjuntos regulares se construyen a partir de los elementos básicos 0 (conjunto o estado vacío), λ (cadena vacía) y conjuntos individuales que contienen elementos del alfabeto.
Los diagramas de estado para las máquinas que aceptan dichos conjuntos son:
Conjuntos regulares se construyen de los elementos básicos usando unión, concatenación y operación Kleene Star. Al igual que los conjuntos regulares, autómatas finitos mas complejos se pueden construir a partir de los diagramas anteriores y que acepten la unión, concatenación y operación Kleene Star de lenguajes regulares.
Ejemplo: El lenguaje L(M1) U L(M2) es aceptado por la máquina siguiente:
La concatenación de dos lenguajes L(M1) L(M2) regulares puede ser aceptado por la máquina siguiente:
Una máquina que acepta L(M1)* es la siguiente:
CONCLUSION
Usando los autómatas finitos anteriores podemos construir una máquina para cualquier expresión regular que describa a un lenguaje o conjunto regular. Por lo tanto, la conclusión es de que la familia de lenguajes aceptados por una máquina o autómata finito son del tipo regular.
2.5 Autómatas Finitos y Expresiones Regulares.
Los lenguajes regulares son definidos por medio de expresiones regulares y aceptados por medio de autómatas finitos. Podemos establecer que un lenguaje es regular si
- Es una expresión regular bajo un ∑.
- Es aceptado por un AFD, AFN o AFN- λ.
- Es generado por una gramática regular.
En cuanto a las expresiones regulares y autómatas, hemos ya comprobado en la sección anterior que podemos construir un autómata finito para cualquier expresión regular dada. Por otra parte existen métodos para producir una expresión regular a partir de un autómata finito.
2.6 Determinación de lenguajes regulares y no regulares.
Dado el lenguaje {aibi | i<=n} ¿podemos construir un AFD que acepte dicho lenguaje?
El siguiente AFD acepta dicho lenguaje pero está incompleto.
El AFD anterior está incompleto puesto que es imposible construir un AFD para un lenguaje que no es regular. De hecho dicho lenguaje es del tipo contexto libre, o es un lenguaje no regular.
Se puede demostrar que un lenguaje es regular al construir un autómata finito que lo acepte. Pero para demostrar que no es regular necesitamos usar otras técnicas.
