Рубрики

ВОРОТА | GATE-CS-2003 | Вопрос 15

Если строки языка L можно эффективно перечислить в лексикографическом (т. Е. Алфавитном) порядке, какое из следующих утверждений верно?
(A) L обязательно конечна
(B) L регулярно, но не обязательно конечно
(C) L не зависит от контекста, но не обязательно является регулярным
(D) L является рекурсивным, но не обязательно контекстно-свободным

Ответ: (D)
Объяснение:
Строки языка L могут быть эффективно перечислены, что означает, что для языка L существует машина Тьюринга, которая будет перечислять все допустимые строки языка.

Если строка в лексикографическом порядке, то TM примет строку и остановится в конечном состоянии.
Но если строка не лексикографического порядка, то TM отклонит строку и остановится в неконечном состоянии.

Таким образом, L является рекурсивным языком.

Мы не можем построить PDA для языка L. Таким образом, данный язык не является контекстно-свободным.

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

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

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

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

ВОРОТА | GATE-CS-2003 | Вопрос 15

0.00 (0%) 0 votes