получение регулярных выражений из регулярного языка

Question

Учитывая язык ниже, как мне найти регулярное выражение для языка

L = {a ^ n b ^ m | n => 1, m => 1, нм => 3}

Answer 1

n> = 1 и m> = 1 и nm> = 3 верно для каждого из следующего:

п = 1, т> = 3

п> = 3, т = 1

п> = 2, т> = 2

Итак, L = {abbb, abbbb, abbbbb, ...} U {aaab, aaaab, aaaaab, ...} U {a ^ n b ^ m | n> = 2, m> = 2}

Это регулярное выражение должно быть эквивалентно L:

((abbb (b *)) | (aaa (a *) b) | (aa (a *) bb (b *)))

Вероятно, есть гораздо более краткий ответ, чем этот.

Answer 2

Запишите набор примеров слов языка. Почувствуй их. Ищите шаблоны. Ищите общие префиксы / суффиксы / подстроки.

abbb
abbbb
abbbbb
aabb
aabbb
aabbbb
aaab
aaabb
aaabbb
aaaab
aaaabb
aaaabbb

Например: обратите внимание, что все слова начинаются с a и заканчиваются b. Итак, ваше регулярное выражение выглядит примерно так: a...b. Как выглядит деталь ...?

bb
bbb
bbbb
ab
abb
abbb
aa
aab
aabb
aaa
aaab
aaabb

Этот вид выглядит как a, за которым следует хотя бы один a или b, за которым, возможно, следует ноль или более b с. Или просто серия из более чем двух b с.

a(a+|b)b*|b{2,}

Можно также сказать, что это либо серия из не менее двух a с, либо серия из не менее двух b с, либо серия из a с, за которой следуют b с. Я не собираюсь записывать это выражение.

Это это домашнее задание, в конце концов, так что я оставлю это вам, чтобы сделать это и соединить с первым результатом. (Кстати: все ярлыки, которые я использовал , являются просто синтаксическим сахаром, а они не делают регулярные выражения более мощными. Т.е. существует простое синтаксическое преобразование, которое превращает их в стандартное регулярное выражение.)

[Я просто надеюсь, что я прав и не делаю из себя задницу: -)]