Myhill-Nerodova věta

  • Pokud je jazyk regulární, platí MNv

  • Pokud platí MNv, 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 a jistými ekvivalenčními relacemi nad řetězci

  • 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

  • Binární relace
  • Reflexivní, symetrická, tranzitivní

Formálně

Platí 3 ekvivalentní tvrzení:

  1. je jazyk přijímaný DKA
  2. je sjednocením některých tříd rozkladu určeného pravou kongruencí na s konečným indexem
  3. Relace má konečný index (prefixová ekvivalence)

Vytvořeno: 7. 8. 2024, 13:25
Poslední aktualizace: 7. 8. 2024, 13:25