Academic
Publications
Converting Deterministic Finite Automata to Regular Expressions

Converting Deterministic Finite Automata to Regular Expressions,Christoph Neumann

Converting Deterministic Finite Automata to Regular Expressions   (Citations: 6)
BibTex | RIS | RefWorks Download
This paper explores three techniques for converting deterministic - nite automata (DFA) to regular expressions and compares the usefulness of each technique. The techniques examined are the transitive closure method, the state removal method, and the Brzozowski algebraic method. 1 Background Kleene's seminal article denes regular expressions and their relationship to nite automata (7). Kleene proves the equivalence of nite automata and regular expressions thereby providing us with the rst technique, the transitive closure method, for converting DFAs to regular expressions. Later Brzozowski expanded on Kleene's method by introducing the notion of derivatives of regular expressions (3), but his paper passed into obscurity until G. Berry and R. Sethi brought Brzozowski's paper to the forefront in (2)1. The state removal method appears in (4) but Linz presents a more
Cumulative Annual
Sort by: