#Haskell 757 705 700 692
import Data.List data R=L Char|A R R|T R R|E h=[' '..'~'] k(']':s)a=(a,s) k('^':s)_=l(k[]s) k('-':c:s)(a:b)=k([a..c]++b)s k('\\':c:s)a=k s(c:a) k(c:s)a=k s(c:a) l(a,b)=(h\\a,b) i c E=L c i c r=A(L c)r o(a,b)=(foldr i E a,b) z 0 t=E z n t=A(z(n-1)t)(T t(z(n-1)t)) d s n=m(fst$r s)[[]] where{m E a=a;m(L c)a=[b++[c]|b<-a,length b<n];m(A r s)x=nub$(m r x)++m s x;m(T r s)a=m s(m r(a));r s=w(e s E);w(u,'|':v)=(\(a,b)->(A u a,b))(r v);w x=x;e(')':xs)t=(t,xs);e s@('|':_)t=(t,s);e s@(c:_)t=g t$f(b s);e[]t=(t,[]);g t(u,v)=e v(T t u);f(t,'*':s)=(z n t,s);f(t,'+':s)=(T t(z n t),s);f(t,'?':s)=(A t E,s);f(t,s)=(t,s);b('(':s)=r s;b('\\':s:t)=(L s,t);b('.':s)=o(h,s);b('[':s)=o(k s[]);b(s:t)=(L s,t)} output:
ghci> d "a{3}" 4 ["a{3}"] ghci> d ".*" 1 [""," ","!","\"","#","$","%","&","'","(",")","*","+",",","-",".","/","0","1","2","3","4","5","6","7","8","9",":",";","<","=",">","?","@","A","B","C","D","E","F","G","H","I","J","K","L","M","N","O","P","Q","R","S","T","U","V","W","X","Y","Z","[","\\","]","^","_","`","a","b","c","d","e","f","g","h","i","j","k","l","m","n","o","p","q","r","s","t","u","v","w","x","y","z","{","|","}","~"] ghci> d "w\\w+" 3 ["ww","www"] ghci> d "[abx-z][^ -}][\\\\]" 3 ["x~\\","y~\\","z~\\","b~\\","a~\\"] ghci> d "ab*a|c[de]*" 3 ["aa","aba","c","ce","cd","cee","cde","ced","cdd"] ghci> d "(foo)+(bar)?!?" 6 ["foo!","foobar","foo","foofoo"] ghci> d "(a+|b*c)d" 4 ["ad","aad","aaad","cd","bcd","bbcd"] ghci> d "p+cg" 4 ["pcg","ppcg"] ghci> d "a{3}" 4 ["a{3}"] Explanation: this one's a textbook regex implementation. R is the regex type, with constructors A (alternate), L (literal) and T (then). The usual 'Star' doesn't appear because I inline it as alternates during the parse (see 'z'). 'm' runs the simulation. The parser (start at 'r s=....') is just recursive descent; 'k' parses ranges. The function 'i' expands ranges into alternations.