Deterministic PDA (DPDA)

Back to IF2224 Teori Bahasa Formal dan Otomata

Ekuivalensi PDA & CFG (Bagian 3: Deterministic Pushdown Automata - DPDA)

Questions/Cues

• Apa itu Deterministic PDA (DPDA)?

• Apa 2 kondisi determinisme?

• Contoh: $L_{wcwr}$

• Bagaimana hirarki bahasa (Regular, L(DPDA), CFL)?

• Kenapa $L_{wwr}$ bukan L(DPDA)?

• Apa itu Prefix Property?

• Hubungan DPDA (Empty Stack) & Prefix Property

• Teorema 6.19

• Hubungan DPDA & Ambiguitas

• Teorema 6.20 & 6.21

Reference Points

• Slide 12_2023_Equivalence PDA and CFG.pdf (hlm. 21-25)

Apa itu Deterministic PDA (DPDA)?

Sebuah Deterministic Pushdown Automata (DPDA) adalah PDA yang tidak pernah memiliki pilihan (non-determinisme) dalam langkah komputasinya.

Untuk setiap konfigurasi (state, input, top stack), hanya ada paling banyak satu langkah selanjutnya yang mungkin.

Dua Kondisi Determinisme

Sebuah PDA $P$ bersifat deterministik jika kedua kondisi berikut terpenuhi:

1. Tidak Ada Pilihan Ganda untuk Input:

   • $\delta (q,a,X)$ selalu berisi paling banyak satu anggota. (PDA tidak bisa memilih antara $(p_1,{\alpha }_1)$ dan $(p_2,{\alpha }_2)$).

2. Tidak Ada Pilihan $ϵ$ vs Input:

   • Jika $\delta (q,ϵ,X)$ tidak kosong (ada transisi $ϵ$), maka $\delta (q,a,X)$ harus kosong untuk setiap $a\in \Sigma$. (PDA tidak bisa memilih antara “melakukan transisi $ϵ$” atau “membaca input $a$”).

Contoh: $L_{wcwr}$

Bahasa $L_{wcwr}=\{wc{w}^R:w\in \{0,1{\}}^{\ast }\}$ (contoh: “01c10”) dapat dikenali oleh DPDA.

• Cara Kerja:

  1. Di $q_0$, PUSH semua simbol input ke stack.

  2. Jika membaca ‘c’, pindah ke state $q_1$ (tanpa mengubah stack).

  3. Di $q_1$, POP stack untuk setiap input yang cocok.

  4. Jika stack kosong ($Z_0$) di akhir, pindah ke $q_2$ (final state).

• Kenapa Deterministik? Simbol ‘c’ bertindak sebagai penanda yang jelas. PDA tidak perlu “menebak” kapan harus beralih dari mode PUSH ke POP.

Hirarki Bahasa (Regular $\subset$ L(DPDA) $\subset$ CFL)

DPDA mendefinisikan kelas bahasa baru, $L(DPDA)$.

1. Regular $\subset$ L(DPDA): Setiap bahasa Regular dapat dikenali oleh DPDA (yang pada dasarnya mengabaikan stack-nya, seperti DFA).

2. L(DPDA) $\subset$ CFL:

   • Ada bahasa $L(DPDA)$ yang tidak Regular (contoh: $L_{wcwr}$).

   • Ada bahasa CFL yang tidak L(DPDA) (contoh: $L_{wwr}$).

Kenapa $L_{wwr}$ bukan L(DPDA)?

Bahasa $L_{wwr}=\{w{w}^R\}$ (palindrom genap, misal “0110”) tidak bisa dikenali oleh DPDA.

• Alasan: PDA untuk $L_{wwr}$ harus “menebak” di mana titik tengah string (batas antara $w$ dan $w^R$).

• Sebuah DPDA tidak bisa menebak. Jika ia melihat input “0110”, ia tidak tahu apakah harus PUSH ‘1’ (karena masih di $w$) atau POP ‘1’ (karena sudah di $w^R$).

Prefix Property

Sebuah bahasa $L$ memiliki prefix property jika tidak ada string di $L$ yang merupakan prefix (awalan) dari string lain di $L$.

