Taller Automatas Finitos

TALLER AUTOMATAS FINITOS
1. Relacione los autómatas finitos con los lenguajes que producen con el alfabeto {a,b}:
a. Número par de a’s
b. Número impar dea’s
c. Número de a’s múltiplo de 3
d. Toda a está entre dos b’s
e. No hay dos a’s consecutivas
f. No contiene la subpalabra aa ni bb
Autómata | Lenguaje |
||
| |
| |
| |
| |
| |

2. Dado el siguiente AFD

i) Determinar las cadenas que son aceptadas o no por el autómata (V o F)
a) bab ____
b)aaba ____
c) aaaaaab ____
d) babababab ____
ii) Determinar si los lenguajes dados son aceptados o no por el autómata (V o F)
a) (a)* ____
b) aa*____
c) ab* ____
d) (ab)* ____
e) a*b* ____
f) a (a|b)* ____

3. Hallar un autómata determinista que reconozca los siguientes lenguajes sobre {x,y}
a)xyxxy b) xn, n > 2 c) xy+x* d) x (yx)*y e) (x|y)(yx|xyx)*

4. Dibuje un diagrama de transición que acepte la cerradura de Kleene del lenguaje aceptado por elsiguiente diagrama:

5. Dibuje el diagrama de transición que acepte la unión de los lenguajes aceptados por los diagramas siguientes:

6. Sea M = (Q, , , q0,F) un AFD con Q = {q0,q1,q2}, = {a, b}, F = {q2} y la función de transición :

a) Dibuja el autómata M
b) Traza los cómputos de M que procesan las palabras abaa,bbbabb, bababa, bbbaa
c) ¿Qué palabras de las procesadas en (b) son aceptadas por M?
7. Construya AFN por el método de Thompson para las siguientes expresiones:
a.(a|b)*
b. (a*|b*)*
c. ((e|a)b*)*
d. (b|b)*abb(a|b)*
e. (aa|b)*(a|bb)*

8. Desarrolle un autómata finito para números de punto flotante

9.