Combining regular expressions with near-optimal automata

B.W. Watson, M. Frishert, L.G.W.A. Cleophas

Research output: Chapter in Book/Report/Conference proceedingChapterAcademic

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 publicationInquiries into Words, Constraints and Contexts (Festschrift in the Honour of Professor Kimmo Koskenniemi on his 60th Birthday)
EditorsA. Arppe, xx et al.
Place of PublicationStanford CA, USA
PublisherCSLI
Pages163-171
Publication statusPublished - 2005

Publication series

NameCSLI Studies in Computational Linguistics

Fingerprint

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

Cite this