AUTÓMATAS Y LENGUAJES FORMALES
TEMA Lenguajes Regulares y sus máquinas
Fase: No 2
Actividad: No. 1, 2
Grupo: 301405_49
Alumno: Manolo Pájaro Borrás Cod: 8.718.129
Tutor: Jheimer Julián Sepúlveda
UNIVERSIDAD NACIONAL ABIERTA Y A DISTANCIA UNAD Medellín 2019
De acuerdo al último dígito de su cédula o tarjeta de identidad, identifique el ejercicio asignado en la siguiente tabla: Procedimiento de conversión de Autómata Finito a Expresión Regular paso a paso
EJERCICIO A TRABAJAR
Realice de manera detallada el procedimiento paso a paso de la conversión del autómata a expresión regular y según ejemplo revisado. - Paso 1: Se realiza el proceso de expandir q0 con la finalidad de eliminar q1
En este espacio se realiza: - Identificación del Autómata: Autómata finito no determinista - Paso 2… Se elimina q1 quedando el autómata de la siguiente -maneraM =( { q 0, q 1, q 2 ) , {1,2 } , δ Q 0, {Q 2 } ) - Porque con una entrada podemos tener varias transiciones porque con la misma entrada podemos ir a varios estados - El conjunto finito de estado es designado como: 0, q 1, q 2 } -Paso 3..K={q Se elimina q0 quedando el autómata final en q2 - El conjunto finito de entrada es designado por ∑= {1,2} Caracterización del - El estado Inicial de s=q0 - El estado final de f = q2 autómata Final Autómata - Donde la función convertido δ : {q 0,q 1,q 2 } x {1,2 } viene dada por δ {q 0,1 }=q 1 Lenguaje regular Er =(1+2)*+(2+11) δ {q 0,1 }=q 1 δ {q 1 , 2 }=q 1 δ {q 1 , 1 }=q 2 δ {q 0,2 }=q 2 Q0 Q1 Q1
1 q1 q0 q2
# Q2
ø
2 q2 q1
ø ø
ACTIVIDAD 2: Conversión de Autómatas Finitos Deterministas a Autómatas Finitos No deterministas (AFD a AFND) y viceversa
EJERCICIO A TRABAJAR
Caracterizació n del autómata
En este espacio se realiza: - Identificación del Autómata: Es finito no Determinista - Porque con una entrada podemos tener varias transiciones porque con la misma entrada podemos ir a varios estados - El conjunto finito de estado es designado como Q={q 0, q 1, q 2, q 3 - El conjunto finito de entrada es designado por ∑={a,b,c} - El estado Inicial de uno de los estados de Q es S=q0 - El conjunto de estados finales de aceptación F siendo F un subconjunto de Q -> F = q2
Realice de manera detallada el procedimiento paso a paso de la conversión del autómata según corresponda y según ejemplo revisado. - Paso 1… Eliminamos q3
Procedimiento de conversión paso a paso
- Paso 2…Eliminando q
- Paso 3…
El autómata final Autóm ata Final convert ido
Practic ar y verific ar lo aprend ido