Pushdown Automata adalah automata terbatas dengan memori tambahan yang disebut stack yang membantu Pushdown automata mengenali Bahasa Bebas Konteks.

Pushdown Automata (PDA) dapat didefinisikan sebagai:

Q adalah himpunan negara
Adalah set simbol input
Γ adalah himpunan simbol pushdown (yang dapat didorong dan muncul dari tumpukan)
q0 adalah kondisi awal
Z adalah simbol pushdown awal (yang awalnya ada di tumpukan)
F adalah himpunan status akhir
δ adalah fungsi transisi yang memetakan Q x {Σ ∪ ∈} x Γ ke Q x Γ *. Dalam keadaan tertentu, PDA akan membaca simbol input dan simbol stack (bagian atas stack) dan pindah ke status baru dan mengubah simbol stack.

Instantaneous Description (ID)
Deskripsi sesaat (ID) adalah notasi informal tentang bagaimana PDA "menghitung" string input dan membuat keputusan bahwa string diterima atau ditolak.

ID adalah triple (q, w, α), di mana:
1. q adalah kondisi saat ini.
2. w adalah input yang tersisa.
3.α adalah isi tumpukan, atas di sebelah kiri.

Turnstile notation

Tanda ⊢ disebut "notasi turnstile" dan mewakili
satu langkah.
Tanda ⊢ * mewakili urutan gerakan.
Misalnya- (p, b, T) ⊢ (q, w, α)
Ini menyiratkan bahwa saat mengambil transisi dari keadaan p ke keadaan q, simbol input 'b' dikonsumsi, dan bagian atas tumpukan 'T' diganti oleh string baru 'α'

Contoh: Tetapkan pushdown automata untuk bahasa {a n b n | n> 0}
Solusi: M = di mana Q = {q0, q1} dan Σ = {a, b} dan Γ = {A, Z} dan & delta diberikan oleh:

& delta (q0, a, Z) = {(q0, AZ)}
& delta (q0, a, A) = {(q0, AA)}
& delta (q0, b, A) = {(q1, ∈)}
& delta (q1, b, A) = {(q1, ∈)}
& delta (q1, ∈, Z) = {(q1, ∈)}

Mari kita lihat bagaimana automata ini bekerja untuk aaabbb.

Penjelasan: Awalnya, keadaan automata adalah q0 dan simbol pada tumpukan adalah Z dan inputnya aaabbb seperti yang ditunjukkan pada baris 1. Saat membaca 'a' (ditunjukkan dalam huruf tebal di baris 2), keadaan akan tetap q0 dan akan mendorong simbol A pada tumpukan. Pada 'a' berikutnya (ditunjukkan pada baris 3), itu akan mendorong simbol A lainnya pada stack. Setelah membaca 3 a, tumpukan akan menjadi AAAZ dengan A di atas. Setelah membaca 'b' (seperti yang ditunjukkan pada baris 5), itu akan muncul A dan pindah ke status q1 dan tumpukan akan menjadi AAZ. Ketika semua b dibaca, statusnya adalah q1 dan stack akan menjadi Z. Pada baris 8, pada simbol input '∈' dan Z pada stack, maka akan muncul Z dan stack akan kosong. Jenis penerimaan ini dikenal sebagai penerimaan oleh tumpukan kosong.

Catatan :

Automat pushdown di atas bersifat deterministik karena hanya ada satu gerakan dari status pada simbol input dan simbol stack.
Automata pushdown non-deterministik dapat memiliki lebih dari satu gerakan dari status pada simbol input dan simbol stack.
Tidak selalu mungkin untuk mengonversi automata pushdown non-deterministik menjadi automata pushdown deterministik.
Daya Ekspresif dari PDA non-deterministik lebih banyak dibandingkan dengan PDA deterministik ekspresif karena beberapa bahasa yang diterima oleh NPDA tetapi tidak oleh PDA deterministik yang akan dibahas dalam artikel berikutnya.
Automata push down dapat diimplementasikan menggunakan penerimaan dengan tumpukan kosong atau penerimaan dengan status akhir dan satu dapat dikonversi ke yang lain.

Pertanyaan: Manakah dari pasangan berikut ini yang memiliki kekuatan ekspresif BERBEDA?

A. finite automata (DFA) Deterministic dan Finite automata (NFA) non-deterministik
B. Deterministic push down automata (DPDA) dan Non-deterministic push down automata (NPDA)
C. Mesin Turing single-tape Deterministic dan mesin Turing single-tape Non-deterministik
D. Mesin Single-tape Turing dan mesin multi-tape Turing

Solusi: Setiap NFA dapat dikonversi menjadi DFA. Jadi, ada kekuatan ekspresif yang sama. Sebagaimana dibahas di atas, setiap NPDA tidak dapat dikonversi ke DPDA. Jadi, kekuatan NPDA dan DPDA tidak sama. Maka opsi (B) benar.

Formal definition

Kami menggunakan notasi bahasa formal standar:

\Gamma ^{*}

{\ displaystyle \ Gamma ^ {*}}

\Gamma ^{*}

menunjukkan himpunan string sepanjang hingga alfabet

\Gamma

{\ displaystyle \ Gamma}

\Gamma

dan

\varepsilon

{\ displaystyle \ varepsilon}

\varepsilon

menunjukkan string kosong .

PDA secara resmi didefinisikan sebagai 7-tuple:

M=(Q,\Sigma ,\Gamma ,\delta ,q_{0},Z,F)

{\ displaystyle M = (Q, \ Sigma, \ Gamma, \ delta, q_ {0}, Z, F)}

M=(Q,\Sigma ,\Gamma ,\delta ,q_{0},Z,F)

dimana

${\ displaystyle Q}$ $Q$ adalah seperangkat negara yang terbatas
$\Sigma$ ${\ displaystyle \ Sigma}$ $\Sigma$ adalah himpunan terbatas yang disebut alfabet input
$\Gamma$ ${\ displaystyle \ Gamma}$ $\Gamma$ adalah himpunan terbatas yang disebut tumpukan alfabet
$\delta$ ${\ displaystyle \ delta}$ $\delta$ adalah bagian terbatas dari $Q\times (\Sigma \cup \{\varepsilon \})\times \Gamma \times Q\times \Gamma ^{*}$ ${\ displaystyle Q \ times (\ Sigma \ cup \ {\ varepsilon \}) \ times \ Gamma \ times Q \ times \ Gamma ^ {*}}$ $Q\times (\Sigma \cup \{\varepsilon \})\times \Gamma \times Q\times \Gamma ^{*}$ , hubungan transisi
$q_{0}\in Q$ ${\ displaystyle q_ {0} \ dalam Q}$ $q_{0}\in Q$ adalah kondisi awal
$Z\in \Gamma$ ${\ displaystyle Z \ dalam \ Gamma}$ $Z\in \Gamma$ adalah simbol tumpukan awal
$F\subseteq Q$ ${\ displaystyle F \ subseteq Q}$ $F\subseteq Q$ adalah himpunan negara penerima

