Automi a pila o pda
ragazzi io ho questo problema, non riesco a capire come passare da un linguaggio alla descrizione della tabella delle transizioni per un pda. cioè ad esempio se ho un linguaggio che è riconosciuto per pila vuota come questo : a^n b^2n e devo scrivere la tabella delle transizioni. c'è un metodo? perchè sul libro e sulle dispense non c'è niente per farlo...
Risposte
Te lo spiego a parole perché ora non mi va di stare a disegnare grafi. In pratica siccome i simboli "b" sono il doppio dei simboli "a", allora fai un grafo dove nel primo stato, per ogni simbolo "a" consumato metti due simboli sulla pila, poi al primo "b" che consumi vai nel secondo stato, dove consumi un simbolo per ogni "b".
La tabella delle transizioni semplicemente dice per ogni stato, cosa accade per ogni simbolo incontrato. Quindi per esempio nel primo stato sotto la colonna di "a" c'è il nome del primo stato (perché rimani in quello stato de incontri "a"), mentre sotto la colonna di "b" c'è il nome del secondo stato (perché se incontri "b" cambi di stato).
La tabella delle transizioni semplicemente dice per ogni stato, cosa accade per ogni simbolo incontrato. Quindi per esempio nel primo stato sotto la colonna di "a" c'è il nome del primo stato (perché rimani in quello stato de incontri "a"), mentre sotto la colonna di "b" c'è il nome del secondo stato (perché se incontri "b" cambi di stato).
ok grazie mille!!!
Accedi a tutti gli appunti
Tutor AI: studia meglio e in meno tempo