#context-free-grammar #formal-languages
#контекстно-свободная грамматика #формальные языки
Вопрос:
Как я могу сконструировать контекстно-свободный грамматик для языка x ^ a y ^ b z ^ 2 (a b) где a> = 0, b>= 0. Спасибо за помощь…
Ответ №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
Комментарии:
1. Я только что попытался отменить свой голос за этот ответ, который я дал, когда это была всего лишь подсказка «Подумай об этом так», но по какой-то причине я не могу. Ответ не только выдает решение (для того, что, скорее всего, является проблемой домашнего задания), но и не очень элегантен, потому что в первом правиле есть избыточное
eпредложение.2. @larsmans Действительно. Я отредактировал вопрос, теперь вы можете проголосовать против.
Ответ №2:
Обратите внимание, что для каждого x и для каждого y вам нужно сгенерировать два z из-за 2(a b). Также обратите внимание, что каждую строку можно рассматривать как «внутреннюю» часть y ‘s и z ‘s и как «внешнюю» часть x ‘s и z ‘s.
Поскольку для каждого y вам нужно два z ‘s, внутренняя часть может быть описана (используя заглавные буквы для обозначения нетерминальных символов и [] для пустой строки):
I --> []
I --> y I z z
Теперь напишите грамматику для внешней части таким же образом, но со ссылкой на I в базовом варианте.
Ответ №3:
По сути, есть два случая, которые вам нужно рассмотреть:
- Вы можете либо добавить
xв начале строки, в этом случае вам нужно добавить дваz’s в конце. - Или вы можете добавить
yв середине, и в этом случае вам также нужно добавить двеzбуквы в конце.
Попробуйте свести любое из этих описаний к более простой грамматике (например, a^n b^n ), для которой вы знаете решение.
Этой подсказки должно быть достаточно, чтобы вывести порождающий грамматик.