Рубрики

ВОРОТА | GATE-CS-2006 | Вопрос 29

Если s — это строка над (0 + 1) *, то пусть n 0 (s) обозначает число 0 в s, а n 1 (s) — число 1 в s. Какой из следующих языков не является регулярным?

7 ″ />
(А) А
(Б) Б
(С) С
(D) D

Ответ: (с)
Объяснение: Языки в опции (A) и (D) конечны, поэтому оба варианта исключены.

Для варианта А:
Есть конечно нет. из 3 цифр простых чисел. Существует ФА для каждого конечного множества. Следовательно, ФА возможно.

Для варианта D:
Возможные остатки для 7 — от 0 до 6, а для 5 — от 0 до 4. Используя 35 состояний, можно сделать FA.

Для варианта B:
У нас может быть 6 состояний (включая 1 состояние отказа)
состояние 1: разница равна 0
состояние 2: разница 1 (больше 1 с)
состояние 3: разница 1 (больше 0)
состояние 4: разница 2 (больше 1 с)
состояние 5: разница 2 (больше 0)
состояние 6: отклонить состояние для разности> = 3

Предположим, что строка 000101
Сканирование 0 -> состояние 3
Сканирование 0 -> состояние 5
Сканирование 0 -> отклонить (так как diff. Сейчас 3)

Точно так же, если мы попробуем для строки: 010100, это будет принято.

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

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

ВОРОТА | GATE-CS-2006 | Вопрос 29

0.00 (0%) 0 votes