School of Computing

Regular Expressions and Automata using Haskell

Simon Thompson

Technical Report 5-00, Computing Laboratory, University of Kent, January 2000.


Regular Expressions and Automata

Regular Expressions and Automata

The paper begins with definitions of regular expressions, and how strings are matched to them; this also gives our first Haskell treatment also. After describing the abstract data type of sets we define non-deterministic finite automata, and their implementation in Haskell. We then show how to build an NFA corresponding to each regular expression, and how such a machine can be optimised, first by transforming it into a deterministic machine, and then by minimising the state space of the DFA. We conclude with a discussion of regular definitions, and show how recognisers for strings matching regular definitions can be built.

Download publication 333 kbytes (PostScript)

Bibtex Record

author = {Simon Thompson},
title = {{Regular Expressions and Automata using Haskell}},
month = {January},
year = {2000},
pages = {182-196},
keywords = {determinacy analysis, Craig interpolants},
note = {},
doi = {},
url = {},
    institution = {Computing Laboratory, University of Kent},
    number = {5-00},
    publication_type = {techreport},
    submission_id = {23260_948360512},
    type = {Technical Report},

School of Computing, University of Kent, Canterbury, Kent, CT2 7NF

Enquiries: +44 (0)1227 824180 or contact us.

Last Updated: 21/03/2014