Enumerating Regular Languages

A problem proposed by Jayadev Misra is allegedly a good test for qualities of a language, methodology, individual technique, etc. We can look at it as a good LanguageTestCase. Of course, being heavily algorithmic in nature most OO languages do not fare well with regards to EconomyOfExpression, and to my chagrin it's not even clear how SchemeLanguage can compete with HaskellLanguage and MlLanguage.

The problem is stated as follows: you have a regular language described by a given RegularExpression. Given a natural number N, enumerate the first N strings in that language in a modified lexicographical order: the strings are compared first on their length and two strings of the same length are considered in lexicographical order, with some ordering imposed on the characters of the alphabet (assume ASCII ordering, to keep the problem simpler).

The simplest idea is to generate a (optimized if possible) NondeterministicFiniteAutomaton? that recognizes the language, and emulate its functioning for an unknown input source (do it in reverse, the automaton unrolls the imaginary input source) while when reaching final states outputting the string that led to that final state. A nice Haskell solution can be picked up from DougMcIlroy page. It's an outstanding demonstration of the EconomyOfExpression qualities of HaskellLanguage.

Another brute force solution would be to enumerate all strings in lexicographical order (at least limit the alphabet to the characters present in the RE) while testing for matching and counting up to N. Of course that won't give you much elegance points (and don't try this at home for large expression or big N, you may be disappointed).

Sounds like a job involving lots of CoRoutines...

---

I've translated the version in the paper published at http://www.cs.utexas.edu/users/misra/Notes.dir/RegExp.pdf from HaskellLanguage to RubyLanguage. I've used the lazy lists library for Ruby to handle the lists (http://lazylist.rubyforge.org/). The code base length is just a little bit longer than the original and it's almost copied from there. -- AurelianoCalvo.

Usage is like this:

((("A".atom | "B".atom).repeat ) + "C!".atom).enum.take( 10 ) #enumerates the 10 first elements of the RegularExpression language (a|b)*C!.

The result is:

["C!", "AC!", "BC!", "AAC!", "ABC!", "BAC!", "BBC!", "AAAC!", "AABC!", "ABAC!"]

Below is the implementation:

 require 'lazylist'

 class LazyList
def + (other)
self.merge( other ) do 
|a,b| 
a.length != b.length ? a.length < b.length : a < b
end
end
def * (other)
return list if self.empty? or other.empty?
return list( self.head + other.head ) {
(self.tail * LazyList[[other.head]]) + (self * other.tail) }
end
def closure
return LazyList[[ "" ]] if self.empty?
return closure( self.tail ) if self.head == ""
return list( "" ) {
self * closure
}
end
 end

 class String
def atom
EnumRegLang::Atom.new(self)
end
 end

 module EnumRegLang

class RegLang
def | (other)
Option.new( self, other )
end
def + (other)
Concat.new( self, other )
end
def repeat
Repeat.new( self )
end
end

VOID = RegLang.new

def VOID.enum
list
end

class Atom < RegLang
def initialize( text )
@text = text
end

def enum
LazyList.from_enum [ @text ]
end
end

class Option < RegLang
def initialize( lang1, lang2 )
@lang1 = lang1
@lang2 = lang2
end
def enum
@lang1.enum + @lang2.enum
end
end

class Concat
def initialize( lang1, lang2 )
@lang1 = lang1
@lang2 = lang2
end
def enum
@lang1.enum * @lang2.enum
end
end

class Repeat < RegLang
def initialize( lang )
@lang = lang
end
def enum
@lang.enum.closure
end
end
 end