Wprowadzenie do automatów przesuwających w dół

Podstawowa struktura PDA

Automat przesuwający to sposób na zaimplementowanie gramatyki bezkontekstowej w podobny sposób, w jaki projektujemy DFA dla zwykłej gramatyki. DFA może zapamiętać skończoną ilość informacji, ale PDA może zapamiętać nieskończoną ilość informacji.

Zasadniczo automat przesuwający to -

"Finite state machine" + "a stack"

Automat przesuwający składa się z trzech elementów -

taśma wejściowa,
jednostka sterująca, i
stos o nieskończonej wielkości.

Głowica stosu skanuje górny symbol stosu.

Stos wykonuje dwie operacje -

Push - u góry zostanie dodany nowy symbol.
Pop - czyta się i usuwa górny symbol.

PDA może czytać symbol wejściowy lub nie, ale musi czytać szczyt stosu w każdym przejściu.

PDA można formalnie opisać jako 7-krotkę (Q, ∑, S, δ, q ₀ , I, F) -

Q jest skończoną liczbą stanów
∑ jest alfabetem wejściowym
S to symbole stosu
δ jest funkcją przejścia: Q × (∑ ∪ {ε}) × S × Q × S *
q₀jest stanem początkowym (q ₀ ∈ Q)
I jest początkowym symbolem wierzchołka stosu (I ∈ S)
F jest zbiorem stanów akceptujących (F ∈ Q)

Poniższy diagram pokazuje przejście PDA ze stanu q ₁ do stanu q ₂ , oznaczone jako a, b → c -

To znaczy w stanie q₁, jeśli napotkamy ciąg wejściowy ‘a’ a górnym symbolem stosu jest ‘b’, potem pop ‘b’, Pchać ‘c’ na szczycie stosu i przejdź do stanu q₂.

Terminologie związane z PDA

Natychmiastowy opis

Natychmiastowy opis (ID) PDA jest reprezentowany przez trójkę (q, w, s) gdzie

q jest stan
w jest nieużywanym wejściem
s to zawartość stosu

Notacja kołowrotu

Notacja „kołowrót” jest używana do łączenia par identyfikatorów, które reprezentują jeden lub więcej ruchów PDA. Proces przejścia oznaczony jest symbolem kołowrotu „⊢”.

Rozważ PDA (Q, ∑, S, δ, q ₀ , I, F). Przejście można matematycznie przedstawić za pomocą następującego zapisu kołowrotu -

(p, aw, Tβ) ⊢ (q, w, αb)

Oznacza to, że podczas przechodzenia ze stanu p określić q, symbol wejścia ‘a’ jest zużyty, a wierzchołek stosu ‘T’ jest zastępowany nowym ciągiem ‘α’.

Note - Jeśli chcemy mieć zero lub więcej ruchów PDA, musimy użyć do tego symbolu (⊢ *).