Язык, который вы перечислили, неясен. Я предполагаю, что w E {a,b,c}* означает w ε {a,b,c}*, а nb(w) != na(w) + nc(w) означает, что все строки в языке имеют число b, не равное сумме числа a и числа c.
Если это так, вам нужно подумать о характеристиках всех строк, которые будут в языке, и обо всех характеристиках, которые исключат строку из этого языка.
Этот язык принимает строки, где число b = = число a + количество c. Мы можем переформулировать этот язык так, чтобы он принимал строки, которые:
число a 's + число c' s> число b 's
ИЛИ ЖЕ
число a 's + число c' s <число <code>b 's
Это объясняет первый 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 's / c' s (S0) или более a 's / c' s. чем b (снова S2).
Это характерно для вашего примера, но вы можете увидеть, как мыслительный процесс, который входит в создание этой грамматики:
- Сформулируйте язык как конкретные случаи (
a 's / c' s> или <<code>b 's)
- Для каждого из случаев начните с того, что убедитесь, что он будет удерживаться (принудительно #
b s> чем a s / c s, форсируя хотя бы один b), затем расширяя строка для включения всех возможностей, равных a 's / c' s и b 's, или меньше a' s / c 's, чем b' s.
- Симметрично обрабатывать другой случай.
Проблема в том, что вам нужно убедиться, что каждая строка в языке сгенерирована, а все строки не на языке не сгенерированы. (перечитайте это до тех пор, пока это не произойдет)