AUTÓMATAS Y LENGUAJES FORMALES
TAREA 5 CONSOLIDACIÓN DEL APRENDIZAJE
Presentado Por:
Julio Javier Barbosa Herrera
Código: 1143370115
Yeiner Moreno Julio
Código: 1047443045
Oruel Jaramillo Vargas
Código: 1122731340
Eliecer Adolfo Guzmán Barrios
Código: 1051821043
Ingeniería Sistemas
Tutor
Helena Clara Isabel Alemán
Escuela De Ciencia Básicas, Tecnología E Ingeniería
Universidad Nacional Abierta Y A Distancia
01/Diciembre/2022
1
DESARROLLO
Ejercicio 1: Realizar la conversión de AFD a AFND o de AFND a AFD según
corresponda
• Caracterización del autómata original
• Procedimiento de conversión de Autómata de AFD a AFND o de AFND a AFD según
corresponda con procedimiento paso a paso
• Gráfica del Autómata final convertido
EJERCICIO A
TRABAJAR
Caracterización del Se define como quíntupla de acuerdo a la siguiente expresión
autómata
AFD = (Σ, Q, f, q0, F)
En donde los valores de esta quíntupla están definidos por:
Q: Es el conjunto de estados no vacíos (q0,q1,q2,q4,q5)
Σ: Es el alfabeto del autómata (a, b)
q0: Es el estado inicial (q4)
F: Es el conjunto de estados finales (q3)
f: Es la función de transición
Δ a b
> q4 q1 q3
q0 q1 q2
q1 q2 q4
q2 q2 q3
#q3 q5 q1
q5 q4
Procedimiento de Paso 1. Para la conversión se debe unificar estados, por lo que
conversión paso a los estados con transiciones vacías serán tomadas como un
paso estado y las transiciones que surgan a partir del estado inicial,
se tomaran como un estado
δ a b
> q4 {1,2} {3,4}
q1={1,2} {2} {3,4}
q2={3,4} {1,2,3,4,5} {1,2,3,4}
q3={2} {2} {3,4}
q5={1,2,3,4,5} {1,2,3,4,5} {1,2,3,4}
q6={1,2,3,4} {1,2,3,4,5} {1,2,3,4}
2
Una vez se tenga la nueva tabla de transición, se procede a
graficar
Autómata Final
convertido
Ejercicio 2: Realice la minimización paso a paso del autómata finito determinista
• Con el resultado del autómata del ejercicio 1, realice el proceso paso a paso de la
minimización del autómata
• Gráfica del autómata final minimizado
• Realice la caracterización de ese autómata
AUTOMATA DE PILA
Pasos1:
Se identifica la quíntupla:
5-tupla (k, Σ , δ , S , F )
M = Los estados que conforma el autómata
M = {q4, q1, q3, q2, q5, q6}, {a,b}, δ, q4, {q1,q5,q6}
K = Son lo estados
3
K = [q4, q1, q3, q2, q5, q6]
Alfabeto de entrada:
Σ = {a, b}
Estado inicial:
S = q4
Estado Final:
F= q1,q5,q6
Paso 2:
En este proceso es necesario que se crear los dos conjuntos de estado de aceptados y
no aceptados:
Estados de aceptados:
X = {q2,q5,q6}
Estados de no aceptados:
y = {q1, q3, q4}
Paso 4:
Creación de nueva tabla de transición para el conjunto, se representa de esta manera:
Tabla de transición aceptación
A b
q2 X X
q5 X X
q6 X X
Tabla de transición no aceptación
a b
q1 Y X
q3 Y X
q4 Y X
Determinamos los estados de equivalencia de la siguiente forma:
Estado de equivalencia del conjunto X:
X = {q2,q5,q6}
Estado de equivalencia del conjunto Y:
Y = {q1, q3, q4}
Teniendo en cuenta que todos los conjuntos son equivalentes en los estados.
Realiza la nueva tabla transición final
a b
X X X
Y Y X
Automata minimizado
4
Ejercicio 3: Realizar el autómata a Pila que lea la expresión regular del autómata
minimizado.
• Teniendo en cuenta la expresión regular del resultado del autómata minimizado del
ejercicio 2, realice el autómata de pila que lea las mismas cadenas
• Caracterización del autómata de pila
• Ejecute el RunTest a una cadena aceptada que tenga los menos cinco símbolos.
• Recorra la máquina con al menos una cadena válida explicando lo sucedido tanto en la
cinta como en la secuencia de entrada.
EJERCICIO
PARA TRABAJAR Inicial = q0
Final q1
Teniendo en cuenta (q0, a, λ) = (q0, a)
la expresión regular (q0, b, λ) = (q1, 1)
del resultado del (q1, a, λ) = (q1, a)
autómata
minimizado del
ejercicio 2, realice el
autómata de pila que
lea las mismas
cadenas
Lectura expresión regular autómata minimizada “aba”
Caracterización del En este espacio se realiza:
autómata
- Mediante la definición formal explicar las características del
Caracterización del autómata, identificación de la séptupla.
autómata de pila
Σ = {𝑎, 𝑏}
Γ = {𝑎, 1}
5
𝑄 = {𝑞0, 𝑞1}
𝐴0 𝜖 Γ = {𝜆}
𝑞0 𝜖 𝑄 = {𝑞0}
𝐹 ⊆ 𝑄 = {𝑞1}
𝐹: 𝜎 = (q0, a, λ), (q0, a)
𝜎 = (q0, b, λ), (q1, 1)
𝜎 = (q0, a, λ), (q1, a)
Por lo tanto, la séptupla del autómata es:
𝐴𝑃: (𝑎, 𝑏, 𝜆, 𝑞0, 𝑞1, 𝜆, 𝑞0, 𝑞1)
- Realizar la tabla de transición
𝛿 (a, 1) (b, 1) (a, a)
q0 (q0, a) (q0, b)
q1 (q1, b) (q1, a)
Ejecute el RunTest a
una cadena aceptada
que tenga los menos
cinco símbolos
Procedimiento de Realice de manera detallada y grafica el procedimiento paso a paso
paso a paso del del recorrido de una cadena (La cadena la selecciona el estudiante,
recorrido de una debe contener como mínimo 5 caracteres) en el autómata a pila.
cadena Describir cómo funciona el almacenamiento en la pila, como
funciona LIFO, etc.
Recorra la máquina
con al menos una
cadena válida
explicando lo
sucedido tanto en la
cinta como en la
secuencia de entrada. a b a a a
𝜎 = (q0, a, λ), (q0, a)
𝜎 = (q0, b, λ), (q1, 1)
𝜎 = (q1, a, λ), (q1, a)
- Paso 1…
6
el autómata se encuentra en el estado q0 con Z en la cima de la pila,
lee el símbolo de entrada a, no cambia su estado e introducirá en la
ella la letra a quedando la cabeza de la pila Z1.
a b a a a
𝜎 = (𝑞0, 𝑎, 𝜆), (𝑞0, 𝑎)
𝜎 = (q0, b, λ), (q1, 1)
𝜎 = (q1, a, λ), (q1, a) 1
Z
- Paso 2…
El autómata se encuentra en el estado q0 con Z en la cima de la pila,
lee el símbolo de entrada b, cambia su estado a q1 e introducirá en la
ella quedando la cabeza de la pila Z11.
a b a a a
𝜎 = (𝑞0, 𝑎, 𝜆), (𝑞0, 𝑎)
𝜎 = (q0, b, λ), (q1, 1) 1
𝜎 = (q1, a, λ), (q1, a) 1
Z
- Paso 3…
El autómata se encuentra en el estado q1 con Z11 en la cima de la
pila, lee el símbolo de entrada a, el autómata no cambia de estado q1,
a b a a a
a
1
𝜎 = (𝑞0, 𝑎, 𝜆), (𝑞0, 𝑎) 1
𝜎 = (q0, b, λ), (q0, b) Z
𝜎 = (q0, λ, λ), (q1, λ)
- Paso 4…
El autómata se encuentra en el estado q1 con Z11a en la cima de la
pila, lee el símbolo de entrada a, no cambia su estado e introducirá en
la ella la letra a quedando la cabeza de la pila Z11aa.
a b a a a
a
𝜎 = (𝑞0, 𝑎, 𝜆), (𝑞0, 𝑎) a
𝜎 = (q0, b, λ), (q0, b) 1
𝜎 = (q0, λ, λ), (q1, λ) 1
Z
- Paso 5…
7
El autómata se encuentra en el estado q1 con Z11aa en la cima de la
pila, lee el símbolo de entrada a, no cambia su estado e introducirá en
la ella la letra a quedando la cabeza de la pila Z11aaa.
a b a a a
a
𝜎 = (𝑞0, 𝑎, 𝜆), (𝑞0, 𝑎) a
𝜎 = (q0, b, λ), (q0, b) a
𝜎 = (q0, λ, λ), (q1, λ) 1
1
Z
Practicar y Apoyándose en el simulador JFlap (Anexo 1 - JFLAP) o VAS
verificar lo (Anexo 2- VAS) ejecutar y validar por lo menos cinco cadenas
aprendido válidas y 5 cadenas rechazadas por el autómata. En este espacio
adjunta la imagen.
8
Ejercicio 4: Realizar una máquina de Turing que lea la expresión regular del autómata
minimizado.
Teniendo en cuenta la expresión regular del resultado del autómata minimizado
del ejercicio 2, realice la máquina de Turing que lea las mismas cadenas.
Caracterización de la máquina de Turing
Ejecute el Run Test a una cadena aceptada que tenga la menos cinco símbolos.
Recorra la máquina con al menos una cadena válida explicando lo sucedido
tanto en la cinta como en la secuencia de entrada.
Realización de la máquina de Turing
Teniendo en cuenta la
expresión regular del
resultado del autómata
minimizado del ejercicio
2, realice la máquina de
Turing que lea las
mismas cadenas
Caracterización de la Caracterización de la máquina de Turing:
máquina de Turing
En base a la definición de máquina de Turing con una sola cinta
puede definirse como una séptupla
MT= {𝐾, 𝚺, Γ, s, b, F, δ}
K= {𝑞0, 𝑞1}
𝚺 = {1}
Γ = {𝑎}
s={𝑞0}
F= {𝑞1}
δ = k x Γ => k x Γ x {𝐿, 𝑅} función de transición,
donde L es un movimiento a la izquierda y R es
9
el movimiento a la derecha.
δ (q0,1) = (q0, a, R)
δ (q0, a) = (q1, a, R)
δ (q1,1) = (q1, a, R)
Ejecute el Run Test a
una cadena aceptada que
tenga la menos cinco
símbolos
Para la cadena aceptada a1aaa=
Recorra la máquina con Vamos a recorrer la cadena aceptada a1aaa:
al menos una cadena
válida explicando lo El primer paso es seleccionar input>step> y agregar la
sucedido tanto en la cinta cadena que eligimos.
como en la secuencia de
entrada.
Una vez hemos ingresado la cadena elegida, se procede
a recorrer la máquina. Podemos observar que como
estamos iniciando en el estado q0 lee el alfabeto de la
máquina que es 1.
10
Posteriormente, teniendo en cuenta que partimos de q0,
con un alfabeto de la maquina igual a 1, pero la cinta va
a escribirnos una a y se va a desplazar a la derecha. Por
lo tanto, tenemos que:
Por último, teniendo en cuenta que nos ubicamos en
q1, donde el alfabeto es 1, pero pide cambiar por a y
desplazarse a la derecha, tal como lo observamos en el
ejercicio, por tanto, observamos que este 1 está siendo
cambiado por a, así como se evidencia a continuación:
11
REFERENCIAS BIBLIOGRÁFICAS
Formella, A. (2010). Teoría de autómatas y lenguajes formales. Departamento de
Informática, Universidade de Vigo, Junio.
Sosa, R., & de Sande, F. ToTalf: Tutorial online para Teoría de Autómatas y
Lenguajes Formales.
Máquina de Turing. (2022, 7 de diciembre). Wikipedia, La enciclopedia libre.
desde https://es.wikipedia.org/w/index.php?title=M%C3%A1quina_de_Turing&oldid=
147771353.
Gonzales, A (2020). Máquina de Turing 2. YouTube. Desde
https://www.youtube.com/watch?v=LnKaEcag0jM
Jurado Málaga, E. (2008). Teoría de autómatas y lenguajes formales. Universidad de
Extremadura. Servicio de Publicaciones. (pp. 39 - 70).
https://bibliotecavirtual.unad.edu.co/login?url=http://search.ebscohost.com/login.aspx?d
irect=true&db=edsbas&AN=edsbas.62161440&lang=es&site=eds-live&scope=site
Concha Vega P, Torres Avilés R. A. (2021). Binary Complete and Aperiodic Turing
Machine. International Journal of Unconventional Computing.;16(1):19-39.
https://search-ebscohost-
com.bibliotecavirtual.unad.edu.co/login.aspx?direct=true&db=aci&AN=149259622&la
ng=es&site=eds-live&scope=site
12
