Рубрики

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

Рассмотрим следующий DFA, в котором s0 — начальное состояние, а s1, s3 — конечные состояния.

Какой язык распознает этот DFA?
(A) Все строки х и у
(B) Все строки х и у, которые имеют четное число х и четное число у или нечетное число или х и нечетное число у
(C) Все строки х и у, которые имеют одинаковое количество х и у
(D) Все строки x и y с четным числом x и нечетным числом y или нечетным числом x и четным числом y

Ответ: (D)
Объяснение:
Алфавит x переместится на S1, а алфавит y переместится на S3 из состояния S0. Следовательно, наименьшей строкой, принятой DFA, являются {x, y}. Дальнейшие возможные перемещения из S1 или S3 в принимающие состояния могут быть любой комбинацией x и y четной длины, то есть любой из {xx, xy, yx, yy} и их комбинаций. Следовательно, язык, принятый DFA, может быть распознан как (x + y) + (xx + xy + yx + yy) *, то есть все строки x и y с нечетной длиной (четные номера x и нечетные номера y или четное число у и нечетное число х).

Метод исключения опций: (опция, в которой есть хотя бы один пример, который не принят DFA)
Вариант (A): False, поскольку {xx, xy и т. Д.} Не приняты DFA.
Вариант (B): Ложь, как нет. х и даже нет. из y строка {xxyy} не принята DFA.
Вариант (C): False как строка с равным номером. х и равно нет. из y {xy} не принимается DFA.
Вариант (D): Все строки с четным числом x и нечетным числом y или нечетным числом x и четным числом y принимаются.
Следовательно, ответ — вариант (D).

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

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

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

0.00 (0%) 0 votes