Implementasi Model Deterministic Finite Automaton untuk Interpretasi Regular Expression pada Studi Kasus Permasalahan SPOJ Klasik 10354

Regular expression merupakan salah satu bentuk pola yang banyak digunakan untuk melakukan pencarian dan validasi string. Namun pada implementasinya sering kali regular expression hanya ditransformasi menjadi sebuah model Nondeterministic Finite Automaton (NF A) yang masih memiliki kekurangan apabila digunakan untuk melakukan validasi dan pencarian string. Kekurangan tersebut adalah lamanya waktu yang diperlukan untuk melakukan proses pencarian dan validasi. Pengembangan pencarian dan validasi dari model NFA teras berkembang dan memunculkan teknik konversi model NFA menjadi model Deterministic Finite Automaton (DFA) untuk menambah peiforma pencarian dan validasi. Dalam Tugas Akhir ini akan dibahas mengenai teknik yang digunakan dalam konversi model NFA ke DFA dan bagaimana implementasi tersebut dalam program. ======================================================================================================= Regular expression is a pattern that often used for searching and validate a string. But the implementation of regular expression often just transformed into Nondeterministic Finite Automaton (NF A) that still has flaws. One main flaw is NF A took a long time to do a validation and string matching. The development of validation and string matching is continuously expanding and some of discoveries are made to improve validation and string matching performance. One of them is converting NF A into Deterministic Finite Automaton (DFA) to reduce active states in NF A. In this final project conversion technique from NF A to DFA and how to implement that technique into a program will be explaine