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.

Gegeben sei eine Sprache ${\displaystyle L}${\displaystyle L} über dem Alphabet ${\displaystyle \Sigma }${\displaystyle \Sigma }. Die Nerode-Relation ${\displaystyle \sim _{L}}${\displaystyle \sim _{L}} (auch ${\displaystyle \sim }${\displaystyle \sim }, falls ${\displaystyle L}${\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}${\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 ^{*}}${\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,y\in \Sigma ^{*}}:

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

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

${\displaystyle [x]=\{y\in \Sigma ^{*}\mid x\sim _{L}y\}}${\displaystyle [x]=\{y\in \Sigma ^{*}\mid x\sim _{L}y\}}

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

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

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

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

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}${\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})}${\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.

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

• Theorie formaler Sprachen