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 ${\displaystyle L}$ über dem Alphabet ${\displaystyle \Sigma }$. Die Nerode-Relation ${\displaystyle \sim _{L}}$ (auch ${\displaystyle \sim }$, falls ${\displaystyle 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 ${\displaystyle L}$ ergänzt werden.

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

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

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

Äquivalenzklasse

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

${\displaystyle [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 ${\displaystyle 0^{\star }1^{\star }}$ definierte Sprache über dem Alphabet ${\displaystyle \{0,1\}}$. Diese Sprache induziert genau drei Äquivalenzklassen:

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

Die Relation wird außerdem verwendet, um zu einer gegebenen regulären Sprache ${\displaystyle 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 ${\displaystyle \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.

Einzelnachweise

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