Sebuah elemen

(p,a,A,q,\alpha )\in \delta

{\ displaystyle (p, a, A, q, \ alpha) \ in \ delta}

(p,a,A,q,\alpha )\in \delta

adalah transisi dari

{\ displaystyle M}

M

. Ini memiliki makna yang dimaksudkan itu

{\ displaystyle M}

M

, dalam keadaan

p\in Q

{\ displaystyle p \ dalam Q}

p\in Q

, pada input

a\in \Sigma \cup \{\varepsilon \}

{\ displaystyle a \ in \ Sigma \ cup \ {\ varepsilon \}}

a\in \Sigma \cup \{\varepsilon \}

dan dengan

A\in \Gamma

{\ displaystyle A \ in \ Gamma}

A\in \Gamma

sebagai simbol tumpukan teratas, dapat dibaca

{\ displaystyle a}

a

, ubah status menjadi

{\ displaystyle q}

q

, pop

{\ displaystyle A}

A

, menggantinya dengan mendorong

\alpha \in \Gamma ^{*}

{\ displaystyle \ alpha \ dalam \ Gamma ^ {*}}

\alpha \in \Gamma ^{*}

. Itu

(\Sigma \cup \{\varepsilon \})

{\ displaystyle (\ Sigma \ cup \ {\ varepsilon \})}

(\Sigma \cup \{\varepsilon \})

komponen hubungan transisi digunakan untuk memformalkan bahwa PDA dapat membaca surat dari input, atau melanjutkan membiarkan input tidak tersentuh. ^{[ rujukan? ]}

Dalam banyak teks ^[2] ^: 110 relasi transisi digantikan oleh formalisasi (setara), di mana

$\delta$ ${\ displaystyle \ delta}$ $\delta$ adalah fungsi transisi , pemetaan $Q\times (\Sigma \cup \{\varepsilon \})\times \Gamma$ ${\ displaystyle Q \ times (\ Sigma \ cup \ {\ varepsilon \}) \ times \ Gamma}$ $Q\times (\Sigma \cup \{\varepsilon \})\times \Gamma$ menjadi himpunan bagian terbatas dari $Q\times \Gamma ^{*}$ ${\ displaystyle Q \ times \ Gamma ^ {*}}$ $Q\times \Gamma ^{*}$

Sini

\delta (p,a,A)

{\ displaystyle \ delta (p, a, A)}

\delta (p,a,A)

berisi semua tindakan yang mungkin dilakukan dalam status

{\ displaystyle p}

p

dengan

{\ displaystyle A}

A

di tumpukan, saat membaca

{\ displaystyle a}

a

pada input. Seseorang menulis misalnya

\delta (p,a,A)=\{(q,BA)\}

{\ displaystyle \ delta (p, a, A) = \ {(q, BA) \}}

\delta (p,a,A)=\{(q,BA)\}

kapan tepatnya

(q,BA)\in \{(q,BA)\},(q,BA)\in \delta (p,a,A),

{\ displaystyle (q, BA) \ in \ {(q, BA) \}, (q, BA) \ in \ delta (p, a, A),}

(q,BA)\in \{(q,BA)\},(q,BA)\in \delta (p,a,A),

karena

((p,a,A),\{(q,BA)\})\in \delta

{\ displaystyle ((p, a, A), \ {(q, BA) \}) \ in \ delta}

((p,a,A),\{(q,BA)\})\in \delta

. Perhatikan bahwa terbatas dalam definisi ini sangat penting.

Perhitungan

langkah dari automat pushdown

Untuk memformalkan semantik dari otomat pushdown deskripsi situasi saat ini diperkenalkan. 3-tuple

(p,w,\beta )\in Q\times \Sigma ^{*}\times \Gamma ^{*}

{\ displaystyle (p, w, \ beta) \ dalam Q \ kali \ Sigma ^ {*} \ times \ Gamma ^ {*}}

(p,w,\beta )\in Q\times \Sigma ^{*}\times \Gamma ^{*}

disebut deskripsi sesaat (ID) dari

{\ displaystyle M}

M

, yang mencakup keadaan saat ini, bagian dari pita input yang belum dibaca, dan isi tumpukan (simbol paling atas ditulis terlebih dahulu). Relasi transisi

\delta

{\ displaystyle \ delta}

\delta

mendefinisikan langkah-relasi

\vdash _{M}

{\ displaystyle \ vdash _ {M}}

\vdash _{M}

dari

{\ displaystyle M}

M

pada deskripsi instan. Untuk instruksi

(p,a,A,q,\alpha )\in \delta

{\ displaystyle (p, a, A, q, \ alpha) \ in \ delta}

(p,a,A,q,\alpha )\in \delta

ada langkah

(p,ax,A\gamma )\vdash _{M}(q,x,\alpha \gamma )

{\ displaystyle (p, kapak, A \ gamma) \ vdash _ {M} (q, x, \ alpha \ gamma)}

(p,ax,A\gamma )\vdash _{M}(q,x,\alpha \gamma )

, untuk setiap

x\in \Sigma ^{*}

{\ displaystyle x \ dalam \ Sigma ^ {*}}

x\in \Sigma ^{*}

dan setiap

\gamma \in \Gamma ^{*}

{\ displaystyle \ gamma \ in \ Gamma ^ {*}}

\gamma \in \Gamma ^{*}

Secara umum pushdown automata adalah makna non-deterministik yang dalam deskripsi instan yang diberikan

(p,w,\beta )

{\ displaystyle (p, w, \ beta)}

(p,w,\beta )

mungkin ada beberapa langkah yang mungkin. Setiap langkah ini dapat dipilih dalam perhitungan. Dengan definisi di atas pada setiap langkah selalu simbol tunggal (atas tumpukan) muncul, menggantinya dengan simbol sebanyak yang diperlukan. Sebagai akibatnya tidak ada langkah yang didefinisikan ketika tumpukan kosong.

Komputasi dari automat pushdown adalah urutan langkah. Perhitungan dimulai pada keadaan awal

q_{0}

{\ displaystyle q_ {0}}

q_{0}

dengan simbol tumpukan awal

{\ displaystyle Z}

Z

pada tumpukan, dan sebuah string

{\ displaystyle w}

w

pada pita input, dengan demikian dengan deskripsi awal

(q_{0},w,Z)

{\ displaystyle (q_ {0}, w, Z)}

(q_{{0}},w,Z)

. Ada dua mode penerimaan. Automat pushdown menerima dengan kondisi akhir, yang berarti setelah membaca inputnya robot tersebut mencapai kondisi penerimaan (dalam

{\ displaystyle F}

F

), atau menerima dengan tumpukan kosong (

\varepsilon

{\ displaystyle \ varepsilon}

\varepsilon

), yang berarti setelah membaca inputnya robot mengosongkan tumpukannya. Mode penerimaan pertama menggunakan memori internal (keadaan), yang kedua adalah memori eksternal (tumpukan).

