Analisis Perbandingan DFA dan NFA Dalam Pencocokan String

Abstract

String matching is a fundamental process in pattern recognition systems and large-scale text processing, where computational efficiency significantly affects system performance. This study analyzes the comparison between Deterministic Finite Automata (DFA) and Non-deterministic Finite Automata (NFA) in string matching using the pattern (a|b)*abb. The research was implemented through a web-based simulator developed with JavaScript, HTML, and CSS and evaluated using eight short test strings representing accepted and rejected inputs, as well as longer strings to observe execution time differences. The results indicate that DFA and NFA produce identical acceptance outcomes for all test cases, indicating that both automata recognize the same language. However, DFA demonstrates better computational efficiency because each input symbol is processed through a single deterministic transition, whereas NFA requires tracking a set of active states, which increases computational overhead. For longer strings, the execution time gap becomes more pronounced, with DFA remaining consistently faster than NFA. These findings suggest that DFA is more suitable for string matching applications requiring time efficiency, while NFA offers greater flexibility in transition design.