Рубрики

ВОРОТА | GATE-CS-2001 | Вопрос 50

Рассмотрим DFA для ∑ = {a, b}, принимающий все строки, у которых число a делится на 6, а число b делится на 8. Какое минимальное количество состояний будет иметь DFA?
(А) 8
(Б) 14
(С) 15
(D) 48

Ответ: (D)
Объяснение:
Построим DFA для строк, кратных 6.
Требуется минимум 6 состояний, так как длина строки mod 6 = 0, 1, 2, 3, 4, 5

Мы строим DFA для строк, кратных 8.
Требуется минимум 8 состояний, так как длина строки mod 8 = 0, 1, 2, 3, 4, 5, 6, 7

Если первое DFA является минимальным, а второе DFA также минимальным, то после объединения обоих DFA результирующее DFA также будет минимальным. Такой DFA называется составным автоматом.

Итак, минимальные состояния в результирующем DFA = 6 * 8 = 48

Таким образом, вариант (D) является ответом.

Пожалуйста, прокомментируйте ниже, если вы найдете что-то не так в вышеуказанном посте.

Тест на этот вопрос

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

ВОРОТА | GATE-CS-2001 | Вопрос 50

0.00 (0%) 0 votes