Die Frage ist, eine kontextfreie Grammatik für Sprache zu entwickeln, die alle Zeichenfolgen enthält, die eine größere Anzahl von As als Bs haben.Kontextfreie Grammatik für Sprachen mit mehr als as bs
Ich kann nicht an eine logische Lösung denken. Gibt es eine Möglichkeit, solche Probleme anzugehen, was kann mir helfen, solche Probleme besser anzugehen? Kann jemand einen logischen Weg vorschlagen, um solche Grammatikprobleme zu analysieren?
Die folgende Grammatik generiert alle Zeichenfolgen über {a,b}, die mehr a als b haben. Ich bezeichne mit eps die leere Zeichenfolge.
S -> Aa | RS | SRA
A -> Aa | eps
R -> RR | aRb | bRa | eps
Es ist offensichtlich, es immer mehr a 's als b' s erzeugt. Es ist weniger offensichtlich, es alle möglichen Strings über {a,b} erzeugt, die mehr a ‚s als b‘ s
Die Produktion R -> RR | aRb | bRa | eps erzeugt alle ausgeglichen Strings (dies ist leicht zu sehen) haben, und die Produktion A -> Aa erzeugt die Sprache a* (dh Strings mit null oder mehr a 's).
Hier ist die Logik hinter der Grammatik. Beachten Sie, dass, wenn w=c1,c2,c3,...,cn eine Zeichenkette über {a,b} mit mehr a als b ist, dann können wir es immer in eine Verkettung von symmetrischen Strings (dh gleiche Anzahl von a 's und b' s, die die leere Zeichenfolge enthält) zerlegen und Zeichenfolgen der Form a+.
Zum Beispiel ababaaaba = abab (kann durch R erzeugt werden), aaa (kann durch A erzeugt werden), ba (kann durch R erzeugt werden).
Jetzt beachten Sie, dass die Produktion S -> Aa | RS | SRA genau Strings dieser Form erzeugt.
Es genügt, um sicherzustellen, dass S die folgenden Fälle abdeckt (weil jeder andere Fall kann durch Brechen in eine solche Unterfälle abgedeckt werden, wie Sie überprüfen sollten):
[a][balanced]: S => SRA => AaR verwenden.[balanced][a]: S => RS => RA => RAa verwenden.[balanced][a]balanced]: S => SRA => RSRA => RAaR verwenden.Eine andere vielleicht einfachere Lösung:
S->A|AAB|BAA|e A->AA | a B->AB | BA | b
Können Sie die Sprache beschreiben Sie möchten genauer generieren? Zum Beispiel, ist 'aabbaba' eine gültige Zeichenfolge? – blazs
@blazs Ja aabbaba wäre eine gültige Zeichenfolge, es gibt keine Einschränkung in der Reihenfolge von a oder b. Ich bin in der Lage, Grammatiken für Fälle zu schreiben, wenn Bs As folgen, aber die Allgemeinheit des gegebenen Problems erweist sich als schwierig – nino