Gibt es eine Erweiterung für reguläre Ausdrücke, die die kontextfreien Sprachen erfasst?

25

In vielen Arbeiten mit kontextfreien Grammatiken (CFGs) lassen die dort vorgestellten Beispiele für solche Grammatiken oft einfache Charakterisierungen der von ihnen erzeugten Sprache zu. Beispielsweise:

SaaSb
S

erzeugt ,{a2ibi|i0}

SaSb
SaaSb
S

erzeugt{aibjij0} und

SaSa
SbSb
S

erzeugt oder äquivalent (wobei sich auf den Teil bezieht, der von erfasst wurde ).{wwRw(a|b)}{((a|b))1((a|b))2p1=p2R}p1(...)1

Die obigen Beispiele können alle durch Hinzufügen von Indizes ( ), einfachen Einschränkungen für diese Indizes ( ) und Musterübereinstimmung mit regulären Ausdrücken generiert werden . Ich frage mich daher, ob alle kontextfreien Sprachen durch eine Erweiterung der regulären Ausdrücke generiert werden können.aii>j

Gibt es eine Erweiterung von regulären Ausdrücken, die alle oder einige signifikante Teilmengen der kontextfreien Sprachen generieren können?

Alex ten Brink
quelle
3
Beachten Sie, dass das Hinzufügen von Indizes und Abhängigkeiten zu leistungsfähig ist: Sie können , bei dem es sich nicht um eine CFL handelt. anbncn
Shaull

Antworten:

34

Ja da ist. Definieren Sie einen kontextfreien Ausdruck als einen Begriff, der von der folgenden Grammatik generiert wird:

g::=ϵEmpty string|cCharacter c in alphabet Σ|ggConcatenation|Failing pattern|ggDisjunction|μα.gRecursive grammar expression|αVariable expression

Dies sind alle Konstruktoren für reguläre Sprachen mit Ausnahme von Kleene star, der durch einen allgemeinen Festkommaoperator und einen variablen Referenzmechanismus. (Der Kleene-Stern wird nicht benötigt, da er als g μ α definiert werden kann .μα.g .)gμα.ϵgα

Die Interpretation eines kontextfreien Ausdrucks erfordert die Berücksichtigung der Interpretation freier Variablen. So ein definieren Umgebung eine Karte von Variablen zu Sprachen (dh Teilmengen sein Σ * ), und lassen Sie [ ρ | α : L ] ist die Funktion, die sich bei allen Eingaben mit Ausnahme von α wie ρ verhält und die die Sprache L für α zurückgibt .ρΣ[ρ|α:L]ραLα

Definieren Sie nun die Interpretation eines kontextfreien Ausdrucks wie folgt:

[[ϵ]]ρ={ϵ}[[c]]ρ={c}[[g1g2]]ρ={w1w2|w1[[g1]]ρw2[[g2]]ρ}[[]]ρ=[[g1g2]]ρ=[[g1]]ρ[[g2]]ρ[[α]]ρ=ρ(α)[[μα.g]]ρ=nNLnwhereL0=Ln+1=Ln[[g]][ρ|α:Ln]

Mit dem Knaster-Tarski-Theorem ist leicht zu erkennen, dass die Interpretation von ist das am wenigsten feste des Ausdrucks.μα.g

Es ist einfach (wenn auch nicht ganz trivial) zu zeigen, dass Sie einen kontextfreien Ausdruck geben können, der dieselbe Sprache wie jede kontextfreie Grammatik hat, und umgekehrt. Die Nicht-Trivialität ergibt sich aus der Tatsache, dass kontextfreie Ausdrücke verschachtelte Fixpunkte haben und kontextfreie Grammatiken Ihnen einen einzelnen Fixpunkt über einem Tupel geben. Dies erfordert die Verwendung von Bekics Lemma, das genau besagt, dass ein verschachtelter Fixpunkt über ein Produkt in einen einzelnen Fixpunkt umgewandelt werden kann (und umgekehrt). Aber das ist die einzige Subtilität.

