Reguläre Ausdrücke für reguläre Relationen

[ Weiter ] [ Zurück ] [ Zurück (Seitenende) ] [ Seitenende ] [ Überkapitel ] [ Bitte Skript-Fehler melden ]

5.4. Reguläre Ausdrücke für reguläre Relationen

5.4.1. Produkt

Das kartesische Produkt in XFST
Wenn die RA A und B die Sprachen A und B über Σ bezeichnen, dann bezeichnet [ A .x. B ] die Relation A × B.

Frage

Welche Relation beschreibt folgender Transduktor?
xfst[0]: read regex [{cat}|{dog}] .x. [{katze}|{hund}];

Universale Relation

Der RA [ ?* .x. ?* ] bezeichnet die universale Relation Σ^∗× Σ^∗, welche irgendeine Zeichenkette mit einer beliebigen andern paart.

Doppelpunkt-Operator

Anstelle von [ A .x. B ] kann auch [ A : B ] verwendet werden, der Doppelpunkt bindet einfach stärker. Er wird normalerweise für Symbolpaare verwendet a:b oder zusammen mit Klammernotation: {cat}:{chat}.

ANY-Symbol, Sprachen und Identitätsrelation
Jeder RA A für eine Sprache bezeichnet auch deren Identitätsrelation.

ANY-Symbol als Identitätsrelation

Der reguläre Ausdruck ? steht sowohl für die Sprache aller Zeichenketten der Länge 1 wie auch für die Identitätsrelation über dieser Sprache.

Wegen der Spezialbedeutung von ? steht ?:? nicht für die Identitätsrelation, sondern für Σ¹ × Σ¹.

Beispiel 5.4.1 (ANY-Symbol in Sprache und Relation).

pict

read regex [ ? ];

pict

read regex [ ?:? ];

Fallstrick: UNKNOWN-Kante vs. UNKNOWN-Paar-Kante

?:? als Kantenbeschriftung bedeutet zwingend unterschiedliche Symbole. Nur ? erlaubt identisches Symbolpaar.

Die unterschiedliche Verwendung des Fragezeichens in regulären Ausdrücken und endlichen Automaten ist bei ?:? besonders verwirrlich zugespitzt. Als regulärer Ausdruck (ANY) schliesst es die Identität ein, aber als Kante (UNKNOWN) schliesst es sie gerade aus. ?:? ist also eigentlich ein UNKNOWN:ANOTHERUNKNOWN.

5.4.2. Komposition

Operator für Komposition von Relationen
Wenn die RA R und S die Relationen R und S über Σ bezeichnen, dann bezeichnet [ R .o. S ] eine Relation. Sie beinhaltet ein Zeichenkettenpaar 〈u,w〉 genau dann, wenn R ein Paar 〈u,v〉 enthält und S ein Paar 〈v,w〉.

{〈u,v〉}∘ {〈v,w〉} = {〈u,w〉}

Deﬁnition 5.4.2. Die Komposition von Relationen R ∘ S ⊆ Σ^∗× Σ^∗ ist:

∗ ∗ ∗ ∗ ∗ ∗ ∘ : ℘(Σ × Σ ) × ℘(Σ × Σ ) → ℘ (Σ × Σ )

R ∘ S = {〈u,w〉 | ∃v ∈ Σ∗(〈u,v〉 ∈ R ∧ 〈v,w〉 ∈ S)}

Beispiel 5.4.3 (Flexionsmorphologie mit Komposition und Ersetzung). Ein Beispiel für typisches Zusammenspiel von Komposition und Ersetzung bei der Behandlung eines Ausschnitts der regulären Verbﬂexion des Deutschen ﬁndet sich ▸▸▸hier.

Beispiele zur Komposition
Welche Sprach-Relationen bezeichnen die folgenden RA?

[a:b] .o. [b:c]
[a:b] .o. [c:b]
[b:a|c:b] .o. [a:d]
[c:b] .o. [a:d|b:a]
[a|b|c] .o. [a|c]

Hinweis

Die Komposition ist in XFST zusammen mit der Ersetzung ein fundamentaler Baustein und muss gründlich verstanden sein.

Hinweis

Auf EA angewendet verhält sich die Komposition identisch wie die Schnittmengenbildung:
A .o. B = A & B.

Selbsttest Leichtes QUIZ zur Komposition:
http://www.cl.uzh.ch/ict-open/QUIZ/91

