Генеративные регулярные выражения

Обычно в нашей работе мы используем регулярные выражения в захвате или совпадении операций.

Однако регулярные выражения можно использовать - по крайней мере вручную - для генерации законных предложений, соответствующих регулярному выражению. Конечно, некоторые регулярные выражения могут соответствовать бесконечно длинным предложениям, например, выражению . + .

У меня есть проблема, которую можно решить с помощью алгоритма генерации предложений регулярного выражения.

В псевдокоде это будет работать примерно так:

re = generate("foo(bar|baz)?", max_match = 100);  #Don't give me more than 100 results
assert re == ("foobar", "foobaz", "foo");

Какой алгоритм выполнит это для меня?