Рубрики

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

Какие из следующих утверждений верны?

I. Every left-recursive grammar can be converted to a 
   right-recursive grammar and vice-versa
II. All  productions can be removed from any context-free 
    grammar by suitable transformations
III. The language generated by a context-free grammar all of whose 
     productions are of the form X --> w or X --> wY (where, w is a string of 
     terminals and Y is a non-terminal), is always regular
IV. The derivation trees of strings generated by a context-free grammar 
    in Chomsky Normal Form are always binary trees 

(А) I, II, III и IV
(B) только II, III и IV
(C) только I, III и IV
(D) только I, II и IV

Ответ: (с)
Объяснение:
Я верен, так как мы всегда можем удалить левую рекурсию из любой данной грамматики.
(Для лучшего понимания смотрите это .)

II неверно, так как мы можем удалить все произведения эпсилона, только если грамматика не содержит эпсилон в языке.

III верно, так как это определение регулярной грамматики.
(Для лучшего понимания см. Языки типа 3 в этой статье .)

IV верно, потому что в нормальной форме Хомского все произведения имеют тип X -> YZ или X -> t, где X, Y, Z — переменные, а 't' — терминальная строка. Когда мы рисуем дерево деривации для каждого узла, существует не более 2 дочерних элементов. Именно поэтому деревья дериваций грамматик в хомской нормальной форме являются бинарными деревьями.
(Для лучшего понимания смотрите это .)

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

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

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

0.00 (0%) 0 votes