Ejercicios Unidad 3

CIENCIAS DE LA COMPUTACION I TRABAJO PRACTICO N 2 AUTOMATAS FINITOS
2009
1) Para cada uno de los siguientes lenguajes definidos sobre el alfabeto A = {a, b, d}: a) Defnalo por comprensin; b) Disee el autmata finito determinstico que lo reconozca. i) L1 = { d, ddd, ddddd, ddddddd, } ii) L2 = {b, ab, aab, aaab, , bb, abb, aabb, aaabb, ..., bbb, abbb, aabbb, aaabbb, ..., } iii) L3 = { , abab, abababab, abababababab, ...} 2) Para cada uno de los siguientes lenguajes definidos sobre el alfabeto A = {a, b, c, d, 0, 1, 2, 3, 4, 5, 6, 7, 8, 9}, construya y defina formalmente un autmata finito determinstico que lo reconozca: a) L1 = { x / x { 0, 1, 2, 3, 4, 5, 6, 7, 8, 9 }* y x es un nmero par} b) L2 = { (ab)n c (ba)2m+1 / n 1, m 0 } c) L3 = {x / x {a, b, c}* y x no termina en ab} d) L4 = L = { x / x {0, 1, 2}* y x contiene al menos una vez cada smbolo} e) L5 = {x / x {a, b}* y x contiene la subcadena aba exactamente una vez} f) L6 = { xba / x {a, b}* y x contiene cantidad par de b y x contiene al menos tres a } g) L7 = {x / x {a, b}* y x no contiene la subcadena bab y la cantidad de ocurrencias de a es par} h) L8 = { x / x {1, 2, 3}* y x> 0 y la suma de los smbolos de x es mltiplo de 3 y x termina en 2} i) L9 = { x02k+1 / x {a, b, c}* y la longitud de x es mltiplo de 4 y x termina en bb y k 0}
3) Construya un autmata finito determinstico que, para el lenguaje L8 del ejercicio 2, cuente en unario la cantidad de ocurrencias del smbolo 2. 4) Considere el envo de mensajes de texto en un celular. Las teclas del celular estn rotuladas con nmeros y letras como se muestra en la figura. Se usarn dos dgitos para codificar cada letra: el primero es la tecla que contiene la letra y el segundo es el ndice 1, 2, 3 4 de la letra en la tecla. Por ejemplo, la secuencia 42635321 representa el mensaje hola. Modele un autmata finito que dada una secuencia de dgitos decodifique el mensaje correspondiente.
CIENCIAS DE LA COMPUTACION I 1 4 ghi 7 pqrs * 2 abc 5 jkl 8 tuv 0 3 def 6 mno 9 wxyz #
2009
5) Disee un autmata finito que tome un texto y determine la cantidad de palabras que comienzan con el prefijo in. Considere como alfabeto de entrada las letras del alfabeto castellano, los signos de puntuacin y los espacios en blanco, y como alfabeto de salida la notacin unaria. 6) Construya un autmata finito que calcule la funcin f(x) = 2x - 1 para una entrada x representada en notacin unaria. 7) Se desea modelar el comportamiento de una mquina expendedora de boletos de colectivo. El precio de cada boleto es $1. La mquina acepta monedas de $0.25 y $0.50; y devuelve el cambio necesario. Para comprar un boleto se deben introducir las monedas, y luego apretar el botn B para solicitarlo. 8) Construya el autmata finito determinstico correspondiente al siguiente autmata finito no determinstico: AFND = <{e0, e1, e2, e3}, {0, 1}, e0, , {e1, e3}> 1 e0 0 0, 1 1 e3 e1 0, 1 1 e2 0
9) Minimice los siguientes autmatas finitos a) AFD1 = <{p, q, r, s, t, u}, {a, b}, p, 1, {q, r}> 1 est definida por la siguiente tabla 1 p q r s t u a q r q t s q b p s t u u u
CIENCIAS DE LA COMPUTACION I b) AFD2 = <{e0, e1, e2, e3, e4, e5, e6, e7}, {a, b}, e0, 2, {e2, e3, e5}> 2 est definido por el siguiente diagrama de transicin de estados a e1 e0 a b b b e3 a e5 b e2 a b b e7 c) AFND3 = <{p, q, r, s}, {a, b}, p, 3, {s}> 3 est definida por la siguiente tabla 3 p q r s a {q, r, s} s b {p, q, r, s} {p, q, r, s} {p, q, r, s} {q, r, s} e4 b a a e6
2009
d) AFND4 = <{q0, q1, q2, q3, q4, q5}, {a, b, c}, q0, 4, {q2, q5}> 4 se define como 4(q0, a) = {q0, q3} 4(q0, b) = {q2} 4(q0, c) = {q5} 4(q1, a) = {q3} 4(q1, b) = {q2, q5} 4(q1, c) = {q2} 4(q2, a) = {q2} 4(q2, b) = {q1, q4} e) Autmatas construdos en el ejercicio 2. 4(q2, c) = {q4} 4(q3, a) = {q0} 4(q3, b) = {q5} 4(q3, c) = {q2, q5} 4(q4, c) = {q5} 4(q5, a) = {q2} 4(q5, b) = {q4} 4(q5, c) = {q1, q4}
EJERCICIOS ADICIONALES - Para el ejercicio 2 a) L10 = { x / x {a, b}* y los dos ltimos smbolos de x coinciden con el primer smbolo y x contiene la subcadena ba} b) L11 = { wax / w {c, d}* y los dos ltimos smbolos de w son distintos y x {0, 1}* y x termina en 00 y x es par}
CIENCIAS DE LA COMPUTACION I
2009
c) L12 ={z.u / z {7, 8, 9}* y dos posiciones consecutivas en z no contienen el mismo smbolo y u {d}* y | u | mod 2 = 0} d) L13 ={x.z / x {a, b}* y x contiene la subcadena aaa y x no contiene la subcadena bb y z {0}* y | z | mod 2 =0} e) L14 = L10* - Para el ejercicio 8 AFND = <{e0, e1, e2, e3}, {a, b, c, d}, e0, , {e2}> a, c, d d c, d a e2 e1 e0 b b e3 - Para el ejercicio 9 AFD = <{e0, e1, e2, e3, e4, e5, e6}, {a, b}, e0, , {e4, e5}>, donde est definida por la siguiente tabla e0 e1 e2 e3 e4 e5 e6 a e1 e5 e1 e1 e1 e2 e2 b e2 e3 e2 e4 e2 e1 e5 b b

Ejercicios Unidad 3

Cargado por

Copyright:

Formatos disponibles

Ejercicios Unidad 3

Cargado por

Información del documento

Derechos de autor

Formatos disponibles

Compartir este documento

Compartir o incrustar documentos

Opciones para compartir

¿Le pareció útil este documento?

¿Este contenido es inapropiado?

Copyright:

Formatos disponibles

Ejercicios Unidad 3

Cargado por

Copyright:

Formatos disponibles

CIENCIAS DE LA COMPUTACION I TRABAJO PRACTICO N 2 AUTOMATAS FINITOS

También podría gustarte