Tarea 3 Construcción de Autómatas de Pila

Tarea 3 Construcción de Autómatas de Pila
Autómatas y Lenguajes Formales
301405_47
Presentado por
Julio Cesar Corrales
Presentado a
Jaime Jose Valdes
Universidad Nacional Abierta y a Distancia

Abril 2021
EJERCICIO MINIMIZACIÓN DE AUTÓMATA
Ejercicio
Para
Trabajar
Proceso de Se realiza la minimización por medio del procedimiento de eliminación de

Minimización conjuntos.
• Este es un autómata finito determinista (AFD), ya que cada tiene
una transición por cada estado.
• Identificamos la quíntupla del autómata sin minimizar:
𝑀 = {𝑞0, 𝑞1, 𝑞2, 𝑞3, 𝑞4, 𝑞5, 𝑞6}, {0,1}

𝐾 = {𝑞0 , 𝑞1 , 𝑞2 , 𝑞3 , 𝑞4 , 𝑞5 , 𝑞6 }
𝛴 = {0,1}
𝛿 = 𝑞0
𝐹 = {𝑞4 , 𝑞6 }
𝛿(𝑞0 , 0) = 𝑞4
𝛿(𝑞0 , 1) = 𝑞1
𝛿(𝑞1 , 0) = 𝑞4
𝛿(𝑞1 , 1) = 𝑞5
𝛿(𝑞2 , 0) = 𝑞3
𝛿(𝑞2 , 1) = 𝑞4
𝛿(𝑞3 , 0) = 𝑞5
𝛿(𝑞3 , 1) = 𝑞4
𝛿(𝑞4 , 0) = 𝑞2
𝛿(𝑞4 , 1) = ∅
𝛿(𝑞5 , 0) = 𝑞5
𝛿(𝑞5 , 1) = 𝑞4
𝛿(𝑞6 , 0) = 𝑞5
𝛿(𝑞6 , 1) = 𝑞3
• Creamos los conjuntos con los estados de aceptación y con los

estados de no aceptación.
𝑥 = {𝑞4 , 𝑞6 }
𝑦 = {𝑞0 , 𝑞1 , 𝑞2 , 𝑞3 , 𝑞5 }
• Realizamos las tablas de transición mencionando los conjuntos

pertenecientes a cada estado
𝑥 0 1
𝑞4 𝑦
𝑞6 𝑦 𝑦
• La tabla anterior no ha quedado equivalente, pero continuaremos
con la tabla de transición para el conjunto
𝑦
𝑦 0 1
𝑞0 𝑥 𝑦
𝑞1 𝑥 𝑦
𝑞2 𝑦 𝑥
𝑞3 𝑦 𝑥
𝑞5 𝑦 𝑥
• Crearemos nuevos conjuntos para esta tabla (x) ya que no ha

quedado equivalente.
𝑚 = {𝑞0 , 𝑞1 }
𝑧 = {𝑞2 , 𝑞3 , 𝑞5 }
𝑟 = {𝑞4 }
𝑠 = {𝑞6 }
𝑟 0 1
𝑞4 𝑧
𝑠 0 1
𝑞6 𝑧 𝑧
• En la tabla anterior (y) vemos que existen dos conjuntos

equivalentes, asignaremos nuevas tablas de transición para estos y
traeremos los dos nuevos conjuntos r y s.
𝑚 = {𝑞0 , 𝑞1 }
𝑧 = {𝑞2 , 𝑞3 , 𝑞5 }
𝑟 = {𝑞4 }
𝑠 = {𝑞6 }
𝑚 0 1
𝑞0 𝑟 𝑟
𝑞1 𝑟 𝑧
𝑧 0 1
𝑞2 𝑧 𝑟
𝑞3 𝑧 𝑟
𝑞5 𝑧 𝑟
• El conjunto z quedo equivalente, en caso contrario el conjunto m
no ha quedado equivalente crearemos dos nuevos conjuntos
creando sus tablas de transición.
𝑝 = {𝑞0 }
𝑞 = {𝑞1 }
𝑟 = {𝑞4 }
𝑠 = {𝑞6 }
𝑧 = {𝑞2 , 𝑞3 , 𝑞5 }
𝑝 0 1
𝑞0 𝑟 𝑞
𝑞 0 1
𝑞1 𝑟 𝑧
• Con los conjuntos ya en equivalencia creamos la tabla de transición
𝛿 0 1
𝑝 𝑟 𝑞
𝑞 𝑟 𝑧
𝑟 𝑧
𝑠 𝑧 𝑧
𝑧 𝑧 𝑟
• Analizando la tabla de transición podríamos omitir el estado (s) ya

