Рубрики

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

Язык {a m b n C m + n | m, n ≥ 1}

(А) регулярный
(B) контекстно-свободный, но не регулярный
(C) контекстно-зависимый, но не контекстно-свободный
(D) тип 0, но не зависит от контекста

Ответ: (Б)
Объяснение:
Мы строим КПК для данного языка.

Нажмите Z 0 в стеке изначально.
Нажмите X в стеке для каждого вхождения 'a'.
Нажмите Y в стеке для каждого вхождения 'b'.
POP X и Y из стека для каждого вхождения 'c'.

Если после извлечения всех X и Y из стека в строке не останется входного элемента, и мы получим Z 0 на вершине стека, тогда строка будет принята.

Таким образом, вариант (B) является правильным.

Пожалуйста, прокомментируйте ниже, если вы найдете что-то не так в вышеуказанном посте.

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

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

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

0.00 (0%) 0 votes