Secara formal seseorang mendefinisikan

$L(M)=\{w\in \Sigma ^{*}|(q_{0},w,Z)\vdash _{M}^{*}(f,\varepsilon ,\gamma )$ ${\ displaystyle L (M) = \ {w \ in \ Sigma ^ {*} | (q_ {0}, w, Z) \ vdash _ {M} ^ {*} (f, \ varepsilon, \ gamma)}$ $L(M)=\{w\in \Sigma ^{*}|(q_{0},w,Z)\vdash _{M}^{*}(f,\varepsilon ,\gamma )$ dengan $f\in F$ ${\ displaystyle f \ dalam F}$ $f\in F$ dan $\gamma \in \Gamma ^{*}\}$ ${\ displaystyle \ gamma \ in \ Gamma ^ {*} \}}$ $\gamma \in \Gamma ^{*}\}$ (keadaan akhir)
$N(M)=\{w\in \Sigma ^{*}|(q_{0},w,Z)\vdash _{M}^{*}(q,\varepsilon ,\varepsilon )$ ${\ displaystyle N (M) = \ {w \ in \ Sigma ^ {*} | (q_ {0}, w, Z) \ vdash _ {M} ^ {*} (q, \ varepsilon, \ varepsilon)}$ $N(M)=\{w\in \Sigma ^{*}|(q_{0},w,Z)\vdash _{M}^{*}(q,\varepsilon ,\varepsilon )$ dengan $q\in Q\}$ ${\ displaystyle q \ dalam Q \}}$ $q\in Q\}$ (tumpukan kosong)

Sini

\vdash _{M}^{*}

{\ displaystyle \ vdash _ {M} ^ {*}}

\vdash _{M}^{*}

mewakili penutupan refleksif dan transitif dari relasi langkah

\vdash _{M}

{\ displaystyle \ vdash _ {M}}

\vdash _{M}

artinya sejumlah langkah berurutan (nol, satu atau lebih).

Untuk setiap otomat pushdown tunggal, kedua bahasa ini tidak perlu memiliki hubungan: keduanya mungkin sama tetapi biasanya tidak demikian. Spesifikasi otomat juga harus mencakup mode penerimaan yang dimaksudkan. Diambil dari semua pushdown automata, kedua kondisi penerimaan menentukan kelompok bahasa yang sama.

Dalil. Untuk setiap otomat pushdown

{\ displaystyle M}

M

seseorang dapat membuat otomat pushdown

