Automata de pila

Autómata Push – Down Algoritmo para generar un APD:

Unidad III Teoría de la Computación

1. Se designa el alfabeto de M comolos símbolos Terminales de G y los símbolos de Pila de M de la siguiente manera: 2. Los estados de M como i, p, q, f donde i =Estado Inicial y f = Estado de Aceptación. 3. Introduce la transición ( i, λ, λ, p , # ) 4. Introduce la transición ( p, λ, λ, q, ,S) S = Símbolo Inicial de la GIC 5. Introduce (p, λ, N, q, w) para cada regla de producción N que produzca w en G, N w, puede seruna cadena de 0 ó más símbolos, incluyendo Terminales y No Terminales. Todas las reglas de Producción de la GIC. 6. Introduce latransición (q, x, x, q, λ) para cada Terminal de x en G para cada símbolo del alfabeto M. 7. Introduce la transición de laforma:(q, λ, #, f, λ). L(G) = { z an z an bm z bm | m,n >= 0} S zMNz M aMa M z N bMb N z 1. - Σ = { a, b, z, M, N, S, # } 2.La notación(p, x, S; q, y) donde: p es el estado actual x es el símbolo del alfabeto que se lee de la cadena S es el símbolo que se extrae dela pila q es al nuevo estado que se pasa y es el símbolo que se inserta en la pila

i
3.-

p
4. λ, λ;# λ, λ; S

q
7.λ, x;#

f

i

p
5. -

q

f

6. -

λ,S ; z M N z λ,M ; a M a λ,M ; z λ,N ; b M b λ,N ; z z, z; λ a, a; λ b. b; λ