Werden kontextfreie Sprachen in

20

Die kontextfreien Sprachen werden nicht unter Ergänzung geschlossen, das wissen wir.

Nach meinem Verständnis werden kontextfreie Sprachen, die für einige Buchstaben eine Teilmenge von sind, unter Komplement (!?) geschlossen.aba,b

Hier ist mein Argument. Jede CF-Sprache hat ein halblineares Parikh-Bild . Semilineare Mengen werden unter Ergänzung geschlossen. Die Menge der Vektoren, die die semilineare Menge darstellen, kann leicht in eine lineare Grammatik umgewandelt werden.π ( L ) = { ( m , n ) a m b nL }Lπ(L)={(m,n)ambnL}

Frage. Gibt es einen leicht zugänglichen Hinweis auf diese Tatsache?

Technisch werden diese Sprachen als beschränkt bezeichnet , dh eine Teilmenge von für einige Wörter . w 1 , , w kw1wkw1,,wk

Meine Motivation für diese Frage ist eine aktuelle Frage zur Kontextfreiheit von . Die Ergänzung innerhalb von scheint einfacher zu handhaben zu sein.a b {anbmn2m}ab

Hendrik Jan
quelle
Haben Sie Ginsburgs "The Mathematical Theory of Context-Free Languages" überprüft? Anscheinend gibt Satz 5.4.2 die Charakterisierung von beschränkten kontextfreien Sprachen an, auf die Sie sich beziehen, und ich wette, Ginsburg würde die Implikation für die Ergänzung von beschränkten kontextfreien Sprachen erwähnen (im zweidimensionalen Fall).
Yuval Filmus

Antworten:

12

kk2w1w2

Ginsburg erwähnt diese Implikationen in seinem Buch.

M1w1w2M2w1w2M1M2

M1w1w2M2w1w2M1M2M2M1

Yuval Filmus
quelle
2

Ein anderer Beweis verwendet die folgende in dieser Antwort bewiesene Charakterisierung :

{aibj:(i,j)A}A

AA¯

Liab

Yuval Filmus
quelle