Combining regular expressions with (near-)optimal Brzozowski automata

M. Frishert, B.W. Watson

Research output: Chapter in Book/Report/Conference proceedingConference contributionAcademicpeer-review

1 Downloads (Pure)

Abstract

Derivatives of regular expressions were first introduced by Brzozowski in [1]. By recursively computing all derivatives of a regular expression, and associating a state with each unique derivative, a deterministic finite automaton can be constructed. Convergence of this process is guaranteed if uniqueness of regular expressions is recognized modulo associativity, commutativity, and idempotence of the union operator. Additionaly, through simplification based on the identities for regular expressions, the number of derivatives can be further reduced.
Original languageEnglish
Title of host publicationImplementation and Application of Automata (Revised Selected Papers, Ninth International Conference, CIAA 2004, Kingston ON, Canada, July 22-24, 2004)
EditorsM. Domaratzki, A. Okhotin, K. Salomaa, S. Yu
Place of PublicationBerlin
PublisherSpringer
Pages319-320
ISBN (Print)3-540-24318-6
DOIs
Publication statusPublished - 2005

Publication series

NameLecture Notes in Computer Science
Volume3317
ISSN (Print)0302-9743

Fingerprint Dive into the research topics of 'Combining regular expressions with (near-)optimal Brzozowski automata'. Together they form a unique fingerprint.

Cite this