Aşağı Açılan Otomata Giriş

PDA'nın Temel Yapısı

Aşağı açılan otomat, DFA'yı normal bir dilbilgisi için tasarladığımıza benzer şekilde bağlamdan bağımsız bir dilbilgisi uygulamanın bir yoludur. Bir DFA, sınırlı miktarda bilgiyi hatırlayabilir, ancak bir PDA sonsuz miktarda bilgiyi hatırlayabilir.

Temel olarak bir aşağı açılan otomat -

"Finite state machine" + "a stack"

Aşağı açılan otomatın üç bileşeni vardır -

• bir giriş bandı,
• bir kontrol ünitesi ve
• sonsuz boyutlu bir yığın.

Yığın kafası, yığının üstteki sembolünü tarar.

Bir yığın iki işlem yapar -

• Push - üst kısma yeni bir sembol eklenir.

• Pop - üstteki sembol okunur ve kaldırılır.

Bir PDA bir giriş sembolünü okuyabilir veya okuyamayabilir, ancak her geçişte yığının en üstünü okumak zorundadır.

Bir PDA resmi olarak bir 7-tuple (Q, ∑, S, δ, q ₀ , I, F) olarak tanımlanabilir -

• Q sonlu devlet sayısı

• ∑ giriş alfabesidir

• S yığın sembolleri

• δ geçiş fonksiyonudur: Q × (∑ ∪ {ε}) × S × Q × S *

• q₀başlangıç ​​durumu (q ₀ ∈ Q)

• I ilk yığının üst sembolüdür (I ∈ S)

• F bir kabul durumları kümesidir (F ∈ Q)

Aşağıdaki diyagram bir PDA'da q ₁ durumundan a, b → c olarak etiketlenen q ₂ durumuna geçişi gösterir -

Bu eyalette anlamına gelir q₁, bir girdi dizesiyle karşılaşırsak ‘a’ ve yığının üst sembolü ‘b’sonra patlıyoruz ‘b’, it ‘c’ yığının tepesinde ve duruma geç q₂.

PDA ile İlgili Terminolojiler

Anlık Açıklama

Bir PDA'nın anlık açıklaması (ID), bir üçlü (q, w, s) ile temsil edilir, burada

• q devlet

• w tüketilmemiş girdidir

• s yığın içeriği

Turnike Notasyonu

"Turnike" notasyonu, bir PDA'nın bir veya daha fazla hareketini temsil eden kimlik çiftlerini bağlamak için kullanılır. Geçiş süreci turnike sembolü "⊢" ile gösterilir.

Bir PDA düşünün (Q, ∑, S, δ, q ₀ , I, F). Bir geçiş, aşağıdaki turnike gösterimi ile matematiksel olarak temsil edilebilir -

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

Bu, devletten geçiş yaparken p belirtmek q, giriş sembolü ‘a’ tüketilir ve yığının tepesi ‘T’ yeni bir dizeyle değiştirilir ‘α’.

Note - Bir PDA'nın sıfır veya daha fazla hamlesini istiyorsak, bunun için (⊢ *) sembolünü kullanmalıyız.