Automa a Pila

Rispondi
Avatar utente
InformateciBot
Messaggi: 314
Iscritto il: 30/09/2018, 16:33

cgiorgia_93
Ho molti dubbi sul modo in cui si costruiscono gli automi a pila.. ho guardato le slide del prof e visitato molti siti dove spiegano come si costruiscono e in particolare mi sono imbattuta in questo esercizio di cui non riesco a tirarmi fuori (non so proprio come muovermi). qualcuno mi aiuterebbe a svolgerlo?
L'esercizio è:
{ a^n b^m | n>0, m>n/2 +1}
Ringrazio in anticipo a chi vorrà aiutami

MindFlyer
L'esercizio è abbastanza semplice: idealmente all'inizio conti le [math] riempiendo lo stack a metà della "velocità", e poi conti le [math] poppando lo stack a "velocità piena". Alla fine accetti se e solo se lo stack non è vuoto. Perché funzioni esattamente, devi inizializzare il tutto mettendo come prima cosa il numero giusto di simboli nello stack.

Se hai bisogno di più dettagli, vediamo di costruire insieme una soluzione esplicita...

cgiorgia_93
Scusami non ti seguo :( ..in questo caso il numero delle b deve essere la metà delle "a" a cui sommo 1 però nn capisco come debba muovermi in questo caso...se riesci a darmi qualche dettaglio in più provo a svolgerlo da sola .

MindFlyer
Sì. Praticamente devi contare le [math], poi contare le [math], e confrontarle. Alla fine vuoi che le [math] siano meno del doppio delle [math] più 2.

Come si fa a fare questo confronto? Ovviamente bisogna usare lo stack. Prima lo si riempie di simboli per contare le [math], e poi si tolgono simboli per contare le [math]. Solo che le [math] devono togliere simboli a velocità doppia. Un'idea potrebbe essere quella di mettere un simbolo nello stack per ogni [math], e toglierne due per ogni [math]. Ma siccome puoi togliere un solo simbolo ad ogni passo, quando trovi una [math] dovresti fare un passo extra (con etichetta vuota [math]) per togliere il secondo simbolo.

Alternativamente puoi fare la cosa opposta: metti "mezzo" simbolo nello stack ad ogni [math], e togli un simbolo intero ad ogni [math]. In che senso mezzo simbolo? Diciamo che hai un simbolo [math] per indicare il mezzo, e un simbolo [math] per indicare l'intero. Allora, per esempio, la stringa [math] fa evolvere la cima dello stack così:
[math]
[math]
[math]
[math]
[math]
Se la cima dello stack contiene una [math], poppi la [math] e pushi una [math]. Altrimenti, pushi una [math]. Così alla fine hai un numero di [math] nello stack che è circa la metà delle [math] che hai visto. Poi le [math] toglieranno una [math] alla volta.

Questo è il funzionamento a grandi linee... A te la scelta della prima o della seconda alternativa. La prima sembra più semplice, ma entrambe sono istruttive.

Poi ci sono un paio di dettagli da sistemare, sia per inizializzare lo stack col numero giusto di simboli (ricorda quel +1 e quel <...), sia perché alla fine bisogna fare i controlli giusti per terminare. Oltretutto, se segui il secondo metodo, quando la cima dello stack è [math], ogni [math] dovrebbe togliere [math], togliere [math], e aggiungere [math], e questo ovviamente non si può fare. Per risolvere quest'ultimo problema, si può fare un percorso separato nell'automa, che toglie un simbolo ad ogni [math] (contraendo un "debito" di una [math]), e alla fine toglierà un simbolo extra (per estinguere il "debito").

Spero che sia abbastanza chiaro... A questo punto, scrivere il codice esplicito è un buon esercizio.
Rispondi

Torna a “[ECC] Elementi di calcolabili e complessità”