Нужна контекстно-свободная грамматика, в которой одного символа в 5 раз больше, чем другого.

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

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

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

S = aSbbbb | λ

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


context-free-grammar pushdown-automaton
person Aurast    schedule 21.03.2012    source источник
comment
У вас есть доказательства того, что можно выразить грамматику с помощью нескольких правил?   -  person Simeon Visser    schedule 21.03.2012

Ответы (1)


arrow_upward
4
arrow_downward

Прежде всего, обратите внимание, что если в предложении в 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).

person Simeon Visser    schedule 21.03.2012
comment
Я не знаю, что вы только что сказали, но вы использовали символ, который я не знаю, как сделать с клавиатурой, так что это должно быть правильно. +1 ;) - person hvgotcodes; 21.03.2012
comment
Спасибо за ответ! Но я не уверен, что это правильно. Я не могу понять, как вывести, например, baaaaaaaaaab из этих правил. Мои извинения, если я что-то упускаю из виду. Вы видите способ получить baaaaaaaaaab? Кажется возможным получить b только на одном конце строки. - person Aurast; 22.03.2012
comment
Вы правы, я не смог найти способ вывести baaaaaaaaaab. Я изменил правило для S, чтобы сделать это возможным: S = AS = AAS = AA = BaaaaaA = BaaaaaaaaaaB = bSaaaaaaaaaaB = bSaaaaaaaaaabS = bSaaaaaaaaaab = baaaaaaaaaab. - person Simeon Visser; 22.03.2012
comment
Красиво, я думаю, это работает. Спасибо! Не думаю, что я когда-либо мог придумать это ›.‹ - person Aurast; 22.03.2012