6.1.  Formale Relationen

Geordnete Paare 

Definition 6.1.1 (Geordnetes Paar). Ein geordnetes Paar besteht aus einer ersten und einer zweiten Komponente (Koordinate). Diese werden zwischen spitzen Klammern notiert: a,b. Oft aber auch in runden: (a,b).

Definition 6.1.2 (Gleichheit von geordneten Paaren). Zwei geordnete Paare sind gleich , wenn sie in ihren beiden Komponenten gleich sind. Formal: a,b= c,d= df.a = c b = d

Beispiel 6.1.3 (Unterschied von geordneten Paaren und Zweier-Mengen).
Sei a = b. Dann gilt {a,b} = {b,a}, aber b,a= a,bgilt nicht.

Kreuzprodukt 

Definition 6.1.4 (Produktmenge, kartesisches Produkt). Ein Kreuzprodukt zweier Mengen besteht aus der Menge der geordneten Paare, welche sich aus deren Elementen kombinieren.

M  × N  = { 〈x,y 〉 | x ∈ M ∧y ∈ N }

Beispiel 6.1.5 (Kreuzprodukt).
Sei A = {a,b,c} und B = {1,2}:

A × B = {〈a,1,a,2,b,1,b,2,c,1,c,2〉}

B × B = {〈1,1,1,2,2,1,2,2〉}

pict

Frage

Welche Menge ergibt sich, wenn B = ?

Formale Sprach-Relationen 

Definition 6.1.6. Eine formale Sprach-Relation ist eine Teilmenge des kartesischen Produktes des Sterns von Sigma

R ⊆ Σ ∗ × Σ ∗
Eine Sprach-Relation ist also eine Menge von Paaren von Zeichenketten.

Beispiel 6.1.7. Sei Σ = {a,b,c,A,B,C}.
Dann ist beispielsweise R = {〈aa,AA,ab,AB,cc,CC〉} eine formale Sprach-Relation über Σ.

Frage

Wie sieht ein Automat aus, der beliebige kleingeschreibene Wörter kapitalisiert?

6.1.1.  Sprach-Ebenen

Obere vs. untere Sprache 

Relation ⊆ UP P ER × LOW   ER

Definition 6.1.8 (Obere Sprache,upper language). Die obere Sprache umfasst alle Zeichenketten aus der 1. Komponente des kartesischen Produkts.

Sie enthält bei lexikalischen Transduktoren traditionell die abstrakte lexikalisch-morphologische Seite (lexical language).

Definition 6.1.9 (Untere Sprache, lower language)). Die untere Sprache umfasst alle Zeichenketten aus der 2. Komponente des kartesischen Produkts.

Sie enthält bei lexikalischen Transduktoren traditionell die Wortform .

Beispiel 6.1.10 (Obere und untere Sprache im Spanischen).
cantar+Verb+PresInd+1P+Sg , canto〉∈ Rspanisch

Hinweis

Bei andern Ansätzen zur Morphologie mit endlichen Automaten wie [ANTWORTH 1990] bezeichnet man die Ebene der Wortformen mit surface form. Dies entspricht aber in XFST-Sprechweise der lower language!

6.1.2.  Identitätsrelation

Identitätsrelation einer Sprache 
Sie ist eine technisch wichtige, inhaltlich aber uninteressante Relation und macht Sprachen zu Relationen, ohne an der Menge der erkannten Zeichenketten etwas zu ändern.
Obere und untere Sprache der Relation sind identisch mit der zugrundeliegenden Sprache.

Definition 6.1.11 (Identitätsrelation). Eine Identitätsrelation ID einer Sprache L über dem Alphabet Σ paart jede Zeichenkette der Sprache L nur mit sich selbst:
Für L Σ:

                  ∗    ∗
IDL  = {〈w,w 〉 ∈ Σ × Σ  | w ∈ L }

Beispiel 6.1.12 (Identitätsrelation). Sei L = {canto,cantamos}.
Dann ist IDL = {〈canto,canto,cantamos,cantamos〉}.