5_AFDyAFND - Fernando Cesar Sandoval Padilla

Vista previa del material en texto

43 
 
AUTÓMATAS 
FINITOS 
 
 
44 
 
Introducción 
La teoría de autómatas se ocupa de clasificar y estudiar de modo sistemático diferentes 
tipos de máquinas abstractas que llevan a cabo un procesamiento secuencial de la 
información. 
Viendo desde el punto de vista de lenguajes, un autómata finito o máquina de estado 
finito es un modelo matemático de un sistema que recibe una cadena constituida por 
símbolos de un alfabeto y determina si esa cadena pertenece al lenguaje que el 
autómata reconoce. 
En la vida cotidiana, los autómatas finitos se utilizan para modelar el comportamiento, 
tanto de dispositivos mecánicos, como de sistemas naturales. Concretamente, permite 
estudiar procesos que dependen de una historia, es decir, sistemas cuyo comportamiento 
actual depende del pasado. 
Un ejemplo de la vida cotidiana es el control de una puerta automática. Las puertas 
automáticas que encontramos en las entradas y salidas de los supermercados se abren 
cuando el sensor detecta a una persona. 
Las puertas automáticas tiene sensores en la parte frontal de la puerta para detectar la 
presencia de una o varias personas que están a punto de atravesar la puerta. También 
cuenta con sensores en la parte trasera de la puerta para que el controlador pueda 
mantener la puerta abierta el suficiente tiempo para que la persona pase sin ser golpeada. 
 
Figura 1. Configuración de los sensores 
El controlador tiene dos estados, “OPEN” o “CLOSED” que representan los estados de la 
puerta. Como se muestra en la figura 2, existen 4 posibles entradas: “FRONT” (cuando la 
persona esta parada en la parte frontal de la puerta), “REAR” (cuando la persona esta 
parada en la parte trasera de la puerta), “BOTH” (hay personas paradas tanto al frente 
como atrás), y “NEITHER” (No hay alguien parado al frente ni atrás). El diagrama de 
 
 
45 
 
transición de un autómata finito puede estar representado como se muestra en la figura 
2. 
 
Figura 2. Diagrama de transición de una puerta automática 
Por otro lado, si enfocamos dicha definición en el contexto de los lenguajes, es posible ver 
a un autómata como un dispositivo que procesa cadenas de símbolos que recibe como 
entrada, cambiando de estado y produciendo una salida que, en algunos casos, puede 
estar formada por otra cadena de símbolos. 
Algunos de los modelos de autómatas finitos más conocidos son: Autómatas Finitos 
Determinas, Autómatas Finitos No-Deterministas, Autómatas Finitos de Pila y Máquinas 
de Turing. Durante esta unidad estaremos tratando sólo los dos primeros, Autómatas 
Finitos Deterministas y No-Deterministas. 
Una de las diferencias fundamentales entre las clases de autómatas finitos es si el cambio 
de estado es “Determinista”, lo que quiere decir que el autómata no puede encontrarse 
en más de un estado a un mismo tiempo, o “No-Determinista”, lo que significa que SÍ 
puede estar en varios estados a la vez. 
Comprobaremos que añadir el no determinismo NO nos permite definir ningún lenguaje 
que no pueda ser definido mediante un autómata finito determinista, aunque se obtiene 
una eficacia sustancial al describir una aplicación utilizando un autómata finito no 
determinista. En efecto, el no determinismo nos permite “programar” soluciones para los 
problemas utilizando un lenguaje de alto nivel. Entonces el autómata finito no 
determinista se puede cambiar en un autómata finito determinista mediante un 
algoritmo. 
 
 
 
46 
 
