- Els autòmats pushdown són una manera d'implementar un CFG de la mateixa manera que dissenyem DFA per a una gramàtica normal. Un DFA pot recordar una quantitat finita d'informació, però un PDA pot recordar una quantitat infinita d'informació.
- L'autòmat Pushdown és simplement un NFA augmentat amb una 'memòria de pila externa'. L'addició de la pila s'utilitza per proporcionar una capacitat de gestió de memòria d'últim en entrar, primer en sortir als autòmats Pushdown. Els autòmats pushdown poden emmagatzemar una quantitat il·limitada d'informació a la pila. Pot accedir a una quantitat limitada d'informació a la pila. Una PDA pot empènyer un element a la part superior de la pila i treure un element de la part superior de la pila. Per llegir un element a la pila, els elements superiors s'han de treure i es perden.
- Un PDA és més potent que FA. Qualsevol idioma que pugui ser acceptat per FA també pot ser acceptat per PDA. PDA també accepta una classe de llenguatge que ni tan sols pot ser acceptada per FA. Així, PDA és molt més superior a FA.
Components PDA:
Cinta d'entrada: La cinta d'entrada es divideix en moltes cel·les o símbols. El capçal d'entrada és només de lectura i només es pot moure d'esquerra a dreta, un símbol a la vegada.
Control finit: El control finit té algun punter que assenyala el símbol actual que s'ha de llegir.
Pila: La pila és una estructura en la qual podem empènyer i treure els articles només d'un extrem. Té una mida infinita. A PDA, la pila s'utilitza per emmagatzemar els elements temporalment.
Definició formal de PDA:
La PDA es pot definir com una col·lecció de 7 components:
P: el conjunt finit d'estats
∑: el conjunt d'entrada
C: un símbol de pila que es pot empènyer i treure de la pila
q0: l'estat inicial
intercanvi de memòria
AMB: un símbol d'inici que es troba a Γ.
F: un conjunt d'estats finals
d: funció de mapeig que s'utilitza per passar de l'estat actual al següent.
Descripció instantània (ID)
L'ID és una notació informal de com una PDA calcula una cadena d'entrada i pren una decisió que s'accepta o rebutja.
Una descripció instantània és un triple (q, w, α) on:
q descriu l'estat actual.
En descriu l'entrada restant.
tallar la matriu java
a descriu el contingut de la pila, a la part superior a l'esquerra.
Notació del torniquet:
El signe ⊢ descriu la notació del torniquet i representa un moviment.
El signe ⊢* descriu una seqüència de moviments.
Per exemple,
(p, b, T) ⊢ (q, w, α)
A l'exemple anterior, mentre es fa una transició de l'estat p a q, es consumeix el símbol d'entrada 'b' i la part superior de la pila 'T' es representa amb una nova cadena α.
Exemple 1:
Dissenyar una PDA per acceptar un idioma anb2n.
Solució: En aquest llenguatge, n nombre de a ha d'anar seguit de 2n nombre de b. Per tant, aplicarem una lògica molt senzilla, i és a dir, si llegim una sola 'a', posarem dues a a la pila. Tan bon punt llegim 'b', per a cada 'b' només hauria de sortir una 'a' de la pila.
L'identificador es pot construir de la següent manera:
δ(q0, a, Z) = (q0, aaZ) δ(q0, a, a) = (q0, aaa)
Ara, quan llegim b, canviarem l'estat de q0 a q1 i començarem a aparèixer la 'a' corresponent. Per tant,
δ(q0, b, a) = (q1, ε)
Així, aquest procés d'esclatar 'b' es repetirà tret que es llegeixin tots els símbols. Tingueu en compte que l'acció d'esclatar només es produeix a l'estat q1.
zeenat aman actor
δ(q1, b, a) = (q1, ε)
Després de llegir totes les b, totes les a corresponents haurien de sortir. Per tant, quan llegim ε com a símbol d'entrada, no hi hauria d'haver res a la pila. Per tant, el moviment serà:
δ(q1, ε, Z) = (q2, ε)
On
PDA = ({q0, q1, q2}, {a, b}, {a, Z}, δ, q0, Z, {q2})
Podem resumir l'ID com:
δ(q0, a, Z) = (q0, aaZ) δ(q0, a, a) = (q0, aaa) δ(q0, b, a) = (q1, ε) δ(q1, b, a) = (q1, ε) δ(q1, ε, Z) = (q2, ε)
Ara simularem aquesta PDA per a la cadena d'entrada 'aaabbbbbb'.
exemple de subcadena en java
δ(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
Exemple 2:
Dissenyar una PDA per acceptar un idioma 0n1m0n.
Solució: En aquest PDA, n nombre de 0 va seguit de qualsevol nombre d'1 seguit d'n nombre de 0. Per tant, la lògica per al disseny d'aquest PDA serà la següent:
Premeu tots els 0 a la pila quan trobeu els primers 0. Aleshores, si llegim l'1, no fem res. A continuació, llegiu 0 i, a cada lectura de 0, traieu un 0 de la pila.
Per exemple:
Aquest escenari es pot escriure en el formulari d'identificació com:
δ(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)
Ara simularem aquesta PDA per a la cadena d'entrada '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