Solucion a examenes y problemario teoria de automatas

Instituto Politécnico Nacional
Escuela Superior de Ingeniería
Mecánica y Eléctrica
Unidad Culhuacán




Teoría de Autómatas
4CV25

Alumnos:

García Romero Jorge Luis
Sarabia López Edgar


Profesor:
Vásquez Fernández Eduardo


Tareas e investigaciones del tercer parcial


22/01/21

Ciclo:21-1

, Ejercicio 6.1.1. Suponga que el autómata a pila P = ( { q, p }, { 0,1 }, { Z0,X }, 𝛿, q,
Z0,{ p } ) tiene la siguiente función de transición:

1. 𝛿 (q,0,Z0) = {(q,XZ0)}.
2. 𝛿 (q,0,X) = {(q,XX)}.
3. 𝛿 (q,1,X) = {(q,X)}.
4. 𝛿 (q,ε ,X) = {(p,ε )}.
5. 𝛿 (p,ε ,X) = {(p,ε )}.
6. 𝛿 (p,1,X) = {(p,XX)}.
7. 𝛿 (p,1,Z0) = {(p,ε )}.
Partiendo de la descripción instantánea inicial (q,w,Z0), especifique todas las ID
alcanzables cuando la entrada w es:

a) 01.
(q,01,Z0)

(q,1,XZ0)

(q,ε,XZ0) (p,1,Z0)

(p, ε,Z0) (p, ε, ε)


b) 0011.
(q,0011,Z0)

(q,011,X Z0)

(q,11,XX Z0)

(q,1,XXX Z0) (p,11,X Z0)

(q, ε ,XXXX Z0) (p,1, Z0)

(p, ε,Z0) (p, ε, ε)