An Optimal Construction of Finite Automata from Regular Expressions

Authors Stefan Gulan, Henning Fernau



PDF
Thumbnail PDF

File

LIPIcs.FSTTCS.2008.1754.pdf
  • Filesize: 443 kB
  • 12 pages

Document Identifiers

Author Details

Stefan Gulan
Henning Fernau

Cite AsGet BibTex

Stefan Gulan and Henning Fernau. An Optimal Construction of Finite Automata from Regular Expressions. In IARCS Annual Conference on Foundations of Software Technology and Theoretical Computer Science. Leibniz International Proceedings in Informatics (LIPIcs), Volume 2, pp. 211-222, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2008)
https://doi.org/10.4230/LIPIcs.FSTTCS.2008.1754

Abstract

We consider the construction of finite automata from their corresponding regular expressions by a series of digraph-transformations along the expression\'s structure. Each intermediate graph represents an extended finite automaton accepting the same language. The character of our construction allows a fine-grained analysis of the emerging automaton\'s size, eventually leading to an optimality result.
Keywords
  • Finite automata,regular expressions,descriptional complexity

Metrics

  • Access Statistics
  • Total Accesses (updated on a weekly basis)
    0
    PDF Downloads
Questions / Remarks / Feedback
X

Feedback for Dagstuhl Publishing


Thanks for your feedback!

Feedback submitted

Could not send message

Please try again later or send an E-mail