Ingeniería en Sistemas

1. Busca tres palabras aceptadas y tres palabras rechazadas por cada uno de los siguientes autómatas mostrando el cómputo que las procesa. Determina cuáles de ellos están totalmente especificados. ¿Sabrías cuál es el lenguaje aceptado por cada uno de ellos?

a) a+b aceptadas { ab,aab,aaab} No aceptadas {aba,abb,ba,bb}

b) a(ba)* aceptadas {a, aba, ababa} No aceptadas {abb,bb,ba,}

2. Construye expresiones regulares para cada uno de los siguientes autómatas:

a) b* a+a {aa,baa,bbaa,bbaaa,bbbaa,bbaaaa }b) a[a(ab)]* {a, aaa,aaaaa,aabab,aaaaaaa,aababab}

3. En la siguiente figura se representan dos autómatas finitos A1 y A2, que aceptarán sendos lenguajes L1 y L2. Hallar: El autómata finito determinista mínimo que reconozca la unión de los lenguajes L1 y L2.

1

Ingeniería en Sistemas

4. Dada la expresión regular construir el AFD.

5. Dada la expresión regularconstruir el AFD.

2

Ingeniería en Sistemas

6.

7.

3

Ingeniería en Sistemas

a) b*ab {, bab, bbab} ACEPTADAb) aa(ab)b* {aab, aabb} no aceptadac) [aa(ab)]*b* {, aaa, aaaaaab, aabb} ACEPTADAd) b*(ab)* {, bab, bbab, babababab} aceptadae)

4

Ingeniería en Sistemas

a) {, a, aa, aaa} no aceptadab) {a,aa,aaa} no aceptadac) {a,ab,abb} no aceptadad) {,ab,abab,ababab} aceptadae) {,a,b,ab,aab,abb} no aceptadaf) {a,aa,ab,aaa,abb,aaaa} no aceptada

8.

I. (01)II. (01)21*0

III. (01)21*210IV. (01)(21*210)*V. (01)21*2110

VI. (01)(21*2110)*

5

Ingeniería en Sistemas

VII. (01)21*20

(01) [(01)21*0] [(01)21*210] [(01)(21*210)*] [(01)21*2110] [(01)(21*2110)*] [(01)21*20]

6