Рубрики

ВОРОТА | GATE-IT-2004 | Вопрос 9

GATE

Какое из следующих утверждений ЛОЖНО?
(A) Существуют языки без контекста, так что все генерирующие их грамматики без контекста неоднозначны
(B) Однозначная контекстно-свободная грамматика всегда имеет уникальное дерево разбора для каждой строки сгенерированного ею языка.
(C) Как детерминированные, так и недетерминированные автоматы нажатия всегда принимают один и тот же набор языков
(D) Конечный набор строк из одного алфавита всегда является обычным языком.

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

A) Для реальных языков программирования эталонный CFG часто неоднозначен из-за таких проблем, как висящая проблема. // Википедия

Б) Строка является неоднозначной, если она имеет два различных дерева разбора: Грамматика однозначна, если строка имеет различные деревья разбора.

C) Детерминированные выпадающие автоматы могут распознавать все детерминированные контекстно-свободные языки, а недетерминированные могут распознавать все контекстно-свободные языки

Поэтому это ЛОЖЬ

D) Свойства обычного языка:

  • Набор регулярных языков над алфавитом закрыто под операциями объединения, конкатенации и клини звезды.
  • Конечные языки являются регулярными

Итак, ответ — C
Тест на этот вопрос

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

ВОРОТА | GATE-IT-2004 | Вопрос 9

0.00 (0%) 0 votes