KAL
Menu

Intuisi dari Regex ke DFA

Bagaimana pencocokan pola berbasis regex ditangani oleh otomata hingga pada lexer.

Daftar isi

Ekspresi reguler (regex) adalah notasi ringkas untuk menyatakan pola teks, dan otomata hingga adalah mesin abstrak yang dapat memutuskan apakah sebuah string cocok dengan pola itu. Topik ini menjelaskan bagaimana sebuah regex diubah menjadi otomata hingga, lalu bagaimana otomata itu dijalankan untuk menerima atau menolak string. Pembaca memperoleh intuisi yang menghubungkan notasi pola pada satu sisi dengan transisi karakter yang dilakukan scanner pada sisi lain.

Regex dan otomata hingga#

Regex menyatakan himpunan string lewat tiga operator dasar, yaitu urutan (ab), pilihan (a|b), dan pengulangan (a*). Operator ini cukup untuk menyatakan seluruh pola yang dikenali otomata hingga, sehingga keduanya ekuivalen dalam daya ekspresi. Bahasa reguler adalah himpunan string yang dapat dinyatakan dengan regex, dan himpunan itu persis yang dapat diterima oleh otomata hingga.

Otomata hingga memiliki sejumlah state, sebuah state awal, himpunan state penerima, dan tabel transisi yang memetakan pasangan (state, simbol) ke state berikutnya. Dua jenis otomata hingga yang dipakai adalah NFA (nondeterministic finite automaton) dan DFA (deterministic finite automaton). NFA memperbolehkan transisi ke beberapa state sekaligus untuk satu simbol, sedangkan DFA membatasi setiap simbol ke paling banyak satu state berikutnya. DFA lebih mudah dijalankan karena pada setiap langkah hanya ada satu state aktif, sedangkan NFA lebih ringkas untuk dibangun dari regex.

Lexer memakai otomata hingga untuk memutuskan lexeme mana yang dimulai pada posisi tertentu. Setiap kelas token memiliki pola sendiri, misalnya digit+ untuk NUMBER dan digit+ . digit+ untuk bagian desimal. Dalam praktik, scanner tulis tangan mengkodekan transisi otomata itu sebagai percabangan if dan while, sehingga diagram otomata tetap menjadi perangkat berpikir, bukan berkas yang dijalankan langsung.

Dari regex ke NFA#

Konversi regex ke NFA memakai teknik Thompson’s construction, yang membangun NFA secara rekursif sesuai struktur regex. Untuk regex ab, NFA dibangun dengan menyambung NFA a dan NFA b lewat transisi epsilon. Untuk regex a|b, dua NFA ditempatkan paralel dengan transisi epsilon dari state awal baru ke kedua state awal. Untuk regex a*, ditambahkan state awal baru yang dapat melompat ke NFA a, ke state penerima, atau kembali dari akhir NFA a ke awalnya.

Teknik ini menghasilkan NFA yang ukurannya linier terhadap panjang regex, sehingga pembangunan otomata dari regex menjadi murah. Namun, menjalankan NFA langsung memerlukan pelacakan himpunan state aktif pada setiap langkah, yang kurang efisien dibanding menjalankan DFA. Karena itu, biasanya NFA dikonversi lagi ke DFA sebelum dijalankan.

Untuk regex a(b|c)*, struktur NFA yang dibangun memiliki satu state awal untuk karakter a, lalu bercabang ke dua jalur untuk b dan c, dengan loop epsilon kembali ke titik cabang tersebut. Banyaknya transisi epsilon membuat NFA sulit dibaca jika digambar langsung, sehingga langkah konversi ke DFA menjadi penting untuk kejelasan. Pada NFA, himpunan state aktif dapat tumbuh melebihi satu pada titik cabang, sedangkan DFA meredusinya menjadi satu state aktif saja setelah konversi.

Dari NFA ke DFA#

Konversi NFA ke DFA memakai teknik subset construction. Setiap state DFA adalah himpunan state NFA yang dapat dicapai lewat transisi epsilon dan transisi biasa dari posisi saat ini. State awal DFA adalah epsilon-closure dari state awal NFA, yaitu himpunan state NFA yang dicapai tanpa mengonsumsi simbol apa pun. Transisi DFA dari himpunan S dengan simbol x adalah epsilon-closure dari himpunan state NFA yang dicapai dari S lewat x.

