Нахождение дополнения к регулярному языку

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

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

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

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


regular-language computation-theory
person SpikeBZ    schedule 20.11.2011    source источник

Ответы (1)


arrow_upward
1
arrow_downward

Может быть, я вас не понимаю, но не проще ли. Я (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])

person ony    schedule 20.11.2011
comment
Благодарю за ваш ответ. Я не уверен, понимаю ли я, как вы думаете, делая это. Значит, нам не нужны все остальные комбинации из четырех букв (над {a,b})? И (a|b)* остается прежним? Означает ли это, что если у нас есть какой-то язык со звездой Клини, он всегда остается таким, как был? - person SpikeBZ; 21.11.2011
comment
да. Поскольку у нас есть привязка к концу слова, этого достаточно, чтобы сделать последнюю часть слова несовместимой. Итак, начиная с последней буквы, я начинаю итерацию, и на каждом шагу я иду в два набора: несоответствие - означает, что вы можете иметь что-то еще сразу после него; match - у вас должно быть несоответствие на дальнейших шагах. Насчет последнего вопроса я бы не был так уверен. Рассмотрим дополнительный язык для (a|b)*abab(a|b)* - единственное место, где эти (a|b)* будут разрешены, - это описание слов длиной менее 4. Другие, вероятно, будут содержать одну букву под звездочным оператором. - person ony; 21.11.2011