Рубрики

ВОРОТА | GATE-CS-2004 | Вопрос 86

GATE

Следующий конечный автомат принимает все те двоичные строки, в которых число 1 и 0 соответственно.


(А) делится на 3 и 2
(Б) нечетные и четные
(С) четные и нечетные
(D) делится на 2 и 3

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

Опция (B) исключена, потому что строка 100 содержит нечетное число 1 с и четное число 0, но не принимается DFA.
Опция (C) исключена, поскольку строка 011 содержит четное число 1 с и нечетное число 0, но не принимается DFA.
Опция (D) исключена, потому что строка 11000 имеет число 1, кратное 2, и число 0, кратное 3, но все еще не принятое DFA.
Опция (A) принимает все строки с числом 1, кратным 3, и числом 0, кратным 2.

Дополнительное примечание: В любом случае, когда (нет 1 с) MOD N = некоторое целое число k и (нет 0 с) MOD M = некоторое целое число q, число состояний в DFA будет равно N * M.
(Продукт может быть взят для всех входных алфавитов.)
Например, если мы скажем нет. из них четных и нет. из 0 с нечетным (мы проверяем, если (№ 1 из) MOD 2 = 0 и (№ 0 из) MOD 2 = 0), поэтому нет. состояний в DFA = 2 * 2 = 4.
Следовательно, опции (B) и (C) могут быть исключены напрямую, поскольку DFA имеет 6 состояний, и мы можем рассмотреть только оставшиеся два варианта.


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

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

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

ВОРОТА | GATE-CS-2004 | Вопрос 86

0.00 (0%) 0 votes