School of Computing

Regular Expressions and Automata using Haskell

Simon Thompson

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

Abstract

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

@techreport{958,
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 = {http://www.cs.kent.ac.uk/pubs/2000/958},
    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