Рубрики

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

Рассмотрим схему перехода КПК, приведенную ниже, с входным алфавитом и суммой; = {a, b} и составлять алфавит & Gamma; = {X, Z}. Z — начальный символ стека. Пусть L обозначает язык, принятый КПК.

(А) А
(Б) Б
(С) С
(D) D

Ответ: (D)
Объяснение:

В данном КПК мы можем нумеровать состояния как q1, q2 и q3 слева направо.

Переходы КПК следующие:

  1. (q1, a, Z) -> (q1, XZ)

  2. (q1, a, X) -> (q1, XX)

  3. (q1, b, X) -> (q2, €)

  4. (q2, b, X) — > (q2, €)

  5. (q2, €, Z) -> (q3, Z)

Поскольку начальное состояние является конечным, следовательно, КПК всегда принимает нулевую строку.
Первые два перехода показывают, что состояние остается q1 (конечное состояние) на входном алфавите «a», и с каждым «a» мы помещаем X в стек. Следовательно,
n n всегда принимается при n≥0.
Переходы 3 и 4 показывают, что для входного алфавита 'b' и символа стека X (то есть 'a' произошло в строке) мы можем вытолкнуть X из стека. Переход 5 показывает, что мы можем перейти в конечное состояние (q3) только тогда, когда строка пуста и символом стека является Z. Это возможно, когда мы вытолкнули все X из стека, т.е. «b» произошло ровно столько же раз, сколько «a» ». Следовательно, a
n b n всегда принимается при n≥0. Язык, принятый КПК, — {a n | n≥0} U {a n b n | n≥0} и является детерминированным КЛЛ.
(a
n b n | n≥0 не является регулярным, но принимается КПК). Отсюда вариант (D).

Это решение предоставлено Яшикой Арора .
Тест на этот вопрос

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

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

0.00 (0%) 0 votes