PDA e Lignuaggi Context-Free

[BHK1]

Spero che qualcuno conosca l'argomento e possa darmi una mano.
Ho questo esercizio:
Definire un PDA per ${a^ib^jc^k|j=k}$
Definito l'automa $P=(Q,E,Gamma,delta,q_0,Z_0)$ quindi un automa che accetta per pila vuota.

$P=({q_0,q_1,q_2},{a,b,c}{B},delta,{q_0}{Z_0})$

Ho definito queste transazioni:
$delta(q_0,a,Z_0)={q_0,Z_0}$
$delta(q_0,b,Z_0)={q_1,B}$
$delta(q_1,b,alpha)={q_1,Balpha}
$delta(q_1,c,Balpha)={q2,alpha}$
$delta(q_2,c,Balpha)={q_2,alpha}$
$delta(q_2,c,B)={q_2,epsilon}$

[Rggb1]

Premesso che sono passati diversi eoni da quando facevo 'sti esercizi , e magari uno più fresco di studi sarebbe meglio, vediamo:
- quando incontri 'a' da q0 la passi senza mettere nulla nello stack;
- quando incontri 'b' da q0 passi a q1 e metti 'b' nello stack; prosegui per ogni 'b'
- quando incontri 'c' passi a q2 e togli 'b' dallo stack; prosegui per ogni 'c'.

L'automa accetta su q2 con stack vuoto.

Nelle tue transizioni, usando la tua notazione, comprendo $B alpha$ come "simbolo 'b' in cima allo stack". A me sembra corretto.

PS. Hai controllato con JFlap?

[BHK1]

Si $alpha$ indica gli altri simboli nella pila, che potrebbe contenere anche $epsilon$, su jflap funziona.

[BHK1]

come posso convertirlo in un in un PDA che accetta per stato finale?
$P=(Q,E,Gamma,delta,q_0,Z_0,{q_f})$
$P=({q_0,q_1_q_2,q_f},{a,b,c},{B},delta,{q_0}{Z_0,X_0},{q_f})$

[Rggb1]

Informalmente, per ogni transazione da $q_x$ a $q_y$ per un certo simbolo, costruisci tante transizioni quanti sono i simboli nello stack coinvolti; il metodo viene esemplificato molto chiaramente qui:
http://en.wikipedia.org/wiki/Pushdown_a ... .28GPDA.29

[BHK1]

Non ci ho capito molto, provo a convertirlo
$P=(Q,E,Gamma,delta,p_0,Z_0,{p_f})$
$P=({q_0,q_1,q_2,p_0},{a,b,c},{B,Z_0},delta,{p_0}{X_0},{p_f})$

Transazioni:
$(p_0,a,X_0)=(q_0,Z_0X_0)$
$(q_0,a,Z_0alpha)=(q_0,Z_0alpha)$
$(q_0,b,Z_0)=(q_1,BZ_0alpha)$
$(q_1,b,Balpha)=(q_1,BBalpha)$
$(q_1,c,Balpha)=(q_2,alpha)$
$(q_2,c,Balpha)=(q_2,alpha)$
$(q_2,epsilon,Z_0alpha)=(q_f,alpha)$
$(p_f,epsilon,X_0)=(p_f,epsilon)$