• Author / Uploaded
• Luis G. Silvestre

Citation preview

Tarea 1

Problema 1 Para cada una de las siguientes lenguajes, dibuje el diagrama de estados del autómata finito determinista que reconozca el lenguaje. Todos son sobre el alfabeto {a,b} a) La = {w/ w posee al menos 2 a’s no consecutivas}. Nota: aaba esta en La

b) Lb= {w/ w termina en ab}

c) Lc= {w/ w posee una sola b en la cuarta posiciones de derecha a izquierda}

El razonamiento para esta solución esta basada sobre las posibilidades de las ultimas 4 posiciones de cada String w y gracias a las probabilidades sabemos que existen 2 exp 4 posibilidades lo que reduce a una expresión matemática de resultados como Casos analizados y contemplados en el Lenguaje: W aceptada será igual a N mod 16 >7

d) Ld= {w/ w no posee 2 a’s consecutivas ni 2 b’s consecutivas en posiciones impares} Nota: posiciones en un string se enumeran desde 1.

e) Le= {w/ w comienza y termina con el mismo símbolo}

f) Lf= {w/ w tiene solo una b o comienza con a}

Problema 2

Para cada uno de los autómatas finitos deterministas que se presentan a continuación describa en castellano el lenguaje que reconoce. La descripción para todos los autómatas debe ser concisa y clara, si la descripción es una explicación del cómputo del AFD, esta no será considerada como respuesta correcta. a)

La = {w  0,1 / w está formado por un bloque de 0’s o 1’s seguido de un bloque de 1’s } *

Nota: Bloque se considera a símbolos idénticos consecutivos b)

Lb = {w  0,1 / w termina en 101} *

Problema 3 Convierta los siguientes AFND a su AFD equivalente con le procedimiento mostrado en clases a)

RESPUESTA AUTOMATA FINITO DETERMINISTA EQUIVALENTE

Mediante el estudio de las Transiciones para cada Estado se tiene el siguiente razonamiento:

 (q 0,  )  {q1}  (q1,  )  {}  (q 0,0)  {q 0, q1}  (q1,1)  {}  (q 0,0)  {}  (q1,1)  {q1}  ({q 0, q1},0)  {q 0, q1}  ({q 0, q1},1)  {q1} b)

RESPUESTA AUTOMATA FINITO DETERMINISTA EQUIVALENTE

Mediante el estudio de las Transiciones para cada Estado se tiene el siguiente razonamiento:

 (q 0,  )  {}  (q1,  )  {}  (q 2,  )  {}  (q3,  )  {}  (q 0,0)  {q1, q 2}  (q1,0)  {q3}  (q 2,0)  {q3}  (q3,0)  {}  (q 0,1)  {q3}  (q1,1)  {q 2}  (q 2,1)  {}  (q3,1)  {}  ({q1, q 2},0)  {q3}  ({q1, q 2},1)  {q 2}