Nerode-Relation

Die Nerode-Relation (auch: Nerode-Kongruenz oder Nerode-Rechtskongruenz) ist eine Äquivalenzrelation auf den Präfixen einer formalen Sprache, die in der Theoretischen Informatik untersucht wird.

Sie ist nach Anil Nerode benannt.

Definition

Gegeben sei eine Sprache $L$ über dem Alphabet $Σ$ . Die Nerode-Relation $\sim_{L}$ (auch $\sim$ , falls $L$ aus dem Kontext klar wird) ist definiert durch:

Zwei Wörter sind bezüglich der Nerode-Relation genau dann äquivalent zueinander, wenn sie beide durch exakt dieselben Suffixe zu Wörtern der Sprache

L

ergänzt werden.

Umgangssprachlich: zwei Worte sind genau dann bez. der Nerode-Relation äquivalent zueinander, wenn sie sich auf beliebige Suffixe zu Worten

z \in Σ^{*}

„gleich verhalten“, d. h., beide Worte sind in der Sprache oder nicht.

Formal gilt also für alle $x, y \in Σ^{*}$ :

x \sim_{L} y ⟺ (\forall z \in Σ^{*} : x z \in L ⟺ y z \in L)

Äquivalenzklasse

Die Äquivalenzklasse $[x]$ eines $x \in Σ^{*}$ bezüglich der Nerode-Relation ist definiert als Menge aller Wörter $y \in Σ^{*}$ , die bezüglich der Nerode-Relation äquivalent zu $x$ sind. Es gilt also:

[x] = {y \in Σ^{*} ∣ x \sim_{L} y}

Index

Der Index einer Nerode-Relation ist die Anzahl der vorhandenen Äquivalenzklassen.

Beispiel

Gegeben sei die durch den regulären Ausdruck $0^{⋆} 1^{⋆}$ definierte Sprache über dem Alphabet ${0, 1}$ . Diese Sprache induziert genau drei Äquivalenzklassen:

$[0]$ , enthält alle Präfixe, welche aus Folgen von Nullen oder dem leeren Wort $ϵ$ bestehen (also ${0}^{*}$ ).
$[1]$ , besteht aus Wörtern, die mit 0en oder $ϵ$ beginnen und mit 1en enden (also ${0}^{*} {1}^{+}$ )
$[10]$ , welche aus allen illegalen Präfixen besteht; das sind alle Wörter, die 10 enthalten (also ${0, 1}^{*} {10} {0, 1}^{*}$ ).

Weitere Beispiele finden sich in dem Artikel über den Satz von Myhill-Nerode.

Anwendung

Die Nerode-Relation bildet den Ausgangspunkt für den Satz von Myhill-Nerode, mit dem sich bestimmen lässt, ob eine Sprache regulär ist oder nicht. Der Satz besagt, dass eine Sprache genau dann regulär ist, wenn es endlich viele Äquivalenzklassen bezüglich der Nerode-Relation gibt.

Die Relation wird außerdem verwendet, um zu einer gegebenen regulären Sprache $L$ einen minimalen deterministischen endlichen Automaten zu konstruieren, also einen Automaten, der möglichst wenige Zustände besitzt. Der so konstruierte Automat enthält exakt $ind (\sim_{L})$ Zustände. Dabei können Zustände auftreten, die vom Startzustand aus unerreichbar sind; nach Entfernung dieser hat der Automat tatsächlich die minimale Anzahl an Zuständen.

Einzelnachweise

↑ Uwe Schöning: Theoretische Informatik – kurz gefasst. 5. Auflage. Spektrum Akademischer Verlag, Heidelberg 2008, ISBN 978-3-8274-1824-1, S. 34.

[1] Uwe Schöning: Theoretische Informatik – kurz gefasst. 5. Auflage. Spektrum Akademischer Verlag, Heidelberg 2008, ISBN 978-3-8274-1824-1, S. 34.