• Author / Uploaded
• Anita Gonzalez

Citation preview

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

b) a(ba)*

aceptadas No aceptadas

{aba,abb,ba,bb}

{a, aba, ababa} {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(ab)]* {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 regular

2

Ingeniería en Sistemas

construir el AFD.

6.

7.

3

Ingeniería en Sistemas

a) b*ab

{, bab, bbab}

ACEPTADA

b) aa(ab)b*

{aab, aabb}

no aceptada

c) [aa(ab)]*b*

{, aaa, aaaaaab, aabb}

ACEPTADA

d) b*(ab)*

{, bab, bbab, babababab}

aceptada

4

Ingeniería en Sistemas

a) {, a, aa, aaa}

no aceptada

b) {a,aa,aaa}

no aceptada

c) {a,ab,abb}

no aceptada

d) {,ab,abab,ababab}

aceptada

e) {,a,b,ab,aab,abb}

no aceptada

f)

no aceptada

{a,aa,ab,aaa,abb,aaaa}

8.

I. II. III. IV. V. VI. VII.

(01) (01)21*0 (01)21*210 (01)(21*210)* (01)21*2110 (01)(21*2110)* (01)21*20

(01)  [(01)21*0]  [(01)21*210]  [(01)(21*210)*]  [(01)21*2110]  [(01)(21*2110)*]  [(01)21*20]

5