Wie leistungsfähig sind CFGs, die eine unendliche Anzahl von Regeln zulassen?

9

Ich habe mich kürzlich gefragt, was passieren würde, wenn wir kontextfreien Grammatiken eine unendliche Anzahl von Regeln erlauben würden. Wenn wir willkürlich solche unendlichen Regelsätze zulassen würden, könnte jede Sprache L über einem Alphabet Σ durch ein CFG G=({S},Σ,R,S) mit R={SwwL} . Was aber, wenn wir R auf solche Regelsätze beschränken , die durch kontextfreie Grammatiken erstellt werden können?

Zu diesem Zweck betrachten wir bei einer Menge von Nichtterminals N und Terminals Σ Regeln nicht als Elemente von N×(NΣ) , sondern als Zeichenfolgen über dem Alphabet . Meine Frage ist nun, ob wir eine CFG mit unendlicher Regel als Tupel wobeiR(N,Σ)=NΣ{}G=(N,Σ,R,S)

  • N ist eine endliche Menge von Nichtterminalen
  • Σ ist ein endliches Alphabet
  • A w A N w ( N Σ ) G R ( N , Σ ) R = L ( G )R ist ein Satz von Regeln der Form mit , so dass es ein CFG über mit gibtAwANw(NΣ)GR(N,Σ)R=L(G)
  • SN ist das anfängliche Nichtterminal

und wir definieren für solche CFGs mit unendlichen Regeln, genau wie es für CFGs gemacht wird. Wie ist die Beziehung zwischen der Klasse von Sprachen, die durch CFGs mit unendlichen Regeln erzeugt werden (nennen wir diese Klasse ), der Klasse der kontextfreien Sprachen und die Klasse ?i r C F C F R E.L(G)irCFCFRE

haben wir , aber entspricht einer dieser Klassen (oder einer anderen Klasse)?i r C F.CFirCFREirCF

Messgerät
quelle

Antworten:

7

Nehmen wir an, wir nehmen das Metagramm und faktorisieren es durch Präfixe mit zwei Symbolen. Mit anderen Worten, für jedes A N- Konstrukt G ' A ist die linke Ableitung von G ' über die Zeichenkette A . Das ergibt eine (endliche) Menge von (endlichen) Metagrammen, von denen jedes alle (möglicherweise unendlichen) Produktionen für einige A N erzeugt .GANGAGAAN

G ' A A S G ' A G ' A S G ' A G ' A G " N G ' A G G " G G "GGAASGAGAS.GEIN'GEIN'GN.GEIN'GGGGist eine endliche Grammatik für dieselbe Sprache, da der Ableitungsprozess nicht vom Ursprung der Regeln beeinflusst wird; Es ist nur eine Zeichenfolgenersetzung über ein Alphabet.

Wenn der obige Proof-Umriss gültig ist, sind und gleich.i r C F.C.F.ichrC.F.

Wie ich in einem Kommentar angedeutet habe, gibt es interessantere Beispiele für zweistufige Grammatiken, einschließlich der Van-Wijngaarden-Grammatiken und der verschiedenen Versuche, überschaubarere Formalismen zu schaffen, ohne die zusätzliche Kraft zu verlieren.

Rici
quelle