• Author / Uploaded
• TheBodkins

Citation preview

Instituto Tecnológico de Parral Ingeniería en sistemas computacional Lenguajes y Autómatas 1

Conversión de AFND a AFD

Alumno: David Hernández Escárcega 17410414 Maestra: M.S.C. Jessica Ivette Rodríguez Montoya

Ejercicio 1 Nueva variable

Variable actual

a

b

A

q0

q0,q2

q0

B

q0,q2

q0,q2,q3

q0

C

q0,q2,q3

q0,q2,q3,q1

q0

D

q0,q2,q3,q1

q0,q2,q3,q1

q0,q1

E

q0,q1

qo,q2,q1

q0,q1

F

q0,q2,q1

q0,q2,q3,q1

q0,q1

Ejercicio 2 Nueva variable

Variable actual

a

A

q0

q1,q2

b

B

q1,q2

C

q3

q1,q2

q3

Ejercicio 3 Nueva variable

Variable actual

a

A

q0

q1

B

q1

q2,q3

C

q2,q3

D

q3,q0

b

q3,q0 q1

q0

b

Ejercicio 4 Nueva variable

Variable actual

a

A

q0

q1,q2,q3

B

q1,q2,q3

q4

C

q4

q3

D

q1,q2,q4

q3

E

q3

q4

q1,q2,q4

q4,q2,q1

Ejercicio 5 Nueva variable

Variable actual

a

b

A

q0

q1

q3

B

q1

q3

q2

C

q3

q1,q2

D

q2

E

q1,q2

q3

q2

Ejercicio 6 Nueva variable

Variable actual

a

A

q0

q1,q3

B

q1,q3

q2

C

q2

q1

D

q0,q1

q1,q2,q3

E

q1

q2

F

q1,q2,q3

q1,q2

G

q1,q2

q1,q2

b

q0,q1

q1

Conclusión Me di cuenta al realizar este trabajo, que puede llegar a surgir confusión si se usan nuevamente las mismas variables, y sobre todo si la tabla de transiciones es muy grande, por lo cual decidí asignar nuevas variables a los nodos, lo cual se me hizo menos confuso, además me di cuenta, que en algunas ocasiones el autómata puede simplificarse al momento de realizar la conversión, en otras ocasiones se puede hacerse más grande, sin embargo me di cuenta que muchas veces estos se pueden ser simplificados y que no dejen de ser deterministas.