Рубрики

ВОРОТА | Gate IT 2008 | Вопрос 6

Пусть N будет NFA с n состояниями, и пусть M будет минимизированным DFA с m состояниями, распознающими один и тот же язык. Что из следующего в ОБЯЗАТЕЛЬНО верном?
(A) m ≤ 2 n
(B) n ≤ m
(C) M имеет одно принимающее состояние
(D) m = 2 н

Ответ: (А)
Пояснение: Состояние в DFA является надлежащим подмножеством состояний NFA соответствующего DFA.

=> набор состояний NFA = n

=> нет подмножеств множества с n элементами = 2 n

=> m <= 2 n
Тест на этот вопрос

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

ВОРОТА | Gate IT 2008 | Вопрос 6

0.00 (0%) 0 votes