5.3.  Reguläre Relationen

5.3.1.  Konkatenation und Stern

Konkatenation von Sprach-Relationen

Definition 5.3.1. Die Konkatenation von Relationen erweitert die Verkettung auf Mengen von Paaren von Zeichenketten. Für alle R,S ⊆ Σ^∗× Σ^∗:

Stern einer Relation

Die Konkatenation von Relationen mit sich selbst erweitert sich wie bei den Sprachen zum Stern einer Relation.

5.3.2.  Rekursive Definition

Reguläre binäre Relationen

• Die leere Menge ∅ ist regulär .
• Wenn 〈x,y〉∈ Σ_ε × Σ_ε, dann ist die Menge {〈x,y〉} regulär.
• Wenn R₁ und R₂ regulär sind, dann auch (R₁ ∪ R₂).
• Wenn R₁ und R₂ regulär sind, dann auch (R₁ ∙ R₂).
• Ist R regulär, dann auch R^∗.

Abschlusseigenschaften regulärer Relationen

• Über der Menge der regulären Relationen sind die Operationen R₁ ∙ R₂, R^∗ und R₁ ∪ R₂ per Definition abgeschlossen.
• Der Abschluss bezüglich der Operationen R⁺, R₁ ∘ R₂ (Komposition), R⁻¹ (Inversion) lässt sich beweisen.
• Der Abschluss bezüglich der Operationen R₁ ∩ R₂, R₁ ∖ L₂ und Komplementmenge L ist nicht gegeben.

Abschlusseigenschaften längengleicher regulärer Relationen

Reguläre Relationen, bei denen alle Paare von Zeichenketten gleich lang sind, sind abgeschlossen unter R₁ ∩ R₂ und R₁ ∖ R₂. Hinweis: Bei der Zwei-Ebenen-Morphologie mit Zwei-Ebenen-Regeln wird dies ausgenützt, indem das ε als ein Spezialsymbol verrechnet wird.

Reguläre Relationen und ET
Die Menge der regulären Relationen ist gleich der Menge der von ET akzeptierten Sprachen-Relationen.