Как написать этот CFG?

Question

вопрос заключается в построении CFG, который генерирует язык

мое решение: S -> aSb | aS | bS | a | b, однако, эта грамматика может также генерировать строки, как aabb, так как сделать это?

Спасибо за помощь.

Answer 1

Итак, вы хотите строку a-х затем строку b-х, с неравным числом a х и b годов. Во-первых, давайте проигнорируем условие равенства. Тогда:

S -> aSb | 0

будет генерировать все строки, которые начинаются с a-х, а затем b 'с. Это правило гарантирует равное количество a и b или пустую строку. Теперь мы хотим либо больше a, либо больше b, но не оба. Потому что, если бы мы хотели еще один a И еще один b, мы бы снова применили S. Таким образом, мы добавим два новых правила:

A -> aA 
B -> bB 

и обновить S быть:

S -> aSb | A | B

Итак, теперь мы можем добавить равное количество a и b, или добавить больше a «S, или добавьте еще b, но не оба. Это гарантирует неравенство, поэтому мы почти закончили. Если вам не нужна пустая строка, вы можете просто остановиться здесь. Для пустой строки, мы не можем сделать:

S -> aSb | A | B | 0,

потому что это может привести к S -> aSb -> a0b -> ab, что нарушает условия. Мы также не можем сделать:

A -> aA | 0,

потому, что может привести к S -> aSb -> aAb -> a0b -> ab. Так что же нам делать? Хитрость заключается в том, чтобы заставить S «s позже расширения, чтобы иметь по крайней мере один a или b, как это:

S -> aSb | aA | bB 
A -> aA | 0 
B -> bB | 0 

и это ваше решение.