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 CoRoutine''''''s...''

----
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 Lazy''''''List
	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 * Lazy''''''List[[other.head]]) + (self * other.tail) }
	end
	def closure
		return Lazy''''''List[[ "" ]] if self.empty?
		return closure( self.tail ) if self.head == ""
		return list( "" ) {
			self * closure
		}
	end
 end

 class String
	def atom
		EnumRegL''''''ang::Atom.new(self)
	end
 end

 module EnumRegL''''''ang

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

	VOID = Reg''''''Lang.new
	
	def VOID.enum
		list
	end

	class Atom < Reg''''''Lang
		def initialize( text )
			@text = text
		end

		def enum
			Lazy''''''List.from_enum [ @text ]
		end
	end

	class Option < Reg''''''Lang
		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 < Reg''''''Lang
		def initialize( lang )
			@lang = lang
		end
		def enum
			@lang.enum.closure
		end
	end
 end