Рубрики

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

Две грамматики, приведенные ниже, генерируют язык по алфавиту {x, y, z}

Какой из следующих вариантов описывает свойства, которым удовлетворяют строки в этих языках?
(A) G1: ни один y не появляется перед любым x
G2: за каждым x следует хотя бы один y
(B) G1: ни один y не появляется перед любым x
G2: x не появляется перед любым y
(C) G1: y не появляется после любого x
G2: за каждым x следует хотя бы один y
(D) G1: ни один y не появляется после любого x
G2: за каждым у следует хотя бы один х

Ответ: (А)
Пояснение: для приведенного выше вопроса мы видим, что для всех параметров свойства, удовлетворяемые строками, могут быть определены как некоторое отношение между алфавитами x и y.
Для грамматики 1 строки с комбинацией x и y могут быть сгенерированы только со следующей формой (ами) производства грамматики.

S–> xS -> xyB или

S-> zS-> zxS-> zxyB

(В случае, если начальное производство S–> x | z | yB, в строке не может быть указано и x, и y)
Следовательно, в любой строке с x и y оба y не могут появиться, прежде чем x можно будет описать как свойство, удовлетворяемое строками языка.

Аналогично для грамматики 2 строки с комбинацией x и y могут быть сгенерированы следующим образом

форма производства только грамматики.

S–> yS -> yxB–> yxy ИЛИ S–> yS -> yxB–> yxyB

S–> xB -> xy ИЛИ S–> xB -> xyB

Следовательно, в любой строке с x и y за каждым x следует, по крайней мере, один y, который может быть описан как свойство, удовлетворяемое строками языка.

Это решение предоставлено Яшикой Арора .
Тест на этот вопрос

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

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

0.00 (0%) 0 votes