Pada penerapan ekspresi regular sebuah bahasa dikatakan regular, jika terdapat Finite State Automata yang menerimanya.
Bahasa-bahasa yang diterima suatu Finite State Automata bisa dinyatakan sederhana dengan ekspresi regular
Penerapan Ekspresi Regular (ER)
ER dimana memerikan suatu pola atau template untuk untai dari suatu bahasa, untai yang dimaksud yaitu yang menyusun dari suatu bahasa regular akan cocok dengan pola bahasa tersebut. Penerapan ekspresi regular yang tampak, misalnya pencarian (searching), utai karakter (string).
Contoh penerapan yang lain adalah pembatasan data masukan yang diperkenankan, misalnya suatu field masukan hanya menerima input (0….9).
Bila dalam bahasa indonesia bisa dikatakan bahwa automata pada gambar 1 menerima masukan simbol input antara 0 sampai 9 sedangkan ekspresi regularnya dinyatakan sebagai: (digit) (digit)*.
Dengan digit adalah 0….9.
Dalam implementasi suatu FSA akan diterjemahkan menjadi kode dalam sebuah bahasa pemrograman.
Notasi Ekspresi Regular
Berikut notasi yang akan kita gunakan: (*) , (+) , (+) , (∪), ‘.’ :
* yaitu karakter asterik, berarti bisa tidak muncul, bisa juga muncul berhingga kali (0-n)
+ (pada posisi superscript/diatas) berarti minimal muncul satu kali (1-n)
+ atau ∪ berarti union
. (titik) berarti konkatenasi, biasasanya titik dihilangkan, misal: ab bermakna sama seperti a.b
Contoh ekspresi regular (ER)
- ER : ab*cc
contoh string yang dibangkitkan: abcc, abbcc, abbbcc, abbbbcc, acc - ER : 010*
contoh string yang dibangkitkan: 01, 010, 0100, 01000 - ER : a*d
contoh string yang dibangkitkan: d, ad, aad, aaad - ER : a+d
contoh string yang dibangkitkan: ad, aad, aaad
(a minimal muncul sekali) - ER : a*∪b* (ingat ‘∪’ berarti atau)
contoh string yang dibangkitkan: a, b, aa, bb, aaa, bbb, aaaa, bbbb - ER : a∪b
contoh string yang dibangkitkan: a, b - ER : 01*+0
contoh string yang dibangkitkan: 0, 01, 011, 0111, 01111
Hubungan ER dan FSA
untuk setiap ER ada satu NDFA dengan transisi ∈ (NFA ∈-move) yang ekivalen.
Sementara untuk setiap DFA ada satu ER dari bahasa yang diterima oleh DFA.
Yang perlu diperhatikan state akhir akan menandakan apakah input diterima atau tidak.
contoh NFA ∈-move untuk ER : ab
contoh NFA ∈-move untuk ER : a*b
contoh NFA ∈-move untuk ER : a∪b
Kemudian dari NDFA ∈-move tersebut kita ubah ke NDFA dan selanjutnya ke DFA atau prosesnya sebagai berikut:
NFA ∈-move → NFA → DFA
Bila ER cukup sederhana kita bisa langsung mengkonstruksikan NFA nya tanpa melalui NFA ∈-move.
Contoh NFA untuk ER : ab
Contoh NFA untuk ER : a∪b
Contoh NFA untuk ER : 010*
Contoh NFA untuk ER : 0(1∪0)
Contoh NFA untuk ER : 0(1∪0)*
Contoh NFA untuk ER : 01* 0
Contoh NFA untuk ER : 0*10*
Contoh NFA untuk ER : a*
Contoh NFA untuk ER : a(ba)*
