Рубрики

ВОРОТА | GATE CS 2011 | Вопрос 9

Какие из следующих пар обладают РАЗЛИЧНОЙ выразительной силой?
(A) Детерминированные конечные автоматы (DFA) и Недетерминированные конечные автоматы (NFA)
(B) Детерминированные понижающие автоматы (DPDA) и Недетерминированные понижающие автоматы (NPDA)
(C) Детерминированная одноленточная машина Тьюринга и Недетерминированная одноленточная машина Тьюринга
(D) Одноленточная машина Тьюринга и многоленточная машина Тьюринга

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

NDPDA может обрабатывать языки или грамматики с неоднозначностью, но DPDA не может обрабатывать языки с неоднозначностью и любой контекстно-свободной грамматикой.

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

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

ВОРОТА | GATE CS 2011 | Вопрос 9

0.00 (0%) 0 votes