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

Question

альтернативный текст http://img31.imageshack.us/img31/4383/image24xu.jpg

В моем листе упражнений есть вопрос, чтобы найти дополнение к r = (a|b)*ab(a|b)*

Я придумала решение, но не уверена, правильно ли оно. Пожалуйста, помогите мне проверить и исправить мои ошибки.

Answer 1

Я предполагаю, что a и b являются единственными разрешенными символами.

Ваше оригинальное выражение соответствует любой строке, содержащей ab. Дополнением является любая строка, которая не содержит ab. Другими словами, если есть a, следующий символ должен быть другим a или концом строки. Если происходит b, это должно быть раньше всех a с.

Итак, это дает результат:

b*a*

Я думаю, что ваше выражение эквивалентно этому.

Answer 2

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

Следовательно, b * a * - правильный ответ