- Gli automi pushdown sono un modo per implementare un CFG nello stesso modo in cui progettiamo DFA per una grammatica normale. Un DFA può ricordare una quantità finita di informazioni, ma un PDA può ricordarne una quantità infinita.
- Gli automi pushdown sono semplicemente un NFA arricchito con una 'memoria stack esterna'. L'aggiunta dello stack viene utilizzata per fornire una funzionalità di gestione della memoria last-in-first-out agli automi Pushdown. Gli automi pushdown possono memorizzare una quantità illimitata di informazioni nello stack. Può accedere a una quantità limitata di informazioni sullo stack. Un PDA può spingere un elemento in cima alla pila e far staccare un elemento dalla cima della pila. Per leggere un elemento nello stack, gli elementi in cima devono essere estratti e vanno persi.
- Un PDA è più potente di un FA. Qualsiasi linguaggio che possa essere accettabile da FA può essere accettabile anche da PDA. PDA accetta anche una classe di linguaggio che non può essere accettata nemmeno da FA. Pertanto il PDA è molto più superiore all’FA.
Componenti del PDA:
Nastro di ingresso: Il nastro di input è diviso in molte celle o simboli. La testina di input è di sola lettura e può spostarsi solo da sinistra a destra, un simbolo alla volta.
Controllo finito: Il controllo finito ha un puntatore che punta al simbolo corrente che deve essere letto.
Pila: La pila è una struttura in cui possiamo spingere e rimuovere gli oggetti solo da un'estremità. Ha una dimensione infinita. Nel PDA, lo stack viene utilizzato per archiviare temporaneamente gli elementi.
Definizione formale di PDA:
Il PDA può essere definito come un insieme di 7 componenti:
Q: l’insieme finito degli stati
∑: il set di input
C: un simbolo dello stack che può essere spinto ed estratto dallo stack
q0: lo stato iniziale
numero Java da stringa
CON: un simbolo iniziale che è in Γ.
F: un insieme di stati finali
D: funzione di mappatura utilizzata per passare dallo stato corrente allo stato successivo.
Descrizione istantanea (ID)
L'ID è una notazione informale di come un PDA calcola una stringa di input e decide se la stringa viene accettata o rifiutata.
Una descrizione istantanea è una tripla (q, w, α) dove:
Q descrive lo stato attuale.
In descrive l'input rimanente.
ordinamento dell'array Java
UN descrive il contenuto dello stack, in alto a sinistra.
Notazione del tornello:
Il segno ⊢ descrive la notazione del tornello e rappresenta una mossa.
Il segno ⊢* descrive una sequenza di mosse.
Per esempio,
(p, b, T) ⊢ (q, w, α)
Nell'esempio precedente, durante la transizione dallo stato p allo stato q, il simbolo di input 'b' viene consumato e la parte superiore dello stack 'T' è rappresentata da una nuova stringa α.
Esempio 1:
Progettare un PDA per accettare una lingua aNB2n.
Soluzione: In questo linguaggio, n numero di a dovrebbe essere seguito da 2n numero di b. Quindi, applicheremo una logica molto semplice, ovvero se leggiamo una singola 'a', inseriremo due a nello stack. Non appena leggiamo 'b', per ogni singola 'b' dovrebbe essere estratta dalla pila solo una 'a'.
logica del primo ordine
L'ID può essere costruito come segue:
δ(q0, a, Z) = (q0, aaZ) δ(q0, a, a) = (q0, aaa)
Ora, quando leggiamo b, cambieremo lo stato da q0 a q1 e inizieremo a far apparire la corrispondente 'a'. Quindi,
δ(q0, b, a) = (q1, ε)
Pertanto questo processo di estrazione della 'b' verrà ripetuto a meno che non vengano letti tutti i simboli. Si noti che l'azione di scoppio avviene solo nello stato q1.
δ(q1, b, a) = (q1, ε)
Dopo aver letto tutte le b, dovrebbero essere spuntate tutte le a corrispondenti. Quindi quando leggiamo ε come simbolo di input non dovrebbe esserci nulla nello stack. Quindi la mossa sarà:
δ(q1, ε, Z) = (q2, ε)
Dove
per il ciclo in c
PDA = ({q0, q1, q2}, {a, b}, {a, Z}, δ, q0, Z, {q2})
Possiamo riassumere l'ID come:
δ(q0, a, Z) = (q0, aaZ) δ(q0, a, a) = (q0, aaa) δ(q0, b, a) = (q1, ε) δ(q1, b, a) = (q1, ε) δ(q1, ε, Z) = (q2, ε)
Ora simuleremo questo PDA per la stringa di input 'aaabbbbbb'.
δ(q0, aaabbbbbb, Z) ⊢ δ(q0, aabbbbbb, aaZ) ⊢ δ(q0, abbbbbb, aaaaZ) ⊢ δ(q0, bbbbbb, aaaaaaZ) ⊢ δ(q1, bbbbb, aaaaaZ) ⊢ δ(q1, bbbb, aaaaZ) ⊢ δ(q1, bbb, aaaZ) ⊢ δ(q1, bb, aaZ) ⊢ δ(q1, b, aZ) ⊢ δ(q1, ε, Z) ⊢ δ(q2, ε) ACCEPT
Esempio 2:
Progettare un PDA per accettare una lingua 0N1M0N.
Soluzione: In questo PDA, n numero di 0 sono seguiti da un qualsiasi numero di 1 seguito da n numero di 0. Quindi la logica per la progettazione di tale PDA sarà la seguente:
Metti tutti gli 0 in pila quando incontri i primi 0. Quindi se leggiamo 1, non fare nulla. Quindi leggi 0 e, ad ogni lettura di 0, estrai uno 0 dallo stack.
Ad esempio:
Questo scenario può essere scritto nella forma ID come:
δ(q0, 0, Z) = δ(q0, 0Z) δ(q0, 0, 0) = δ(q0, 00) δ(q0, 1, 0) = δ(q1, 0) δ(q0, 1, 0) = δ(q1, 0) δ(q1, 0, 0) = δ(q1, ε) δ(q0, ε, Z) = δ(q2, Z) (ACCEPT state)
Ora simuleremo questo PDA per la stringa di input '0011100'.
δ(q0, 0011100, Z) ⊢ δ(q0, 011100, 0Z) ⊢ δ(q0, 11100, 00Z) ⊢ δ(q0, 1100, 00Z) ⊢ δ(q1, 100, 00Z) ⊢ δ(q1, 00, 00Z) ⊢ δ(q1, 0, 0Z) ⊢ δ(q1, ε, Z) ⊢ δ(q2, Z) ACCEPT