Рубрики

ВОРОТА | GATE-CS-2005 | Вопрос 54

Обозначим через Nf и Np классы языков, принимаемых недетерминированными конечными автоматами и недетерминированными автоматами с нажатием вниз соответственно. Обозначим через Df и Dp классы языков, принимаемые детерминированными конечными автоматами и детерминированными автоматами с нажатием вниз соответственно. Что из следующего является ИСТИННЫМ?
(А) Df ⊂ Nf и Dp ⊂ Np
(B) Df ⊂ Nf и Dp = Np
(C) Df = Nf и Dp = Np
(D) Df = Nf и Dp ⊂ Np

Ответ: (D)
Объяснение: Детерминированные автоматы, работающие при нажатии, могут распознавать все детерминированные контекстно-свободные языки, а недетерминированные могут распознавать все контекстно-свободные языки. В основном первые используются в дизайне парсера (Источник: http://en.wikipedia.org/wiki/Pushdown_automaton ). Детерминированные контекстно-свободные языки (DCFL) являются подходящим подмножеством контекстно-свободных языков.

Недетерминированные конечные автоматы и детерминированные конечные автоматы, оба принимают один и тот же набор языков, поскольку NFA могут быть переведены в эквивалентные DFA с использованием алгоритма построения подмножества.

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

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

ВОРОТА | GATE-CS-2005 | Вопрос 54

0.00 (0%) 0 votes