in questo modulo inizieremo a introdurre formalmente gli automi a pila definendo le diverse componenti che lo compongono E attraverso queste componenti dandone la definizione formale prima di dare la definizione Però analizzeremo alcuni esempi per introdurre la notazione in modo informale e cercare di capire al meglio come gli automi funzionano vediamo quindi un esempio consideriamo il linguaggio a all n b ^ n con N Mag 0 che abbiamo visto non essere riconoscibile da un automa a stati finiti questo linguaggio è riconoscibile attraverso un automa pila in quanto possiamo utilizzare la pila per ricordare il numero di alette e confrontare poi questo numero di a con il numero di B mentre le leggiamo l'idea Cioè è quella di salvare una a sulla pila per ogni a Letta nel nastro d'ingresso e consumare cioè leggere una a dalla pila per ogni B letta dal nastro d'ingresso se alla fine della scansione dell'intera stringa la pila è vuota significa che il numero di a era uguale al numero di B per cui vogliamo riconoscere la stringa Altrimenti se la stringa non è vuota o se quando la stringa è vuota o ancora altri simboli da leggere non vogliamo riconoscere la stringa perché significa che il numero di a e il numero di B non è lo stesso l'automa in figura rappresenta l'idea che abbiamo appena spiegato la notazione sulle transizioni è la seguente a è il simbolo letto in ingresso z0 è il simbolo letto sulla pila Cioè se ho a in ingresso e z0 sulla fila posso prendere questa transizione e se prendo la transizione Allora scriverò sulla fila al posto di z0 che è stato consumato z0 B cioè adottiamo la convenzione che il simbolo che va più in alto sulla si troverà a sinistra e quello che va più in basso si troverà a destra quindi mi muovo dallo stato iniziale q0 verso Q1 se leggo una a quando ho la pila vuota e in questo caso segno sulla pila una b oltre allo z0 notate che mi muovo dallo stato iniziale solo con una a perché la stringa vuota non è accettata in quanto n deve essere maggiore di 0 quindi la stringa più piccola che fa parte del linguaggio è la stringa AB e seconda cosa le a devono essere tutte prima delle i cioè le stringhe che fanno parte del mio linguaggio sono le stringhe del tipo AB aab BB 3A 3B e così via dopo la prima a Vado nello stato Q1 nello stato Q1 resto finché ho a in ingresso alla seconda A che leggo in ingresso dopo la prima cioè quella che mha portato da q0 a Q1 avrò B in cima alla pila in tal caso riscrivo il b perché non mi voglio dimenticare di aver letto la prima a e aggiungo una a per ricordarmi anche della seconda a Letta da lì in poi per ogni a Letta continuerò ad aggiungere a se ho avuto più di 2A quando leggerò la prima B avrò a grande in Cim alla pila Allora con quella B mi sposterò da Q1 a Q2 consumando la a cioè sostituendo a con la stringa vuota come dire che non metto nessun simbolo sulla pila ma visto che ho letto a a è stata tolta Quindi questa operazione Riduce la dimensione della pila di 1 se quando leggo la prima B ho B grande sulla pila vuol dire che ho letto prima di questa B soltanto una a per cui mi muovo direttamente sullo stato finale Q3 ad indicare che se non ho più niente in ingresso posso accettare la parola infatti la mia condizione di accettazione era Sono in uno stato finale e ho finito l'ingresso per cui supponete di avere una b in più quindi di avere un linguaggio del tipo A B B è vero che con la prima B mi muovo in Q3 ma in Q3 non posso più muovermi e non ho finito di leggere l'ingresso quindi la stringa giustamente non verrà accettata torniamo al caso in cui avevo avuto più di una a Cioè in cui una volta ricevuta la prima b o a sulla pila in quel caso mi muovevo in Q2 in Q2 continuo a consumare le a sulla pila per ogni biletta con la stessa operazione che da Q1 mi aveva portato in Q2 come l'op che da Q1 mi ha portato in Q3 quando ho B in ingresso e B sulla pila vuol dire che quella B è esattamente l'ennesima dove n il numero di a che ho letto per cui mi sposto nello stato finale in questo caso validano le stesse considerazioni che avevo fatto muovendomi da Q1 a Q3 Cioè se dopo questa b o altre B sarò Sì in uno stato finale ma non potrò accettare la parola perché non ho finito di scand l'ingresso simuliamo la nostra macchina con la stringa AAA bbb cioè Supponiamo che questa stringa sia nel nastro di ingresso inizialmente l'organo di controllo si troverà in q0 cioè sarò nello stato iniziale dell'automa la testina del nastro di inresso si troverà in corrispondenza della prima in ingresso cioè della a e la pila sarà vuota cioè conterrà soltanto z0 avendo ha in ingresso z0 sulla pila potrò prendere la transizione che da q0 mi porta in Q1 questa transizione farà sì che io rimetterò lo z0 lettio sulla pila aggiungendo sopra adesso una b e farà avanzare la testina sul Nasso di ingresso Ora mi trovo in Q1 in Q1 con la A in in adesso avendo B sulla pila prendo la transizione AB che scrive sulla pila prima b e poi a e mi sposterò in avanti sul nastro in ingresso poi con l'altra a prenderò la transizione a a cioè la transizione che da Q1 mi pte in Q1 e che sostituisce la la a Letta con 2A ora sul nastro in ingresso ho b e e sulla pila o a per cui prenderò la transizione che da Q1 mi porta in Q2 cancellando la a dalla pila e avanzando sul nastro in ingresso Ora sono in Q2 e ho B sul nastro d' ingresso e a sulla pila per cui prenderò la transizione che da Q2 mi porta in Q2 consumando la a e avanzando sul nastro ingresso sono nuovamente in Q2 con B in ingresso e B sulla pila per cui ora prenderò la transizione che da Q2 mi porta in Q3 consumando la biletta e avanzando sul nastro in ingresso mi trovo in uno stato finale e ho completamente letto il nastro in ingresso per cui la parola è accettata esattamente come mi aspettavo ora che abbiamo un'idea più chiara di come sono fatti gli automi a pila in modo informale possiamo darne la definizione formale un automa a Pila è una tupla composta da sette elementi q i gamma Delta q0 z0 ed F dove Q è un insieme finito di stati i è l'alfabeto di ingresso cioè l'alfabeto su cui sono definite le stringhe che leggo dal nastro in ingresso gamma è l'alfabeto della pila cioè l'alfabeto dei simboli che uso per memorizzare informazioni sulla pila Delta è la funzione di transizione q0 appartenente a Q è lo stato iniziale z0 appartenente a gamma è il simbolo iniziale sulla pila ed F contenuto coincidente con Q è l'insieme di stati finali la funzione di transizione Delta è definita a partire da uno Stato Q leggendo un simbolo in ingresso i o il simbolo ep che vedremo poi cosa vuol dire è un simbolo della pila in uno stato q e una stringa di gamma eventualmente vuota Cioè è la funzione Delta che va da q * i un * gamma in Q Star la funzione di transizione si rappresenta graficamente come nella figura riportata sul lucido cioè come un arco che collega due stati etichettato con il simbolo che causa la transizione in ingresso virgola sulla pila barra la stringa che scriverò sulla pila una volta presa la transizione Notiamo che nella nostra definizione di automa pila q i q0 f sono definiti esattamente come negli automi stati finiti e che Delta pur essendo definita diversamente perché in questo caso tiene conto della pila è anche in questo caso una funzione parziale Notiamo poi che il simbolo z0 è molto utile perché ci permette di identificare in modo semplice la fine della pila cioè quando la pila è vuota ma non è essenziale eliminarlo permetterebbe di dare magari in modo un po' più complesso e meno intuitivo le stesse definizioni ci rimane da capire Quindi Che cos'è eps epsil vuol dire Non leggere niente Cioè io faccio una transizione da Q se o a sulla pila con ep senza le leggere dal nastro d'ingresso cioè le transizioni con ep al posto del simbolo in ingresso chiamate Epsilon mosse sono transizioni spontanee notate che fare un epsil mossa non dipende dallo stato del nastro in ingresso cioè un Epsilon mossa non significa che il nastro in ingresso è vuoto ma un Epsilon mossa può avvenire sia che il nastro in ingresso sia a vuoto sia che ci siano dei simboli se ovviamente la condizione sulla Pila è verificata vediamo come l'uso delle Epsilon mosse può semplificare l'automa per riconoscere a ^ n b ^ n nell' automa che avevamo visto precedentemente per riconoscere questo linguaggio avevamo marcato sulla pila la prima a Letta con una b invece che con una a come avevamo fatto per tutte le altre con l'uso delle Epsilon mosse non abbiamo più bisogno di questo stratagemma per riconoscere la teoricamente ultima B infatti possiamo ricordarci tutte le a col simbolo a e consumare una a per ogni biletta aggiungiamo poi una transizione marcata con ep cioè un EP mossa da Q2 in Q3 quando sulla pila c'è z0 cioè quando ho già letto tante B quante le a che avevo letto in precedenza ep non vuol dire come abbiamo già detto stringa vuota per cui io prenderò questa transizione sia che in ingresso io abbia ancora qualcosa da leggere sia che io non abbia niente da leggere però accetterò la parola una volta arrivata in Q3 soltanto se non ho più niente da leggere Cioè se effettivamente il numero di a è uguale al numero di B per cui questo automa riconosce esattamente a alla n b all n