Указанный вами язык неясен. Я предполагаю, что w E {a,b,c}* означает w ε {a,b,c}*, а nb(w) != na(w) + nc(w) означает, что все строки в языке имеют количество b, не равное сумме количества a и количества c.
Если это так, вы должны подумать о характеристиках всех строк, которые будут на языке, и всех характеристиках, которые исключают строку из этого языка.
Этот язык принимает строки, в которых количество b = / = количество a + количество c. Мы можем переформулировать этот язык так, чтобы он принимал строки, которые:
число a + число c> число b ИЛИ число a + число c ‹число b
Это объясняет первое S -> S1 | S2
S1 гарантирует наличие как минимум 1 b (S3), а затем форсирует либо равное количество b, сколько a и c (S0), или больше b, чем a и c (S1). Конечный результат правила S1 - это строка с большим количеством b, чем a и c.
S2 гарантирует, что имеется больше a и / или c, чем b. Он делает это, выставляя a или c (X), а затем разрешая равное количество a / c (S0) или больше a / c, чем b (снова S2).
Это характерно для вашего примера, но вы можете увидеть, как мыслительный процесс входит в создание этой грамматики:
- Сформулируйте язык в виде конкретных случаев (
a's / c's> или ‹b's)
- Для каждого из случаев начните с того, чтобы убедиться, что регистр будет сохраняться (принудительно установите #
b's>, чем a / c, заставив хотя бы один b), затем разверните строку, чтобы включить все возможности равных a / c и b или меньше a / c, чем b.
- Симметрично обработайте другой случай.
Проблема в том, что вам необходимо убедиться, что создается каждая строка на языке, а все строки не на этом языке не создаются. (перечитайте это до тех пор, пока не уляжется смысл)
person
prelic
schedule
16.11.2010
