Рубрики

ВОРОТА | GATE CS 2008 | Вопрос 8

Что из следующего верно для языка

(A) Он не принимается машиной Тьюринга
(Б) Это регулярно, но не контекстно-свободный
(C) Это не зависит от контекста, но не регулярно
(D) Оно не является ни регулярным, ни контекстно-зависимым, но принимается машиной Тьюринга

Ответ: (D)
Пояснение: Машина Тьюринга может быть спроектирована для р с использованием концепции «Сито Эратосфена».

Предположим, нам дано целое число «n», и мы хотим выяснить все простые числа, меньшие или равные «n».

Мы повторяем следующие шаги:
Мы находим наименьшее число в списке, объявляем его простым и удаляем все кратные этому числу из списка. Мы продолжаем делать это до тех пор, пока каждый элемент не будет объявлен простым или исключенным из списка.

Теперь, если p = 0 или p = 1, мы отклоняем ввод.
Иначе, мы заменяем первый и последний 'a' символом $.

На предыдущих этапах мы находим первый не черный символ слева. Пусть этот символ находится в позиции «х». Предположим, что «x» — простое число.
Если этот непустой символ равен $, входная строка будет принята.
Но если символ «а», мы помечаем его как * и заменяем все кратные «х» на символ «пусто».
Если в конце символ $ заменяется на «пусто», мы отклоняем входную строку (потому что в этом случае p будет кратно некоторому «x»).
Иначе мы вернемся и повторим шаги.

Таким образом, ввод не является ни регулярным, ни контекстно-зависимым, но принимается машиной Тьюринга.

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

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

ВОРОТА | GATE CS 2008 | Вопрос 8

0.00 (0%) 0 votes