Definición de Autómatas Finitos Deterministas (AFD) 
Los Autómatas Finitos son máquinas teóricas que van cambiando de estado dependiendo 
de la entrada que reciban. La salida de estos Autómatas está limitada a dos valores: 
aceptado y no aceptado, que pueden indicar si la cadena que se ha recibido como entrada 
es o no válida. Generalmente utilizaremos los Autómatas Finitos para reconocer lenguajes 
regulares, es decir, una palabra se considerará válida sólo si pertenece a un determinado 
lenguaje. 
Formalmente un Autómata Finito Determinista se define como una tupla: 
(Σ, Q, f, 𝑞0, 𝐹) donde: 
Σ es el alfabeto de entrada 
𝑄 es el conjunto finito y no vacío de los estados de los Autómatas. 
𝑓 es la función de transición que indica en que situaciones el Autómata pasa de un estado 
a otro, se define 𝑓: 𝑄 × Σ → 𝑄 
𝑞0 ∈ 𝑄 es el estado inicial 
𝐹 ⊆ 𝑄 es el conjunto de estados finales de aceptación (𝐹 ≠⊘) 
Representación de autómatas 
Existen dos formas de representar un AFD, mediante tablas de transición o mediante 
diagramas de transición. Introduciremos estas dos representaciones con un ejemplo. 
Sea el autómata finito determinista definido por: ({𝑎, 𝑏}, {𝑝, 𝑞, 𝑟}, 𝑓, 𝑝, {𝑞}) donde 𝑓 se 
define de la siguiente forma: 
Tabla 1. Función f 
𝑓(𝑝, 𝑎) = 𝑞 𝑓(𝑝, 𝑏) = 𝑟 
𝑓(𝑞, 𝑎) = 𝑞 𝑓(𝑞, 𝑏) = 𝑟 
𝑓(𝑟, 𝑎) = 𝑟 𝑓(𝑟, 𝑏) = 𝑟 
 
La tabla de transición corresponde a la siguiente: 
 
Tabla 2. Tabla de transición 
 a b 
→ 𝑃 q r 
∗ 𝑞 q r 
𝑟 r r 
 
 
 
47 
 
La flecha indica que 𝑝 es el estado inicial, y el asterisco indica que 𝑞 es el estado final de 
aceptación (en general, pueden aparecer muchos asteriscos aunque sólo puede aparecer 
una flecha ya que sólo hay un estado inicial) 
El diagrama de transición es el siguiente: 
 
Figura 3. Automata Finito Determinista 
Los estado finales de aceptación se identifican por estar encerrados en un doble círculo. El 
estado inicial se destaca por una flecha apuntando hacia el nodo que parte desde ningún 
otro nodo del grafo. 
Al analizar el autómata del ejemplo es evidente que sólo considera como cadenas 
aceptadas aquellas que están formadas solamente por a’s. Cualquier cadena que con- 
tenga una b hará que el autómata acabe en el estado de no aceptación. 
A menudo nos encontramos con autómatas para los que no están definidas todas las 
transiciones. Las situaciones que no están definidas deben de estar consideradas como 
situaciones de error, es decir, si una cadena hace llegar a un autómata a una situación no 
definida, consideraremos que la cadena no ha sido reconocida por dicho autómata. 
Si deseamos completar un autómata, bastará con añadir un estado que reciba todas las 
transiciones que le falta a un autómata incompleto. 
 
 
48 
 
 
Figura 4. Izquierda: automata sin estado de error, Derecha: automata con estado de error 
 
Autómatas Finitos que reconocen lenguajes 
Ahora veamos ejemplos de un autómata para reconocer un lenguaje. Los autómatas que 
reconocen lenguajes pueden aceptar varias cadenas, pero sólo reconocerán un lenguaje 
(recordemos que los lenguajes están formados por varias cadenas). Si el autómata no 
acepta alguna cadena, aun así está reconociendo un lenguaje, el lenguaje vacío L∅. 
Es común en la literatura que trata sobre autómatas finitos, que éstos sean conocidos 
también como máquinas de estado finito. Para identificar una máquina de estados finitos 
de otra, es común etiquetarlas, por lo que en general, si A es el conjunto de todas las 
cadenas que la máquina M acepta, se dice que A es el lenguaje de la máquina M y se 
escribe L(M) = A . Otra forma de decirlo es que M reconoce a A. 
Ejemplo. Sea el lenguaje A definido por: 
𝐴 = {𝑤 | 𝑤 𝑡𝑒𝑟𝑚𝑖𝑛𝑎 𝑐𝑜𝑛 1} 
El autómata que reconoce dicho lenguaje está definido por M1 =
({0,1}, {q1, q2}, f, q1, {q2}) y su correspondiente diagrama de estado se muestra en la 
figura siguiente: 
 
