Андрюха

А если перевести регулярное выражение в конечный автомат (лучше детерминированный), а потом идти в обратном направлении кидая монетку по какому символу делать переход назад. Если дошли до стартового состояния автомата (если стартовое состояние имеет переход на себя, то и в нем надо кинуть монетку), вот вам и случайная строка. (если конечных состояний несколько, то тоже кинуть монетку какое выбрать, и тут конечно перевод регулярного выражения в автомат основная часть работы, но почему сразу не задавать выражение с помощью автомата, тогда программа может уместится наверное в строк 50).

как то не очень понятно. вот взять строку: cba. Moжно ли сказать, что в ней 3 последовательности букв в алфавитном порядке, или одна? или например: bcd, это в алфавитном порядке?

Регулярное выражение, это по сути конечный автомат, он не может распарсить такую строку, так как у нее есть подсчет {} кавычек. Это уже контекстно свободная грамматика.