Рубрики

Способность | GATE IT 2006 | Вопрос 3

В автомате ниже s — начальное состояние, а t — единственное конечное состояние.

Рассмотрим строки u = abbaba, v = bab и w = aabb. Какие из следующих утверждений верно?

(A) Автомат принимает u и v, но не w
(B) Автомат принимает каждое из u, v и w
(C) Автомат отклоняет каждое из u, v и w
(D) автомат принимает вас, но отклоняет v и w

Ответ: (D)
Объяснение:

Для принятия и отклонения любой строки мы можем просто проверить движение каждого входного алфавита между состояниями. Строка принимается, если мы остановимся на каком-либо конечном состоянии DFA.
Для строки u = abbaba строка заканчивается в t (конечное состояние), следовательно, она принята DFA.
Для строки v = bab строка заканчивается в s (не конечное состояние) и, следовательно, отклоняется DFA.
Для строки w = aabb строка заканчивается в s (не конечное состояние) и, следовательно, отклоняется DFA.

 

Это решение предоставлено Яшикой Арора .
Тест на этот вопрос

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

Способность | GATE IT 2006 | Вопрос 3

0.00 (0%) 0 votes