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.

[thumbnail of 5111100079-Undergraduate Thesis.pdf]
Preview
Text
5111100079-Undergraduate Thesis.pdf - Published Version

Download (13MB) | Preview

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 > 55201-(S1) Undergraduate Thesis
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