Вопрос заключается в разработке контекстной свободной грамматики для языка, содержащего все строки, имеющие большее число, чем Bs.Контекстная свободная грамматика для языков с большим числом символов, чем bs
Я не могу думать о логическом решении. Есть ли способ приблизиться к таким проблемам, что может помочь мне лучше подойти к таким проблемам? Может ли кто-нибудь предложить логический способ анализа таких проблем грамматики?
Следующая грамматика генерирует все строки над {a,b}, у которых больше a, чем b. Я обозначаю eps пустую строку.
S -> Aa | RS | SRA
A -> Aa | eps
R -> RR | aRb | bRa | eps
Очевидно, что всегда порождает больше a 'ю.ш., чем b-х гг. Это менее очевидно, что это порождает все возможные строки над {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->A|AAB|BAA|e A->AA | a B->AB | BA | b
Можете ли вы описать язык вы хотели бы произвести более точно? Например, является ли «aabbaba» допустимой строкой? – blazs
@blazs Да aabbaba будет действительной строкой, нет ограничений на порядок a или b. Я умею писать грамматики для случаев, когда Bs следуют так же, но общность данной проблемы оказывается непростой – nino