Combining regular expressions with (near-)optimal Brzozowski automata

M. Frishert, B.W. Watson

Onderzoeksoutput: Hoofdstuk in Boek/Rapport/CongresprocedureConferentiebijdrageAcademicpeer review

1 Downloads (Pure)


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.
Originele taal-2Engels
TitelImplementation and Application of Automata (Revised Selected Papers, Ninth International Conference, CIAA 2004, Kingston ON, Canada, July 22-24, 2004)
RedacteurenM. Domaratzki, A. Okhotin, K. Salomaa, S. Yu
Plaats van productieBerlin
ISBN van geprinte versie3-540-24318-6
StatusGepubliceerd - 2005

Publicatie series

NaamLecture Notes in Computer Science
ISSN van geprinte versie0302-9743


Duik in de onderzoeksthema's van 'Combining regular expressions with (near-)optimal Brzozowski automata'. Samen vormen ze een unieke vingerafdruk.

Citeer dit