Рубрики

ВОРОТА | GATE CS 2013 | Вопрос 33

Рассмотрим ДФА.

Что из перечисленного ЛОЖНО?

1. Complement of L(A) is context-free.
2. L(A) = L((11*0+0)(0 + 1)*0*1*)
3. For the language accepted by A, A is the minimal DFA.
4. A accepts all strings over {0, 1} of length at least 2. 

(А) 1 и 3 только
(B) только 2 и 4
(C) только 2 и 3
(D) только 3 и 4

Ответ: (Д)
Пояснение: 1 верно. L (A) регулярно, его дополнение также будет регулярным. Обычный язык также не зависит от контекста.

2 верно.

3 ложно, DFA может быть сведен к минимуму до двух состояний. Где второе состояние является окончательным, и мы достигаем второго состояния после 0.

4 явно ложно, так как DFA принимает один 0.
Тест на этот вопрос

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

ВОРОТА | GATE CS 2013 | Вопрос 33

0.00 (0%) 0 votes