EDIT: Nein, ich kenne keine Standardreferenz dafür: Ich habe es für mein eigenes Interesse ausgearbeitet. Es ist jedoch offensichtlich genug, dass ich zuversichtlich bin, dass es zuvor erfunden wurde. Einige Gelegenheits-Googler enthüllen Joost Winter, Marcello Bonsangue und Jan Ruttens kürzlich erschienene Veröffentlichung Context-Free Languages, Coalgebraically , in der sie eine Variante dieser Definition angeben (wobei alle Fixpunkte geschützt werden müssen), die sie auch als kontextfreie Ausdrücke bezeichnen.

Neel Krishnaswami
quelle
Das ist ziemlich genial. Gibt es einen Standardnamen oder eine Referenz dafür?
Alex ten Brink
5
Arto Salomaa behandelt dies 1973 in seinem Buch „Formale Sprachen“. Er nennt sie „reguläre Ausdrücke“.
Tim Schaeffer
3

Zu MathOverflow gab es eine eng verwandte Frage (und mehrere Antworten) zu den Sprachen, deren generierende Funktionen holonom sind .

μ

Jacques Carette
quelle
μα.g[μα.g/α]g
1

Wir haben kürzlich die Umrisse eines Frameworks veröffentlicht, das genau das ermöglicht. Schauen Sie unter comp.compilers nach , wo ich eine Benachrichtigung zusammen mit einigen Links gesendet habe.

Die neuen Entwicklungen stützen sich auf das Chomsky-Schützenberger-Theorem und können als Ergänzung dieses Ergebnisses angesehen werden. Chomsky selbst wurde über die Entwicklungen informiert und zeigt den Wunsch, "aufzuholen".

Zusammen mit dieser Entwicklung stellen wir auch die Äquivalenz von zwei getrennten Formulierungen für kontextfreie Ausdrücke fest - eine, die eine Erweiterung / Vervollständigung der Mu-Kalkülform "kleinster fester Punkt" darstellt (ursprünglich von Gruska, Yntema und McWhirter). die eine endgültige Formulierung von Art im Jahr 2014 erhalten - und die andere im Jahr 2008 veröffentlicht.

NinjaDarth
quelle
4
Bitte geben Sie alle relevanten Informationen in der Antwort selbst an. "Look under comp.compilers" ist bereits jetzt eine hilflose Antwort und wird in ein paar Monaten völlig unbrauchbar sein.
Emil Jeřábek unterstützt Monica
Das ist völlig falsch. Comp.compilers (im Gegensatz zu dieser Site und anderen Blogs übrigens) werden permanent archiviert. Dort finden Sie alle Details, die Sie benötigen. Es gibt viele Links, die auch im zuletzt geposteten Artikel zu finden sind. Im Gegensatz zu Blogseiten ist es auch nach außen offen und für ein viel breiteres Publikum nützlich. Sie sollten keine Schwierigkeiten haben, im USENET etwas zu finden - hier sollten Fragen wie diese beantwortet und diskutiert werden. Wenn Sie Schwierigkeiten haben, finden Sie hier den Link. groups.google.com/forum/#!topic/comp.compilers/YCa5jHUR1iQ
NinjaDarth
2
Das Problem ist nicht, dass es nicht archiviert ist, sondern dass die Archive riesig sind. Wenn ich jetzt in den Archiven nachschaue, kann ich Ihren Beitrag irgendwo oben finden, aber wenn jemand diese Antwort in einigen Monaten oder Jahren in der Zukunft sieht, hat er keine Ahnung, wo er anfangen soll zu graben. Es ist arrogant und unhöflich, die Leser zu einer längeren und unzuverlässigen Suche zu veranlassen, wenn Sie sie auf einen genaueren Ort verweisen können. Jetzt habe ich es für dich getan. Es dauerte ungefähr 30 Sekunden. Das hättest du selbst tun können.
Emil Jeřábek unterstützt Monica