Teorema: Un linguaggio è acontestuale esiste un automa a pila (PDA) che lo riconosce.

Dimostrazione del lemma

Se per una qualche CFG , allora esiste un PDA tale che

Intuizione

Nel concreto, per dimostare questo lemma, bisogna trovare una strategia universale per costruire un PDA partendo da una qualsiasi CFG.

L’idea è che il PDA deve:

  1. Mettere il simbolo $ all’inizio dello stack.
  2. Fare il pop sullo stack e agire di conseguenza:
    1. Se il simbolo estratto è un simbolo di variabile , creare non deterministicamente tanti rami di computazione per quante regole esistono e sostituisci con ogni , poi ripetere il loop.
    2. Se la cima dello stack ha un simbolo terminale, leggere il prossimo simbolo di input e compararlo ad esso:
      1. Se coincidono, ripeti il loop.
      2. Se non coincidono, rifiuta la stringa e scarta questo ramo di computazione.
    3. Se la cima dello stack ha il simbolo $, entra nello stato accept. Questo accetta la stringa completa in input, se già letta per intero.

Notazioni ausiliarie

È utile definire una notazione per scrivere insieme più passi della funzione di transizione, espandendola per poter pushare un’intera stringa sullo stack in un singolo step. per fare ciò bisogna introdurre degli stati intermedi che corrispondono ai push dei singoli simboli.

Come la notazione per il singolo carattere (“se ricevi in input e sulla cima dello stack c’è , allora fai pop e pusha ”), la notazione per la stringa completa, ad esempio “xyz”, sarà , cioè “se ricevi in input il simbolo e sulla cima dello stack c’è il simbolo , allora pusha , poi , poi ” (da destra a sinistra).

Riassumendo:

Sarà eseguita passando per due stati ausiliari:

  1. , cioè
  2. , cioè
  3. , cioè

Dimostrazione formale

Il vantaggio di avere la notazione abbreviata per il push di stringhe intere ci permette di definire esplicitamente solo tre stati, tutti quelli intermedi () saranno impliciti. Segue che gli stati di sono .

Si possono definire i passi del loop come casi della definizione della funzione di transizione:

  1. \delta(q_{\text{start}}, \varepsilon, \varepsilon) = \{(q_{\text{loop}}, S\)}$
  2. Loop:
    1. Variabile in cima: , dove è una regola della CFG .
    2. Terminale in cima:
    3. $ in cima: \delta(q_{\text{loop}}, \varepsilon, \) = {(q_{\text{accept}}, \varepsilon)}$

Dimostrazione del lemma

Se per una qualche PDA , allora esiste un CFG tale che

Intuizione

Nel concreto, per dimostare questo lemma, bisogna trovare una strategia universale per definire una CFG le cui regole simulano un dato PDA, cioè trovare una che genera ogni stringa che, data in input al PDA , lo porta dallo stato iniziale allo stato di accept una volta processata per intero.

L’idea è di trasformare le transizioni tra stati di in regole di .

Implementiamo ciò con regole nel formato ” tutte le stringhe che possono portare dallo stato allo stato lasciando lo stack invariato alla fine della loro esecuzione e funzionando indipendentemente dai contenuti già presenti sullo stack” (cioè svuotando lo stack di tutti i simboli aggiunti nel cammino tra a ).

Semplificazione necessaria di

Senza perdita di generalità, semplifichiamo in modo che:

  • Abbia un solo stato di accettazione;
  • Svuoti lo stack prima di accettare;
  • Faccia push o pop di esattamente un simbolo in ogni transizione, senza fare entrambi insieme: si rimpiazza ogni transizione da a che faccia entrambe le cose con due transizioni da a uno stato di appoggio (la quale fa push) e dallo stato di appoggio a (la quale fa pop). Inoltre si rimpiazza ogni transizione da a che non fa ne pop ne push con due transizioni da a uno stato di appoggio (la quale fa push di un simbolo arbitrario) e dallo stato di appoggio a (la quale fa pop).

Date queste semplificazioni, possiamo assumere che la prima transizione compiuta da ricevendo una stringa in input è un push, e l’ultima è un pop. Quindi, per costruzione, il contenuto dello stack rimane invariato tra la prima e ultima mossa.

L’ultimo simbolo su cui si fa pop può essere:

  • Il simbolo pushato all’inizio di : significa che lo stack è vuoto solo all’inizio e alla fine della processazione della stringa . Modelliamo ciò con la regola , dove è lo stato successivo di e è lo stato precedente di e dove è il primo simbolo di e l’ultimo.
  • Un altro simbolo: significa che, in qualche istante intermedio della computazione, lo stack è stato svuotato completamente per poi essere stato popolato da nuovi simboli. Modelliamo ciò con la regola , dove è lo stato intermedio in cui lo stack si svota completamente.

Ora bisogna provare che quanto detto sopra funziona, dimostrando che genera se e solo se porta da con lo stack vuoto a con lo stack vuoto.

dadimostrare

Dimostrazione formale

Definizioni del PDA e della CFG

Definizione di ogni regola della CFG

  • L’ultimo pop è sul simbolo del primo push:
  • L’ultimo pop è su un’altro simbolo:
  • Regola banale: