Нахождение дополнения обычного языка

Question

Не могли бы вы помочь мне найти дополнение к языку, которое заканчивается на abab - (a|b)*abab (over an alphabet {a,b})

Я полагаю, дополнение должно содержать все строки, которые не заканчиваются на abab. Можно попытаться сделать это с помощью алгоритма Rij после создания DFA для дополнения (a|b)*abab, но, пожалуйста, помогите мне понять, как это работает без Automaton и Rij (потому что этот автомат имеет 5 состояний).

Хорошо, слова не могут заканчиваться на abab. Есть 2 ⁴ путей для четырех букв a и b в конце. Хорошо, abab необходимо стереть, чтобы было 15 комбинаций. Означает ли это, что языком комплемента является (a|b)*. (Объединение всех этих комбинаций a и b без abab)? Но (a|b) все еще остается прежним?

Помогите, пожалуйста, понять это.

Answer 1

Может быть, я не понимаю вас, но не намного ли проще? Я (a|b)*(a|bb|aab|bbab) или событие (a|b)*(a|(b|(a|bb)a)b)?

P.S. Не забывайте, что есть слова короче abab, и все они также должны быть включены. То есть (a|b){0,3} (где {0,3} обозначает количество повторов [0; 3])