5.4.3. Ersetzung

Operator für Ersetzung (replace)
Wenn die RA A und B die Sprachen A und B über Σ bezeichnen, dann bezeichnet [ A -> B ] eine Relation. Sie besteht aus Paaren von beliebigen Zeichenketten, welche identisch sind, ausgenommen aller Teilzeichenketten aus A in der oberen Sprache, die mit Teilzeichenketten aus B gepaart sein müssen.

Hinweis zur Namensgebung des Operators

Falls B genau eine Zeichenkette enthält, werden alle Vorkommen von A durch B ersetzt.

Beispiel 5.4.4 (xfst und Zustandsdiagramm).

read regex [ A -> B] ;

pict

Die Semantik des Ersetzungsoperators

Beispiel 5.4.5 (Ersetzung ▸▸▸). Gegeben sei die Relation [ [ a | b ] -> [ c | d ] ]. Welche Zeichenketten der unteren Sprache sind zur Zeichenkette eab aus der oberen Sprache gepaart?

xfst[0]: read regex [ [a|b] -> [c|d] ];
180 bytes. 1 state, 7 arcs, Circular.
xfst[1]: apply down eab
...

Reduktion des replace-Operators

[ A -> B ] = [ NO_A [ A .x. B ] ]* NO_A ]
wobei NO_A = ~ $ [ A - 0 ].

Eine beliebig wiederholte Konkatenation von Zeichenketten, welche nichts aus A enthalten, mit dem Kreuzprodukt von A und B. Gefolgt von beliebigen Zeichenketten, welche ebenfalls nichts aus A enthalten.

QUIZ Ersetzung und Komposition in Kombination

Optionale Ersetzung
Wenn die RA A und B die Sprachen A und B über Σ bezeichnen, dann bezeichnet [ A (->) B ] eine Relation.

Sie besteht aus Paaren von beliebigen Zeichenketten, welche identisch sind. Zusätzlich können alle Teilzeichenketten aus A in der oberen Sprache mit Teilzeichenketten aus B gepaart sein.

Beispiel 5.4.6 (xfst und Zustandsdiagramm).

read regex [ A (->) B ] ;

pict

Bedingte Ersetzung (conditional replacement)
Wenn die RA A, B, L und R Sprachen über Σ bezeichnen, dann bezeichnet
[ A -> B || L _ R ] eine Relation.

Sie besteht aus Paaren von beliebigen Zeichenketten, welche identisch sind, ausgenommen aller Teilzeichenketten aus A in der oberen Sprache, die mit Teilzeichenketten aus B gepaart sein müssen, sofern sie nach L und vor R stehen.

Beispiel 5.4.7 (xfst und Zustandsdiagramm).

read regex [
A -> B || L _ R
] ;

pict

Bedingte Ersetzung mit mehrfachen Kontexten
Anstelle nur eines einzigen möglichen Kontexts lassen sich beliebig viele durch Komma getrennt angeben, in denen eine Ersetzung stattﬁnden muss:
[ A -> B || L1 _ R1 , L1 _ R1 , … , Ln _ Rn ]

Beispiel 5.4.8 (xfst und Zustandsdiagramm).

read regex [
A -> B
|| L1 _ R1 , L2 _ R2
] ;

pict

Wortende verankern in Kontexten

Die Spezialmarkierung für Wortanfang/-ende

Die Kontexte in [ A -> B || L _ R , L1 _ R2 ] sind gegen Aussen implizit mit der universalen Sprache verkettet:

[ A -> B || ?* L _ R ?* , ?* L1 _ R2 ?*]

Wie beim =>-Operator bedeutet die Spezialmarkierung .#. in den Kontexten Verankerung an der Wortgrenze und verhindert so die implizite Verkettung.

Im resultierenden ET ist .#. nicht vorhanden, es kann aber wie ein Symbol in die RA eingefügt werden.

Beispiel 5.4.9 (xfst und Zustandsdiagramm).