Untuk regex a(b|c)*, hasil konversi menghasilkan DFA dengan dua state yang berperan, yaitu q0 dan q1, ditambah satu state dead opsional. State q0 adalah state awal. Transisi q0 --a--> q1 memindahkan state aktif ke state penerima q1. Dari q1, simbol b dan c mempertahankan state aktif pada q1, sehingga q1 menjadi state penerima sekaligus loop. Simbol selain a, b, c masuk ke state dead yang tidak memiliki transisi keluar.

Jumlah state DFA dapat tumbuh eksponensial terhadap jumlah state NFA pada kasus terburuk, tetapi pada pola leksikal khas bahasa pemrograman, pertumbuhannya tetap terkendali. Algoritma subset construction berhenti ketika tidak ada lagi himpunan state NFA baru yang muncul, dan tabel transisi yang dihasilkan langsung dapat dipakai sebagai input scanner. Untuk bahasa mini v1, DFA setiap kelas token cukup kecil sehingga transisi dapat ditulis langsung sebagai kode Python, sebagaimana akan ditunjukkan oleh scanner tulis tangan.

Diagram DFA untuk a(b|c)*#

Diagram berikut memperlihatkan DFA hasil konversi regex a(b|c)*. State q0 adalah state awal, dan state q1 (ditandai lingkaran ganda) adalah state penerima. Transisi a dari q0 ke q1 dijalankan sekali pada awal string, lalu b dan c mempertahankan state aktif pada q1 selama karakter tersebut terus berlanjut.

startq0q1ab, cstate penerima
DFA untuk regex a(b|c)* dengan dua state: q0 sebagai state awal dan q1 sebagai state penerima

State dead yang menampung transisi selain a, b, dan c tidak digambar agar diagram tetap ringkas. Dalam implementasi, transisi yang tidak terdapat pada tabel dipandang sebagai transisi ke state dead, sehingga string seperti aba atau abx ditolak begitu karakter ketiga dibaca. Pada aba, karakter ketiga a tidak memiliki transisi keluar dari q1, sedangkan pada abx, karakter x memang berada di luar alphabet. Keduanya memasuki state dead dan tidak dapat kembali ke state penerima.

Simulasi transisi DFA#

Simulasi transisi DFA membantu memperjelas cara mesin ini beroperasi. Berkas dfa_demo.py berikut memodelkan DFA untuk a(b|c)* sebagai kelas DFA dengan tabel transisi, lalu menjalankan DFA pada sepuluh string uji. Setiap string dicocokkan langkah demi langkah, dan jalur state dicetak bersama keputusan akhir.

python dfa_demo.py 
"""Simulasi transisi DFA untuk pola regex a(b|c)* pada topik dari-regex-ke-dfa.

DFA ini memiliki tiga state:
  - q0: state awal, menerima 'a'
  - q1: state penerima, menerima 'b' atau 'c' berulang
  - qd: state dead (jebakan), tidak ada transisi keluar
"""
from collections import deque


class DFA:
    """Otomata hingga deterministik dengan tabel transisi eksplisit."""

    def __init__(self, states, alphabet, trans, start, accept):
        self.states = states
        self.alphabet = alphabet
        self.trans = trans            # dict[(state, simbol)] = state berikutnya
        self.start = start
        self.accept = accept          # himpunan state penerima

    def run(self, input_str):
        """Jalankan DFA pada seluruh string, kembalikan (state_akhir, jalur)."""
        state = self.start
        path = [state]
        for ch in input_str:
            state = self.trans.get((state, ch), "qd")
            path.append(state)
        return state, path

    def accept_q(self, input_str):
        """Apakah string diterima (state akhir termasuk state penerima)."""
        return self.run(input_str)[0] in self.accept


