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

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

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

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

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

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

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

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

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

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

• ВОРОТА | Sudo GATE 2020 Mock I (27 декабря 2019) | Вопрос 52
• ВОРОТА | Sudo GATE 2020 Mock I (27 декабря 2019) | Вопрос 65
• ВОРОТА | Sudo GATE 2020 Mock I (27 декабря 2019) | Вопрос 64
• ВОРОТА | Sudo GATE 2020 Mock I (27 декабря 2019) | Вопрос 53
• ВОРОТА | Sudo GATE 2020 Mock I (27 декабря 2019) | Вопрос 54
• ВОРОТА | Sudo GATE 2020 Mock I (27 декабря 2019) | Вопрос 55
• ВОРОТА | Sudo GATE 2020 Mock I (27 декабря 2019) | Вопрос 56
• ВОРОТА | Sudo GATE 2020 Mock I (27 декабря 2019) | Вопрос 57
• ВОРОТА | Sudo GATE 2020 Mock I (27 декабря 2019) | Вопрос 58
• ВОРОТА | Sudo GATE 2020 Mock I (27 декабря 2019) | Вопрос 59
• ВОРОТА | Sudo GATE 2020 Mock I (27 декабря 2019) | Вопрос 60
• ВОРОТА | Sudo GATE 2020 Mock I (27 декабря 2019) | Вопрос 61
• ВОРОТА | Sudo GATE 2020 Mock I (27 декабря 2019) | Вопрос 62
• ВОРОТА | Sudo GATE 2020 Mock I (27 декабря 2019) | Вопрос 63
• ВОРОТА | Sudo GATE 2020 Mock II (10 января 2019 года) | Вопрос 65