06.4 Myhill-Nerodova věta
$$
\require{mathtools}
\DeclarePairedDelimiter\ceil{\lceil}{\rceil}
\DeclarePairedDelimiter\floor{\lfloor}{\rfloor}
\newcommand{\dv}[1]{\frac{\mathrm{d}}{\mathrm{d} #1}}
\newcommand{\dvv}[2]{\frac{\mathrm{d} #1}{\mathrm{d} #2}}
$$
# Myhill-Nerodova věta
Pokud je jazyk regulární, platí MHv
Pokud platí MHv, je jazyk regulární
Popisuje přesně a právě vlastnost RJ
MNv charakterizuje některé zásadní vztahy mezi konečnými automaty nad abecedou $\Sigma$ a jistými ekvivalenčními relacemi nad řetězci $\Sigma^{*}$
Popisuje některé nutné a postačující podmínky pro regularitu (používá se pro důkaz neregularity)
Poskytuje formální bázi pro důkaz existence unikátního minimálního DKA k danému regulárnímu jazyku
# Ekvivalence $\sim$
- Binární relace
- Reflexivní, symetrická, tranzitivní
- #todo přehodit na vlastní note 06.3 Ekvivalence
# Formálně
Platí 3 ekvivalentní tvrzení:
- $L$ je jazyk přijímaný DKA
- $L$ je sjednocením některých tříd rozkladu určeného pravou kongruencí na $\Sigma^{*}$ s konečným indexem
- Relace $\sim_{L}$ má konečný index (prefixová ekvivalence)