Matematické Fórum

V tom priklade na wikipedii, to je jenom priklad, X* si praveze mozes rozdelit do kolko skupin chces pokial plati ta podmienka, ze ked pridas pismeno ku vsetkym slovam v skupine, tak skoncia vsetky v spolocnej skupine. A to rozdelenie bude stale ine, podla toho co chces dosiahnut a aky jazyk chces prijmat a aky automat chces postavit. Skutocne triedy ekvivalencie zodpovedaju stavom DKA, pretoze vsetky slova v jednej triede ekvivalencie, skoncia v tom istom stave. Zaroven ked k nim pridas zprava jedno pismeno, tak sa dostanes do dalsieho stavu v automate a do dalsej triedy ekvivalencie. No neviem, ci som to pomohol objasnit :)

↑ guri:
Hm tak to me trochu zmatlo, to co sem popisoval nebyla prefixova ekvivalence ale prava kongruence. A ta skutocne odpoveda stavom akehokolvek automatu, ne jenom minimalniho. A Nerodova veta prave rika, ze je mozno prevadet DKA na pravou kongruenci s konecnim poctom trid a nazpatek. Myhill-Nerodova veta navic rika ze existuje relace prefixove ekvivalence, ktorej tridy zodpovedaji minimalnimu DKA prijmajiciho ten jazyk a skutocne zavisi jenom na tom jazyku L a pomoci ni dokazes udelat minimalni DKA pro ten jazyk. A v tom clanku na wiki, taky popisuji pravou kongruenci a o prefixovej ekvivalenci tam je jenom zminka. Ked som to googlil, tak som nasiel nejake skripta
http://foja.dcs.fmph.uniba.sk/materialy/skripta.pdf
str.25 tam to je celkom dobre popsane.