Figura 5. Autómata M1 
 
 
49 
 
Y su tabla de transición sería: 
 0 1 
q1 q1 q2 
q2 q1 q2 
Ejercicio: Sea el lenguaje 
𝐴 = {𝑤 | 𝑤 𝑒𝑚𝑝𝑖𝑒𝑧𝑎 𝑦 𝑡𝑒𝑟𝑚𝑖𝑛𝑎 𝑐𝑜𝑛 𝑎 𝑜 𝑒𝑚𝑝𝑖𝑒𝑧𝑎 𝑦 𝑡𝑒𝑟𝑚𝑖𝑛𝑎 𝑐𝑜𝑛 𝑏} 
El diagrama de transición está dado por: 
 
Dar la descripción formal del autómata anterior: 
1. Q = ? 
2. Σ = ? 
3. 𝑓 
4. 𝑞0 
5. 𝐹 = ¿ 
Autómatas Finitos No-Deterministas (AFN) 
En los autómatas deterministas sabemos exactamente cuál es la transición que debemos 
llevar a cabo ante una determinada situación.Sin embargo, en los no-deterministas 
podemos encontrarnos con varias opciones e, incluso, con 𝜆 − 𝑡𝑟𝑎𝑛𝑠𝑖𝑐𝑖𝑜𝑛𝑒𝑠 o 𝜀 −
𝑡𝑟𝑎𝑛𝑠𝑖𝑐𝑖𝑜𝑛𝑒𝑠. 
El no determinismo es una generalización del determinismo, de tal forma que para cada 
autómata finito determinista existe, automáticamente, un autómata finito no-
determinista. 
 
 
 
50 
 
Las diferencias entre los autómatas finitos deterministas (AFD) de los autómatas finitos 
no-deterministas (AFN) son: 
1. Cada AFD siempre tiene UNA TRANSICIÓN para cada símbolo del alfabeto, y en el 
caso de los AFN puede tener MÁS DE UNA TRANSICIÓN por símbolo del alfabeto. 
2. En los AFD, las etiquetas de las transiciones son símbolos del alfabeto. En AFN los 
símbolos 𝜀 ó 𝜆 pueden estar como etiquetas en las flechas de transición indicando 
que es posible cambiar de estado aunque no se reciba nada en la entrada. A estos 
autómatas se les conoce como AFN-𝜆 
 
¿Cómo funciona un AFN? 
Suponga que estamos probando un AFN para una cadena de entrada dada y, en algún 
punto de la prueba, nos encontramos en un estado que tiene múltiples salidas para 
proceder. Una vez que se ha leído el símbolo de la cadena de entrada, el autómata se 
divide en varias copias de sí mismo y sigue todas las posibles opciones en paralelo. Cada 
una de las copias toma una opción de los posibles caminos y en caso de encontrarse de 
nuevo en un estado con varias salidas para el mismo símbolo, repite el procedimiento 
anterior. Si en alguna de las copias el AFN recibe una entrada de la cadena que no está 
considerada, esa copia termina su proceso. Si al final, cualquiera de las copias del AFN 
original termina en un estado de aceptación, el AFN acepta la cadena. 
La siguiente figura muestra un esquema de los AFD y AFN: 
 
 
 
 
51 
 
Ejemplo 1: Considere el siguiente autómata finito no-determinista N1 
 
Supongamos que queremos probar la cadena 010110, la siguiente figura nos muestra 
cuales serían los caminos a seguir. 
 
 
 
 
 
