Рубрики

ВОРОТА | Gate IT 2007 | Вопрос 49

Рассмотрим следующие грамматики. Имена, представляющие терминалы, были указаны заглавными буквами.

Какое из следующих утверждений верно?
(A) G 1 не зависит от контекста, но не является регулярным, а G 2 является регулярным
(B) G 2 не зависит от контекста, но не является регулярным, а G 1 является регулярным
(C) G 1 и G 2 являются регулярными
(D) G 1 и G 2 не зависят от контекста, но ни один из них не является регулярным

Ответ: (D)
Пояснение: данные грамматики могут быть переписаны как:
Скажем, пока = w, expr = E, stmt = S, other = o
Здесь мы можем написать правильную линейную грамматику для G 1 как
S -> W (E) S
S -> o
E-> ID

Итак, L (G 1 ) регулярно.
Теперь для G 2 мы также можем написать правильную линейную грамматику:
S -> W (E) S

E -> E + E
E -> E * E
S -> o
Но в этом вопросе обе эти грамматики не являются ни линейными, ни линейными.
Таким образом, вариант (D) является правильным.
Тест на этот вопрос

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

ВОРОТА | Gate IT 2007 | Вопрос 49

0.00 (0%) 0 votes