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 $\Sigma$. 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 \Sigma ^{*}$ „gleich verhalten“, d. h., beide Worte sind in der Sprache oder nicht.

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

$x\sim _{L}y\iff (\forall z\in \Sigma ^{*}:\ xz\in L\iff yz\in L)$

Äquivalenzklasse

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

$[x]=\{y\in \Sigma ^{*}\mid 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^{\star }1^{\star }$ 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 $\epsilon$ bestehen (also $\{0\}^{*}$).
• $[1]$, besteht aus Wörtern, die mit 0en oder $\epsilon$ 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 $\operatorname {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.