Autómatas FinitosAutómata Finitos Informalmente
Autómatas Finitos Deterministas (AFD)Autómatas Finitos No Deterministas (AFND)
Autómatas Finitos con Transiciones
Introducción a la Teoría de Autómatas, Lenguajesy Computación
Gustavo Rodríguez Gómez y Aurelio López López
INAOE
Propedéutico 2020
1 / 103
Autómatas FinitosAutómata Finitos Informalmente
Autómatas Finitos Deterministas (AFD)Autómatas Finitos No Deterministas (AFND)
Autómatas Finitos con Transiciones
Capítulo 2
Autómatas Finitos
2 / 103
Autómatas FinitosAutómata Finitos Informalmente
Autómatas Finitos Deterministas (AFD)Autómatas Finitos No Deterministas (AFND)
Autómatas Finitos con Transiciones
Outline I
1 Autómatas FinitosIntroducción
2 Autómata Finitos InformalmenteEjemplo e-comercio 1/3Ejemplo e-comercio 2/3Ejemplo e-comercio 2/3
3 Autómatas Finitos Deterministas (AFD)Definición Formal de un AFDComo un AFD Procesa CadenasDiagramas y Tablas de Transición AFDEjemploExtensión de la Función de Transición a Cadenas AFDLenguaje de un AFD
3 / 103
Autómatas FinitosAutómata Finitos Informalmente
Autómatas Finitos Deterministas (AFD)Autómatas Finitos No Deterministas (AFND)
Autómatas Finitos con Transiciones
Outline II4 Autómatas Finitos No Deterministas (AFND)
Definición Formal de AFNDEspecificación Formal de un AFND EjemploFunción de Transición Extendida AFNDEl Lenguaje de un AFNDEquivalencia entre AFD y AFND
5 Autómatas Finitos con TransicionesUso de las Transiciones-εEpsilón CerradurasTransiciones Extendidas y Lenguajes para epsilón AFND
4 / 103
Autómatas FinitosAutómata Finitos Informalmente
Autómatas Finitos Deterministas (AFD)Autómatas Finitos No Deterministas (AFND)
Autómatas Finitos con Transiciones
Introducción
Introducción
Lenguajes regulares y su relación con los autómatas finitos(AF)
Notación estructural para describir los mismos patrones quepueden ser representados por un autómata finito.
Autómata finito
Tiene un conjuntos de estadosTiene un control que lo mueve de un estado a otro estado enrespuesta a entradas externas
Autómata finito determinista (AFD)
El autómata no puede estas en más de un estado al mismotiempo
Autómata finito no determinista (AFND)
El autómata puede estar en varios estado al mismo tiempo
AFD vs AFND
5 / 103
Autómatas FinitosAutómata Finitos Informalmente
Autómatas Finitos Deterministas (AFD)Autómatas Finitos No Deterministas (AFND)
Autómatas Finitos con Transiciones
Introducción
Introducción
Lenguajes regulares y su relación con los autómatas finitos(AF)
Notación estructural para describir los mismos patrones quepueden ser representados por un autómata finito.
Autómata finito
Tiene un conjuntos de estadosTiene un control que lo mueve de un estado a otro estado enrespuesta a entradas externas
Autómata finito determinista (AFD)
El autómata no puede estas en más de un estado al mismotiempo
Autómata finito no determinista (AFND)
El autómata puede estar en varios estado al mismo tiempo
AFD vs AFND
6 / 103
Autómatas FinitosAutómata Finitos Informalmente
Autómatas Finitos Deterministas (AFD)Autómatas Finitos No Deterministas (AFND)
Autómatas Finitos con Transiciones
Introducción
Introducción
Lenguajes regulares y su relación con los autómatas finitos(AF)
Notación estructural para describir los mismos patrones quepueden ser representados por un autómata finito.
Autómata finito
Tiene un conjuntos de estadosTiene un control que lo mueve de un estado a otro estado enrespuesta a entradas externas
Autómata finito determinista (AFD)
El autómata no puede estas en más de un estado al mismotiempo
Autómata finito no determinista (AFND)
El autómata puede estar en varios estado al mismo tiempo
AFD vs AFND
7 / 103
Autómatas FinitosAutómata Finitos Informalmente
Autómatas Finitos Deterministas (AFD)Autómatas Finitos No Deterministas (AFND)
Autómatas Finitos con Transiciones
Introducción
Introducción
Lenguajes regulares y su relación con los autómatas finitos(AF)
Notación estructural para describir los mismos patrones quepueden ser representados por un autómata finito.
Autómata finitoTiene un conjuntos de estados
Tiene un control que lo mueve de un estado a otro estado enrespuesta a entradas externas
Autómata finito determinista (AFD)
El autómata no puede estas en más de un estado al mismotiempo
Autómata finito no determinista (AFND)
El autómata puede estar en varios estado al mismo tiempo
AFD vs AFND
8 / 103
Autómatas FinitosAutómata Finitos Informalmente
Autómatas Finitos Deterministas (AFD)Autómatas Finitos No Deterministas (AFND)
Autómatas Finitos con Transiciones
Introducción
Introducción
Lenguajes regulares y su relación con los autómatas finitos(AF)
Notación estructural para describir los mismos patrones quepueden ser representados por un autómata finito.
Autómata finitoTiene un conjuntos de estadosTiene un control que lo mueve de un estado a otro estado enrespuesta a entradas externas
Autómata finito determinista (AFD)
El autómata no puede estas en más de un estado al mismotiempo
Autómata finito no determinista (AFND)
El autómata puede estar en varios estado al mismo tiempo
AFD vs AFND
9 / 103
Autómatas FinitosAutómata Finitos Informalmente
Autómatas Finitos Deterministas (AFD)Autómatas Finitos No Deterministas (AFND)
Autómatas Finitos con Transiciones
Introducción
Introducción
Lenguajes regulares y su relación con los autómatas finitos(AF)
Notación estructural para describir los mismos patrones quepueden ser representados por un autómata finito.
Autómata finitoTiene un conjuntos de estadosTiene un control que lo mueve de un estado a otro estado enrespuesta a entradas externas
Autómata finito determinista (AFD)
El autómata no puede estas en más de un estado al mismotiempo
Autómata finito no determinista (AFND)
El autómata puede estar en varios estado al mismo tiempo
AFD vs AFND
10 / 103
Autómatas FinitosAutómata Finitos Informalmente
Autómatas Finitos Deterministas (AFD)Autómatas Finitos No Deterministas (AFND)
Autómatas Finitos con Transiciones
Introducción
Introducción
Lenguajes regulares y su relación con los autómatas finitos(AF)
Notación estructural para describir los mismos patrones quepueden ser representados por un autómata finito.
Autómata finitoTiene un conjuntos de estadosTiene un control que lo mueve de un estado a otro estado enrespuesta a entradas externas
Autómata finito determinista (AFD)El autómata no puede estas en más de un estado al mismotiempo
Autómata finito no determinista (AFND)
El autómata puede estar en varios estado al mismo tiempo
AFD vs AFND
11 / 103
Autómatas FinitosAutómata Finitos Informalmente
Autómatas Finitos Deterministas (AFD)Autómatas Finitos No Deterministas (AFND)
Autómatas Finitos con Transiciones
Introducción
Introducción
Lenguajes regulares y su relación con los autómatas finitos(AF)
Notación estructural para describir los mismos patrones quepueden ser representados por un autómata finito.
Autómata finitoTiene un conjuntos de estadosTiene un control que lo mueve de un estado a otro estado enrespuesta a entradas externas
Autómata finito determinista (AFD)El autómata no puede estas en más de un estado al mismotiempo
Autómata finito no determinista (AFND)
El autómata puede estar en varios estado al mismo tiempo
AFD vs AFND
12 / 103
Autómatas FinitosAutómata Finitos Informalmente
Autómatas Finitos Deterministas (AFD)Autómatas Finitos No Deterministas (AFND)
Autómatas Finitos con Transiciones
Introducción
Introducción
Lenguajes regulares y su relación con los autómatas finitos(AF)
Notación estructural para describir los mismos patrones quepueden ser representados por un autómata finito.
Autómata finitoTiene un conjuntos de estadosTiene un control que lo mueve de un estado a otro estado enrespuesta a entradas externas
Autómata finito determinista (AFD)El autómata no puede estas en más de un estado al mismotiempo
Autómata finito no determinista (AFND)El autómata puede estar en varios estado al mismo tiempo
AFD vs AFND
13 / 103
Autómatas FinitosAutómata Finitos Informalmente
Autómatas Finitos Deterministas (AFD)Autómatas Finitos No Deterministas (AFND)
Autómatas Finitos con Transiciones
Introducción
Introducción
Lenguajes regulares y su relación con los autómatas finitos(AF)
Notación estructural para describir los mismos patrones quepueden ser representados por un autómata finito.
Autómata finitoTiene un conjuntos de estadosTiene un control que lo mueve de un estado a otro estado enrespuesta a entradas externas
Autómata finito determinista (AFD)El autómata no puede estas en más de un estado al mismotiempo
Autómata finito no determinista (AFND)El autómata puede estar en varios estado al mismo tiempo
AFD vs AFND14 / 103
Autómatas FinitosAutómata Finitos Informalmente
Autómatas Finitos Deterministas (AFD)Autómatas Finitos No Deterministas (AFND)
Autómatas Finitos con Transiciones
Ejemplo e-comercio 1/3Ejemplo e-comercio 2/3Ejemplo e-comercio 2/3
e-comercio
1 Hay tres participantes: el cliente, la tienda y el banco2 Eventos permitidos
1 El cliente puede decidir pagar2 El cliente puede decidir cancelar3 La tienda puede enviar las mercancías al cliente4 La tienda puede realizar el cobro del dinero5 El banco puede transferir el dinero a la tienda
15 / 103
Autómatas FinitosAutómata Finitos Informalmente
Autómatas Finitos Deterministas (AFD)Autómatas Finitos No Deterministas (AFND)
Autómatas Finitos con Transiciones
Ejemplo e-comercio 1/3Ejemplo e-comercio 2/3Ejemplo e-comercio 2/3
Protocolo e-comercio
Protocolo por cada participante
16 / 103
Autómatas FinitosAutómata Finitos Informalmente
Autómatas Finitos Deterministas (AFD)Autómatas Finitos No Deterministas (AFND)
Autómatas Finitos con Transiciones
Ejemplo e-comercio 1/3Ejemplo e-comercio 2/3Ejemplo e-comercio 2/3
Protocolo e-comercio completo
17 / 103
Autómatas FinitosAutómata Finitos Informalmente
Autómatas Finitos Deterministas (AFD)Autómatas Finitos No Deterministas (AFND)
Autómatas Finitos con Transiciones
Ejemplo e-comercio 1/3Ejemplo e-comercio 2/3Ejemplo e-comercio 2/3
Todo el Sistema como Autómata
18 / 103
Autómatas FinitosAutómata Finitos Informalmente
Autómatas Finitos Deterministas (AFD)Autómatas Finitos No Deterministas (AFND)
Autómatas Finitos con Transiciones
Definición Formal de un AFDComo un AFD Procesa CadenasDiagramas y Tablas de Transición AFDEjemploExtensión de la Función de Transición a Cadenas AFDLenguaje de un AFD
Definición Formal de AFD
DefinitionUn AFD es una quíntupla
A = (Q,Σ, δ, q0,F )
1 Q es un conjunto finito de estados.2 Σ es un alfabeto finito, los símbolos de entrada.3 δ : Q × Σ→ Q es una función de transición δ(q, a) = p.4 q0 ∈ Q es el estado de inicio.5 F ⊆ Q es el conjunto de estado aceptados o finales.
19 / 103
Autómatas FinitosAutómata Finitos Informalmente
Autómatas Finitos Deterministas (AFD)Autómatas Finitos No Deterministas (AFND)
Autómatas Finitos con Transiciones
Definición Formal de un AFDComo un AFD Procesa CadenasDiagramas y Tablas de Transición AFDEjemploExtensión de la Función de Transición a Cadenas AFDLenguaje de un AFD
Procesamiento de Cadenas por un AFD
Sea A AFD y w = a1a2 · · · an una cadena de entrada para A.
Iniciamos con A en su estado q0, δ(q0, a1) = q1.
Procesamos a2, δ(q1, a2) = q2 y continuamos encontrandoq3, q4, . . . , qn.δ(qi−1, ai ) = qi para cada i .
Si qn ∈ F diremos que la entrada w = a1a2 · · · an esaceptada sino es rechazada
20 / 103
Autómatas FinitosAutómata Finitos Informalmente
Autómatas Finitos Deterministas (AFD)Autómatas Finitos No Deterministas (AFND)
Autómatas Finitos con Transiciones
Definición Formal de un AFDComo un AFD Procesa CadenasDiagramas y Tablas de Transición AFDEjemploExtensión de la Función de Transición a Cadenas AFDLenguaje de un AFD
Procesamiento de Cadenas por un AFD
Sea A AFD y w = a1a2 · · · an una cadena de entrada para A.Iniciamos con A en su estado q0, δ(q0, a1) = q1.
Procesamos a2, δ(q1, a2) = q2 y continuamos encontrandoq3, q4, . . . , qn.δ(qi−1, ai ) = qi para cada i .
Si qn ∈ F diremos que la entrada w = a1a2 · · · an esaceptada sino es rechazada
21 / 103
Autómatas FinitosAutómata Finitos Informalmente
Autómatas Finitos Deterministas (AFD)Autómatas Finitos No Deterministas (AFND)
Autómatas Finitos con Transiciones
Definición Formal de un AFDComo un AFD Procesa CadenasDiagramas y Tablas de Transición AFDEjemploExtensión de la Función de Transición a Cadenas AFDLenguaje de un AFD
Procesamiento de Cadenas por un AFD
Sea A AFD y w = a1a2 · · · an una cadena de entrada para A.Iniciamos con A en su estado q0, δ(q0, a1) = q1.
Procesamos a2, δ(q1, a2) = q2 y continuamos encontrandoq3, q4, . . . , qn.
δ(qi−1, ai ) = qi para cada i .
Si qn ∈ F diremos que la entrada w = a1a2 · · · an esaceptada sino es rechazada
22 / 103
Autómatas FinitosAutómata Finitos Informalmente
Autómatas Finitos Deterministas (AFD)Autómatas Finitos No Deterministas (AFND)
Autómatas Finitos con Transiciones
Definición Formal de un AFDComo un AFD Procesa CadenasDiagramas y Tablas de Transición AFDEjemploExtensión de la Función de Transición a Cadenas AFDLenguaje de un AFD
Procesamiento de Cadenas por un AFD
Sea A AFD y w = a1a2 · · · an una cadena de entrada para A.Iniciamos con A en su estado q0, δ(q0, a1) = q1.
Procesamos a2, δ(q1, a2) = q2 y continuamos encontrandoq3, q4, . . . , qn.δ(qi−1, ai ) = qi para cada i .
Si qn ∈ F diremos que la entrada w = a1a2 · · · an esaceptada sino es rechazada
23 / 103
Autómatas FinitosAutómata Finitos Informalmente
Autómatas Finitos Deterministas (AFD)Autómatas Finitos No Deterministas (AFND)
Autómatas Finitos con Transiciones
Definición Formal de un AFDComo un AFD Procesa CadenasDiagramas y Tablas de Transición AFDEjemploExtensión de la Función de Transición a Cadenas AFDLenguaje de un AFD
Procesamiento de Cadenas por un AFD
Sea A AFD y w = a1a2 · · · an una cadena de entrada para A.Iniciamos con A en su estado q0, δ(q0, a1) = q1.
Procesamos a2, δ(q1, a2) = q2 y continuamos encontrandoq3, q4, . . . , qn.δ(qi−1, ai ) = qi para cada i .
Si qn ∈ F diremos que la entrada w = a1a2 · · · an esaceptada sino es rechazada
24 / 103
Autómatas FinitosAutómata Finitos Informalmente
Autómatas Finitos Deterministas (AFD)Autómatas Finitos No Deterministas (AFND)
Autómatas Finitos con Transiciones
Definición Formal de un AFDComo un AFD Procesa CadenasDiagramas y Tablas de Transición AFDEjemploExtensión de la Función de Transición a Cadenas AFDLenguaje de un AFD
Lenguaje de un AFD
DefinitionEl lenguaje de un AFD es el conjunto de todas las cadenas w queel AFD acepta.
25 / 103
Autómatas FinitosAutómata Finitos Informalmente
Autómatas Finitos Deterministas (AFD)Autómatas Finitos No Deterministas (AFND)
Autómatas Finitos con Transiciones
Definición Formal de un AFDComo un AFD Procesa CadenasDiagramas y Tablas de Transición AFDEjemploExtensión de la Función de Transición a Cadenas AFDLenguaje de un AFD
Ejemplo 1-1/4
Example
Especificar formalmente un AFD que acepte únicamente cadenasque tenga 0′s y 1′s conteniendo la subcadena 01 en alguna partede la cadena. El lenguaje L se puede describir como
L = {x01y | x , y ∈ {0, 1}∗}
Las siguientes cadenas pertenecen a L:01, 11010, 1001, 110001011.
Las siguientes cadenas no pertenecen a L: ε, 0, 11000.
26 / 103
Autómatas FinitosAutómata Finitos Informalmente
Autómatas Finitos Deterministas (AFD)Autómatas Finitos No Deterministas (AFND)
Autómatas Finitos con Transiciones
Definición Formal de un AFDComo un AFD Procesa CadenasDiagramas y Tablas de Transición AFDEjemploExtensión de la Función de Transición a Cadenas AFDLenguaje de un AFD
Ejemplo 1-1/4
Example
Especificar formalmente un AFD que acepte únicamente cadenasque tenga 0′s y 1′s conteniendo la subcadena 01 en alguna partede la cadena. El lenguaje L se puede describir como
L = {x01y | x , y ∈ {0, 1}∗}
Las siguientes cadenas pertenecen a L:01, 11010, 1001, 110001011.
Las siguientes cadenas no pertenecen a L: ε, 0, 11000.
27 / 103
Autómatas FinitosAutómata Finitos Informalmente
Autómatas Finitos Deterministas (AFD)Autómatas Finitos No Deterministas (AFND)
Autómatas Finitos con Transiciones
Definición Formal de un AFDComo un AFD Procesa CadenasDiagramas y Tablas de Transición AFDEjemploExtensión de la Función de Transición a Cadenas AFDLenguaje de un AFD
Ejemplo 1-2/4
¿Qué es lo que debemos conocer para definir el autómata queacepta al lenguaje L?
1 Sus estados Q
2 Su estado de inicio q03 Su alfabeto Σ ({0, 1})4 Su conjunto de estados aceptados
28 / 103
Autómatas FinitosAutómata Finitos Informalmente
Autómatas Finitos Deterministas (AFD)Autómatas Finitos No Deterministas (AFND)
Autómatas Finitos con Transiciones
Definición Formal de un AFDComo un AFD Procesa CadenasDiagramas y Tablas de Transición AFDEjemploExtensión de la Función de Transición a Cadenas AFDLenguaje de un AFD
Ejemplo 1-2/4
¿Qué es lo que debemos conocer para definir el autómata queacepta al lenguaje L?
1 Sus estados Q2 Su estado de inicio q0
3 Su alfabeto Σ ({0, 1})4 Su conjunto de estados aceptados
29 / 103
Autómatas FinitosAutómata Finitos Informalmente
Autómatas Finitos Deterministas (AFD)Autómatas Finitos No Deterministas (AFND)
Autómatas Finitos con Transiciones
Definición Formal de un AFDComo un AFD Procesa CadenasDiagramas y Tablas de Transición AFDEjemploExtensión de la Función de Transición a Cadenas AFDLenguaje de un AFD
Ejemplo 1-2/4
¿Qué es lo que debemos conocer para definir el autómata queacepta al lenguaje L?
1 Sus estados Q2 Su estado de inicio q03 Su alfabeto Σ ({0, 1})
4 Su conjunto de estados aceptados
30 / 103
Autómatas FinitosAutómata Finitos Informalmente
Autómatas Finitos Deterministas (AFD)Autómatas Finitos No Deterministas (AFND)
Autómatas Finitos con Transiciones
Definición Formal de un AFDComo un AFD Procesa CadenasDiagramas y Tablas de Transición AFDEjemploExtensión de la Función de Transición a Cadenas AFDLenguaje de un AFD
Ejemplo 1-2/4
¿Qué es lo que debemos conocer para definir el autómata queacepta al lenguaje L?
1 Sus estados Q2 Su estado de inicio q03 Su alfabeto Σ ({0, 1})4 Su conjunto de estados aceptados
31 / 103
Autómatas FinitosAutómata Finitos Informalmente
Autómatas Finitos Deterministas (AFD)Autómatas Finitos No Deterministas (AFND)
Autómatas Finitos con Transiciones
Definición Formal de un AFDComo un AFD Procesa CadenasDiagramas y Tablas de Transición AFDEjemploExtensión de la Función de Transición a Cadenas AFDLenguaje de un AFD
Ejemplo 1-3/4
El autómata A debe tener la capacidad de reconocer si 01 es unasubcadena de la cadena de entrada. Necesita recordar
1 ¿Ya ha visto la cadena 01? En caso afirmativo, entoncesacepta toda secuencia posterior de entradas.
2 ¿Nunca ha visto un 01, pero su entrada mas reciente fue un 0,si así fue ahora ve un 1, luego al haber visto un 01 podráaceptar todo lo que ve de aquí en adelante?
3 ¿Nunca ha visto un 01, pero su última entrada fue inexistente(recién comienza) o lo último que vio fue un 1? En este caso,A no puede aceptar hasta que vea un 0 y luego vea 1inmediatamente después.
32 / 103
Autómatas FinitosAutómata Finitos Informalmente
Autómatas Finitos Deterministas (AFD)Autómatas Finitos No Deterministas (AFND)
Autómatas Finitos con Transiciones
Definición Formal de un AFDComo un AFD Procesa CadenasDiagramas y Tablas de Transición AFDEjemploExtensión de la Función de Transición a Cadenas AFDLenguaje de un AFD
Ejemplo 1-3/4
El autómata A debe tener la capacidad de reconocer si 01 es unasubcadena de la cadena de entrada. Necesita recordar
1 ¿Ya ha visto la cadena 01? En caso afirmativo, entoncesacepta toda secuencia posterior de entradas.
2 ¿Nunca ha visto un 01, pero su entrada mas reciente fue un 0,si así fue ahora ve un 1, luego al haber visto un 01 podráaceptar todo lo que ve de aquí en adelante?
3 ¿Nunca ha visto un 01, pero su última entrada fue inexistente(recién comienza) o lo último que vio fue un 1? En este caso,A no puede aceptar hasta que vea un 0 y luego vea 1inmediatamente después.
33 / 103
Autómatas FinitosAutómata Finitos Informalmente
Autómatas Finitos Deterministas (AFD)Autómatas Finitos No Deterministas (AFND)
Autómatas Finitos con Transiciones
Definición Formal de un AFDComo un AFD Procesa CadenasDiagramas y Tablas de Transición AFDEjemploExtensión de la Función de Transición a Cadenas AFDLenguaje de un AFD
Ejemplo 1-3/4
El autómata A debe tener la capacidad de reconocer si 01 es unasubcadena de la cadena de entrada. Necesita recordar
1 ¿Ya ha visto la cadena 01? En caso afirmativo, entoncesacepta toda secuencia posterior de entradas.
2 ¿Nunca ha visto un 01, pero su entrada mas reciente fue un 0,si así fue ahora ve un 1, luego al haber visto un 01 podráaceptar todo lo que ve de aquí en adelante?
3 ¿Nunca ha visto un 01, pero su última entrada fue inexistente(recién comienza) o lo último que vio fue un 1? En este caso,A no puede aceptar hasta que vea un 0 y luego vea 1inmediatamente después.
34 / 103
Autómatas FinitosAutómata Finitos Informalmente
Autómatas Finitos Deterministas (AFD)Autómatas Finitos No Deterministas (AFND)
Autómatas Finitos con Transiciones
Definición Formal de un AFDComo un AFD Procesa CadenasDiagramas y Tablas de Transición AFDEjemploExtensión de la Función de Transición a Cadenas AFDLenguaje de un AFD
Ejemplo 1-3/4
El autómata debe tener la capacidad de reconocer si 01 es unasubcadena de la cadena de entrada.
1 q0: (condición 3) Si la cadena de entrada es ε permanecemosen q0, δ(q0, ε) = q0. Si la cadena de entrada es 1permanecemos en q0, δ(q0, 1) = q0.
2 q2: (condición 2) No se ha detectado la cadena 01 pero laentrada mas reciente ha sido un 0. Usaremos q2 pararepresentar δ(q0, 0) = q2. Luego si vemos un 1 se tendrá lacadena 01, δ(q0, 0) = q2, δ(q2, 1) = q1.
3 q1: Ya se detecto la cadena 01, se acepta entonces todasucesión posterior de entradas, δ(q1, 0) = δ(q1, 1) = q1.
35 / 103
Autómatas FinitosAutómata Finitos Informalmente
Autómatas Finitos Deterministas (AFD)Autómatas Finitos No Deterministas (AFND)
Autómatas Finitos con Transiciones
Definición Formal de un AFDComo un AFD Procesa CadenasDiagramas y Tablas de Transición AFDEjemploExtensión de la Función de Transición a Cadenas AFDLenguaje de un AFD
Ejemplo 1-3/4
El autómata debe tener la capacidad de reconocer si 01 es unasubcadena de la cadena de entrada.
1 q0: (condición 3) Si la cadena de entrada es ε permanecemosen q0, δ(q0, ε) = q0. Si la cadena de entrada es 1permanecemos en q0, δ(q0, 1) = q0.
2 q2: (condición 2) No se ha detectado la cadena 01 pero laentrada mas reciente ha sido un 0. Usaremos q2 pararepresentar δ(q0, 0) = q2. Luego si vemos un 1 se tendrá lacadena 01, δ(q0, 0) = q2, δ(q2, 1) = q1.
3 q1: Ya se detecto la cadena 01, se acepta entonces todasucesión posterior de entradas, δ(q1, 0) = δ(q1, 1) = q1.
36 / 103
Autómatas FinitosAutómata Finitos Informalmente
Autómatas Finitos Deterministas (AFD)Autómatas Finitos No Deterministas (AFND)
Autómatas Finitos con Transiciones
Definición Formal de un AFDComo un AFD Procesa CadenasDiagramas y Tablas de Transición AFDEjemploExtensión de la Función de Transición a Cadenas AFDLenguaje de un AFD
Ejemplo 1-3/4
El autómata debe tener la capacidad de reconocer si 01 es unasubcadena de la cadena de entrada.
1 q0: (condición 3) Si la cadena de entrada es ε permanecemosen q0, δ(q0, ε) = q0. Si la cadena de entrada es 1permanecemos en q0, δ(q0, 1) = q0.
2 q2: (condición 2) No se ha detectado la cadena 01 pero laentrada mas reciente ha sido un 0. Usaremos q2 pararepresentar δ(q0, 0) = q2. Luego si vemos un 1 se tendrá lacadena 01, δ(q0, 0) = q2, δ(q2, 1) = q1.
3 q1: Ya se detecto la cadena 01, se acepta entonces todasucesión posterior de entradas, δ(q1, 0) = δ(q1, 1) = q1.
37 / 103
Autómatas FinitosAutómata Finitos Informalmente
Autómatas Finitos Deterministas (AFD)Autómatas Finitos No Deterministas (AFND)
Autómatas Finitos con Transiciones
Definición Formal de un AFDComo un AFD Procesa CadenasDiagramas y Tablas de Transición AFDEjemploExtensión de la Función de Transición a Cadenas AFDLenguaje de un AFD
Ejemplo 1-4/4
¿Qué es lo que debemos conocer para definir el autómata queacepta al lenguaje L?
1 Sus estados Q = {q0, q1, q2}
2 Su estado de inicio q0.3 Su alfabeto Σ = {0, 1}.4 Su conjunto de estado aceptados: F = {q1}
38 / 103
Autómatas FinitosAutómata Finitos Informalmente
Autómatas Finitos Deterministas (AFD)Autómatas Finitos No Deterministas (AFND)
Autómatas Finitos con Transiciones
Definición Formal de un AFDComo un AFD Procesa CadenasDiagramas y Tablas de Transición AFDEjemploExtensión de la Función de Transición a Cadenas AFDLenguaje de un AFD
Ejemplo 1-4/4
¿Qué es lo que debemos conocer para definir el autómata queacepta al lenguaje L?
1 Sus estados Q = {q0, q1, q2}2 Su estado de inicio q0.
3 Su alfabeto Σ = {0, 1}.4 Su conjunto de estado aceptados: F = {q1}
39 / 103
Autómatas FinitosAutómata Finitos Informalmente
Autómatas Finitos Deterministas (AFD)Autómatas Finitos No Deterministas (AFND)
Autómatas Finitos con Transiciones
Definición Formal de un AFDComo un AFD Procesa CadenasDiagramas y Tablas de Transición AFDEjemploExtensión de la Función de Transición a Cadenas AFDLenguaje de un AFD
Ejemplo 1-4/4
¿Qué es lo que debemos conocer para definir el autómata queacepta al lenguaje L?
1 Sus estados Q = {q0, q1, q2}2 Su estado de inicio q0.3 Su alfabeto Σ = {0, 1}.
4 Su conjunto de estado aceptados: F = {q1}
40 / 103
Autómatas FinitosAutómata Finitos Informalmente
Autómatas Finitos Deterministas (AFD)Autómatas Finitos No Deterministas (AFND)
Autómatas Finitos con Transiciones
Definición Formal de un AFDComo un AFD Procesa CadenasDiagramas y Tablas de Transición AFDEjemploExtensión de la Función de Transición a Cadenas AFDLenguaje de un AFD
Ejemplo 1-4/4
¿Qué es lo que debemos conocer para definir el autómata queacepta al lenguaje L?
1 Sus estados Q = {q0, q1, q2}2 Su estado de inicio q0.3 Su alfabeto Σ = {0, 1}.4 Su conjunto de estado aceptados: F = {q1}
41 / 103
Autómatas FinitosAutómata Finitos Informalmente
Autómatas Finitos Deterministas (AFD)Autómatas Finitos No Deterministas (AFND)
Autómatas Finitos con Transiciones
Definición Formal de un AFDComo un AFD Procesa CadenasDiagramas y Tablas de Transición AFDEjemploExtensión de la Función de Transición a Cadenas AFDLenguaje de un AFD
Definición Diagramas de Transición
Definition
Un diagrama de transición de AFD A = (Q,Σ, δ, q0,F ) es ungrafo que cumple con las siguientes condiciones
1 Para cada q ∈ Q existe un nodo.
2 Para cada q ∈ Q y a ∈ Σ, sea δ(q, a) = p. Entonces eldiagrama de transición tiene un arco que va del nodo q alnodo p cuya etiqueta es a.
3 Hay una flecha entrando al estado q0 cuya etiqueta es Inicio.4 Los nodos correspondientes a los estados aceptados, F , sonmarcados por un círculo doble. Los estado que no pertenecena F tienen un círculo simple.
42 / 103
Autómatas FinitosAutómata Finitos Informalmente
Autómatas Finitos Deterministas (AFD)Autómatas Finitos No Deterministas (AFND)
Autómatas Finitos con Transiciones
Definición Formal de un AFDComo un AFD Procesa CadenasDiagramas y Tablas de Transición AFDEjemploExtensión de la Función de Transición a Cadenas AFDLenguaje de un AFD
Definición Diagramas de Transición
Definition
Un diagrama de transición de AFD A = (Q,Σ, δ, q0,F ) es ungrafo que cumple con las siguientes condiciones
1 Para cada q ∈ Q existe un nodo.2 Para cada q ∈ Q y a ∈ Σ, sea δ(q, a) = p. Entonces eldiagrama de transición tiene un arco que va del nodo q alnodo p cuya etiqueta es a.
3 Hay una flecha entrando al estado q0 cuya etiqueta es Inicio.4 Los nodos correspondientes a los estados aceptados, F , sonmarcados por un círculo doble. Los estado que no pertenecena F tienen un círculo simple.
43 / 103
Autómatas FinitosAutómata Finitos Informalmente
Autómatas Finitos Deterministas (AFD)Autómatas Finitos No Deterministas (AFND)
Autómatas Finitos con Transiciones
Definición Formal de un AFDComo un AFD Procesa CadenasDiagramas y Tablas de Transición AFDEjemploExtensión de la Función de Transición a Cadenas AFDLenguaje de un AFD
Definición Diagramas de Transición
Definition
Un diagrama de transición de AFD A = (Q,Σ, δ, q0,F ) es ungrafo que cumple con las siguientes condiciones
1 Para cada q ∈ Q existe un nodo.2 Para cada q ∈ Q y a ∈ Σ, sea δ(q, a) = p. Entonces eldiagrama de transición tiene un arco que va del nodo q alnodo p cuya etiqueta es a.
3 Hay una flecha entrando al estado q0 cuya etiqueta es Inicio.
4 Los nodos correspondientes a los estados aceptados, F , sonmarcados por un círculo doble. Los estado que no pertenecena F tienen un círculo simple.
44 / 103
Autómatas FinitosAutómata Finitos Informalmente
Autómatas Finitos Deterministas (AFD)Autómatas Finitos No Deterministas (AFND)
Autómatas Finitos con Transiciones
Definición Formal de un AFDComo un AFD Procesa CadenasDiagramas y Tablas de Transición AFDEjemploExtensión de la Función de Transición a Cadenas AFDLenguaje de un AFD
Definición Diagramas de Transición
Definition
Un diagrama de transición de AFD A = (Q,Σ, δ, q0,F ) es ungrafo que cumple con las siguientes condiciones
1 Para cada q ∈ Q existe un nodo.2 Para cada q ∈ Q y a ∈ Σ, sea δ(q, a) = p. Entonces eldiagrama de transición tiene un arco que va del nodo q alnodo p cuya etiqueta es a.
3 Hay una flecha entrando al estado q0 cuya etiqueta es Inicio.4 Los nodos correspondientes a los estados aceptados, F , sonmarcados por un círculo doble. Los estado que no pertenecena F tienen un círculo simple.
45 / 103
Autómatas FinitosAutómata Finitos Informalmente
Autómatas Finitos Deterministas (AFD)Autómatas Finitos No Deterministas (AFND)
Autómatas Finitos con Transiciones
Definición Formal de un AFDComo un AFD Procesa CadenasDiagramas y Tablas de Transición AFDEjemploExtensión de la Función de Transición a Cadenas AFDLenguaje de un AFD
Definición de Tablas de Transición
DefinitionUna tabla de transición es una representación tabularconvencional de la función δ. Los renglones de la tablacorresponden a los estados y las columnas corresponden a lasentradas. La entrada para el renglón correspondiente al estado q ycolumna correspondiente a la entrada “a”es el estado δ(q, a).
46 / 103
Autómatas FinitosAutómata Finitos Informalmente
Autómatas Finitos Deterministas (AFD)Autómatas Finitos No Deterministas (AFND)
Autómatas Finitos con Transiciones
Definición Formal de un AFDComo un AFD Procesa CadenasDiagramas y Tablas de Transición AFDEjemploExtensión de la Función de Transición a Cadenas AFDLenguaje de un AFD
Ejemplo de Diagramas y Tablas de Transición
Diagrama y tabla de transición del ejemplo 1.
A = {{q0, q1, q2}, {0, 1}, δ, q0, {q1}}
Figure: Diagrama de transición Figure: Tabla de transición
47 / 103
Autómatas FinitosAutómata Finitos Informalmente
Autómatas Finitos Deterministas (AFD)Autómatas Finitos No Deterministas (AFND)
Autómatas Finitos con Transiciones
Definición Formal de un AFDComo un AFD Procesa CadenasDiagramas y Tablas de Transición AFDEjemploExtensión de la Función de Transición a Cadenas AFDLenguaje de un AFD
Example
Dado el siguiente autómata determine cuál de las siguientescadenas acepta.
a) bbaaa
b) aabbba
c) bab
d) aba
48 / 103
Autómatas FinitosAutómata Finitos Informalmente
Autómatas Finitos Deterministas (AFD)Autómatas Finitos No Deterministas (AFND)
Autómatas Finitos con Transiciones
Definición Formal de un AFDComo un AFD Procesa CadenasDiagramas y Tablas de Transición AFDEjemploExtensión de la Función de Transición a Cadenas AFDLenguaje de un AFD
Extensión de la Función de Transición a Cadenas
La función de transición δ : Q × Σ→ Q se puede extenderpara que actúe sobre estados y cadenas
A la función extendida la denotaremos por δ̂.
La definición de δ̂ se hace por inducción sobre la longitud dela cadena de entrada.
49 / 103
Autómatas FinitosAutómata Finitos Informalmente
Autómatas Finitos Deterministas (AFD)Autómatas Finitos No Deterministas (AFND)
Autómatas Finitos con Transiciones
Definición Formal de un AFDComo un AFD Procesa CadenasDiagramas y Tablas de Transición AFDEjemploExtensión de la Función de Transición a Cadenas AFDLenguaje de un AFD
Extensión de la Función de Transición a Cadenas
La función de transición δ : Q × Σ→ Q se puede extenderpara que actúe sobre estados y cadenasA la función extendida la denotaremos por δ̂.
La definición de δ̂ se hace por inducción sobre la longitud dela cadena de entrada.
50 / 103
Autómatas FinitosAutómata Finitos Informalmente
Autómatas Finitos Deterministas (AFD)Autómatas Finitos No Deterministas (AFND)
Autómatas Finitos con Transiciones
Definición Formal de un AFDComo un AFD Procesa CadenasDiagramas y Tablas de Transición AFDEjemploExtensión de la Función de Transición a Cadenas AFDLenguaje de un AFD
Extensión de la Función de Transición a Cadenas
La función de transición δ : Q × Σ→ Q se puede extenderpara que actúe sobre estados y cadenasA la función extendida la denotaremos por δ̂.
La definición de δ̂ se hace por inducción sobre la longitud dela cadena de entrada.
51 / 103
Autómatas FinitosAutómata Finitos Informalmente
Autómatas Finitos Deterministas (AFD)Autómatas Finitos No Deterministas (AFND)
Autómatas Finitos con Transiciones
Definición Formal de un AFDComo un AFD Procesa CadenasDiagramas y Tablas de Transición AFDEjemploExtensión de la Función de Transición a Cadenas AFDLenguaje de un AFD
Definición de la Función de Transición Extendida
1 Definimosδ̂(q, ε) = q,
donde ε es la cadena vacía.
2 Sea w cualquier cadena tal que |w | = 1, suponga que w = a.Definimos
δ̂(q,w) = δ(δ̂(q, ε), a
)= δ (q, a) = p1
3 Sea w cualquier cadena tal que |w | = 2, suponga quew = ba. Entonces
δ̂(q, ba) = δ(δ̂(q, b), a
)= δ (p, a) = p2,
donde estamos suponiendo que δ̂(q, b) = p.
52 / 103
Autómatas FinitosAutómata Finitos Informalmente
Autómatas Finitos Deterministas (AFD)Autómatas Finitos No Deterministas (AFND)
Autómatas Finitos con Transiciones
Definición Formal de un AFDComo un AFD Procesa CadenasDiagramas y Tablas de Transición AFDEjemploExtensión de la Función de Transición a Cadenas AFDLenguaje de un AFD
Definición de la Función de Transición Extendida
1 Definimosδ̂(q, ε) = q,
donde ε es la cadena vacía.2 Sea w cualquier cadena tal que |w | = 1, suponga que w = a.Definimos
δ̂(q,w) = δ(δ̂(q, ε), a
)= δ (q, a) = p1
3 Sea w cualquier cadena tal que |w | = 2, suponga quew = ba. Entonces
δ̂(q, ba) = δ(δ̂(q, b), a
)= δ (p, a) = p2,
donde estamos suponiendo que δ̂(q, b) = p.
53 / 103
Autómatas FinitosAutómata Finitos Informalmente
Autómatas Finitos Deterministas (AFD)Autómatas Finitos No Deterministas (AFND)
Autómatas Finitos con Transiciones
Definición Formal de un AFDComo un AFD Procesa CadenasDiagramas y Tablas de Transición AFDEjemploExtensión de la Función de Transición a Cadenas AFDLenguaje de un AFD
Definición de la Función de Transición Extendida
1 Definimosδ̂(q, ε) = q,
donde ε es la cadena vacía.2 Sea w cualquier cadena tal que |w | = 1, suponga que w = a.Definimos
δ̂(q,w) = δ(δ̂(q, ε), a
)= δ (q, a) = p1
3 Sea w cualquier cadena tal que |w | = 2, suponga quew = ba. Entonces
δ̂(q, ba) = δ(δ̂(q, b), a
)= δ (p, a) = p2,
donde estamos suponiendo que δ̂(q, b) = p.54 / 103
Autómatas FinitosAutómata Finitos Informalmente
Autómatas Finitos Deterministas (AFD)Autómatas Finitos No Deterministas (AFND)
Autómatas Finitos con Transiciones
Definición Formal de un AFDComo un AFD Procesa CadenasDiagramas y Tablas de Transición AFDEjemploExtensión de la Función de Transición a Cadenas AFDLenguaje de un AFD
Definición Formal de Lenguaje para un AFD
Definition
Formalmente el lenguaje (aceptado) de un AFDA = (Q,Σ, δ, q0,F ) es
L(A) ={w | δ̂(q0,w) ∈ F
}DefinitionLos lenguajes aceptados por los AFD son llamados lenguajesregulares.
55 / 103
Autómatas FinitosAutómata Finitos Informalmente
Autómatas Finitos Deterministas (AFD)Autómatas Finitos No Deterministas (AFND)
Autómatas Finitos con Transiciones
Definición Formal de un AFDComo un AFD Procesa CadenasDiagramas y Tablas de Transición AFDEjemploExtensión de la Función de Transición a Cadenas AFDLenguaje de un AFD
Ejemplo 2 de AFD
1 Diseño de un AFD que acepta únicamente cadenas con unnúmero par de 0′s y un número par de 1′s.
2 El lenguaje aceptado del AFD es
L ={w | w tiene un número par de 0′s y de 1′s
}.
3 q0: El número de 0′s y 1′s vistos hasta el momento es par.4 q1: El número de 0′s vistos hasta el momento es par pero los1′s son impares.
5 q2: El número de 1′s vistos hasta el momento es par pero los0′s son impares.
6 q3: El número de 0′s y 1′s vistos hasta el momento es impar.
56 / 103
Autómatas FinitosAutómata Finitos Informalmente
Autómatas Finitos Deterministas (AFD)Autómatas Finitos No Deterministas (AFND)
Autómatas Finitos con Transiciones
Definición Formal de un AFDComo un AFD Procesa CadenasDiagramas y Tablas de Transición AFDEjemploExtensión de la Función de Transición a Cadenas AFDLenguaje de un AFD
Ejemplo 2 de AFD
1 Diseño de un AFD que acepta únicamente cadenas con unnúmero par de 0′s y un número par de 1′s.
2 El lenguaje aceptado del AFD es
L ={w | w tiene un número par de 0′s y de 1′s
}.
3 q0: El número de 0′s y 1′s vistos hasta el momento es par.4 q1: El número de 0′s vistos hasta el momento es par pero los1′s son impares.
5 q2: El número de 1′s vistos hasta el momento es par pero los0′s son impares.
6 q3: El número de 0′s y 1′s vistos hasta el momento es impar.
57 / 103
Autómatas FinitosAutómata Finitos Informalmente
Autómatas Finitos Deterministas (AFD)Autómatas Finitos No Deterministas (AFND)
Autómatas Finitos con Transiciones
Definición Formal de un AFDComo un AFD Procesa CadenasDiagramas y Tablas de Transición AFDEjemploExtensión de la Función de Transición a Cadenas AFDLenguaje de un AFD
Ejemplo 2 de AFD
1 Diseño de un AFD que acepta únicamente cadenas con unnúmero par de 0′s y un número par de 1′s.
2 El lenguaje aceptado del AFD es
L ={w | w tiene un número par de 0′s y de 1′s
}.
3 q0: El número de 0′s y 1′s vistos hasta el momento es par.
4 q1: El número de 0′s vistos hasta el momento es par pero los1′s son impares.
5 q2: El número de 1′s vistos hasta el momento es par pero los0′s son impares.
6 q3: El número de 0′s y 1′s vistos hasta el momento es impar.
58 / 103
Autómatas FinitosAutómata Finitos Informalmente
Autómatas Finitos Deterministas (AFD)Autómatas Finitos No Deterministas (AFND)
Autómatas Finitos con Transiciones
Definición Formal de un AFDComo un AFD Procesa CadenasDiagramas y Tablas de Transición AFDEjemploExtensión de la Función de Transición a Cadenas AFDLenguaje de un AFD
Ejemplo 2 de AFD
1 Diseño de un AFD que acepta únicamente cadenas con unnúmero par de 0′s y un número par de 1′s.
2 El lenguaje aceptado del AFD es
L ={w | w tiene un número par de 0′s y de 1′s
}.
3 q0: El número de 0′s y 1′s vistos hasta el momento es par.4 q1: El número de 0′s vistos hasta el momento es par pero los1′s son impares.
5 q2: El número de 1′s vistos hasta el momento es par pero los0′s son impares.
6 q3: El número de 0′s y 1′s vistos hasta el momento es impar.
59 / 103
Autómatas FinitosAutómata Finitos Informalmente
Autómatas Finitos Deterministas (AFD)Autómatas Finitos No Deterministas (AFND)
Autómatas Finitos con Transiciones
Definición Formal de un AFDComo un AFD Procesa CadenasDiagramas y Tablas de Transición AFDEjemploExtensión de la Función de Transición a Cadenas AFDLenguaje de un AFD
Ejemplo 2 de AFD
1 Diseño de un AFD que acepta únicamente cadenas con unnúmero par de 0′s y un número par de 1′s.
2 El lenguaje aceptado del AFD es
L ={w | w tiene un número par de 0′s y de 1′s
}.
3 q0: El número de 0′s y 1′s vistos hasta el momento es par.4 q1: El número de 0′s vistos hasta el momento es par pero los1′s son impares.
5 q2: El número de 1′s vistos hasta el momento es par pero los0′s son impares.
6 q3: El número de 0′s y 1′s vistos hasta el momento es impar.
60 / 103
Autómatas FinitosAutómata Finitos Informalmente
Autómatas Finitos Deterministas (AFD)Autómatas Finitos No Deterministas (AFND)
Autómatas Finitos con Transiciones
Definición Formal de un AFDComo un AFD Procesa CadenasDiagramas y Tablas de Transición AFDEjemploExtensión de la Función de Transición a Cadenas AFDLenguaje de un AFD
Ejemplo 2 de AFD
1 Diseño de un AFD que acepta únicamente cadenas con unnúmero par de 0′s y un número par de 1′s.
2 El lenguaje aceptado del AFD es
L ={w | w tiene un número par de 0′s y de 1′s
}.
3 q0: El número de 0′s y 1′s vistos hasta el momento es par.4 q1: El número de 0′s vistos hasta el momento es par pero los1′s son impares.
5 q2: El número de 1′s vistos hasta el momento es par pero los0′s son impares.
6 q3: El número de 0′s y 1′s vistos hasta el momento es impar.
61 / 103
Autómatas FinitosAutómata Finitos Informalmente
Autómatas Finitos Deterministas (AFD)Autómatas Finitos No Deterministas (AFND)
Autómatas Finitos con Transiciones
Definición Formal de un AFDComo un AFD Procesa CadenasDiagramas y Tablas de Transición AFDEjemploExtensión de la Función de Transición a Cadenas AFDLenguaje de un AFD
Diagrama y Tabla de Transición del Ejemplo 2
Un AFD que acepta únicamente cadenas con un número parde 0′s y un número par de 1′s
A = {{q0, q1, q2, q3}, {0, 1}, δ, q0, {q0}}
62 / 103
Autómatas FinitosAutómata Finitos Informalmente
Autómatas Finitos Deterministas (AFD)Autómatas Finitos No Deterministas (AFND)
Autómatas Finitos con Transiciones
Definición Formal de un AFDComo un AFD Procesa CadenasDiagramas y Tablas de Transición AFDEjemploExtensión de la Función de Transición a Cadenas AFDLenguaje de un AFD
Evolución de la función de transición extendida
Considere w = 110101
1 δ̂(q0, ε) = q02 δ̂(q0, 1) = δ(δ̂(q0, ε), 1) = δ(q0, 1) = q13 δ̂(q0, 11) = δ(δ̂(q0, 1), 1) = δ(q1, 1) = q04 δ̂(q0, 110) = δ(δ̂(q0, 11), 0) = δ(q0, 0) = q25 δ̂(q0, 1101) = δ(δ̂(q0, 110), 1) = δ(q2, 1) = q36 δ̂(q0, 11010) = δ(δ̂(q0, 1101), 0) = δ(q3, 0) = q17 δ̂(q0, 110101) = δ(δ̂(q0, 11010), 1) = δ(q1, 1) = q0
63 / 103
Autómatas FinitosAutómata Finitos Informalmente
Autómatas Finitos Deterministas (AFD)Autómatas Finitos No Deterministas (AFND)
Autómatas Finitos con Transiciones
Definición Formal de AFNDEspecificación Formal de un AFND EjemploFunción de Transición Extendida AFNDEl Lenguaje de un AFNDEquivalencia entre AFD y AFND
Autómatas Finitos No Deterministas (AFND)
Un AFND puede estar en varios estados al mismo tiempo.Capacidad de adivinar algo relacionado con su entrada.
[Ejemplo 1 AFND] Considere el AFND, A01, que acepta todaslas cadenas formadas de 0′s y 1′s pero que terminan en 01
64 / 103
Autómatas FinitosAutómata Finitos Informalmente
Autómatas Finitos Deterministas (AFD)Autómatas Finitos No Deterministas (AFND)
Autómatas Finitos con Transiciones
Definición Formal de AFNDEspecificación Formal de un AFND EjemploFunción de Transición Extendida AFNDEl Lenguaje de un AFNDEquivalencia entre AFD y AFND
Autómatas Finitos No Deterministas (AFND)
Un AFND puede estar en varios estados al mismo tiempo.Capacidad de adivinar algo relacionado con su entrada.
[Ejemplo 1 AFND] Considere el AFND, A01, que acepta todaslas cadenas formadas de 0′s y 1′s pero que terminan en 01
65 / 103
Autómatas FinitosAutómata Finitos Informalmente
Autómatas Finitos Deterministas (AFD)Autómatas Finitos No Deterministas (AFND)
Autómatas Finitos con Transiciones
Definición Formal de AFNDEspecificación Formal de un AFND EjemploFunción de Transición Extendida AFNDEl Lenguaje de un AFNDEquivalencia entre AFD y AFND
Definición Formal de AFND
DefinitionUn AFND es una quíntupla
A = (Q,Σ, δ, q0,F )
1 Q es un conjunto finito de estados.
2 Σ es un alfabeto finito, los símbolos de entrada.3 q0 ∈ Q, el estado de inicio.4 F ⊆ Q, los estados aceptados5 δ : Q × Σ→ 2|Q |, la función de transición.
66 / 103
Autómatas FinitosAutómata Finitos Informalmente
Autómatas Finitos Deterministas (AFD)Autómatas Finitos No Deterministas (AFND)
Autómatas Finitos con Transiciones
Definición Formal de AFNDEspecificación Formal de un AFND EjemploFunción de Transición Extendida AFNDEl Lenguaje de un AFNDEquivalencia entre AFD y AFND
Definición Formal de AFND
DefinitionUn AFND es una quíntupla
A = (Q,Σ, δ, q0,F )
1 Q es un conjunto finito de estados.2 Σ es un alfabeto finito, los símbolos de entrada.
3 q0 ∈ Q, el estado de inicio.4 F ⊆ Q, los estados aceptados5 δ : Q × Σ→ 2|Q |, la función de transición.
67 / 103
Autómatas FinitosAutómata Finitos Informalmente
Autómatas Finitos Deterministas (AFD)Autómatas Finitos No Deterministas (AFND)
Autómatas Finitos con Transiciones
Definición Formal de AFNDEspecificación Formal de un AFND EjemploFunción de Transición Extendida AFNDEl Lenguaje de un AFNDEquivalencia entre AFD y AFND
Definición Formal de AFND
DefinitionUn AFND es una quíntupla
A = (Q,Σ, δ, q0,F )
1 Q es un conjunto finito de estados.2 Σ es un alfabeto finito, los símbolos de entrada.3 q0 ∈ Q, el estado de inicio.
4 F ⊆ Q, los estados aceptados5 δ : Q × Σ→ 2|Q |, la función de transición.
68 / 103
Autómatas FinitosAutómata Finitos Informalmente
Autómatas Finitos Deterministas (AFD)Autómatas Finitos No Deterministas (AFND)
Autómatas Finitos con Transiciones
Definición Formal de AFNDEspecificación Formal de un AFND EjemploFunción de Transición Extendida AFNDEl Lenguaje de un AFNDEquivalencia entre AFD y AFND
Definición Formal de AFND
DefinitionUn AFND es una quíntupla
A = (Q,Σ, δ, q0,F )
1 Q es un conjunto finito de estados.2 Σ es un alfabeto finito, los símbolos de entrada.3 q0 ∈ Q, el estado de inicio.4 F ⊆ Q, los estados aceptados
5 δ : Q × Σ→ 2|Q |, la función de transición.
69 / 103
Autómatas FinitosAutómata Finitos Informalmente
Autómatas Finitos Deterministas (AFD)Autómatas Finitos No Deterministas (AFND)
Autómatas Finitos con Transiciones
Definición Formal de AFNDEspecificación Formal de un AFND EjemploFunción de Transición Extendida AFNDEl Lenguaje de un AFNDEquivalencia entre AFD y AFND
Definición Formal de AFND
DefinitionUn AFND es una quíntupla
A = (Q,Σ, δ, q0,F )
1 Q es un conjunto finito de estados.2 Σ es un alfabeto finito, los símbolos de entrada.3 q0 ∈ Q, el estado de inicio.4 F ⊆ Q, los estados aceptados5 δ : Q × Σ→ 2|Q |, la función de transición.
70 / 103
Autómatas FinitosAutómata Finitos Informalmente
Autómatas Finitos Deterministas (AFD)Autómatas Finitos No Deterministas (AFND)
Autómatas Finitos con Transiciones
Definición Formal de AFNDEspecificación Formal de un AFND EjemploFunción de Transición Extendida AFNDEl Lenguaje de un AFNDEquivalencia entre AFD y AFND
Especificación Formal del Ejemplo 1 AFND
1
A = {{q0, q1, q2} , {0, 1} , δ, q0, {q2}}
2 La función de transición δ está dada por
71 / 103
Autómatas FinitosAutómata Finitos Informalmente
Autómatas Finitos Deterministas (AFD)Autómatas Finitos No Deterministas (AFND)
Autómatas Finitos con Transiciones
Definición Formal de AFNDEspecificación Formal de un AFND EjemploFunción de Transición Extendida AFNDEl Lenguaje de un AFNDEquivalencia entre AFD y AFND
Especificación Formal del Ejemplo 1 AFND
1
A = {{q0, q1, q2} , {0, 1} , δ, q0, {q2}}
2 La función de transición δ está dada por
72 / 103
Autómatas FinitosAutómata Finitos Informalmente
Autómatas Finitos Deterministas (AFD)Autómatas Finitos No Deterministas (AFND)
Autómatas Finitos con Transiciones
Definición Formal de AFNDEspecificación Formal de un AFND EjemploFunción de Transición Extendida AFNDEl Lenguaje de un AFNDEquivalencia entre AFD y AFND
Definición de la Función de Transición Extendida
DefinitionLa definición de la función de transición extendida para AFND lahacemos por inducción
Base: δ̂(q, ε) = {q}
Inducción: Supongamos que w = xa, a es el símbolo final de w y xes el antecedente de w . Supongamos queδ̂(q, x) = {p1, p2, . . . , pk}. Sea
k⋃i=1
δ(pi , a) = {r1, r2, . . . , rm} .
Entoncesδ̂(q,w) = {r1, r2, . . . , rm} 73 / 103
Autómatas FinitosAutómata Finitos Informalmente
Autómatas Finitos Deterministas (AFD)Autómatas Finitos No Deterministas (AFND)
Autómatas Finitos con Transiciones
Definición Formal de AFNDEspecificación Formal de un AFND EjemploFunción de Transición Extendida AFNDEl Lenguaje de un AFNDEquivalencia entre AFD y AFND
Ejemplo Función de Transición Extendida AFND 1/2
74 / 103
Autómatas FinitosAutómata Finitos Informalmente
Autómatas Finitos Deterministas (AFD)Autómatas Finitos No Deterministas (AFND)
Autómatas Finitos con Transiciones
Definición Formal de AFNDEspecificación Formal de un AFND EjemploFunción de Transición Extendida AFNDEl Lenguaje de un AFNDEquivalencia entre AFD y AFND
Ejemplo Función de Transición Extendida AFND 2/2
Sea w = 00101 y el AFND A01
1 δ̂(q0, ε) = {q0}2 δ̂(q0, 0) = δ(q0, 0) = {q0, q1}3 δ̂(q0, 00) = δ(q0, 0) ∪ δ(q1, 0) = {q0, q1} ∪ φ = {q0, q1}4 δ̂(q0, 001) = δ(q0, 1) ∪ δ(q1, 1) = {q0} ∪ {q2} = {q0, q2}5 δ̂(q0, 0010) = δ(q0, 0) ∪ δ(q1, 0) ∪ δ(q2, 0) ={q0, q1} ∪ φ ∪ φ = {q0, q1}
6 δ̂(q0, 00101) = δ(q0, 1) ∪ δ(q1, 1) ∪ δ(q2, 1) ={q0} ∪ {q2} = {q0, q2}
75 / 103
Autómatas FinitosAutómata Finitos Informalmente
Autómatas Finitos Deterministas (AFD)Autómatas Finitos No Deterministas (AFND)
Autómatas Finitos con Transiciones
Definición Formal de AFNDEspecificación Formal de un AFND EjemploFunción de Transición Extendida AFNDEl Lenguaje de un AFNDEquivalencia entre AFD y AFND
Definición Formal de Lenguaje de un AFND
Definition
Si A = (Q,Σ, δ, q0,F ) es un AFND entonces
L(A) ={w | δ̂(q0,w) ∩ F 6= φ
}En palabras L(A) es el conjunto de cadenas w en Σ∗ tal queδ̂(q0,w) contiene al menos un estado aceptado.
76 / 103
Autómatas FinitosAutómata Finitos Informalmente
Autómatas Finitos Deterministas (AFD)Autómatas Finitos No Deterministas (AFND)
Autómatas Finitos con Transiciones
Definición Formal de AFNDEspecificación Formal de un AFND EjemploFunción de Transición Extendida AFNDEl Lenguaje de un AFNDEquivalencia entre AFD y AFND
Equivalencia AFD y AFND I
Los AFND en general son más fáciles de construir que unAFD.
Sorprendentemente para cualquier AFND N existe un AFD Dtal que L(D) = L(N) y viceversa.
La demostración de la equivalencia entre AFD y AFNDinvolucra una “construcción” llamada el subconjunto deconstrucción.
77 / 103
Autómatas FinitosAutómata Finitos Informalmente
Autómatas Finitos Deterministas (AFD)Autómatas Finitos No Deterministas (AFND)
Autómatas Finitos con Transiciones
Definición Formal de AFNDEspecificación Formal de un AFND EjemploFunción de Transición Extendida AFNDEl Lenguaje de un AFNDEquivalencia entre AFD y AFND
Equivalencia AFD y AFND II
Dado un AFND
N = (QN ,Σ, δN , q0,FN )
se construye un AFD
D = (QD ,Σ, δD , {q0},FD )
tal queL(D) = L(N)
78 / 103
Autómatas FinitosAutómata Finitos Informalmente
Autómatas Finitos Deterministas (AFD)Autómatas Finitos No Deterministas (AFND)
Autómatas Finitos con Transiciones
Definición Formal de AFNDEspecificación Formal de un AFND EjemploFunción de Transición Extendida AFNDEl Lenguaje de un AFNDEquivalencia entre AFD y AFND
Construcción Equivalencia
QD = {S | S ⊆ QN} , QD = 2|QN |, en general no todos losestados son accesibles a partir del estado de inicio de QD .
FD = {S ⊆ QN | S ∩ FN 6= φ}Para cada S ⊆ QN y a ∈ Σ
δD (S , a) =⋃p∈S
δN (p, a)
Para calcular δD (S , a) buscamos en todos los estados p ∈ S ,vemos a qué estados va N desde p con la entrada a, ytomamos la unión de todos esos estados.
79 / 103
Autómatas FinitosAutómata Finitos Informalmente
Autómatas Finitos Deterministas (AFD)Autómatas Finitos No Deterministas (AFND)
Autómatas Finitos con Transiciones
Definición Formal de AFNDEspecificación Formal de un AFND EjemploFunción de Transición Extendida AFNDEl Lenguaje de un AFNDEquivalencia entre AFD y AFND
Ejemplo Equivalencia AFND, AFD
Sea N el autómata de la figuraadjunta que acepta todos lascadenas que terminan en 01.Entonces QD tiene 23 estados.A continuación ponemos la Latabla de transición yrenombramos los conjuntos.
80 / 103
Autómatas FinitosAutómata Finitos Informalmente
Autómatas Finitos Deterministas (AFD)Autómatas Finitos No Deterministas (AFND)
Autómatas Finitos con Transiciones
Definición Formal de AFNDEspecificación Formal de un AFND EjemploFunción de Transición Extendida AFNDEl Lenguaje de un AFNDEquivalencia entre AFD y AFND
Equivalencia
Theorem
Si D = (QD ,ΣD , δD , {q0} ,FD ) es el AFD construido a partir delAFND N = (QN ,Σ, δN , q0,FN ) por medio del subconjuntoconstrucción, entonces L(D) = L(N).
TheoremSi un lenguaje L es aceptado por algún AFD ⇔ es aceptado poralgún AFND.
81 / 103
Autómatas FinitosAutómata Finitos Informalmente
Autómatas Finitos Deterministas (AFD)Autómatas Finitos No Deterministas (AFND)
Autómatas Finitos con Transiciones
Uso de las Transiciones-εEpsilón CerradurasTransiciones Extendidas y Lenguajes para epsilón AFND
Autómatas Finitos con Transiciones
Introducimos una nueva característica a los autómatas que lespermite una transición con ε la cadena vacía.
Se pueden hacer transiciones de forma “espontánea”, sinrecibir un símbolo de entrada.
La nueva característica no expande la clase de lenguajes quepuede ser aceptada.
Incorpora facilidades para la programación.
82 / 103
Autómatas FinitosAutómata Finitos Informalmente
Autómatas Finitos Deterministas (AFD)Autómatas Finitos No Deterministas (AFND)
Autómatas Finitos con Transiciones
Uso de las Transiciones-εEpsilón CerradurasTransiciones Extendidas y Lenguajes para epsilón AFND
Autómatas Finitos con Transiciones
Introducimos una nueva característica a los autómatas que lespermite una transición con ε la cadena vacía.
Se pueden hacer transiciones de forma “espontánea”, sinrecibir un símbolo de entrada.
La nueva característica no expande la clase de lenguajes quepuede ser aceptada.
Incorpora facilidades para la programación.
83 / 103
Autómatas FinitosAutómata Finitos Informalmente
Autómatas Finitos Deterministas (AFD)Autómatas Finitos No Deterministas (AFND)
Autómatas Finitos con Transiciones
Uso de las Transiciones-εEpsilón CerradurasTransiciones Extendidas y Lenguajes para epsilón AFND
Autómatas Finitos con Transiciones
Introducimos una nueva característica a los autómatas que lespermite una transición con ε la cadena vacía.
Se pueden hacer transiciones de forma “espontánea”, sinrecibir un símbolo de entrada.
La nueva característica no expande la clase de lenguajes quepuede ser aceptada.
Incorpora facilidades para la programación.
84 / 103
Autómatas FinitosAutómata Finitos Informalmente
Autómatas Finitos Deterministas (AFD)Autómatas Finitos No Deterministas (AFND)
Autómatas Finitos con Transiciones
Uso de las Transiciones-εEpsilón CerradurasTransiciones Extendidas y Lenguajes para epsilón AFND
Autómatas Finitos con Transiciones
Introducimos una nueva característica a los autómatas que lespermite una transición con ε la cadena vacía.
Se pueden hacer transiciones de forma “espontánea”, sinrecibir un símbolo de entrada.
La nueva característica no expande la clase de lenguajes quepuede ser aceptada.
Incorpora facilidades para la programación.
85 / 103
Autómatas FinitosAutómata Finitos Informalmente
Autómatas Finitos Deterministas (AFD)Autómatas Finitos No Deterministas (AFND)
Autómatas Finitos con Transiciones
Uso de las Transiciones-εEpsilón CerradurasTransiciones Extendidas y Lenguajes para epsilón AFND
Ejemplo Informal
Ejemplo de un ε-AFND que acepta números decimales queconsisten de:
1 Un signo opcional + o −.
2 Una cadena de dígitos.3 Un punto decimal.4 Otra cadena de dígitos;esta cadena de dígitos o lacadena dada en (2) puedeser vacía, pero al menosuna de las dos cadenas dedígitos debe ser no vacía.
86 / 103
Autómatas FinitosAutómata Finitos Informalmente
Autómatas Finitos Deterministas (AFD)Autómatas Finitos No Deterministas (AFND)
Autómatas Finitos con Transiciones
Uso de las Transiciones-εEpsilón CerradurasTransiciones Extendidas y Lenguajes para epsilón AFND
Ejemplo Informal
Ejemplo de un ε-AFND que acepta números decimales queconsisten de:
1 Un signo opcional + o −.2 Una cadena de dígitos.
3 Un punto decimal.4 Otra cadena de dígitos;esta cadena de dígitos o lacadena dada en (2) puedeser vacía, pero al menosuna de las dos cadenas dedígitos debe ser no vacía.
87 / 103
Autómatas FinitosAutómata Finitos Informalmente
Autómatas Finitos Deterministas (AFD)Autómatas Finitos No Deterministas (AFND)
Autómatas Finitos con Transiciones
Uso de las Transiciones-εEpsilón CerradurasTransiciones Extendidas y Lenguajes para epsilón AFND
Ejemplo Informal
Ejemplo de un ε-AFND que acepta números decimales queconsisten de:
1 Un signo opcional + o −.2 Una cadena de dígitos.3 Un punto decimal.
4 Otra cadena de dígitos;esta cadena de dígitos o lacadena dada en (2) puedeser vacía, pero al menosuna de las dos cadenas dedígitos debe ser no vacía.
88 / 103
Autómatas FinitosAutómata Finitos Informalmente
Autómatas Finitos Deterministas (AFD)Autómatas Finitos No Deterministas (AFND)
Autómatas Finitos con Transiciones
Uso de las Transiciones-εEpsilón CerradurasTransiciones Extendidas y Lenguajes para epsilón AFND
Ejemplo Informal
Ejemplo de un ε-AFND que acepta números decimales queconsisten de:
1 Un signo opcional + o −.2 Una cadena de dígitos.3 Un punto decimal.4 Otra cadena de dígitos;esta cadena de dígitos o lacadena dada en (2) puedeser vacía, pero al menosuna de las dos cadenas dedígitos debe ser no vacía.
89 / 103
Autómatas FinitosAutómata Finitos Informalmente
Autómatas Finitos Deterministas (AFD)Autómatas Finitos No Deterministas (AFND)
Autómatas Finitos con Transiciones
Uso de las Transiciones-εEpsilón CerradurasTransiciones Extendidas y Lenguajes para epsilón AFND
Segundo Ejemplo
Un ε-AFND que acepta las palabras {ebay, web}
90 / 103
Autómatas FinitosAutómata Finitos Informalmente
Autómatas Finitos Deterministas (AFD)Autómatas Finitos No Deterministas (AFND)
Autómatas Finitos con Transiciones
Uso de las Transiciones-εEpsilón CerradurasTransiciones Extendidas y Lenguajes para epsilón AFND
Definición de AFND con Epsilón Transiciones
DefinitionUn ε−AFND es una quíntupla
A = (Q,Σ, δ, q0,F )
1 Q es un conjunto finito de estados.2 Σ es un alfabeto finito, los símbolos de entrada.3 q0 ∈ Q, el estado de inicio.4 F ⊆ Q, los estados aceptados5 δ : Q × Σ ∪ {ε} → 2Q , la función de transición.
91 / 103
Autómatas FinitosAutómata Finitos Informalmente
Autómatas Finitos Deterministas (AFD)Autómatas Finitos No Deterministas (AFND)
Autómatas Finitos con Transiciones
Uso de las Transiciones-εEpsilón CerradurasTransiciones Extendidas y Lenguajes para epsilón AFND
Ejemplo
Representación formal del ε−AFND que acepta números decimales
E = ({q0, q1, . . . , q5} , {·,+,−, 0, 1, . . . , 9} , δ, q0, {q5})
Figure: Tabla de transición
92 / 103
Autómatas FinitosAutómata Finitos Informalmente
Autómatas Finitos Deterministas (AFD)Autómatas Finitos No Deterministas (AFND)
Autómatas Finitos con Transiciones
Uso de las Transiciones-εEpsilón CerradurasTransiciones Extendidas y Lenguajes para epsilón AFND
Definición de Epsilón Cerraduras
La ε−cerradura de un estado q es simplemente seguir todas lastransiciones de salida de q etiquetadas con ε.
Definition
Definimos la ε−cerradura del estado q, denotada por ECLOSE (q),inductivamente q ∈ ECLOSE (q), inducción
p ∈ ECLOSE (q) y r ∈ δ(p, ε)⇒ r ∈ ECLOSE (q)
93 / 103
Autómatas FinitosAutómata Finitos Informalmente
Autómatas Finitos Deterministas (AFD)Autómatas Finitos No Deterministas (AFND)
Autómatas Finitos con Transiciones
Uso de las Transiciones-εEpsilón CerradurasTransiciones Extendidas y Lenguajes para epsilón AFND
Ejemplo de epsilón Cerradura
Ejemplo
ECLOSE (1) = {1, 2, 3, 4, 6}
94 / 103
Autómatas FinitosAutómata Finitos Informalmente
Autómatas Finitos Deterministas (AFD)Autómatas Finitos No Deterministas (AFND)
Autómatas Finitos con Transiciones
Uso de las Transiciones-εEpsilón CerradurasTransiciones Extendidas y Lenguajes para epsilón AFND
Definición de la Transición Extendida para AFND
Por inducciónBase:
δ̂(q, ε) = ECLOSE (q)
Inducción:δ̂(q, xa) =
⋃p∈(δ(q,x ),a)
ECLOSE (p)
95 / 103
Autómatas FinitosAutómata Finitos Informalmente
Autómatas Finitos Deterministas (AFD)Autómatas Finitos No Deterministas (AFND)
Autómatas Finitos con Transiciones
Uso de las Transiciones-εEpsilón CerradurasTransiciones Extendidas y Lenguajes para epsilón AFND
Ejemplo Transición Extendida I
Calcularemos δ̂(q0, 5.6) para el autómata definido en el siguientediagrama
δ̂(q0, ε) = ECLOSE (q0) = {q0, q1}Para calcular δ̂(q0, 5), primero computamosδ(q0, 5) ∪ δ(q1, 5) = {q1, q4}.
96 / 103
Autómatas FinitosAutómata Finitos Informalmente
Autómatas Finitos Deterministas (AFD)Autómatas Finitos No Deterministas (AFND)
Autómatas Finitos con Transiciones
Uso de las Transiciones-εEpsilón CerradurasTransiciones Extendidas y Lenguajes para epsilón AFND
Ejemplo Transición Extendida II
δ̂(q0, 5) = ECLOSE (q1) ∪ ECLOSE (q2) = {q1} ∪ {q4} ={q1, q4}.Para calcular δ̂(q0, 5.), primero computamosδ(q1, .) ∪ δ(q4, .) = {q2} ∪ {q3} = {q2, q3}.δ̂(q0, 5.) = ECLOSE (q2) ∪ ECLOSE (q3) ={q2} ∪ {q3, q5} = {q2, q3, q5}.Para calcular δ̂(q0, 5.6), primero computamosδ(q2, 6) ∪ δ(q3, 6) ∪ δ(q5, 6). = {q3} ∪ {q3} ∪ φ = {q3}.δ̂(q0, 5.6) = ECLOSE{q3} = {q3, q5}
97 / 103
Autómatas FinitosAutómata Finitos Informalmente
Autómatas Finitos Deterministas (AFD)Autómatas Finitos No Deterministas (AFND)
Autómatas Finitos con Transiciones
Uso de las Transiciones-εEpsilón CerradurasTransiciones Extendidas y Lenguajes para epsilón AFND
Lenguaje de un epsilón AFND
Definition
Sea E = (Q,Σ, , δ, q0,F ) un ε−AFND, entonces el lenguaje de Eestá dado por
L(E ) ={w : δ̂(q0,w) ∩ F 6= φ
}
98 / 103
Autómatas FinitosAutómata Finitos Informalmente
Autómatas Finitos Deterministas (AFD)Autómatas Finitos No Deterministas (AFND)
Autómatas Finitos con Transiciones
Uso de las Transiciones-εEpsilón CerradurasTransiciones Extendidas y Lenguajes para epsilón AFND
Eliminando epsilón Transiciones I
Dado un ε−AFND
E = (QE ,Σ, , δE , q0,FE )
podemos construir un AFD
D = (QD ,Σ, , δD , qD ,FD )
tal queL(D) = L(E )
Detalles de construcción
QD = {S : S ⊆ QE y S = ECLOSE (S)}qD = ECLOSE (q0)
99 / 103
Autómatas FinitosAutómata Finitos Informalmente
Autómatas Finitos Deterministas (AFD)Autómatas Finitos No Deterministas (AFND)
Autómatas Finitos con Transiciones
Uso de las Transiciones-εEpsilón CerradurasTransiciones Extendidas y Lenguajes para epsilón AFND
Eliminando epsilón Transiciones II
FD = {S : S ∈ QD y S ∩ FE 6= φ}δD (S , a) =
⋃{ECLOSE (p) : p ∈ δ(t, a) para alguna t ∈ S}
100 / 103
Autómatas FinitosAutómata Finitos Informalmente
Autómatas Finitos Deterministas (AFD)Autómatas Finitos No Deterministas (AFND)
Autómatas Finitos con Transiciones
Uso de las Transiciones-εEpsilón CerradurasTransiciones Extendidas y Lenguajes para epsilón AFND
Ejemplo
Autómata E ε−AFND AFD D correspondiente a E
101 / 103
Autómatas FinitosAutómata Finitos Informalmente
Autómatas Finitos Deterministas (AFD)Autómatas Finitos No Deterministas (AFND)
Autómatas Finitos con Transiciones
Uso de las Transiciones-εEpsilón CerradurasTransiciones Extendidas y Lenguajes para epsilón AFND
Equivalencia de los Lenguajes I
TheoremUn lenguaje L es aceptado por algún E ε−AFND ⇔ L es aceptadopor algún AFD.
Demostración. Suficiencia. Sea E = (QE ,Σ, , δE , q0,FE ) unε−AFND. Empleamos el autómata D construido anteriormente ymostraremos L(D) = L(E ) lo que es equivalente a demostrar queδ̂D (q0,w) = δ̂E (qD ,w). Lo haremos por inducción sobre lalongitud de w .Base: Si |w | = 0, entonces w = ε, se concluye fácilmente queδ̂E (q0, ε) = δ̂D (qD , ε).
102 / 103
Autómatas FinitosAutómata Finitos Informalmente
Autómatas Finitos Deterministas (AFD)Autómatas Finitos No Deterministas (AFND)
Autómatas Finitos con Transiciones
Uso de las Transiciones-εEpsilón CerradurasTransiciones Extendidas y Lenguajes para epsilón AFND
Equivalencia de los Lenguajes II
Inducción:
δ̂E (q0, xa) =⋃
p∈δE (δ̂E (q0,x ),a)
ECLOSE (p)
=⋃
p∈δD (δ̂D (qD ,x ),a)
ECLOSE (p)
=⋃
p∈δ̂D (qD ,xa)
ECLOSE (p)
= δ̂D (qD , xa)
103 / 103