{\ displaystyle M '}

M'

seperti yang

L(M)=N(M')

{\ displaystyle L (M) = N (M ')}

L(M)=N(M')

, dan sebaliknya, untuk setiap automat pushdown

{\ displaystyle M}

M

seseorang dapat membuat otomat pushdown

{\ displaystyle M '}

M'

seperti yang

N(M)=L(M')

{\ displaystyle N (M) = L (M ')}

N(M)=L(M')

Contoh

Berikut ini adalah deskripsi formal dari PDA yang mengenali bahasa tersebut

\{0^{n}1^{n}\mid n\geq 0\}

{\ displaystyle \ {0 ^ {n} 1 ^ {n} \ mid n \ geq 0 \}}

\{0^{n}1^{n}\mid n\geq 0\}

menurut keadaan akhir:

PDA untuk

\{0^{n}1^{n}\mid n\geq 0\}

{\ displaystyle \ {0 ^ {n} 1 ^ {n} \ mid n \ geq 0 \}}

\{0^{n}1^{n}\mid n\geq 0\}

(dengan kondisi akhir)

M=(Q,\ \Sigma ,\ \Gamma ,\ \delta ,\ q_{0},\ Z,\ F)

{\ displaystyle M = (Q, \ \ Sigma, \ \ Gamma, \ \ delta, \ q_ {0}, \ Z, \ F)}

M=(Q,\ \Sigma ,\ \Gamma ,\ \delta ,\ q_{0},\ Z,\ F)

dimana

menyatakan: $Q=\{p,q,r\}$ ${\ displaystyle Q = \ {p, q, r \}}$ $Q=\{p,q,r\}$
masukan alfabet: $\Sigma =\{0,1\}$ ${\ displaystyle \ Sigma = \ {0,1 \}}$ $\Sigma =\{0,1\}$
tumpukan alfabet: $\Gamma =\{A,Z\}$ ${\ displaystyle \ Gamma = \ {A, Z \}}$ $\Gamma =\{A,Z\}$
mulai keadaan: $q_{0}=p$ ${\ displaystyle q_ {0} = p}$ $q_{0}=p$
mulai simbol tumpukan: $Z$
negara penerima: $F=\{r\}$ ${\ displaystyle F = \ {r \}}$ $F=\{r\}$

Relasi transisi

\delta

{\ displaystyle \ delta}

\delta

terdiri dari enam instruksi berikut:

(p,0,Z,p,AZ)

{\ displaystyle (p, 0, Z, p, AZ)}

(p,0,Z,p,AZ)

(p,0,A,p,AA)

{\ displaystyle (p, 0, A, p, AA)}

(p,0,A,p,AA)

(p,\epsilon ,Z,q,Z)

{\ displaystyle (p, \ epsilon, Z, q, Z)}

(p,\epsilon ,Z,q,Z)

(p,\epsilon ,A,q,A)

{\ displaystyle (p, \ epsilon, A, q, A)}

(p,\epsilon ,A,q,A)

(q,1,A,q,\epsilon )

{\ displaystyle (q, 1, A, q, \ epsilon)}

(q,1,A,q,\epsilon )

, dan

(q,\epsilon ,Z,r,Z)

{\ displaystyle (q, \ epsilon, Z, r, Z)}

(q,\epsilon ,Z,r,Z)

Dengan kata-kata, dua instruksi pertama mengatakan bahwa dalam keadaan

p

setiap saat simbol 0 dibaca, satu

A

didorong ke tumpukan. Mendorong simbol

A

di atas

A

lainnya diformalkan sebagai mengganti top

A

dengan

AA

(dan juga untuk mendorong simbol

A

di atas

Z

Instruksi ketiga dan keempat mengatakan bahwa, setiap saat otomat dapat bergerak dari keadaan

p

ke keadaan

q

Instruksi kelima mengatakan bahwa dalam keadaan

q

, untuk setiap simbol Saya membaca, satu

A

muncul.

Akhirnya, instruksi keenam mengatakan bahwa mesin dapat bergerak dari keadaan

q

ke keadaan menerima

r

hanya ketika tumpukan terdiri dari satu

Z.

Tampaknya tidak ada representasi yang umum digunakan untuk PDA. Di sini kita menggambarkan instruksinya

(p,a,A,q,\alpha )

{\ displaystyle (p, a, A, q, \ alpha)}

(p,a,A,q,\alpha )

oleh tepi dari negara

p

ke negara

q

diberi label oleh

a;A/\alpha

{\ displaystyle a; A / \ alpha}

a;A/\alpha

(baca

a

; ganti

A

dengan

\alpha

{\ displaystyle \ alpha}

\alpha

Generalized pushdown automaton (GPDA)

GPDA adalah PDA yang menulis seluruh string dengan panjang yang diketahui ke stack atau menghapus seluruh string dari stack dalam satu langkah.

GPDA secara resmi didefinisikan sebagai 6-tuple:

$M=(Q,\ \Sigma ,\ \Gamma ,\ \delta ,\ q_{0},\ F)$ ${\ displaystyle M = (Q, \ \ Sigma, \ \ Gamma, \ \ delta, \ q_ {0}, \ F)}$ $M=(Q,\ \Sigma ,\ \Gamma ,\ \delta ,\ q_{0},\ F)$

dimana $Q,\Sigma \,,\Gamma \,,q_{0}$ ${\ displaystyle Q, \ Sigma \ ,, \ Gamma \ ,, q_ {0}}$ $Q,\Sigma \,,\Gamma \,,q_{0}$ , dan ${\ displaystyle F}$ $F$ didefinisikan dengan cara yang sama seperti PDA.

$\,\delta$ ${\ displaystyle \, \ delta}$ $\,\delta$ : $Q\times \Sigma _{\epsilon }\times \Gamma ^{}\longrightarrow P(Q\times \Gamma ^{})$ ${\ displaystyle Q \ times \ Sigma _ {\ epsilon} \ times \ Gamma ^ {} \ longrightarrow P (Q \ times \ Gamma ^ {})}$ $Q\times \Sigma _{\epsilon }\times \Gamma ^{}\longrightarrow P(Q\times \Gamma ^{})$

adalah fungsi transisi.

Aturan perhitungan untuk GPDA adalah sama dengan PDA kecuali bahwa $a_{i+1}$ ${\ displaystyle a_ {i + 1}}$ $a_{{i+1}}$ dan $b_{i+1}$ ${\ displaystyle b_ {i + 1}}$ $b_{{i+1}}$ Sekarang adalah string, bukan simbol.

GPDA dan PDA adalah sama karena jika suatu bahasa dikenali oleh PDA, itu juga diakui oleh GPDA dan sebaliknya.

Seseorang dapat merumuskan bukti analitik untuk kesetaraan GPDA dan PDA menggunakan simulasi berikut:

Membiarkan $\delta (q_{1},w,x_{1}x_{2}\cdot x_{m})\longrightarrow (q_{2},y_{1}y_{2}...y_{n})$ ${\ displaystyle \ delta (q_ {1}, w, x_ {1} x_ {2} \ cdot x_ {m}) \ longrightarrow (q_ {2}, y_ {1} y_ {2} ... y_ {n })}$ $\delta (q_{1},w,x_{1}x_{2}\cdot x_{m})\longrightarrow (q_{2},y_{1}y_{2}...y_{n})$ menjadi transisi dari GPDA

dimana $q_{1},q_{2}\in Q,w\in \Sigma _{\epsilon },x_{1},x_{2},\ldots ,x_{m}\in \Gamma ^{},m\geq 0,y_{1},y_{2},\ldots ,y_{n}\in \Gamma ^{},n\geq 0$ ${\ displaystyle q_ {1}, q_ {2} \ di Q, w \ in \ Sigma _ {\ epsilon}, x_ {1}, x_ {2}, \ ldots, x_ {m} \ dalam \ Gamma ^ { }, m \ geq 0, y_ {1}, y_ {2}, \ ldots, y_ {n} \ dalam \ Gamma ^ {}, n \ geq 0}$ $q_{1},q_{2}\in Q,w\in \Sigma _{\epsilon },x_{1},x_{2},\ldots ,x_{m}\in \Gamma ^{},m\geq 0,y_{1},y_{2},\ldots ,y_{n}\in \Gamma ^{},n\geq 0$ .

Bangun transisi berikut untuk PDA:

${\begin{array}{lcl}\delta ^{'}(q_{1},w,x_{1})&\longrightarrow &(p_{1},\epsilon )\\\delta ^{'}(p_{1},\epsilon ,x_{2})&\longrightarrow &(p_{2},\epsilon )\\&\vdots &\\\delta ^{'}(p_{m-1},\epsilon ,x_{m})&\longrightarrow &(p_{m},\epsilon )\\\delta ^{'}(p_{m},\epsilon ,\epsilon )&\longrightarrow &(p_{m+1},y_{n})\\\delta ^{'}(p_{m+1},\epsilon ,\epsilon )&\longrightarrow &(p_{m+2},y_{n-1})\\&\vdots &\\\delta ^{'}(p_{m+n-1},\epsilon ,\epsilon )&\longrightarrow &(q_{2},y_{1})\end{array}}$ ${\ displaystyle {\ begin {array} {lcl} \ delta ^ {'} (q_ {1}, w, x_ {1}) & \ longrightarrow & (p_ {1}, \ epsilon) \\\ delta ^ { '} (p_ {1}, \ epsilon, x_ {2}) & \ longrightarrow & (p_ {2}, \ epsilon) \\ & \ vdots & \\ delta ^ {'} (p_ {m-1} , \ epsilon, x_ {m}) & \ longrightarrow & (p_ {m}, \ epsilon) \\ delta ^ {'} (p_ {m}, \ epsilon, \ epsilon) & \ longrightarrow & (p_ {m +1}, y_ {n}) delta ^ {'} (p_ {m + 1}, \ epsilon, \ epsilon) & \ longrightarrow & (p_ {m + 2}, y_ {n-1}) \\ & \ vdots & \\ delta ^ {'} (p_ {m + n-1}, \ epsilon, \ epsilon) & \ longrightarrow & (q_ {2}, y_ {1}) \ end {array} }}$ ${\begin{array}{lcl}\delta ^{'}(q_{1},w,x_{1})&\longrightarrow &(p_{1},\epsilon )\\\delta ^{'}(p_{1},\epsilon ,x_{2})&\longrightarrow &(p_{2},\epsilon )\\&\vdots &\\\delta ^{'}(p_{m-1},\epsilon ,x_{m})&\longrightarrow &(p_{m},\epsilon )\\\delta ^{'}(p_{m},\epsilon ,\epsilon )&\longrightarrow &(p_{m+1},y_{n})\\\delta ^{'}(p_{m+1},\epsilon ,\epsilon )&\longrightarrow &(p_{m+2},y_{n-1})\\&\vdots &\\\delta ^{'}(p_{m+n-1},\epsilon ,\epsilon )&\longrightarrow &(q_{2},y_{1})\end{array}}$

Push Down Automata (Ekivalensi PDA dan CFG serta deterministic PDA)

Terinspirasi dari bahasa natural manusia, ilmuwan-ilmuwan ilmu komputer yang mengembangkan bahasa pemrograman turut serta memberikan tata bahasa (pemrograman) secara formal. Tata bahasa ini diciptakan secara bebas-konteks dan disebut CFG (Context Free Grammar). Hasilnya, dengan pendekatan formal ini, kompiler suatu bahasa pemrograman dapat dibuat lebih mudah dan menghindari ambiguitas ketika parsing bahasa tersebut. Contoh desain CFG untuk parser, misal : B -> BB | (B) | e untuk mengenali bahasa dengan hanya tanda kurung {‘(’,’)’} sebagai terminal-nya. Proses parsing adalah proses pembacaan untai dalam bahasa sesuai CFG tertentu, proses ini harus mematuhi aturan produksi dalam CFG tersebut.

Secara formal, CFG didefinisikan[2] : CFG G = (V,T,P,S), dimana V adalah daftar variabel produksi T, adalah daftar simbol atau terminal yang dipakai dalam CFG P, adalah aturan produksi CFG S, adalah variabel start aturan produksi CFG dapat ‘dinormalkan’ dengan pola tersendiri supaya tidak ambigu dan lebih sederhana, meskipun normalisasi CFG kadang membuat aturan produksi menjadi lebih banyak dari sebelumnya. Teknik normalisasi yang digunakan dalam makalah ini adalah CNF (Chomsky Normal For)

Gambaran parsing bahasa natural (Inggris)

Contoh desain CNF dari bahasa CFG, semisal CFGberikut:

S -> aA | bB (1)

A-> Baa|ba

B -> bAA|ab

CFG (1) tersebut ekivalen dengan CFG dibawah ini,dimana symbol terminal memiliki variabel produksi tersendiri:

S -> DA | EB (2)

A -> BDD | ED

B -> EAA | DE D -> a

E -> b

CNF yang dihasilkan dari CFG (2) diatas ialah:

S -> DA | EB (3)

A -> BF | ED

B -> EH | DE

F -> DD

H -> AA

D -> a

E -> b

Setelah terbentuk CFG yang telah dinormalkan secara CNF, dalam implementasi parsing, terdapat algoritma yang berguna untuk menentukan apakah suatu untai ‘valid’, atau dapat diciptakan dari aturan-aturan CFG yang ada. Salah satu algoritma yang dapat dipakai adalah Algoritma Cocke-Younger-Kasami (CYK). Algoritma ini menyelesaikan masalah analisa kembali sebuah sub-untai yang sama karena seharusnya analisa sub-untai independen terhadap parsing sub-untai yang diparsing setelahnya. Dengan Program Dinamis, independensi yang diinginkan dapat dicapai ketika parsing. Algoritma CYK termasuk dalam bidang Program Dinamis karena algoritma ini membangun tabel status dua dimensi ketika parsing dimana penentuan parsing selanjutnya diturunkan atau dihasilkan dari parsing sebelumnya, hingga akhir untai. Selain untuk mengetahui validitas untai dalam suatu CFG, algoritma CYK yang dimodifikasi dapat dipergunakan pula untuk membangun pohon parsing.

Pohon parsing yang terbentuk dari sebuah bahasa natural

Contoh 1 :

Diketahui grammar G 1 = {I → H I H IA, H → a b c … z, A → 0 1 2 … 9} dengan I adalah simbol awal. Berikut ini kedua cara analisa sintaks untuk kalimat x23b.

Cara 1 (derivasi)

⇒ IH

IAAH

HAAH

xAAH

x2AH

x23H

x23b

cara 2 (parsing)

Sebuah kalimat dapat saja mempunyai lebih dari satu pohon.

Contoh 2 :

Diketahui grammar G 2 = {S → SOS A , O → * +, A → 0 1 2 … 9} Kalimat : 2*3+7 mempunyai dua pohon sintaks berikut :

Pohon parsing yang terbentuk dari sebuah bahasa natural

Push Down Automata (PDA)

PDA adalah mesin otomata dari TBBK yang diimplementasikan dengan stack sehingga hanya terdapat operasi “push” dan “pop” Stack (tumpukan) adalah suatu struktur data yang menggunakan prinsip LIFO (Last In First Out). Sebuah stack selalu memiliki top of stack dan elemen-elemen stack itu yang akan masuk ke dalam stack dengan method “push” dan akan keluar dari stack dengan method “pop”.

Definisi : PDA adalah pasangan 7 tuple M = (Q, Σ, , q 0 , Z 0 , δ, A), dimana :

Q : himpunan hingga stata, Σ : alfabet input, : alfabet stack, q 0 ∈ Q : stata awal, Z 0 ∈ : simbol awal stack, A ⊆ Q : himpunan stata penerima,

fungsi transisi δ : Q  (Σ ∪ {ε})  → 2 Q  * (himpunan bagian dari Q  *)

Untuk stata q ∈ Q, simbol input a ∈ Σ, dan simbol stack X∈ , δ(q, a, X) = (p, α) berarti : PDA bertransisi ke stata p dan mengganti X pada stack dengan string α.

Konfigurasi PDA pada suatu saat dinyatakan sebagai triple (q, x, α), dimana :

q ∈ Q : stata pada saat tersebut, x ∈ Σ* : bagian string input yang belum dibaca, dan α ∈ * : string yang menyatakan isi stack dengan karakter terkiri menyatakan top of stack.

Misalkan (p, ay, Xβ) adalah sebuah konfigurasi, dimana : a ∈ Σ, y ∈ Σ*, X ∈ , dan β ∈ *. Misalkan pula δ(p, a, X) = (q, γ) untuk q ∈ Q dan γ ∈ *. Dapat kita tuliskan

bahwa : (p, ay, Xβ) ⇒ (q, y, γβ).

Sebuah PDA dinyatakan dengan :

Q = himpunan state

Σ = himpunan simbol input

T = simbol stack

S = state awal

F = state akhir

Z = top of stack

PDA memiliki 2 jenis transisi, yaitu yang merima simbol input, simbol top of stack, dan state. Setiap pilihan terdiri dari state berikutnya dan simbol- simbol. Penggantian isi stack dilakukan dengan opersi push dan pop. Jenis transisi yang kedua adalah transisi ε. Transisi ε tidak melakukan pembacaan input namun hanya menerima simbol top of stack dan state. Transisi ini memungkinkan PDA untuk memanipulasi isi stack dan berpindah antar state tanpa membaca input.

[Ginanjar] Deterministik Push Down Automata (PDA)

Push Down Automata (PDA) merupakan mesin otomata dari bahasa bebas konteks. PDA di gambarkan sebagai tempat penyipanan yang tidak terbatas berupa stack/ tumpukan.

Stack ialah kumpulan dari elemen-elemen sejenis dengan sifat penambahan elemen dan pengambilan elemen melalui suatu tempat yang disebut top of stack (puncak stack). Prinsip pada stack adalah LIFO. Pengambilan elemen dari stack dinyatakan dengan operasi pop, sedang memasukkan elemen ke dalam stack dengan operasi push.

Contoh stack :

perasi pop :

Jika dilakukan operasi push B, maka kondisi stack akan menjadi :

Definisi : PDA adalah pasangan 7 tuple.

M = (Q, S, q, F, d, G, Z), dimana :

Q : himpunan hingga state,

S : alfabet input,

G : alfabet/simbol stack,

q: state awal, qÎ Q

Z : simbol awal stack, ZÎ G

F : himpunan state penerima, F Í Q

d : fungsi transisi , d : Q ´ (S È {e}) ´ G ® 2 (himpunan bagian dari Q ´ G*)

d(q, a, Z) = (q, AZ). Push/insert

d(q, a, A) = (q1, e). Pop /delete

Untuk state q Î Q, simbol input a Î S, dan simbol stack XÎ G, d(q, a, X) = (p, a) berarti : PDA bertransisi ke state p dan mengganti X pada stack dengan string a.

Konfigurasi PDA pada suatu saat dinyatakan sebagai triple (q, x, a), dimana :

q Î Q : state pada saat tersebut, x Î S* : bagian string input yang belum dibaca, dan a Î G* : string yang menyatakan isi stack dengan karakter terkiri menyatakan top of stack.

Misalkan (p, ay, Xb) adalah sebuah konfigurasi, dimana : a Î S, y Î S*, X Î G, dan b Î G*. Misalkan pula d(p, a, X) = (q, g) untuk q Î Q dan g Î G*. Dapat kita tuliskan bahwa : (p, ay, Xb) Þ (q, y, gb).

[M. Aldi Pratama] PDA dan CFL (Context Free Languages)

Dalam teori bahasa formal , bahasa bebas konteks ( CFL ) adalah bahasa yang dihasilkan oleh beberapa bebas konteks tata bahasa ( CFG ) . tata bahasa CF yang berbeda dapat menghasilkan bahasa CF yang sama . Hal ini penting untuk membedakan sifat dari bahasa ( sifat intrinsik ) dari sifat dari tata bahasa tertentu ( sifat ekstrinsik ) .

Himpunan semua bahasa bebas konteks identik dengan set bahasa diterima oleh pushdown automata , yang membuat bahasa ini setuju untuk parsing . Memang , diberi CFG , ada cara langsung untuk menghasilkan robot pushdown untuk tata bahasa ( dan bahasa yang sesuai ) , meskipun pergi ke arah lain ( menghasilkan tata bahasa diberikan robot ) tidak sebagai langsung .

bahasa bebas konteks memiliki banyak aplikasi dalam bahasa pemrograman ; misalnya , bahasa semua kurung benar cocok dihasilkan oleh tata bahasa { \ displaystyle S \ ke SS ~ | ~ ( S ) ~ | ~ \ varepsilon } . Juga, kebanyakan ekspresi aritmatika yang dihasilkan oleh tata bahasa bebas konteks

Contoh :

Bahasa bebas konteks pola dasar adalah {\ displaystyle L = \ {a ^ {n} b ^ {n}: n \ GEQ 1 \}}, bahasa semua non-kosong string bahkan panjang, seluruh pertama bagian dari yang {\ displaystyle sebuah} ‘s, dan seluruh bagian kedua yang {\ displaystyle b}’ s. {\ Displaystyle L} dihasilkan oleh tata bahasa {\ displaystyle S \ ke ASB ~ | ~ ab}. Bahasa ini tidak biasa. Hal ini diterima oleh otomat pushdown {\ displaystyle M = (\ {Q_ {0}, Q_ {1}, Q_ {f} \}, \ {a, b \}, \ {a, z \}, \ delta , Q_ {0}, z, \ {Q_ {f} \})} dimana {\ displaystyle \ delta} didefinisikan sebagai berikut: [catatan 1]

{\ Displaystyle \ delta (Q_ {0}, a, z) = (Q_ {0}, az)}

{\ Displaystyle \ delta (Q_ {0}, a, a) = (Q_ {0}, aa)}

{\ Displaystyle \ delta (Q_ {0}, b, a) = (Q_ {1}, \ varepsilon)}

{\ Displaystyle \ delta (Q_ {1}, b, a) = (Q_ {1}, \ varepsilon)}

CFL ambigu adalah subset yang tepat dari semua CFL: ada CFL inheren ambigu. Contoh dari CFL inheren ambigu adalah gabungan dari {\ displaystyle \ {a ^ {n} b ^ {m} c ^ {m} d ^ {n} | n, m> 0 \}} dengan {\ displaystyle \ {a ^ {n} b ^ {n} c ^ {m} d ^ {m} | n, m> 0 \}}. set ini bebas konteks, karena penyatuan dua bahasa bebas konteks selalu bebas konteks. Tapi tidak ada cara untuk tegas mengurai string dalam (non-bebas konteks) bagian {\ displaystyle \ {a ^ {n} b ^ {n} c ^ {n} d ^ {n} | n> 0 \} } yang merupakan persimpangan dua bahasa tersebut.

Set { \ displaystyle \ {a ^ { n } b ^ { n } c ^ { n } d ^ { n } | n > 0 \ } } adalah bahasa konteks – sensitif , tapi ada tidak ada konteks bebas tata menghasilkan bahasa ini . [ 2 ] Jadi di sana ada bahasa konteks – sensitif yang tidak bebas konteks . Untuk membuktikan bahwa bahasa yang diberikan tidak bebas konteks , seseorang dapat menggunakan lemma memompa untuk bahasa bebas konteks atau sejumlah metode lain, seperti Ogden lemma atau teorema Parikh ini .

bahasa bebas konteks ditutup di bawah operasi berikut . Artinya, jika L dan P adalah bahasa bebas konteks , bahasa berikut ini adalah bebas konteks juga:

serikat { \ displaystyle L \ secangkir P } L dan P

pembalikan L

Rangkaian { \ displaystyle L \ cdot P } L dan P

tanda star { \ displaystyle L ^ { * } } L

gambar { \ displaystyle \ varphi ( L ) } dari L di bawah homomorfisma sebuah { \ displaystyle \ varphi }

gambar { \ displaystyle \ varphi ^ { – 1 } ( L ) } dari L di bawah homomorfisma terbalik { \ displaystyle \ varphi ^ { – 1 } }

pergeseran siklik dari L ( bahasa { \ displaystyle \ { vu : uv \ di L \ } } )

bahasa bebas konteks tidak tertutup di bawah pelengkap , persimpangan , atau perbedaan .

Namun, jika L adalah bahasa bebas konteks dan D adalah bahasa reguler maka kedua persimpangan mereka { \ displaystyle L \ cap D } dan perbedaan mereka { \ displaystyle L \ setminus D } adalah bahasa bebas konteks .

Nonclosure bawah persimpangan , pelengkap , dan perbedaan [ sunting ]

Bahasa bebas konteks tidak tertutup di bawah persimpangan . Hal ini dapat dilihat dengan mengambil bahasa { \ displaystyle A = \ {a ^ { n } b ^ { n } c ^ { m } \ pertengahan m , n \ GEQ 0 \ } } dan { \ displaystyle B = \ { a ^ { m } b ^ { n } c ^ { n } \ pertengahan m , n \ GEQ 0 \ } } , yang keduanya bebas konteks . [catatan 2 ] persimpangan mereka adalah { \ displaystyle A \ cap B = \ { a ^ { n } b ^ { n } c ^ { n } \ pertengahan n \ GEQ 0 \ } } , yang dapat ditunjukkan untuk menjadi non – konteks bebas oleh lemma memompa untuk bahasa bebas konteks .

bahasa bebas konteks juga tidak tertutup di bawah komplementasi , seperti untuk bahasa apa A dan B : { \ displaystyle A \ cap B = { \ overline { { \ overline { A} } \ cup { \ overline { B } } } } } .

Bebas konteks bahasa juga tidak tertutup di bawah perbedaan : LC = Σ * \ L

PDA (Push down automata)

Dalam ilmu komputer, sebuah robot pushdown (PDA) adalah jenis robot yang mempekerjakan stack.

automata pushdown digunakan dalam teori tentang apa yang dapat dihitung oleh mesin. Mereka lebih mampu dari mesin finite-state tetapi kurang mampu dari mesin Turing. Deterministik pushdown automata dapat mengenali semua bahasa bebas konteks deterministik sementara yang nondeterministic dapat mengenali semua bahasa bebas konteks. Terutama mantan digunakan dalam desain parser.

Istilah “pushdown” mengacu pada fakta bahwa tumpukan dapat dianggap sebagai yang “didorong ke bawah” seperti dispenser nampan di kantin, karena operasi tidak pernah bekerja pada unsur-unsur lain dari elemen atas. Sebuah robot tumpukan, sebaliknya, tidak memungkinkan akses dan operasi pada elemen yang lebih dalam. Stack automata dapat mengenali satu set ketat lebih besar dari bahasa dari pushdown automata. [1] Sebuah bersarang tumpukan otomat memungkinkan akses penuh, dan juga nilai-nilai memungkinkan ditumpuk menjadi seluruh sub-tumpukan bukan hanya simbol yang terbatas tunggal.

Sisa dari artikel ini menjelaskan pushdown otomat nondeterministic.

automata pushdown berbeda dari mesin negara yang terbatas dalam dua cara:

Mereka dapat menggunakan bagian atas tumpukan untuk menentukan transisi untuk mengambil.

Mereka dapat memanipulasi stack sebagai bagian dari melakukan transisi.

automata pushdown memilih transisi dengan mengindeks meja dengan sinyal input, kondisi saat ini, dan simbol di bagian atas tumpukan. Ini berarti bahwa ketiga parameter benar-benar menentukan jalur transisi yang dipilih. mesin negara yang terbatas hanya melihat sinyal masukan dan keadaan saat: mereka tidak memiliki tumpukan untuk bekerja dengan. automata pushdown menambahkan stack sebagai parameter untuk pilihan.

automata pushdown juga dapat memanipulasi stack, sebagai bagian dari melakukan transisi. mesin negara yang terbatas memilih negara baru, hasil berikut transisi. manipulasi dapat mendorong simbol tertentu ke puncak stack, atau pop dari atas tumpukan. otomat alternatif bisa mengabaikan stack, dan biarkan seperti itu. Pilihan manipulasi (atau tidak ada manipulasi) ditentukan oleh tabel transisi.

Disatukan: Mengingat sinyal input, kondisi saat ini, dan simbol tumpukan, otomat dapat mengikuti transisi ke negara bagian lain, dan secara opsional memanipulasi (push atau pop) stack.

Secara umum, pushdown automata mungkin memiliki beberapa perhitungan pada string masukan yang diberikan, beberapa di antaranya dapat menghentikan dalam konfigurasi menerima. Jika hanya satu perhitungan ada untuk semua string yang diterima, hasilnya adalah pushdown robot deterministik (DPDA) dan bahasa string ini adalah bahasa bebas konteks deterministik. Tidak semua bahasa bebas konteks yang deterministik. [2] Sebagai konsekuensi dari atas DPDA adalah varian ketat lemah dari PDA dan tidak terdapat algoritma untuk mengkonversi PDA ke DPDA setara, jika seperti DPDA ada.

Jika kita membiarkan akses robot yang terbatas untuk dua tumpuk, bukan hanya satu, kita mendapatkan perangkat yang lebih kuat, setara dalam kekuatan untuk mesin Turing. Sebuah linear dibatasi robot adalah perangkat yang lebih kuat daripada robot pushdown tapi kurang daripada mesin Turing.

[Resalina Oktaria] Contoh Soal PDA

Misalkan sebuah CFG memiliki aturan produksi:
S aBc | Bac
B b | c
Maka dapat dibuat PDA-nya:
Q= {q1,q2,q3}
?= {a,b,c}
+= {S,B,a,b,c,Z}
S=q1
Z= Z
F= {q3}
Fungsi transisinya:
d (q1,£,Z) = {{q2,SZ)}
d (q2,£,S) = {{q2,aBc),(q2,Bac)}
d (q2,£,B) = {{q2,b),(q2,c)}
d (q2,a,a) = d {{q2,b,b)= d (q2,c,c) = {{q2, £)}
d (q2,£,Z) = {{q3,Z)}
berdasrkan aturan produksi, tata bahasa tersebut dapat menurunkan string ‘acc’:
S => aBc => acc
Langkah-langkah pada PDA ketika menerima string tersebut adalah sebagai berikut:
Z

1. konfigurasi awal mesin : state q1, tanpa menerima input (£), top of stack Z
fungsi transisi : d (q1,£,Z) = {{q2,SZ)}
Konfigurasi mesin menjadi: state q2, S di push
S
Z

2. input : tanpa menerima input (£)
fungsi transisi : d (q2,£,S) = {{q2,aBc) }
konfigurasi mesin menjadi : state q2, pop top of stack, push ‘aBc’
a
B
c
Z

3. input : menerima input ‘a’
fungsi transisi : d (q2,a,a) = {{q2, £) }
konfigurasi mesin menjadi : state q2, pop top of stack
B
c
Z

4. input : tanpa menerima input (£)
fungsi transisi : d (q2, £,B) = {{q2, c) }
konfigurasi mesin menjadi : state q2, pop top of stack, push ‘c’
c
c
Z

5. input : menerima input ‘c’
fungsi transisi : d (q2,c,c) = {{q2, £) }
konfigurasi mesin menjadi : state q2, pop top of stack
c
Z

6. input : menerima input ‘c’
fungsi transisi : d (q2,c,c) = {{q2, £) }
konfigurasi mesin menjadi : state q2, pop top of stack
Z

7. input : tanpa menerima input (£)
fungsi transisi : d (q2, £,Z) = {{q3, Z) }
konfigurasi mesin menjadi : state q3

tidak ada transisi lagi dari q3, karena sudah mencapai state akhir dan string input selesai dibaca, maka string ‘acc’ diterima oleh PDA tersebut. Seperti terlihat pada deskripsi dari contoh diatas, didalam PDA bentuk penggambaran automatanya sendiri diangggap tidak terlalu penting. Jika diperlukan PDA dapat digambarkan sebagai diagram transisi yang umun:

Dari diagram transisi tersebut terlihat bahwa q1 berfungsi sebagai state awal, q3 sebagai final state, dan sebagai transisi lainnya terjadi pada state q2.

(PDA Deterministik):

PDA M = (Q, Σ, , q 0 , Z 0 , δ, A) pengenal palindrome L = {xcx T x ∈ (a b)*}, dimana = {a, b, Z 0 }, dan fungsi transisi δ terdefinisi melalui tabel berikut :

Sebagai contoh, perhatikan bahwa fungsi transisi No. 1 dapat dinyatakan sebagai : δ(q 0 , a, Z 0 ) = (q 0 , aZ 0 ). Pada tabel transisi tersebut terlihat bahwa pada stata q 0 PDA akan melakukan PUSH jika mendapat input a atau b dan melakukan transisi stata ke stata q 1 jika mendapat input c. Pada stata q 1 PDA akan melakukan POP.

Berikut ini pengenalan dua string oleh PDA di atas :

1. abcba : (q 0 , abcba, Z 0 ) ⇒ (q 0	, bcba, aZ 0 )	(1)
⇒ (q 0	, cba, baZ 0 )	(4)
⇒ (q 1 , ba, baZ 0 )		(9)
⇒ (q 1	, a, aZ 0 )	(11)
⇒ (q 1	, ε, Z 0 )	(10)
⇒ (q 2 , ε, Z 0 )		(12)	(diterima)

2.	acb : (q 0 , acb, Z 0 ) ⇒ (q 0 , cb, aZ 0 )		(1)
	⇒ (q 1 , b, aZ 0 )		(8),	(crash → ditolak)
3.	ab : (q 0 , ab, Z 0 ) ⇒ (q 0	, b, aZ 0 )	(1)
	⇒ (q 0	, ε, baZ 0 )	(4)	(crash → ditolak)

Penerimaan dan penolakan tiga string di atas dapat dijelaskan sebagai berikut :

string abcba diterima karena tracing sampai di stata penerima (q 2 ) dan string “abcba” selesai dibaca (string yang belum dibaca = ε)

string acb ditolak karena konfigurasi akhir (q 1 , b, a Z 0 ) sedangkan fungsi transisi δ(q 1 , b, a) tidak terdefinsi

string ab ditolak karena konfigurasi akhir (q 0 , ε, baZ 0 ) sedangkan fungsi transisi δ(q 0 , ε, b) tidak terdefinsi Ilustrasi graf fungsi transisi PDA di atas ditunjukkan melalui gambar berikut :

Notasi (p, ay, Xβ) ⇒ (q, y, γβ) dapat diperluas menjadi : (p, x, α) ⇒* (q, y, β), yang berarti konfigurasi (q, y, β) dicapai melalui sejumlah (0 atau lebih) transisi.

Ada dua cara penerimaan sebuah kalimat oleh PDA, yang masing-masing terlihat dari konfigurasi akhir, sebagaimana penjelasan berikut :

Jika M = (Q, Σ, , q 0 , Z 0 , δ, A) adalah PDA dan x ∈Σ*, maka x diterima dengan stata akhir (accepted by final state) oleh PDA M jika : (q 0 , x, Z 0 ) ⇒* (q, ε, α) untuk α ∈

* dan q ∈ A. x diterima dengan stack hampa (accepted by empty stack) oleh PDA M jika : (q 0 , x, Z 0 ) ⇒* (q, ε, ε) untuk q ∈ Q.

(PDA Non-Deterministik):

PDA M = (Q, Σ, , q 0 , Z 0 , δ, A) pengenal palindrome L = {xx T x ∈ (a b)*} mempunyai komponen tuple berikut : Q = {q 0 , q 1 , q 2 }, A = { q 2 }, Σ = {a, b}, = {a, b, Z 0 }, dan fungsi transisi δ terdefinisi melalui tabel berikut :

Pada tabel transisi tersebut terlihat bahwa pada stata q 0 PDA akan melakukan PUSH jika

mendapat input a atau b dan melakukan transisi stata ke stata q 1 jika mendapat input ε. Pada stata q 1 PDA akan melakukan POP. Contoh menunjukkan bahwa PDA dapat dinyatakan sebagai mesin PUSH-POP.

Berikut ini pengenalan string “baab” oleh PDA di atas :

1. (q 0 , baab, Z 0 )	⇒ (q 0 , aab, bZ 0 )		(2 kiri)
	⇒ (q 0 , ab, abZ 0 )		(5 kiri)
	⇒ (q 1	, ab, abZ 0 )	(3 kanan)
	⇒ (q 1	, b, bZ 0 )	(11)
	⇒ (q 1	, ε, Z 0 )	(10)
	⇒ (q 2 , ε, Z 0 )		(12)	(diterima)

2.	(q 0 , baab, Z 0 )	⇒ (q 1 , baab, Z 0 )		(2 kanan) (crash → ditolak)
3.	(q 0 , baab, Z 0 )	⇒ (q 0 , aab, bZ 0 )		(2 kiri)
		⇒ (q 0 , ab, abZ 0 )		(5 kiri)
		⇒ (q 0 , b, aabZ 0 )		(3 kiri)
		⇒ (q 1 , b, aabZ 0 )		(4 kanan) (crash → ditolak)
4.	(q 0 , baab, Z 0 )	⇒ (q 0 , aab, bZ 0 )		(2 kiri)
		⇒ (q 0	, ab, abZ 0 )	(5 kiri)
		⇒ (q 0	, b, aabZ 0 )	(3 kiri)
		⇒ (q 0	, ε, baabZ 0 )	(4 kiri)
		⇒ (q 1 , ε, baabZ 0 )		(9) (crash → ditolak)

Jika M = (Q, Σ, , q 0 , Z 0 , δ, A) adalah PDA dan x ∈Σ*, maka x diterima dengan stata akhir (accepted by final state) oleh PDA M jika : (q 0 , x, Z 0 ) ⇒* (q, ε, α) untuk α ∈

* dan q ∈ A. x diterima dengan stack hampa (accepted by empty stack) oleh PDA M jika : (q 0 , x, Z 0 ) ⇒* (q, ε, ε) untuk q ∈ Q.

Daftar Pustaka :

1. https://www.geeksforgeeks.org/introduction-of-pushdown-automata/

2. https://en.wikipedia.org/wiki/Pushdown_automaton

3. http://web.if.unila.ac.id/resalinaoktaria/2016/06/29/push-down-automata-ekivalensi-pda-dan-cfg-serta-deterministic-pda/

PENGANTAR APLIKASI KOMPUTER