Taller Introducción autómatas y gramáticas

[pic 2][pic 1]

Taller

Introducción autómatas y gramáticas

Presentado por:

Diego Alejandro Barros Ballestas

CC 1082889414

Curso:

Autómatas, Gramáticas y Lenguajes

PREICA2301B020046

Docente:

Joaquín Aguilar

Programa en Tecnología en Desarrollo de Software

Facultad de Ingeniería y Ciencias Agropecuarias

Institución Universitaria Digital de Antioquia

Periodo_2023-1-B2A

Taller

1. (10%) Obtenga un AFD con el lenguaje definido en el alfabeto Σ={0,1}, que pueda generar entre otras, un subconjunto de las siguientes cadenas {010}, {01110},{01011}, {010101}, {01110}, {101}, {10001}, {1111}.[pic 3]

1. (10%) 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 {010}, {01110}, {01011}, {010101}, {01110},{101}, {10001}, {1111}.

[pic 4]

1. (20%) 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 5]

[pic 6]

1. (60%) Dada la siguiente tabla de transición hacer los siguientes puntos:

1. (5%) Indicar si es AFD o AFND y justifique su respuesta.

Rta// De acuerdo con los datos de la tabla se puede deducir que es un autómata finito no determinista AFND, debido a que su estado inicial Q0 cuando toma el valor de 0 tiene 2 transiciones, y lo mismo cuando toma el valor de 1. Adicionalmente el autómata presenta 2 estados finales tales como Q2 y Q4.

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

Rta// M= (∑, Q, S, F, 𝛿)

∑= {0,1}

Q= {Q0, Q1, Q2, Q3, Q4}

S = Q0

F= {Q2, Q4}

𝛿(Q0,0) = {Q0, Q3}         𝛿(Q0,1) = {Q0, Q1}    

             𝛿(Q1,0) = {λ}                   𝛿(Q2,1) = {Q2}  

             𝛿(Q2,0) = {Q2}               𝛿(Q2,1) = {Q2}    

             𝛿(Q3,0) = {Q4}               𝛿(Q3,1) = {λ}  

             𝛿(Q4,0) = {Q4}               𝛿(Q4,1) = {Q4}

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

[pic 7]

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

[pic 8]

1. (20%) Indique el autómata en lenguaje regular.

Q0 a Q2 = (0+1)*11(0+1)*

Q0 a Q4 = (0+1)*00(0+1)*

ER= ((0+1)*11(0+1)*) + ((0+1)*00(0+1)*)

ER = (0+1)*(00(0+1)*+11(0+1)*)

L(M) = { [pic 9]

...