Минимальная длина регулярного выражения

Question

Работаю над домашней работой для класса, и я пришел к этому вопросу:

Для каждого из следующих регулярных выражений задайте строки минимальной длины, которые не на языке, определенном выражением.

1. (bb)*(aa)*b*
2. a*(bab)*∪b∪ab

Я попытаюсь получить помощь только по первому и посмотреть, смогу ли я выяснить второе. Вот что я знаю: Клини * обозначает 0 или более возможных элементов. и объединение множества - это множество, содержащее все элементы множества a и множества b без повторения элемента. Пройдя первую проблему, вставив лямбду, я получаю:

1й прогон: bbaab
2-й: bbbbaabaabbaabbbbaab
3-е: bbbbbbaabaabbaabbbbaabaabbbbaabaabbaabbbbaabbbbbbaabaabbaabbbbaab

Если я делаю это правильно, то строки длиной от 0 до 5 не на языке. Я делаю это правильно?

Answer 1

Первое регулярное выражение соответствует любому слову, которое начинается с четного числа «b» (включая ноль), за которым следует четное число «a» (с нуля в порядке), затем следуют некоторые «b».

Это означает, что на языке есть пустая строка, а также строка "b". Тем не менее, строка «а» не на языке.

Таким образом, все строки минимальной длины, которых нет в языке, - это "a".

---

Второе регулярное выражение соответствует "", "a" и "aa" (a * (bab) *), а также "b" и "ab". Однако это не совпадает с "ba" и "bb".

Таким образом, минимальные строки имеют длину 2: «bb» и «ba».