Skip to main content

Regular Expressions and Automata using Haskell

Thompson, Simon (2000) Regular Expressions and Automata using Haskell. Technical report. University of Kent (KAR id:22057)

Postscript
Language: English
Download (341kB) Preview
[thumbnail of Regular_Expressions_and_Automata_using_Haskell.ps]
Preview
This file may not be suitable for users of assistive technology.
Request an accessible format
PDF
Language: English
Download (116kB) Preview
[thumbnail of Regular_Expressions_and_Automata_using_Haskell.pdf]
Preview
This file may not be suitable for users of assistive technology.
Request an accessible format

Abstract

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.

Item Type: Monograph (Technical report)
Uncontrolled keywords: regular expression automaton NFA DFA minimisation matching
Subjects: Q Science > QA Mathematics (inc Computing science) > QA 76 Software, computer programming,
Divisions: Divisions > Division of Computing, Engineering and Mathematical Sciences > School of Computing
Depositing User: Mark Wheadon
Date Deposited: 27 Aug 2009 14:21 UTC
Last Modified: 16 Feb 2021 12:33 UTC
Resource URI: https://kar.kent.ac.uk/id/eprint/22057 (The current URI for this page, for reference purposes)
Thompson, Simon: https://orcid.org/0000-0002-2350-301X
  • Depositors only (login required):

Downloads

Downloads per month over past year