Automata a Pila

Introduzione

• Definizione delle componenti di un automa a pila
• Uso di esempi per capire le nozioni informali e il funzionamento

Esempio: Linguaggio a^n b^n con n >= 0

• Non riconoscibile da automa a stati finiti
• Riconoscibile da un automa a pila perché:
  • Si usa la pila per ricordare il numero di a
  • Si confronta il numero di a con quello di b mentre si leggono
• Funzionamento:
  1. Salvare una a sulla pila per ogni a letta dal nastro d'ingresso
  2. Consumare una a dalla pila per ogni b letta dal nastro d'ingresso
  3. Se al termine la pila è vuota, il numero di a è uguale al numero di b e si accetta la stringa
  4. Altrimenti, se la pila non è vuota o ci sono simboli da leggere, non si accetta la stringa

Notazione delle Transizioni

• a / Z0 → Z0 B (dallo stato q0 a q1 leggendo a quando la pila è vuota e scrivendo Z0 B sulla pila)
• Convenzione: simbolo in alto a sinistra, simbolo in basso a destra
• Esempio specifico:
  • Da q0 a q1 con a e pila vuota (Z0), scrive Z0 B sulla pila
  • La stringa più piccola del linguaggio è a^n b^n con n >= 0, quindi non si accetta la stringa vuota
  • q1 finché si legge a, scrivere a sulla pila
  • Da q1 a q2 leggendo b, consumare a dalla pila
  • Da q2 a q3 leggendo b, consumare b dalla pila

Caso Specifico: Stringa a^3 b^3

1. Stato iniziale q0 con nastro vuoto (Z0 sulla pila)
2. Transizione a q1 leggendo la prima a e scrivendo Z0 B
3. Resta in q1, legge altre a e scrive a sulla pila
4. Da q1 a q2 leggendo b, consumare a dalla pila
5. Continua a consumare a in q2 per ogni b letta
6. Da q2 a q3 con pila vuota (Z0), accetta la stringa

Definizione Formale degli Automi a Pila

• Tupla composta da sette elementi: {Q, Σ, Γ, Δ, q0, Z0, F}
  • Q: insieme finito di stati
  • Σ: alfabeto di ingresso
  • Γ: alfabeto della pila
  • Δ: funzione di transizione
  • q0: stato iniziale
  • Z0: simbolo iniziale sulla pila
  • F: insieme di stati finali
• Funzione di transizione Δ definita come:
  • Da uno stato q leggendo un simbolo di ingresso i o il simbolo ε su un simbolo della pila
  • Transizione: q * Σ * Γ → Q * Γ*
• Grafica transizione: arco con etichetta input, pila / output

Transizioni Epsilon (ε-mosse)

• Non leggono niente dal nastro d'ingresso
• ε-mosse può avvenire con nastro vuoto o con simboli
• Simplifica l'automa per a^n b^n senza simboli di marcatura
  • Transizione ε da q2 a q3 con pila vuota (Z0) per accettare se pila Z0

Conclusioni

• Uso di epsilon transizioni per semplificare gli automi
• Automata a pila riconosce esattamente a^n b^n