PDA & Tata Bahasa Bebas Konteks

Jika tata bahasa G bebas konteks, kita dapat membuat PDA nondeterministik yang setara yang menerima bahasa yang dihasilkan oleh tata bahasa bebas konteks G. Parser dapat dibuat untuk tata bahasaG.

Juga, jika P adalah robot pushdown, tata bahasa G tanpa konteks yang setara dapat dibuat di mana

L(G) = L(P)

Pada dua topik berikutnya, kita akan membahas bagaimana mengkonversi dari PDA ke CFG dan sebaliknya.

Algoritma untuk mencari PDA yang sesuai dengan CFG tertentu

Input - CFG, G = (V, T, P, S)

Output- PDA Setara, P = (Q, ∑, S, δ, q ₀ , I, F)

Step 1 - Ubah produksi CFG menjadi GNF.

Step 2 - PDA hanya akan memiliki satu status {q}.

Step 3 - Simbol awal CFG akan menjadi simbol awal di PDA.

Step 4 - Semua non-terminal CFG akan menjadi simbol stack PDA dan semua terminal CFG akan menjadi simbol input PDA.

Step 5 - Untuk setiap produksi dalam bentuk A → aX dimana a adalah terminal dan A, X adalah kombinasi terminal dan non-terminal, buat transisi δ (q, a, A).

Masalah

Buat PDA dari CFG berikut.

G = ({S, X}, {a, b}, P, S)

dimana produksinya -

S → XS | ε , A → aXb | Ab | ab

Larutan

Biarkan PDA yang setara,

P = ({q}, {a, b}, {a, b, X, S}, δ, q, S)

dimana δ -

δ (q, ε, S) = {(q, XS), (q, ε)}

δ (q, ε, X) = {(q, aXb), (q, Xb), (q, ab)}

δ (q, a, a) = {(q, ε)}

δ (q, 1, 1) = {(q, ε)}

Algoritma untuk menemukan CFG yang sesuai dengan PDA tertentu

Input - CFG, G = (V, T, P, S)

Output- PDA Setara, P = (Q, ∑, S, δ, q ₀ , I, F) sedemikian rupa sehingga non-terminal dari tata bahasa G akan menjadi {X _wx | w, x ∈ Q} dan negara mulai akan A _{q0, F} .

Step 1- Untuk setiap w, x, y, z ∈ Q, m ∈ S dan a, b ∈ ∑ jika δ (w, a, ε) berisi (y, m) dan (z, b, m) berisi (x, ε), tambahkan aturan produksi X _wx → a X _yz b dalam tata bahasa G.

Step 2- Untuk setiap w, x, y, z ∈ Q, tambahkan aturan produksi X _wx → X _wy X _yx dalam tata bahasa G.

Step 3- Untuk w ∈ Q, tambahkan aturan produksi X _ww → ε dalam tata bahasa G.