Ausreichende Voraussetzungen für die Ordnungsmäßigkeit einer kontextfreien Sprache

14

Es wäre schön, eine Liste von Bedingungen zu sammeln, die implizieren, dass eine kontextfreie Sprache L regulär ist, dh Bedingungen der Form: "Wenn ein gegebenes CFG / PDA die Eigenschaft P hat, dann sind seine Sprachen regulär".

Die Eigenschaft P muss die CFGs, die reguläre Sprachen erzeugen, nicht charakterisieren. Außerdem muss P nicht entscheidbar sein, und P sollte "irgendwie" davon abhängen, dass die Sprache kontextfrei ist ("das syntaktische Monoid von L ist endlich", "L ist im Raum o entscheidbar (log log n)" usw.) sind nicht das, wonach ich suche).

reference-request fl.formal-languages regular-language context-free survey fh
quelle
Sehr wahrscheinlich ist die allgemeine Frage nicht zu entscheiden. Die Analogie ist, dass es andere Theoreme gibt, die besagen, dass "ist B tatsächlich A", wobei A eine "kleinere" Sprachklasse ist, als B unentscheidbar ist. Ich erinnere mich an eine Frage hierüber, die vielleicht ähnlich war, sie aber im Moment nicht finden kann.
vzn
Mit "Regelmäßigkeit" meinen Sie, ist es wirklich eine reguläre Sprache, oder?
vzn
3
Ok, ich habe es gefunden. diese frage ist dieser sehr ähnlich, "ist eine kfg eigentlich eine
rl
4
@vzn Ich denke, OP sucht nicht nach einem Algorithmus zur Bestimmung der Regelmäßigkeit von CFLs, sondern nach einigen ausreichenden Bedingungen. Zum Beispiel ist die Regelmäßigkeit einer TM-Sprache nicht bestimmbar, aber eine ausreichende Bedingung ist, dass eine Sprache, die in bestimmbar ist, regelmäßig sein muss. Ö(nlÖGn)
aelguindy,
vereinbart, Unterscheidung gilt. Aber es ist auch wichtig, gleichzeitig zu wissen, dass das allgemeine Problem nicht zu entscheiden ist. "Ausreichende Bedingungen" hängen im Allgemeinen eng mit Algorithmen zusammen, z. B. in dem Beispiel, das Sie für die Komplexität der Zeit angegeben haben.
vzn

Antworten:

15

  1. Jede unäre kontextfreie Sprache ist regelmäßig. (zB eine direkte Konsequenz von Parikhs Theorem)

  2. xunyvnz∈L,für alle n≥0⟹xuichyvjz∈L, für alle ich,j≥0.

  3. Wenn eine kontextfreie Sprache kommutativ und linear ist, ist sie regelmäßig. (Ehrenfeucht, Haussler, Rozenberg, "Zur Regelmäßigkeit kontextfreier Sprachen" , 1983)

fh
quelle