Citation |
From Regular Expressions to Finite Automata, International Journal of Computer Mathematics, 72(4):415-431, 1999.
, |
---|---|
Descriptions |
Abstract:
There are three classical algorithms to compute a finite automaton from a regular expression. The Brzozowski algorithm yields a deterministic automaton, the Glushkov algorithm a nondeterministic one, and the general step by step method generally yields a NFA with ε-transitions. Berry and Sethi have adapted Brzozowski's algorithm to compute the Glushkov automaton of an expression. We describe a variant of the step by step construction which associates standard and trim automata to regular languages. We show that the automaton constructed by the variant and the Glushkov automaton (computed by Berry-Sethi algorithm) are isomorphic. Annotation:
Keywords: Regular Expression0.9; |
Resources | |
Bibliography Navigation: Reference List; Author Index; Title Index; Keyword Index
Generated by sharef2html
on 2011-04-15, 02:00:41.