52 
 
 
Ejemplo 2: Sea A el lenguaje compuesto por todas las cadenas sobre {0,1} que contienen 
un 1 en la tercera posición desde el final de la cadena (e.j 000100 pertenece al lenguaje 
pero 011000 o 0011 no pertenecen). El siguiente AFN reconoce A. 
 
Conversión de gramáticas regulares a autómatas finitos 
Sea G=(ΣT, ΣN, S, P) una gramática regular. Un autómata finito que reconoce el mismo 
lenguaje que G es el autómata M=(Σ, Q, f, 𝑞0, 𝐹) dado por: 
1. El conjunto de estados del autómata M están definidos por: 
ΣN U Z si existe alguna regla A::=a (A ∈ ΣN, a ∈ ΣT) 
Q = 
 ΣN en caso contrario 
2. El alfabeto del autómata consiste de los símbolos terminales de la gramática, es decir 
Σ = ΣT 
3. Las transiciones del autómata están dadas por: 
 B cuando exista una regla A::=aB (A,B ∈ ΣN, a ∈ ΣT) 
f(A,a) = 
 Z cuando exista una regla A::=a (A ∈ ΣN, a ∈ ΣT) 
4. El estado inicial del autómata es el símbolo inicial de la gramática. 
5. El conjunto de estados finales del autómata M están dados por: 
{A si existe la regla A::=λ} U {Z si Z ∈ Q} 
F= 
{A si existe la regla A::=λ} en caso contrario 
 
En otras palabras, para convertir una gramática regular a un autómata finito: 
- Asociar los símbolos no terminales de la gramática con los estados del autómata 
- Cada regla A::=bC de la gramática nos define una transición f(A,b)=C; donde A y C 
son símbolos no terminales y b es terminal. 
- Las reglas A::=b, en caso de que existan, nos definen transiciones f(A,b)=Z, donde Z 
es un nuevo estado para el que no hay un símbolo no terminal asociado. 
 
 
 
53 
 
 
 
Ejemplo: 
Sea G={{a,b},{S,A},S,{S::=aS|aA, A::=bA|b}} la gramática que reconoce el lenguaje 
representado por a+b+, el autómata finito que reconoce el mismo lenguaje que G es el 
autómata K=(Σ, Q, f, 𝑞0, 𝐹). 
1. Los estados de K son los símbolos no terminales de la gramática más Z, dado que 
existe la regla A::=b, por lo tanto Q={S,A,Z} 
2. El alfabeto del autómata son los símbolos terminales de la gramática, por lo tanto 
Σ={a,b} 
3. Las transiciones de K serían: 
f(S,a)=S f(S,a)=A f(A,b)=A f(A,b)=Z 
4. El estado inicial del autómata es el símbolo inicial de la gramática, es decir 𝑞0=S 
5. El conjunto de estados está definido por F={Z} 
 
El diagrama de transición se muestra a continuación: 
 
Conversión de autómatas finitos a gramáticas regulares 
1. Los símbolos terminales de la gramática son los mismos que el alfabeto del 
autómata 
2. Asociar a los estados del autómata los símbolos no terminales de la gramática 
3. El símbolo inicial de la gramática corresponde al estado inicial del autómata 
4. La transición f(A,b)=C define la regla A::=bC 
5. En caso de que el estado C en la transición f(A,b)=C sea un estado final, entonces 
añadimos la regla A::=b, además de la regla A::=bC, ya incluida en el paso anterior. 
6. Llevar a cabo el proceso de limpieza y simplificación de gramáticas 
 
Ejemplo 1: 
Tomando el autómata de la sección anterior convertimos a gramática 
1. Los símbolos terminales de la gramática son ΣT ={a,b} 
 
 
54 
 
2. Los símbolos no terminales de la gramática son ΣN ={S,A,Z} 
3. El símbolo inicial es S 
4. Las reglas son S::=aS, S::=aA, A::bA, A::=bZ 
5. Añadimos la regla A::=b por la transición f(A,b)=Z, ya que el estado final es Z 
6. Eliminamos la regla A::=bZ ya que Z es un símbolo no generativo 
 
Ejemplo 2: 
Considere el siguiente autómata 
 
Convirtiendo a gramática regular quedaría: 
1. Los símbolos terminales de la gramática son ΣT ={a,b} 
2. Los símbolos no terminales de la gramática son ΣN ={q0, q1, q2, q3} 
3. El símbolo inicial es q0 
4. Las reglas son q0::=bq0, q0::=aq1, q1::=aq2, q1::=bq0, q2::=aq3, q2::=bq0, q3::=aq3, 
q3::=bq3 
5. Añadimos las reglas q0::=b, q2::=b, q1::=b y q1::=a, dado que q0 y q2 son estados 
finales 
6. La gramática ya está limpia y simplificada 
 
Conversión de Autómata Finito No Determinista a Autómata Finito Determinista 
Los AFN son equivalentes a los AFD, es decir, a partir un autómata finito no determinista 
se puede construir un autómata finito determinista equivalente (que acepte el mismo 
lenguaje). Cabe mencionar que el proceso que se describe a continuación permite 
convertir un AFN a AFD siempre y cuando el AFN no contenga transiciones lambda, es 
decir que no sea un AFN-𝜆. También existe un algoritmo para convertir un AFN-𝜆 a AFD 
pero no se encuentra dentro del alcance de este curso. 
 
 
55 
 
 
Considere el autómata no determinista N=({a,b,c},{q0,q1,q2},f,q0,{q0,q1,q2}) donde f está 
definido en el siguiente diagrama de transición: 
 
Para convertir N en un autómata finito determinista D: 
1. El estado inicial de A será el mismo que de N. En este caso, q0 
2. Se construye una tabla de transiciones para A determinando el conjunto de estados 
alcanzables para cada símbolo del alfabeto, partiendo del símbolo inicial. 
De esta forma, por ejemplo, desde el estado q0 con la entrada del símbolo “a” se 
alcanzan los estados {q0, q1, q2}, para el símbolo “b” se alcanzan los estados {q1,q2} y 
para “c” los estados {q2}. 
 a b c 
 q0 q0, q1, q2 q1,q2 q2 
 
3. Cada uno de los conjuntos de estados que aparecen se considera como un estado de A. 
 a b c 
 q0 q0, q1, q2 q1,q2 q2 
q0, q1, q2 
q1,q2 
q2 
 
4. Para cada uno de los nuevos estados de A: 
Se determina la unión del conjunto de estados alcanzables para un símbolo del alfabeto 
desde cada uno de los estados de N que pertenece al nuevo estado de A. 
Siguiendo el ejemplo, para el nuevo estado “q0,q1,q2” de A con el símbolo “a”: 
a) Los estados alcanzables desde el estado q0 de N para el símbolo “a” son {q0,q1,q2} 
b) Los estados alcanzables desde el estado q1 de N para el símbolo “a” son vacíos. 
c) Los estados alcanzables desde el estado q2 de N para el símbolo “a” son vacíos. 
 
 
56 
 
d) La unión de los tres conjuntos anteriores es {q0,q1,q2} 
 a b c 
 q0 q0, q1, q2 q1,q2 q2 
q0, q1, q2 q0, q1, q2 
q1,q2q2 
 
Para el estado “q0,q1,q2” de A con el símbolo “b”: 
a) Los estados alcanzables desde el estado q0 de N para el símbolo “b” son {q1,q2} 
b) Los estados alcanzables desde el estado q1 de N para el símbolo “b” son {q1,q2} 
c) Los estados alcanzables desde el estado q2 de N para el símbolo “b” son vacíos. 
d) La unión de los tres conjuntos anteriores es { q1,q2} 
 a b c 
 q0 q0, q1, q2 q1,q2 q2 
q0, q1, q2 q0, q1, q2 q1,q2 
q1,q2 
q2 
 
