NULL-Zulässigkeit (Reguläre Ausdrücke)

Question

In Brzozowski "Derivatives of Regular Expressions" und anderswo, die Funktion δ (R) zurückkehr λ, wenn eine R NULL sein kann, und ∅ Ansonsten enthält Klauseln, wie die folgenden:

δ(R1 + R2) = δ(R1) + δ(R2) 
δ(R1 · R2) = δ(R1) ∧ δ(R2) 

klar, wenn beide R1 und R2 sind NULL festlegbaren dann (R1 · R2) ist NULL festlegbaren, und wenn entweder R1 oder R2 ist NULL festlegbaren dann (R1 + R2) ist nullable. Es ist mir unklar, was die obigen Klauseln jedoch bedeuten sollen. Mein erster Gedanke, Mapping (+), (·) oder die Boolesche Operationen regelmäßig Sätze ist unsinnig, da im Basisfall,

δ(a) = ∅ (for all a ∈ Σ) 
δ(λ) = λ 
δ(∅) = ∅ 

und λ ist kein Satz (noch ist ein Satz der Rückgabetyp von δ, was ein regulärer Ausdruck ist). Außerdem wird diese Zuordnung nicht angezeigt, und es gibt eine separate Notation dafür. Ich verstehe NULL-Fähigkeit, aber ich bin bei der Definition der Summe, des Produkts und der Booleschen Operationen in der Definition von δ nicht mehr dabei: Wie werden λ oder ∅ beispielsweise von δ() ∧ δ (R2) zurückgegeben , in der Definition off δ (R1 · R2)?

Answer 1

Ich glaube, du bist immer durch die Notations Freiheiten vom Autor ertappt. Der Rückgabetyp von δ (R) ist mit Sicherheit eine Menge oder eher eine Sprache. Wenn man sich die Definition aussehen:

Sie können sehen, dass es eine Inkonsistenz in dem Rückgabetyp, λ formal ist ein Element, aber ∅ ist die leere Sprache ... Was es sagen soll, ist:

die Tatsache, dass der Autor für λ verwendet nur die leere Zeichenkette, die sowohl die leere Zeichenfolge als auch die Sprache weiter durch seine Definition des Kleene Stern Betreiber belegt wird:

Klar sollte der letzte Teil sein, wenn wir pedantisch sein wollen.

Da der Rückgabetyp von δ (R) ein Satz ist, oder vielmehr eine Sprache, die Gleichungen Sie durchaus Sinn geben machen und Express genau das, was Sie beschrieben.

Answer 2

Ich glaube, Sie hatten Recht, + und ^ auf boolean or bzw. and zu mappen. Es sieht aus wie die beiden Linien, die Sie viel zitierte mit Wechsel (Summe) und Verkettung (Produkt):

δ(R1 + R2) = δ(R1) + δ(R2) 

Der Wechsel von R1 und R2 NULL-Werte zulässt, wenn R1 NULL-Werte zulässt, R2 NULL-Werte zugelassen, oder beide R1 und R2 sind nullfähig.

δ(R1 · R2) = δ(R1) ∧ δ(R2) 

Die Verkettung vonR1 und R2 nur NULL festlegbaren wenn beide R1 und R2 NULL festlegbaren sind.

Eine Haskell-Implementierung dieser Regeln finden Sie unter here.

Answer 3

(Ich kann nicht in den Artikel von Brzozowski schauen, um besser zu verstehen, was dort gemeint ist), aber ich kann zwei Wege vorschlagen, diese Notation zu interpretieren (abgesehen davon, mit der Notation zu gehen, sehe ich, es gibt keine Frage: der beabsichtigte Sinn dieser Definition ist gut verstanden):

1) Auf der linken Seite der Definition haben wir nur "syntaktische" Muster für die regulären Ausdrücke. Auf der rechten Seite produzieren wir Sets; Denken Sie daran, dass ein regulärer Ausdruck eine Möglichkeit ist, eine Sprache (eine Menge) zu bezeichnen, und so wird die Definition der Definition verständlich: Auf der rechten Seite verwenden wir einfach einige (einfache) reguläre Ausdrücke als eine kurze Möglichkeit, auf sie Bezug zu nehmen Sätze. D.h., ∅ bedeutet die leere Sprache (die leere Menge), und λ (wenn interpretiert als als ein regulärer Ausdruck) bedeutet die Sprache, die nur das leere Wort enthält (die Menge mit diesem Element).

Die Operationen sind einfach Operationen auf Sets: wahrscheinlich Union, und Kreuzung.

Wenn die Notation auf diese Weise interpretiert wird, gibt es keinen Widerspruch zu der verwendeten Notation, um den Basisfall zu definieren: "a" ist wiederum ein regulärer Ausdruck, der dort die Sprache mit dem Wort "a" bedeutet.

2) Wir bauen reguläre Ausdrücke auf der rechten, in erster Linie, aber der Autor hat die Operationen erweitert, die reguläre Ausdrücke mit dem Keil, der die Semantik der Kreuzung von Sprachen hat.