• Contoh Punya: $L_{wcwr}$. String “0c0” ada di $L$, tapi “0c01c1” tidak. Tidak ada string yang jadi awalan string lain.

• Contoh Tidak Punya: $\{0{\}}^{\ast }=\{ϵ,0,00,000,\dots \}$. String “0” ada di $L$ dan juga merupakan prefix dari “00” yang juga ada di $L$.

Teorema 6.19: DPDA (Empty Stack) & Prefix Property

Metode penerimaan sangat penting untuk DPDA.

• DPDA yang menerima via empty stack ($N(P)$) memiliki masalah: jika $w$ diterima (stack kosong), DPDA tidak bisa melanjutkan komputasi untuk $wx$ (karena stack sudah kosong).

• Teorema: Sebuah bahasa $L$ adalah $N(P)$ untuk suatu DPDA $P$ jika dan hanya jika $L$ memiliki prefix property DAN $L$ adalah $L(P^{\prime })$ untuk suatu DPDA $P^{\prime }$ (by final state).

DPDA & Ambiguitas

DPDA memiliki hubungan erat dengan grammar yang tidak ambigu.

• Ambiguitas: Grammar G bersifat ambigu jika ada setidaknya satu string $w\in L(G)$ yang memiliki dua atau lebih leftmost derivation (atau parse tree) yang berbeda.

• Teorema 6.20 & 6.21: Jika sebuah bahasa $L$ diterima oleh DPDA (baik $L(P)$ maupun $N(P)$), maka $L$ dijamin memiliki CFG yang unambiguous.

• Poin Penting:

  1. $L(DPDA)\subset$ Himpunan Bahasa Non-Ambigu.
  2. Kebalikannya tidak berlaku. $L_{wwr}$ memiliki grammar non-ambigu ($S\to 0S0\mid 1S1\mid ϵ$), tapi $L_{wwr}$ bukan L(DPDA).

Summary

Sebuah Deterministic PDA (DPDA) adalah PDA yang tidak memiliki pilihan (non-determinisme) pada setiap langkahnya, yang diatur oleh dua kondisi ketat. Kelas bahasa yang dikenali DPDA, $L(DPDA)$, lebih kuat dari Regular (bisa mengenali $L_{wcwr}$) tetapi lebih lemah dari CFL (tidak bisa mengenali $L_{wwr}$ karena DPDA tidak bisa “menebak”). DPDA yang menerima via empty stack hanya bisa mengenali bahasa dengan prefix property. Yang terpenting, setiap bahasa yang diterima oleh DPDA dijamin dapat dibangkitkan oleh CFG yang tidak ambigu.

Additional Information

$L(DPDA)$ vs $N(DPDA)$

Tidak seperti PDA non-deterministik, pada DPDA, pilihan metode penerimaan (final state vs empty stack) sangat berpengaruh.

• $L(DPDA)$ (by final state) adalah kelas bahasa yang diterima oleh DPDA.

• $N(DPDA)$ (by empty stack) adalah subset dari $L(DPDA)$ yang hanya berisi bahasa-bahasa dengan prefix property.

• $L(DPDA)$ lebih kuat dari $N(DPDA)$. Contoh: Bahasa $\{0{\}}^{\ast }$ dapat diterima oleh DPDA final state, tetapi tidak oleh DPDA empty stack (karena tidak punya prefix property).

Parsing dan DPDA

Konsep DPDA adalah fondasi teoretis untuk parser yang digunakan dalam kompilator (misalnya, parser LALR(1) yang digunakan oleh YACC/Bison). Bahasa pemrograman dirancang agar deterministic context-free sehingga dapat di-parse secara efisien (tanpa backtracking) oleh mesin yang mirip DPDA. Inilah mengapa $L(DPDA)$ adalah kelas bahasa yang sangat penting dalam ilmu komputer praktis.

Eksplorasi Mandiri

• Coba buktikan secara informal mengapa $L=\{a^n{b}^n\mid n\ge 0\}\cup \{a^n{b}^{2n}\mid n\ge 0\}$ tidak dapat diterima oleh DPDA. (Petunjuk: Saat membaca $a$, DPDA tidak tahu apakah harus mencocokkannya dengan $b^n$ atau $b^{2n}$).