Рубрики

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

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

Какой детерминированный конечный автомат принимает язык, представленный регулярным выражением R?


(А) А
(Б) Б
(С) С
(D) D

Ответ: (А)
Пояснение: Эквивалент NFA выглядит следующим образом:

Таблица, показывающая переходы между всеми состояниями, выглядит следующим образом:

Таблицу переходов можно преобразовать в таблицу переходов для DFA:

Эквивалентный DFA для приведенной выше таблицы переходов:

Следовательно, опция (A) является обязательным DFA для данного регулярного выражения.

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

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

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

0.00 (0%) 0 votes