Здравствуйте, jhfrek, Вы писали:

J>Угу, но может все-таки нужны не регулярные выражения? Может нужно что-то вроде Дельфийских масок?

Есть много нотаций для грамматик. Это БНФ, РБНФ, регулярные выражения в стиле Perl и Emacs, и т.п.
Суть от этого не меняется.
Если мощность (количество возможных строк) языка, счетна или более, то автомат-генератор должен иметь бесконечное слово состояния.

В некоторых случаях, если можно разбить язык на конечные подмножества, мы можем сделать генераторы для каждого из этих подмножеств и последовательно отработать каждый из них.
Например: простая грамматика

 S -> (a|b|c|d)*

элементарно строится генератор строк длины N.
Последовательно выполняем генерацию строк длины 0, 1, 2, ... пока не надоест.