Quelltext der Seite Nerode-Relation

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

Sie ist nach [[Anil Nerode]] benannt.

== Definition ==
Gegeben sei eine [[Formale Sprache|Sprache]] <math>L</math> über dem [[Alphabet (Informatik)|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 [[Suffix (Theoretische Informatik)|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.&nbsp;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 [[Äquivalenzrelation#Äquivalenzklassen|Index]] einer Nerode-Relation ist die Anzahl der vorhandenen Äquivalenzklassen.

=== Beispiel ===
Gegeben sei die durch den [[Regulärer Ausdruck|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>{{Literatur |Autor=[[Uwe Schöning]] |Titel=Theoretische Informatik – kurz gefasst |Auflage=5. |Verlag=Spektrum Akademischer Verlag |Ort=Heidelberg |Datum=2008 |ISBN=978-3-8274-1824-1 |Seiten=34}}</ref>

Die Relation wird außerdem verwendet, um zu einer gegebenen regulären Sprache <math>L</math> einen minimalen [[Deterministischer endlicher Automat|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 ==
<references />

[[Kategorie:Theorie formaler Sprachen]]