def main() -> None:
    # DFA untuk regex a(b|c)*
    #   q0 --a--> q1 (penerima)
    #   q1 --b--> q1
    #   q1 --c--> q1
    #   transisi lain --> qd (dead)
    dfa = DFA(
        states={"q0", "q1", "qd"},
        alphabet={"a", "b", "c"},
        trans={
            ("q0", "a"): "q1",
            ("q1", "b"): "q1",
            ("q1", "c"): "q1",
        },
        start="q0",
        accept={"q1"},
    )

    uji = ["a", "ab", "ac", "abc", "abcb", "abbccb", "b", "aba", "abx", ""]
    for s in uji:
        state, path = dfa.run(s)
        diterima = state in dfa.accept
        rep = s if s != "" else "(kosong)"
        print(f"{rep!s:<10} -> {state}  path={path}  diterima={diterima}")


if __name__ == "__main__":
    main()

Keluaran berikut diperoleh dengan menjalankan python3 dfa_demo.py. Baris-baris yang berakhir dengan diterima=True adalah string yang diterima DFA, yaitu string yang diawali a dan dilanjutkan nol atau lebih karakter b atau c. String b ditolak karena tidak diawali a, sedangkan aba ditolak karena karakter ketiga a tidak memiliki transisi keluar dari q1, dan abx ditolak karena karakter x berada di luar alphabet.

text Keluaran 
a          -> q1  path=['q0', 'q1']  diterima=True
ab         -> q1  path=['q0', 'q1', 'q1']  diterima=True
ac         -> q1  path=['q0', 'q1', 'q1']  diterima=True
abc        -> q1  path=['q0', 'q1', 'q1', 'q1']  diterima=True
abcb       -> q1  path=['q0', 'q1', 'q1', 'q1', 'q1']  diterima=True
abbccb     -> q1  path=['q0', 'q1', 'q1', 'q1', 'q1', 'q1', 'q1']  diterima=True
b          -> qd  path=['q0', 'qd']  diterima=False
aba        -> qd  path=['q0', 'q1', 'q1', 'qd']  diterima=False
abx        -> qd  path=['q0', 'q1', 'q1', 'qd']  diterima=False
(kosong)   -> q0  path=['q0']  diterima=False

State qd hanya muncul pada string yang ditolak. Karena tidak ada transisi keluar dari qd, sekali string memasuki state ini, kesimpulan akhir sudah pasti diterima=False. Perilaku ini cocok dengan cara scanner menangani karakter di luar pola yang sedang dicocokkan, yaitu menghentikan pemindaian lexeme dan mengembalikan kendali ke loop utama.

Hubungannya dengan scanner tulis tangan#

Scanner tulis tangan mengkodekan transisi DFA sebagai percabangan dalam kode Python. State menjadi variabel lokal yang berubah saat karakter dikonsumsi, dan transisi menjadi blok if yang memeriksa karakter berikutnya. Loop while yang mengonsumsi karakter selama kondisi terpenuhi menyatakan loop pada state penerima, sedangkan transisi ke state dead diekspresikan dengan keluar dari loop dan mengembalikan token.

Pendekatan tulis tangan dipilih karena pola leksikal bahasa mini v1 sederhana, sehingga DFA setiap kelas token dapat ditulis dalam beberapa baris. Pendekatan berbasis generator lexer seperti lex atau re2c bekerja dengan cara yang sama, tetapi menjadikan transisi DFA sebagai tabel yang dihasilkan otomatis dari deklarasi regex. Pemahaman tentang konversi regex ke DFA membantu saat tabel transisi yang dihasilkan perlu diperiksa atau saat pola baru menunjukkan perilaku yang tak terduga.

Ringkasan#

  • Regex dan otomata hingga ekuivalen dalam daya ekspresi untuk bahasa reguler, sehingga pola leksikal dapat dinyatakan dengan salah satunya.
  • Konversi regex ke DFA dilakukan dua tahap, yaitu pembangunan NFA dengan Thompson’s construction, lalu konversi NFA ke DFA dengan subset construction.
  • DFA untuk a(b|c)* memiliki dua state berperan (q0 dan q1) ditambah satu state dead, dengan transisi a dari q0 ke q1 dan loop b, c pada q1.
  • Scanner tulis tangan mengkodekan transisi DFA sebagai percabangan dan loop, sehingga diagram otomata tetap menjadi perangkat berpikir, bukan berkas yang dijalankan langsung.

Referensi#