Рубрики

ВОРОТА | GATE-CS-2007 | Вопрос 30

Язык L = {0 i 21 i | i≥0} над алфавитом {0,1, 2}:
(А) не рекурсивный
(B) является рекурсивным и является детерминированным КЛЛ.
(С) это обычный язык.
(D) не детерминированный КЛЛ, а КЛЛ.

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

  • Для каждого вхождения '0' мы нажимаем X в стеке.
  • Когда появляется «2», стековая операция не выполняется. Но состояние автоматов изменилось.
  • Для каждого вхождения '1' мы POP X из стека.
  • Если в конце Z 0 находится на вершине стека, то входная строка принимается

Мы также разрабатываем машину Тьюринга для данного языка.

  • Когда во входной строке появляется «0», мы заменяем ее на X. Затем переходим к крайнему правому углу и заменяем «1» на Y.
  • Мы возвращаемся к крайнему левому значению «0» и повторяем описанный выше процесс.
  • При перемещении вправо от начала входной строки, если после X появляется «2», а после «2» появляется Y, то мы достигаем состояния HALT.

    Таким образом, данный язык является рекурсивным. Каждый рекурсивный язык — это CFL.
    Таким образом, вариант (B) является ответом.

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

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

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

ВОРОТА | GATE-CS-2007 | Вопрос 30

0.00 (0%) 0 votes