Рубрики

ВОРОТА | Gate IT 2007 | Вопрос 71

Рассмотрим регулярное выражение R = (a + b) * (aa + bb) (a + b) * <br>

Какое из приведенных ниже регулярных выражений определяет тот же язык, что и регулярное выражение R?
(A) (a (ba) * + b (ab) *) (a + b) +
(B) (a (ba) * + b (ab) *) * (a + b) *
(C) (a (ba) * (a + bb) + b (ab) * (b + aa)) (a + b) *
(D) (a (ba) * (a + bb) + b (ab) * (b + aa)) (a + b) +

Ответ: (с)
Объяснение: <! — A принимает ab, но данное не
Б пусто может быть принято, а не дано ->

Приведенный выше DFA можно упростить, разрешив петлю в состояниях B и C и удалив дополнительные переходы в конечных состояниях, а именно:

Чтобы достичь конечного состояния из B, у нас может быть алфавит «a» для перехода в состояние D или «bb» для перехода в состояние E.
Точно так же, чтобы достичь конечного состояния из C, у нас может быть алфавит «b» для перехода в состояние E или «aa» для перехода в состояние D.

Следовательно, регулярное выражение:
(a (ba) * (a + bb) + b (ab) * (b + aa)) (a + b) *

a (ba) * (a + bb): перейти от A к B и B к любому из конечных состояний
b (ab) * (b + aa): перейти от A к C и C к любому из конечных состояний

Примечание. Мы также можем использовать метод исключения опций для таких вопросов, т.е. мы можем отклонить опцию, если мы

найти хотя бы такую строку, которая не проверяет регулярное выражение.
Опция (A) принимает ab, а данное регулярное выражение — нет.
Опция (B) принимает пустую строку, а данное регулярное выражение — нет.
Опция (D) не принимает aa, но данное регулярное выражение принимает.

Это решение предоставлено Yashika Arora
Тест на этот вопрос

Рекомендуемые посты:

ВОРОТА | Gate IT 2007 | Вопрос 71

0.00 (0%) 0 votes