Nerode relation

The Nerode relation (also: Nerode congruence or Nerode legal congruence ) is an equivalence relation on the prefixes of a formal language that is examined in theoretical computer science .

It is named after Anil Nerode .

definition

Given a language above the alphabet . The Nerode relation (also if it becomes clear from the context) is defined by: ${\displaystyle L}$ ${\displaystyle \Sigma }$ ${\displaystyle \sim _{L}}$ ${\displaystyle \sim }$ ${\displaystyle L}$

With regard to the Nerode relation, two words are equivalent to one another if and only if they are both supplemented by exactly the same suffixes to words of the language . ${\displaystyle L}$

Colloquially: two words are then rel. the Nerode relation equivalent to each other if they “behave the same way” to arbitrary suffixes to words , d. i.e., both words are in the language or not. ${\displaystyle z\in \Sigma ^{*}}$

So formally applies to all : ${\displaystyle x,y\in \Sigma ^{*}}$

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

Equivalence class

The equivalence class of a with respect to the Nerode relation is defined as the set of all words which are equivalent to with respect to the Nerode relation . The following applies: ${\displaystyle [x]}$ ${\displaystyle x\in \Sigma ^{*}}$ ${\displaystyle y\in \Sigma ^{*}}$ ${\displaystyle x}$

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

index

The index of a Nerode relation is the number of existing equivalence classes.

example

The language defined by the regular expression is given above the alphabet . This language induces exactly three equivalence classes: ${\displaystyle 0^{\star }1^{\star }}$ ${\displaystyle \{0,1\}}$

• ${\displaystyle [0]}$, contains all prefixes that consist of sequences of zeros or the empty word (i.e. ). ${\displaystyle \epsilon }$ ${\displaystyle \{0\}^{*}}$
• ${\displaystyle [1]}$, consists of words that start with 0s or and end with 1s (i.e. ) ${\displaystyle \epsilon }$ ${\displaystyle \{0\}^{*}\{1\}^{+}}$
• ${\displaystyle [10]}$which consists of all illegal prefixes ; these are all words that contain 10 (so ). ${\displaystyle \{0,1\}^{*}\{10\}\{0,1\}^{*}}$

Further examples can be found in the article on the Myhill-Nerode theorem .

application

The Nerode relation forms the starting point for the Myhill-Nerode theorem, which can be used to determine whether a language is regular or not. The theorem says that a language is regular if and only if there are finitely many equivalence classes with respect to the Nerode relation.

The relation is also used to construct a minimal deterministic finite automaton for a given regular language , i.e. an automaton that has as few states as possible. The automaton constructed in this way contains exactly states. States can arise that cannot be reached from the start state; after this has been removed, the automaton actually has the minimum number of states. ${\displaystyle L}$ ${\displaystyle \operatorname {ind} (\sim _{L})}$

Individual evidence

1. ↑ Uwe Schöning : Theoretical Computer Science - in brief . 5th edition. Spektrum Akademischer Verlag, Heidelberg 2008, ISBN 978-3-8274-1824-1 , p. 34 .