que ningún alfabeto de la tabla realiza la transición esto no afectaría
el autómata.
𝛿 0 1
𝑝 𝑟 𝑞
𝑞 𝑟 𝑧
𝑟 𝑧
𝑧 𝑧 𝑟
Resultado del
Autómata
Minimizado
Notación Identificación de la quíntupla

Formal del
Autómata 𝐾 = {𝑝, 𝑞, 𝑟, 𝑧}
Minimizado 𝛴 = {0,1}
𝛿=𝑝
𝐹=𝑟
𝛿(𝑝, 0) = 𝑟
𝛿(𝑝, 1) = 𝑞
𝛿(𝑞, 0) = 𝑟
𝛿(𝑞, 1) = 𝑧
𝛿(𝑟, 0) = 𝑧
𝛿(𝑧, 0) = 𝑧
𝛿(𝑧, 1) = 𝑟
𝛿 0 1
𝑝 𝑟 𝑞
𝑞 𝑟 𝑧
𝑟 𝑧
𝑧 𝑧 𝑟
Lenguaje 𝐿𝑅 = ({𝑝, 𝑞, 𝑟, 𝑧}, {1,0})

Regular
Validación de
cadenas
Practicar y Para la validación ingresamos la cadena de aceptación (110000001)

Verificar lo
Aprendido
Para el primer paso del autómata del estado inicial (p), pasa al estado (q)
al ingresar el alfabeto 1
En el segundo alfabeto (1), estábamos en el estado q pasamos al estado z.
En la cadena para los 6 ceros (000000) contiguos quedamos en el estado

z, ya que es una estrella de kleene solo saldremos de hay hasta que
ingresemos un uno (1).
Según lo mencionado en el paso anterior, que hasta no obtuviéramos o
ingresáramos un uno (1) en la cadena de aceptación no saldríamos del
estado z.
REFERENCIAS
Alfonseca Cubero, E. (2007). Teoría de autómatas y lenguajes formales. Madrid: McGraw-

Hill España.
Carrasco, R. C. (2000). Teoría de lenguajes, gramáticas y autómatas para informáticos.
Digitalia.
Jurado Málaga, E. (. (2008). Teoría de autómatas y lenguajes formales. Universidad de
Extremadura. Servicio de Publicaciones.

Tarea 3 Construcción de Autómatas de Pila

Cargado por

Copyright:

Formatos disponibles

Tarea 3 Construcción de Autómatas de Pila

Cargado por

Información del documento

Título original

Derechos de autor

Formatos disponibles

Compartir este documento

Compartir o incrustar documentos

Opciones para compartir

¿Le pareció útil este documento?

¿Este contenido es inapropiado?

Copyright:

Formatos disponibles

Tarea 3 Construcción de Autómatas de Pila

Cargado por

Copyright:

Formatos disponibles

Tarea 3 Construcción de Autómatas de Pila

Autómatas y Lenguajes Formales

Jaime Jose Valdes

Universidad Nacional Abierta y a Distancia

Proceso de Se realiza la minimización por medio del procedimiento de eliminación de

𝑀 = {𝑞0, 𝑞1, 𝑞2, 𝑞3, 𝑞4, 𝑞5, 𝑞6}, {0,1}

• Creamos los conjuntos con los estados de aceptación y con los

• Realizamos las tablas de transición mencionando los conjuntos

• Crearemos nuevos conjuntos para esta tabla (x) ya que no ha

• En la tabla anterior (y) vemos que existen dos conjuntos

• Con los conjuntos ya en equivalencia creamos la tabla de transición

• Analizando la tabla de transición podríamos omitir el estado (s) ya

Notación Identificación de la quíntupla

Lenguaje 𝐿𝑅 = ({𝑝, 𝑞, 𝑟, 𝑧}, {1,0})

Practicar y Para la validación ingresamos la cadena de aceptación (110000001)

En la cadena para los 6 ceros (000000) contiguos quedamos en el estado

Alfonseca Cubero, E. (2007). Teoría de autómatas y lenguajes formales. Madrid: McGraw-

También podría gustarte