Haskell code is developed for two ways to list the strings of the language defined by a regular expression: directly by set operations and indirectly by converting to and simulating an equivalent automaton. The exercise illustrates techniques for dealing with infinite ordered domains and leads to an effective standard form for nondeterministic finite automata. Lazy languages are well suited to sequence generation because of the ease with which they handle infinite sequences. The problem of enumerating the strings of a regular language was proposed by Jay Misra as a lovely case in point, simple to state, yet tricky to solve. This paper develops two concise and radically different solutions in Haskell (Peterson et al., 1998) , one direct and one indirect. Both approaches exploit Haskell's outstanding fitness for structural induction. The direct approach interprets regular expressions as recipes for building sets. Here the main concern is programming the primitives for combining sets: union, cross-product, and closure under a binary operation. The primitives apply to any well ordered domain. The indirect approach detours through automata, first constructing an equivalent nondeterministic finite automaton, then tracing execution paths of the automaton in breadth-first order. The automata have an unusual shape: besides a single final state, there is exactly one state per symbol in the regular expression and that state accepts only the one symbol. The set operations developed for the first solution are used again, this time for combining sets of states rather than sets of strings. Working Haskell code is available electronically. (McIlroy, 2003) 1 The problem Devise a program to enumerate the distinct strings of the regular language denoted by a given regular expression. The resulting list should be ordered by string length and lexicographically within each length. Parsing is not at issue; regular expressions are taken to be already parsed data structures.
REF implements the enumeration of all strings of a regular language in Haskell.
Enumerating the strings of regular languages
J. Funct. Program.
J. Funct. Program.
Computer Science