Нужна контекстно-свободная грамматика с 5-кратным числом одного символа по сравнению с другим

Question

Я почти уверен, что у меня действительно есть один, но он имеет 42 правила построения и плохо обобщается. Как я могу сделать это с меньшим количеством правил строительства?

Язык - {a, b} *, где число a в пять раз превышает количество b.

Я знаю, что для языка {a ^ n (сцепленный) b ^ m; m = 5n} это будет просто

S = aSbbbbb | λ

Но когда персонажи могут быть в любом порядке, я теряюсь.

Answer 1

Прежде всего, обратите внимание, что если предложение содержит в 5 раз больше символов, чем другое, оно всегда будет выглядеть примерно так: aaabaabaaaaa.Таким образом, одно предложение может быть aaaaab или aaabaa.Другое наблюдение состоит в том, что всякий раз, когда мы добавляем b, мы должны добавлять пять a символов.

В следующей грамматике действительно * в пять раз больше a символов, чем b символов:

S = AS | λ
A = Baaaaa | aBaaaa | aaBaaa | aaaBaa | aaaaBa | aaaaaB
B = bS | Sb

Мы начинаем с S, который может быть либо пустым (что удовлетворяет требованию), либо A.

Правило для A выдает не менее 5 a символов и B.Теперь для B мы можем либо поместить b и остановиться там (выбрав пустую строку для S), либо начать заново (выбрав A для S).Это гарантирует, что мы всегда помещаем в 5 раз больше a символов, чем b символов.

Наконец, эту грамматику можно легко обобщить до грамматики, которая должна содержать n раз больше символоводно как другое (прямым правилом A).