Teknik Kompilasi : KONVERSI REGULAR EXPESSION KE Ꜫ – NFA

Regular Expession atau yang biasa kita sebut Regex atau RE adalah konstruksi bahasa untuk  mencocokkan teks dengan pola tertentu. Regular expression sangat dibutuhkan untuk menyederhanakan pencarian teks teutama untuk kasus-kasus yang kompleks.  Selain itu Regular Expression juga sering digunakan untuk proses  text parsing (penguraian kata).

Ꜫ – NFA adalah NFA yang memungkinkan adanya transisi antara input kosong (empty) dari suatu state.

Berikut contoh konversi dari Regular Expression (RE) ke Ꜫ – NFA dengan menggunakan Thompson’s Construction :

Teorema :

Setiap Regular Expression R dapat dibuat Ꜫ – NFA, sehingga L (M) = L (R)

Pembuktian :