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.
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