Actividad1_2_manolo Pájaro.docx

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