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 <math>L</math> über dem Alphabet <math>\Sigma</math>. Die Nerode-Relation <math>\sim_L</math> (auch <math>\sim</math>, falls <math>L</math> 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 <math>L</math> ergänzt werden.

Umgangssprachlich: zwei Worte sind genau dann bez. der Nerode-Relation äquivalent zueinander, wenn sie sich auf beliebige Suffixe zu Worten <math>z \in \Sigma^*</math> „gleich verhalten“, d. h., beide Worte sind in der Sprache oder nicht.

Formal gilt also für alle <math>x, y \in \Sigma^*</math>:

<math>x \sim_L y \iff (\forall z \in \Sigma^*: \ xz \in L \iff yz \in L)</math>

Äquivalenzklasse

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

<math>[x] = \{ y \in \Sigma^* \mid x \sim_L y \}</math>

Index

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

Beispiel

Gegeben sei die durch den regulären Ausdruck <math>0^\star 1^\star</math> definierte Sprache über dem Alphabet <math>\{0,1\}</math>. Diese Sprache induziert genau drei Äquivalenzklassen:

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

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.<ref>{{#invoke:Vorlage:Literatur|f}}</ref>

Die Relation wird außerdem verwendet, um zu einer gegebenen regulären Sprache <math>L</math> einen minimalen deterministischen endlichen Automaten zu konstruieren, also einen Automaten, der möglichst wenige Zustände besitzt. Der so konstruierte Automat enthält exakt <math>\operatorname{ind}(\sim_L)</math> 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