Контекстно-бесплатная грамматика для языков с большим количеством символов, чем bs
Вопрос состоит в том, чтобы разработать контекстно-свободную грамматику для языка, содержащего все строки, имеющие большее число As, чем Bs.
Я не могу придумать логического решения. Есть ли способ подойти к таким проблемам, что может помочь мне лучше подойти к таким проблемам? Может кто-нибудь предложить логичный способ анализа таких грамматических проблем?
4 ответа
Следующая грамматика генерирует все строки {a,b} которые имеют больше aчем b"S. Я обозначаю через eps пустая строка.
S -> Aa | RS | SRA
A -> Aa | eps
R -> RR | aRb | bRa | eps
Очевидно, это всегда генерирует больше aчем b"S. Менее очевидно, он генерирует все возможные строки {a,b} которые имеют больше aчем b"s
Производство R -> RR | aRb | bRa | eps генерирует все сбалансированные строки (это легко увидеть), и производство A -> Aa генерирует язык a* (т.е. строки с нулем или более a"S).
Вот логика грамматики. Обратите внимание, что если w=c1,c2,c3,...,cn это строка над {a,b} с более aчем bТогда мы всегда можем разложить его на объединение сбалансированных строк (т.е. равное количество aи bи пустые строки) и строки вида a+,
Например, ababaaaba знак равно abab (может быть сгенерировано R),aaa (может быть сгенерировано A),ba (может быть сгенерировано R).
Теперь обратите внимание, что производство S -> Aa | RS | SRA генерирует именно строки этой формы.
Достаточно проверить, что S охватывает следующие случаи (поскольку любой другой случай может быть охвачен путем разбиения на такие подслучаи, как вы должны проверить):
[a][balanced]: использоватьS => SRA => AaR,[balanced][a]: использоватьS => RS => RA => RAa,[balanced][a]balanced]: использоватьS => SRA => RSRA => RAaR,
Другим простым решением, которое я могу придумать, было бы:
S -> XAX|a
A -> aS|Sa
X -> aXb|bXa|e
Чтобы e было эпсилон.
S → TaT
T → ATb | bTA | TT | ɛ
A → aA | а
T генерирует любую строку, где #a >= #b (включая пустую строку). S гарантирует, что в любой позиции хотя бы на одну букву "a" больше, чем b.
Еще одно, возможно, более простое решение:
S->A|AAB|BAA|e
A->AA | a
B->AB | BA | b