2.6 Myhillova-Nerodova věta
Pravá kongruence
Nechť \(\Sigma\) je abeceda a \(\sim\) je relace ekvivalence (tj. reflexivní, symetrická a tranzitivní) na \(\Sigma^*\). Řekneme, že \(\sim\) je pravá kongruence, jestliže navíc platí:
\[
\forall u, v, w \in \Sigma^* : u \sim v \implies uw \sim vw
\]
Konečný index
Pravá kongruence \(\sim\) je konečného indexu, má-li rozklad \(\Sigma^* / \sim\) konečně mnoho tříd.
Definice (Prefixová ekvivalence)
Prefixová ekvivalence
Nechť \(L\) je libovolný jazyk nad abecedou \(\Sigma\). Prefixovou ekvivalenci \(\sim_L\) na \(\Sigma^*\) pro jazyk \(L\) definujeme následovně:
\[
u \sim_L v \iff (\forall w \in \Sigma^* : uw \in L \iff vw \in L)
\]
Věta 2.1 (Myhillova-Nerodova věta)
Myhillova-Nerodova věta
Myhillova-Nerodova věta je vlastnost regulárních jazyků. Pro regulární jazyk \(L\) nad abecedou \(\Sigma\) nám tato věta říká, že následující tři tvrzení jsou ekvivalentní:
- \(L\) je jazyk přijímaný deterministickým konečným automatem.
- Pro \(L\) existuje pravá kongruence \(\sim\) konečného indexu na \(\Sigma^*\) taková, že \(L\) je sjednocením některých jejích tříd rozkladu \(\Sigma^* / \sim\).
- Relace prefixové ekvivalence \(\sim_L\) má konečný index.