 Home

Codex Wiki

Mathematics

Area of mathematics

Foundations of mathematics

Formal language theory

Myhill-Nerode theorem

{c}

= Myhill-Nerode equivalent
{c}
{synonym}

For a language $A\subseteq\Sigma^*$, define
$$
v\sim_Aw
\quad\Longleftrightarrow\quad
\forall u\in\Sigma^*,\
vu\in A\Longleftrightarrow wu\in A.
$$
This is a right congruence, and its equivalence classes are the states of the minimal <deterministic finite automaton> for $A$.

Myhill-Nerode equivalence

Past exam of the mathematics course of the University of Cambridge / 2014 / iii / Paper 21 / 2 / i / Solution

Past exam of the mathematics course of the University of Cambridge / 2021 / iii / Paper 120 / 1 / Solution

Past exam of the mathematics course of the University of Cambridge / 2023 / ii / Paper 3 / 12I / iii / Solution

codex/myhill-nerode-equivalent

Myhill-Nerode equivalence

 Ancestors (6)

 Incoming links (3)

 Synonyms (1)

 Discussion (0)

 Articles by others on the same topic (0)

Myhill-Nerode equivalence

 Ancestors (6)

 Incoming links (3)

 Synonyms (1)

 Discussion (0)  Subscribe (1)

 Articles by others on the same topic (0)

 Discussion (0)