TALLER: INTRODUCCIÓN A AUTÓMATAS Y GRAMÁTICAS

ACTIVIDAD

TALLER: INTRODUCCIÓN A AUTÓMATAS Y GRAMÁTICAS

PROFESOR

SEBASTIAN GOMEZ JARAMILLO

ESTUDIANTE:

 FRANCISCO JOSE ORTEGA LARA

 UNIVERSIDAD DIGITAL DE ANTIOQUIA

TECNOLOGIA EN DESARROLLO DE SOFTWARE

18 de OCTUBRE del 2020

TALLER

1. Obtenga un AFD con el lenguaje definido en el alfabeto Σ={0,1}, que pueda generar entre otras, un subconjunto de las siguientes cadenas {0,1,0}, {0,1,1,1,0},{0,1,0,1,1}, {0,1,0,1,0,1}, {0,1,1,1,0}, {1,0,1}, {1,0,0,0,1}, {1,1,1,1}.

• R)  Trabajando con la tabla de transiciones  presentada en clases

• Se desarrollo el siguiente AFD y se comprobaron las anteriores cadenas

[pic 1] 

1. Obtenga un AFND diferente al AFD del punto anterior, con el lenguaje

definido en el alfabeto Σ={0,1}, que pueda generar entre otras, un subconjunto de las siguientes cadenas {0,1,0}, {0,1,1,1,0}, {0,1,0,1,1}, {0,1,0,1,0,1}, {0,1,1,1,0},{1,0,1}, {1,0,0,0,1}, {1,1,1,1}.

• Se desarrollo el siguiente AFND trabajado con la siguiente tabla de transiciones  y se comprobaron las anteriores cadenas

[pic 2]

1. Dado el alfabeto Σ= {a,b}, construir un Autómata Finito Determinista, que acepte el lenguaje representado por la siguiente expresión regular a*(ab+ba)(bb)∗  

[pic 3]

1. Dada la siguiente tabla de transición hacer los siguientes puntos

a. (5%) Indicar si es AFD o AFND y justifique su respuesta. ¿Qué cambios le haría para realizar su equivalente?

b. (15%) Indique la quíntupla del autómata

ᵹ (Q0,0) = Q0,Q3

ᵹ (Q0,1) = Q0,Q1

ᵹ (Q1,0) = Φ

ᵹ (Q1,1) = Q2

ᵹ (Q2,0) = Q2

ᵹ (Q2,1) = Q2

ᵹ (Q3,0) = Q4

ᵹ (Q3,1) = Φ

ᵹ (Q4,0) = Q4

ᵹ(Q4,1) = Q4

            Q= q,f

∑= 0,1

q= Q0

f = Q2,Q4

    c. (15%) Dibuje el autómata en un simulador

[pic 4]

d. (5%) Señale tres cadenas que cumplan y tres cadenas que no cumplan con ese autómata.

...