Para el estado “q0,q1,q2” de A con el símbolo “c”: 
a) Los estados alcanzables desde el estado q0 de N para el símbolo “c” son {q2} 
b) Los estados alcanzables desde el estado q1 de N para el símbolo “c” son {q2} 
c) Los estados alcanzables desde el estado q2 de N para el símbolo “c” son {q2} 
d) La unión de los tres conjuntos anteriores es { q2} 
 a b c 
 q0 q0, q1, q2 q1,q2 q2 
q0, q1, q2 q0, q1, q2 q1,q2 q2 
q1,q2 
q2 
 
Para el estado “q1,q2” de A con el símbolo “a”: 
a) Los estados alcanzables desde el estado q1 de N para el símbolo “a” son vacíos. 
b) Los estados alcanzables desde el estado q2 de N para el símbolo “a” son vacíos. 
c) La unión de los dos conjuntos anteriores es vacío. 
 a b c 
 q0 q0, q1, q2 q1,q2 q2 
q0, q1, q2 q0, q1, q2 q1,q2 q2 
q1,q2 - 
 
 
57 
 
q2 
 
Para el estado “q1,q2” de A con el símbolo “b”: 
a) Los estados alcanzables desde el estado q1 de N para el símbolo “b” son {q1,q2}. 
b) Los estados alcanzables desde el estado q2 de N para el símbolo “b” son vacíos. 
c) La unión de los dos conjuntos anteriores es {q1,q2}. 
 a b c 
 q0 q0, q1, q2 q1,q2 q2 
q0, q1, q2 q0, q1, q2 q1,q2 q2 
q1,q2 - q1,q2 
q2 
 
Para el estado “q1,q2” de A con el símbolo “c”: 
a) Los estados alcanzables desde el estado q1 de N para el símbolo “c” son {q2}. 
b) Los estados alcanzables desde el estado q2 de N para el símbolo “c” son {q2}. 
c) La unión de los dos conjuntos anteriores es {q2}. 
 a b c 
 q0 q0, q1, q2 q1,q2 q2 
q0, q1, q2 q0, q1, q2 q1,q2 q2 
q1,q2 - q1,q2 q2 
q2 
 
Para el estado “q2” de A con el símbolo “a”: 
a) Los estados alcanzables desde el estado q2 de N para el símbolo “a” son vacíos. 
b) La unión del conjunto anterior es vacío 
 a b c 
 q0 q0, q1, q2 q1,q2 q2 
q0, q1, q2 q0, q1, q2 q1,q2 q2 
q1,q2 - q1,q2 q2 
q2 - 
 
Para el estado “q2” de A con el símbolo “b”: 
c) Los estados alcanzables desde el estado q2 de N para el símbolo “b” son vacíos. 
d) La unión del conjunto anterior es vacío 
 a b c 
 q0 q0, q1, q2 q1,q2 q2 
q0, q1, q2 q0, q1, q2 q1,q2 q2 
 
 
58 
 
q1,q2 - q1,q2 q2 
q2 - - 
Para el estado “q2” de A con el símbolo “c”: 
e) Los estados alcanzables desde el estado q2 de N para el símbolo “c” son {q2}. 
f) La unión del conjunto anterior es {q2} 
 a b c 
 q0 q0, q1, q2 q1,q2 q2 
q0, q1, q2 q0, q1, q2 q1,q2 q2 
q1,q2 - q1,q2 q2 
q2 - - q2 
5. El proceso se repite mientras aparezcan nuevos estados 
6. Una vez terminada la tabla de transiciones se determinan los estados finales de A que 
serán aquellos en donde al menos uno de los nuevos estados de A es estado final en N. 
En este caso, los estados finales de N son q0,q1 y q2 por lo tanto todos los nuevos 
estados de A son finales, ya que al menos contienen un estado final de N. 
 a b c 
 *q0 q0, q1, q2 q1,q2 q2 
*q0, q1, q2 q0, q1, q2 q1,q2 q2 
*q1,q2 - q1,q2 q2 
*q2 - - q2 
A continuación se muestra el diagrama del autómata finito determinista resultante: