Teoría de la computación

EVIDENCIA PARCIAL

CURSO: TEORÍA DE LA COMPUTACIÓN

Docente: Ing. Juan Carlos Gómez Boza

1. Indique si el primer autómata (AFD)

[pic 1]

Es equivalente al segundo autómata (AFD)

[pic 2]

• Para poder realizar la demostración realice la Matriz de Transición del primer autómata (AFD que se va a reducir)
• Además para que sea más sencillo de realizar puede colocar o dividir los estados que son de aceptación y los que no lo son:

Q/R=[ C0={A,B,C,D},  C1={E} ]

Y en base a ello realizar los despejes y armar el autómata resultante del primero.

[pic 3]

                                        [pic 4]

[pic 5][pic 6][pic 7][pic 8][pic 9][pic 10][pic 11][pic 12][pic 13][pic 14][pic 15][pic 16][pic 17][pic 18][pic 19][pic 20][pic 21][pic 22][pic 23][pic 24][pic 25][pic 26][pic 27][pic 28][pic 29][pic 30][pic 31][pic 32][pic 33][pic 34][pic 35][pic 36][pic 37]

[pic 38]

        [pic 39]

[pic 40]

[pic 41]

[pic 42]

1. Minimizar el siguiente AFD aplicando la eliminación de estados.

[pic 43]

• Indique al final el autómata resultante y también la expresión regular correspondiente.
• Indique la matriz de transición.
• Proceda a realizar su implementación en código (puede aplicar o reutilizar el código del autómata que se proporcionó en clase).

[pic 44]

[pic 45]

[pic 46]

[pic 47]

Estados de aceptación:

W= {E, F}

Estados no aceptados:

X= {A, B, C, D}        

Tabla de transición para X

Tablas de transiciones de W, X

Tabla de W (estados de aceptación)                             Tabla de X(estados no aceptados)

Nuevo esto  y:

Y={b,c}

Construir las tablas de transición de los estados w,x,y

Tabla de W                                                                                     Tabla de X

...