Teknik Kompilasi Tugas Level 2

 STUDI KASUS NFA & DFA DAN PENGIRIMAN PARAMETER

Pengertian NFA & DFA Beserta Contoh Studi Kasusnya

NFA dan DFA adalah singkatan dari Non-deterministic Finite Automaton (Mesin Automat Terbatas Non-Deterministik) dan Deterministic Finite Automaton (Mesin Automat Terbatas Deterministik). Keduanya merupakan model matematika yang digunakan dalam teori bahasa formal dan otomata.

NFA adalah model otomata yang memiliki kemampuan non-deterministik, yang berarti pada suatu keadaan, mesin dapat memiliki lebih dari satu transisi yang mungkin untuk simbol masukan yang sama. Artinya, NFA dapat memasuki beberapa keadaan dalam satu langkah. NFA menggunakan himpunan keadaan, fungsi transisi, dan keadaan awal serta keadaan akhir untuk mengenali bahasa tertentu. Contoh aplikasi NFA adalah dalam pembacaan ekspresi reguler, pengenalan pola, atau pengenalan bahasa program.

DFA, di sisi lain, adalah model otomata yang bersifat deterministik, yang berarti pada setiap keadaan, mesin hanya memiliki satu transisi yang mungkin untuk simbol masukan yang diberikan. DFA memiliki himpunan keadaan, fungsi transisi, keadaan awal, dan keadaan akhir untuk mengenali bahasa tertentu. DFA umumnya digunakan dalam pemrosesan string, analisis lexer dalam kompilasi, atau validasi kata sandi.

Studi kasus:

Misalkan kita ingin membuat otomata untuk mengenali bahasa kata "dog" yang terdiri dari string yang hanya mengandung huruf 'd', 'o', dan 'g'. Berikut adalah langkah-langkah untuk mendesain NFA dan DFA yang mengenali bahasa tersebut.

NFA (Non-deterministic Finite Automaton):

Himpunan keadaan: {q0, q1, q2, q3}

Simbol masukan: {'d', 'o', 'g'}

Keadaan awal: q0

Keadaan akhir: q3

Fungsi transisi:

δ(q0, 'd') = {q1} (dari q0 ke q1)

δ(q1, 'o') = {q2} (dari q1 ke q2)

δ(q2, 'g') = {q3} (dari q2 ke q3)

DFA (Deterministic Finite Automaton):

Himpunan keadaan: {q0, q1, q2, q3}

Simbol masukan: {'d', 'o', 'g'}

Keadaan awal: q0

Keadaan akhir: q3

Fungsi transisi:

δ(q0, 'd') = q1 (dari q0 ke q1)

δ(q1, 'o') = q2 (dari q1 ke q2)

δ(q2, 'g') = q3 (dari q2 ke q3)

δ(q3, 'd') = q0 (dari q3 ke q0)

δ(q3, 'o') = q0 (dari q3 ke q0)

δ(q3, 'g') = q0 (dari q3 ke q0)

Dalam kasus ini, NFA akan memiliki beberapa transisi untuk simbol 'd', 'o', dan 'g', sedangkan DFA hanya memiliki satu transisi yang mungkin untuk setiap simbol masukan. Meskipun kedua otomata ini dapat mengenali bahasa yang sama, DFA bersifat deterministik dan hanya memiliki satu keadaan yang aktif pada suatu waktu, sementara NFA bersifat non-deterministik dan dapat memiliki beberapa keadaan yang aktif secara bersamaan.

Studi Kasus Pengiriman Parameter

Ada beberapa metode yang digunakan untuk mengirimkan parameter dalam pemrograman. Berikut adalah beberapa metode yang umum digunakan:

1. Metode Pemanggilan Nilai (Call by Value):

Pada metode ini, nilai parameter dikirimkan ke fungsi atau prosedur sebagai salinan nilai asli. Artinya, perubahan nilai parameter di dalam fungsi tidak akan mempengaruhi nilai aslinya di luar fungsi. Studi kasus:

def tambah(angka):

    angka = angka + 1

    print(angka)

angka = 5

tambah(angka)

print(angka)

output: 6 5

Nilai variabel angka tetap 5 di luar fungsi, meskipun di dalam fungsi nilainya ditambah 1.

2. Metode Pemanggilan Referensi (Call by Reference):

Pada metode ini, parameter dikirimkan ke fungsi sebagai referensi atau alamat dari nilai aslinya. Perubahan nilai parameter di dalam fungsi akan mempengaruhi nilai aslinya di luar fungsi. Studi kasus:

def tambah(angka):

    angka[0] = angka[0] + 1

    print(angka[0])

angka = [5]

tambah(angka)

print(angka[0])

output: 6 6

Nilai variabel angka berubah menjadi 6 di luar fungsi setelah diubah di dalam fungsi.

3. Metode Pemanggilan Pointer:

Metode ini mirip dengan pemanggilan referensi, di mana parameter dikirimkan sebagai alamat dari nilai aslinya. Namun, metode ini khusus digunakan dalam bahasa pemrograman yang mendukung pointer, seperti C atau C++. Dalam studi kasus ini, saya akan memberikan contoh dalam bahasa C++:

#include <iostream>

void tambah(int* angka) {

    *angka = *angka + 1;

    std::cout << *angka << std::endl;

}

int main() {

    int angka = 5;

    tambah(&angka);

    std::cout << angka << std::endl;

    return 0;

}

output: 6 6

Nilai variabel angka berubah menjadi 6 di luar fungsi setelah diubah di dalam fungsi.

Metode pemanggilan nilai, pemanggilan referensi, dan pemanggilan pointer adalah tiga metode umum yang digunakan untuk mengirimkan parameter. Pilihan metode yang tepat tergantung pada bahasa pemrograman yang digunakan dan kebutuhan spesifik dalam pengembangan perangkat lunak.