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 :