read regex [
A -> B || _ [ C | .#. ]
] ;

pict

Wegen der impliziten Erweiterung dürfen Kontexte auch fehlen.

Epsilon in Ersetzung

ε in Kontexten: Zwecklos

Die leere Sprache in Kontexten macht kaum Sinn:
[A -> B || 0 _ 0]
= [A -> B || ?* 0 _ 0 ?*]
= [A -> B || ?* _ ?*]
= [A -> B]

ε als Ersetzung: Wichtig und nützlich

Die leere Sprache als Ersetzung löscht die Zeichenketten der zu ersetzenden Sprache: [A -> 0]

ε als zu Ersetzendes: Überall und endlos

Die leere Sprache als zu Ersetzendes fügt an beliebiger Stelle beliebig oft das zu Ersetzende ein: [0 -> A]

Ein solcher ET besitzt ein ε-Loop auf der oberen Seite. Jeder Zeichenkette der oberen Sprache entsprechen unendlich viele Zeichenketten der unteren Sprache. (Automatisch prüfbar mit test upper-bounded in xfst.)

Einfügen als Einmal-Ersetzung (single insertion)
Das einmalige Einfügen von Zeichenketten ist wichtig und nützlich.

Gepunktete Klammern (dotted brackets)

In Ersetzungsausdrücken [ [. A .] -> B] beschränken gepunktete Klammern um das zu Ersetzende die Ersetzung von ε in A. An jeder Stelle darf es nur noch einmal ersetzt werden, d.h. B eingefügt werden.

Beispiel 5.4.10 (Einmal-Einfügen).

xfst[0]: regex [ [. 0 .] -> "+" ];
xfst[1]: apply down xyz
+x+y+z+
xfst[1]:

Beispiel 5.4.11 (Mehrfach-Einfügen).

xfst[0]: regex [ 0 -> "+" ];
xfst[1]: down xyz
Network has an epsilon loop \
on the input side.
++x+y+z
++x+y+z+
++x+yz
...

Einfügen als Einmal-Ersetzung (single insertion)

Kurznotation

Der RA [..] wird gerne als Abkürzung für [. 0 .] verwendet.

ε-speziﬁsche Wirkung

Die gepunkteten Klammern modiﬁzieren die Ersetzung nur bezüglich ε. Die Ersetzung von nicht-leeren Teilzeichenketten besteht normal weiter.

Beispiel 5.4.12 (Die Wirkung von [. .]).

pict

[ [. (A) .] -> B ]

pict

[ (A) -> B ]

Nicht-Determinismus in Ersetzung
Auch wenn in [ A -> B ] die Sprache B nur eine einzige Zeichenkette enthält, kann die Ersetzung nicht-deterministisch sein.

Ursache 1: Unterschiedliche Länge der zu ersetzenden Sprache

Der ET aus [ [ a | a a ] -> b ] bildet etwa die obere Sprache {aa} auf {b,bb} ab.

Ursache 2: Überschneidende Ersetzungen

Der ET aus [ [ a b | b c ] -> z ] bildet etwa die obere Sprache {abc} auf {zc,az} ab.

Gerichtete Ersetzungsoperatoren mit Längenpräferenz

Ursache 1 des Nicht-Determinismus eliminieren

Ersetze nur die längste (->) oder kürzeste (>) Teilzeichenkette!

Ursache 2 des Nicht-Determinismus eliminieren

Ersetze nur von links nach rechts (@…) oder von rechts nach links (…@)!

Die 4 möglichen kombinierten Strategien

	von links	von rechts

lang	A @-> B	A ->@ B

kurz	A @> B	A >@ B

Siehe [KARTTUNEN 1996] zur Implementation dieser Operatoren.

Gerichtete Ersetzungsoperatoren

Fragen

Welche untere Sprache ergibt sich für [ [ a | a a ] -> b ] für die obere Sprache {aa} mit den verschiedenen gerichteten Ersetzungsoperatoren?
Welche für [ [ a b | b c ] -> z ] mit {abc}?
Welche Konstrukte aus den regulären Suchmustern sind mit welchen gerichteten Ersetzungsoperatoren verwandt?
Wieso ist der Operator @-> für Tokenisierung und Chunking nützlich?
Inwiefern könnte eine gerichtete Ersetzungsregel bei Wörtern mit Pluralumlautung wie «Laus», «Hut» oder «Rand» nützlich sein?

Kopierendes Ersetzen (marking)
In Ersetzungsausdrücken kann ... als Variable einmal dazu verwendet werden, die zu ersetzende Zeichenkette zu referenzieren.

Deﬁnition 5.4.13 (Marking). Wenn die RA A, B und C die Sprachen A, B und C über Σ bezeichnen, dann bezeichnet [ A -> B ... C ] eine Relation.

Sie besteht aus Paaren von beliebigen Zeichenketten, welche identisch sind, ausgenommen aller Teilzeichenketten aus A in der oberen Sprache, welche gepaart sind mit einer Kopie von sich selbst, die mit einem Präﬁx aus B und einem Suﬃx aus C verkettet ist.

Beispiel 5.4.14 (Markup). [ [a|e|i|o|u] -> "[" ... "]" ] bildet «laut» ab auf «l[a][u]t».

Beispiel: Silbiﬁzierung ▸▸▸

define C [b|c|d|f|g|j|h|k|l|m|n|p|q|r|s|t|v|w|x|z];
define V [a|e|i|o|u|y|ä|ö|ü];
define Silbifizierung [ C* V+ C* @-> ... "-" || _ C V ];

apply down silbe
apply down vorsilbe
apply down leuchtplakat

Beispiel 5.4.15 (Zustandsdiagramm des ET für Silbiﬁzierung).

pict

Ersetzungsoperatorvarianten
Neben den gezeigten Ersetzungsoperatoren gibt es noch weitere systematische Varianten

Jede Ersetzung kann optional gemacht werden mit runden Klammern um Ersetzungspfeil.
Jede Variante kann beliebig viele Bedingungs-Kontexte aufnehmen.
Die Bedingungs-Kontexte können sich in beliebiger Kombination auf obere oder untere Sprache beziehen (|| vs. \\ vs. \/ vs. //)
Jede Variante kann die Ersetzung auch in der Richtung von unterer zu oberer Sprache vornehmen, indem der Pfeil umgekehrt wird (<- statt ->).
Die parallele Ersetzung erlaubt gleichzeitiges Ersetzen von Zeichenketten.

Parallele Ersetzung: Austauschen
Mehrere gleichzeitige Ersetzungen sind im Ersetzungsteil mit Komma getrennt möglich: [ A -> B , C -> D , …, X -> Y ].

Beispiel 5.4.16 (xfst und Zustandsdiagramm).

read regex [ a -> b, b -> a ] ;
apply up abba
baab
apply down abba
baab

pict

read regex [a -> b] .o. [ b -> a] ;
apply up abba

apply down abba
aaaa

pict

Zusammenspiel von Komposition und Ersetzung

Beispiel 5.4.17 (Der ﬁktionale Klassiker: kaNpat).

Das abstrakte und unterspeziﬁzierte Morphophonem N wird an Morphemgrenzen vor p als m realisiert.
[ N -> m || _ p ]
Ein p, das einem m nachfolgt, wird als m realisiert:
[ p -> m || m _ ]
Beachte: Jede Ersetzungsregel bildet aus Sprachen eine Sprach-Relation!
Obige Regeln werden nacheinander als Regelkaskade angewendet: Aus kaNpat wird zunächst kampat und daraus kammat.
Die Regelkaskade lässt sich durch Komposition in einen einzigen Transduktor verwandeln.

Regelkaskade als ein ET

XFST-Skript ▸▸▸

define Rule1 [ N -> m || _ p ] ;

define Rule2 [ p -> m || m _ ] ;

read regex Rule1 .o. Rule2 ;

apply down kaNpat

apply up kammat

pict

Abbildung 5.4:

ET aus den kaNpat-Regeln

5.4.4. Inversion

Deﬁnition 5.4.18 (Inversion von Relationen). Wenn R eine Relation darstellt, dann bezeichnet [ [ R ].i ] die Relation, bei der die obere und untere Sprache vertauscht sind.

Für alle Relationen R gilt: R = R.i.i.

Konstruktion eines inversen ET

Um aus einem ET einen neuen ET zu konstruieren, der die inverse Relation erkennt, müssen nur alle Symbole in den Symbolpaaren ausgetauscht werden.

5.4.5. Projektion

Obere und untere Projektion

Deﬁnition 5.4.19 (Projektion von Relationen auf Sprachen). Wenn R eine Relation darstellt, dann bezeichnet [ [ R ].u ] deren obere Sprache und [ [ R ].l ] deren untere Sprache.

Während das Kreuzprodukt Sprachen zu Relationen verknüpft, reduziert die Projektion Relationen zu Sprachen.

[ Weiter ] [ Zurück ] [ Zurück (Seitenende) ] [ Seitenbeginn ] [ Überkapitel ] [ Bitte Skript-Fehler melden ]