Observations

http://blog.sigfpe.com/2010/08/constraining-types-with-regular.html 

 A finite monoid can be decomposed to a bunch of simple finite groups (afaik, there are 26 kinds of them) and a parallel array of flip-flops.
Since an FSM is basically a monoid, an FSM can be decomposed the same way.

And I wonder, regexes, they can be decomposed/classified the same way.

Anybody here familiar with all this? I just found it.

http://ivan-gandhi.livejournal.com/2488144.html

Yes, I was convinced that it's pretty much doable.
Thank you, migmit, archaicos, sassa_nf, hamster37, mikkim08; good stuff.

Here's my code, based on the code by mstone wrote in C. Mine is in Scala.

def matches(s: String, r: String): Boolean = {
  def matchesOneChar(x:String) = !x.isEmpty && (r(0)=='.' || r(0) == x(0))
  if (r.isEmpty) s.isEmpty                                                     else
  if (!r.tail.startsWith("*")) matchesOneChar(s) && matches(s.tail, r.tail)    else
                               s.tails takeWhile (!matches(_, r drop 2)) forall matchesOneChar
}

def mustMatch   (s: String, r: String) = print(s"<<$s>> vs <<$r>>: ${if (matches(s, r)) "OK" else "*** bad!"}") 
def mustNotMatch(s: String, r: String) = print(s"<<$s>> vs <<$r>>: ${if(!matches(s, r)) "OK" else "*** bad!"}") 

    mustMatch("", "")
    mustNotMatch("", "a")
    mustMatch("a", "a*")
    mustMatch("a", ".*")
    mustMatch("", ".*")
    mustMatch("", "a*")
    mustNotMatch("b", "a*")
    mustMatch("b", ".*")
    mustMatch("b", "ba*")
    mustMatch("abba", "abba")
    mustNotMatch("", ".")
    mustMatch("a", ".")
    mustMatch("ac", "ab*c")
    mustMatch("abbbc", "ab*c")
    mustNotMatch("abbbc", "a.*b")
    mustMatch("abbbc", "a.*c")
    mustMatch("ac", ".*c")
    mustMatch("aac", "a*b*ac")

Comments?