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

Bahari, Muhammad Yunus (2015) Implementasi Model Deterministic Finite Automaton untuk Interpretasi Regular Expression pada Studi Kasus Permasalahan SPOJ Klasik 10354. Undergraduate thesis, Institut Technology Sepuluh Nopember.

[img] Text
5111100079-Undergraduate Thesis.pdf - Published Version

Download (13MB)

Abstract

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 explained

Item Type: Thesis (Undergraduate)
Additional Information: RSIf 005.133 Bah i
Uncontrolled Keywords: Deterministic Finite Automaton, Nondeterministic Finite Atomaton, Regular expression, SPOJ.
Subjects: Q Science > QA Mathematics > QA76.6 Computer programming.
Divisions: Faculty of Information Technology > Informatics Engineering > (S1) Undergraduate Theses
Depositing User: Mr. Tondo Indra Nyata
Date Deposited: 20 Sep 2019 03:29
Last Modified: 20 Sep 2019 03:29
URI: http://repository.its.ac.id/id/eprint/70850

Actions (login required)

View Item View Item