строительство CFG

Question

Как создать контекстно-свободный грамматик для языка x ^ ay ^ bz ^ 2 (a + b) , где a> = 0, b> = 0.Спасибо за помощь ...

Answer 1

Думайте об этом так

x^a y^b z^2(a+b) = x^a y^b z^2a z^2b = x^a y^b (z^2)^b (z^2)^a 

Поэтому

S -> xSzz | S1
S1 -> yS1zz | e

Answer 2

Обратите внимание, что для каждого x и для каждого y вам необходимо сгенерировать два z из-за 2 ( a + b ). Также обратите внимание, что каждую строку можно рассматривать как «внутреннюю» часть y и z и «внешнюю» часть x и z.

Поскольку для каждого y вам нужны два z, внутренняя часть может быть описана с помощью (с использованием заглавных букв для обозначения нетерминальных символов и [] для пустой строки):

I --> []
I --> y I z z

Теперь напишите грамматику для внешней части таким же образом, но со ссылкой на I в базовом случае.

Answer 3

По сути, есть два случая, которые нужно обработать:

• Вы можете добавить x в начале строки, в этом случае вам нужно добавить два z 's в конце.
• Или вы можете добавить y в середине, в этом случае вам также необходимо добавить два z в конце.

Попробуйте свести любое из этих описаний к более простой грамматике (например, a^n b^n), для которой вы знаете решение.

Этой подсказки должно быть достаточно, чтобы вывести порождающую грамматику.