Рубрики

ВОРОТА | GATE-CS-2015 (набор 1) | Вопрос 60

Рассмотрим NPDA 〈Q = {q0, q1, q2}, Σ = {0, 1}, Γ = {0, 1, ⊥}, δ, q0, ⊥, F = {q2}〉, где (как обычно соглашение) Q — набор состояний, Σ — входной алфавит, Γ — алфавит стека, δ — функция перехода состояний, q0 — начальное состояние, ⊥ — начальный символ стека, и F — набор принимающих состояний. Состояние перехода выглядит следующим образом:

Какая из следующих последовательностей должна следовать за строкой 101100, чтобы общая строка была принята автоматом?
(А) 10110
(В) 10010
(С) 01010
(D) 01001

Ответ: (Б)
Объяснение: В состоянии q0 для «1» нажимается «1», а для «0» — «0». В состоянии q1 для «0» выталкивается «1», а для «1» выталкивается «0». Таким образом, данный КПК принимает все строки вида x0x'r, или x1x'r, или xx'r, где x'r — обратная сторона 1-го дополнения к x.

Данная строка 101100 имеет 6 букв, и нам даны 5 буквенных строк. Итак, x0 сделано, с x = 10110. Итак, x'r = (01001) r = 10010.

Следовательно, вариант B является правильным.
Тест на этот вопрос

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

ВОРОТА | GATE-CS-2015 (набор 1) | Вопрос 60

0.00 (0%) 0 votes