Catatan Kuliah tentang Push Down Automata

Pembukaan

• Assalamualaikum w.w.
• Selamat pagi, suara terdengar?
• Libur panjang sudah selesai, minal aidin wal faizin.
• Kelas online, pertemuan tatap muka pekan depan.

Informasi Umum

• Pretest dan posttest belum diperiksa, akan diperiksa akhir pekan ini.
• Remedial tersedia untuk yang nilainya di bawah 50.
• Tidak ada remedial untuk yang mengikuti ujian susulan.

Materi Baru: Push Down Automata (PDA)

• Finite Automata (FA)
  • Automata paling sederhana, menerima bahasa reguler.
  • Digunakan dalam pengenalan pola dan perancangan rangkaian.
• Push Down Automata
  • Versi upgrade dari FA.
  • Memiliki stack untuk menyimpan informasi yang dibaca.
  • Berguna untuk mengenali bahasa yang lebih kompleks.

Pengenalan Stack

• Stack: Struktur data Last In First Out (LIFO).
  • Operasi: Push (menambah) dan Pop (mengambil).
  • Digunakan dalam PDA untuk menyimpan simbol yang dibaca sebelumnya.

Transisi dalam PDA

• Transisi dalam PDA terdiri dari:
  • State awal, simbol input, simbol yang akan dipop, state tujuan, simbol yang akan dipush.
  • Contoh transisi: P, X, S, Q, T (dari state P ke Q).

Contoh Bahasa yang Diterima oleh PDA

• PDA dapat menerima bahasa yang lebih kompleks dari FA, seperti:
  • 0^n 1^n: Bahasa yang memiliki n banyak 0 diikuti n banyak 1.

Teorema Pumping

• Pumping lemma: Kriteria untuk menentukan apakah bahasa adalah bahasa reguler.
• Jika suatu bahasa tidak memenuhi kriteria pumping, maka itu bukan bahasa reguler.

Pembuktian Bahasa Bukan Reguler

1. Misalkan bahasa adalah reguler.
2. Temukan keterbatasan dengan menggunakan pumping lemma.
3. Tunjukkan kontradiksi dari asumsi awal.

Contoh Penggunaan PDA

• Menerima bahasa 0^n 1^n:
  1. Push 0 ke stack untuk setiap 0 yang dibaca.
  2. Pop 0 dari stack untuk setiap 1 yang dibaca.
  3. Pastikan stack kosong di akhir pembacaan.

Pengosongan Stack

• Penting untuk memastikan stack kosong di akhir pembacaan untuk menandakan bahasa diterima.

Contoh Lain

• Menerima bahasa 0^n 1^m dan 0^m:
  • Push 0 untuk setiap kemunculan 0, pop untuk setiap 1, dan pastikan bahasa sesuai dengan ketentuan n dan m.

Penutup

• Pertanyaan sebelum cek presensi?
• Tugas dan materi akan dilanjutkan minggu depan.