Alle kontextfreien Sprachen aus einer Reihe von Basissprachen und Schließungseigenschaften erstellen?

10

Eine Möglichkeit, reguläre Ausdrücke zu betrachten, ist ein konstruktiver Beweis für die folgende Tatsache: Es ist möglich, reguläre Sprachen zu konstruieren, indem mit einer kleinen Menge von Sprachen begonnen und diese über eine kleine, feste Menge von Schließungseigenschaften kombiniert werden. Wenn wir mit der leeren Sprache, der Sprache, die die leere Zeichenfolge enthält, und den Sprachen aller Einzelzeichenfolgen beginnen, können wir alle möglichen regulären Sprachen mithilfe von Union, Verkettung und Kleene-Stern zusammenstellen.

Gibt es eine Reihe von Basissprachen und Schließungseigenschaften, mit denen alle und nur die kontextfreien Sprachen generiert werden können? (Zur Verdeutlichung: Ich frage nicht, ob Sie reguläre Ausdrücke für alle CFLs schreiben können, von denen ich weiß, dass dies unmöglich ist. Stattdessen frage ich mich, ob es eine Möglichkeit gibt, ein Framework für reguläre Ausdrücke für CFLs basierend auf dem zu entwerfen gleiche Grundprinzipien.)

templatetypedef
quelle
1
In diesem Fall enthält eine unserer Referenzfragen möglicherweise das, was Sie benötigen.
Raphael

Antworten:

8

D2{[,],(,)}a1,b1,a2,b2

D2D2M(D2)

g(h1(D2)R)ghRRghD2

Lg(h1(L)R)g,h,R

Hendrik Jan.
quelle
Wow, das ist wirklich interessant! Wenn Sie Referenzen dazu haben, würde ich sie gerne überprüfen!
Templatetypedef
Fantastisch. Dies beantwortet meine Frage perfekt.
Templatetypedef