Nerode equivalence
Nerode equivalence An equivalence relation, =N, arising in formal language theory. It is defined analogously to the Myhill equivalence by the weaker properties:
for a language L over Σ, u =N u′
if, for all w in Σ*, uw ∈ L iff u′w ∈ L
and for a function f, u =N u′
if, for all w in Σ*, f(uw) = f(u′w)
Although coarser than the Myhill equivalence, it is finite only if the latter is. Unlike the latter, it gives only a right congruence: u =N u′ implies uv =N u′v
and thus does not give rise to a semigroup. The number of equivalence classes is the number of states in the minimal machine for L.
for a language L over Σ, u =N u′
if, for all w in Σ*, uw ∈ L iff u′w ∈ L
and for a function f, u =N u′
if, for all w in Σ*, f(uw) = f(u′w)
Although coarser than the Myhill equivalence, it is finite only if the latter is. Unlike the latter, it gives only a right congruence: u =N u′ implies uv =N u′v
and thus does not give rise to a semigroup. The number of equivalence classes is the number of states in the minimal machine for L.
More From encyclopedia.com
Insoluble , in·sol·u·ble / inˈsälyəbəl/ • adj. 1. impossible to solve: the problem is not insoluble. 2. (of a substance) incapable of being dissolved: once dry,… U , U, u [Called ‘you’]. The 21st LETTER of the Roman ALPHABET as used for English. It originated in the Phoenician consonant symbol waw, the common ance… exiguous , exiguous •Ananias, bias, Darius, dryas, Elias, eyas, Gaius, hamadryas, Lias, Mathias, pious, Tobias •joyous • Shavuoth • tempestuous •spirituous • to… Confabulate , confabulate •circumvallate • bedplate • template •breastplate • nameplate • faceplate •chelate • fishplate • sibilate • jubilate •flagellate • legisl… unanimous , unanimous •Lammas • Cadmus • Las Palmas •chiasmus, Erasmus •Nostradamus •famous, ignoramus, Seamus, shamus •Polyphemus, Remus •grimace • Michaelmas •… stipulate , stipulate •circumvallate • bedplate • template •breastplate • nameplate • faceplate •chelate • fishplate • sibilate • jubilate •flagellate • legislat…
You Might Also Like
NEARBY TERMS
Nerode equivalence