https://croatianschoolsydney.com/index.php?action=history&feed=atom&title=Myhill-Nerode_teorem 2026-05-25T01:54:04Z Povijest promjena ove stranice na wikiju MediaWiki 1.36.2 https://croatianschoolsydney.com/index.php?title=Myhill-Nerode_teorem&diff=39417&oldid=prev 2021-08-20T01:54:05Z

<p>Bot: Automatski unos stranica</p> <p><b>Nova stranica</b></p><div>&lt;!--'''Myhill-Nerode teorem'''--&gt;U teoriji [[formalni jezik|formalnih jezika]], '''Myhill-Nerode teorem''' pruža nužne i dovoljne uvjete da bi jezik bio [[regularni jezik|regularan]]. Gotovo se isključivo koristi prilikom dokazivanja neregularnosti nekog danog jezika.<br /> <br /> Teorem je imenovan po Johnu Myhillu i Anil Nerode, koji su ga dokazali na čikaškom sveučilištu 1958.<br /> <br /> == Iskaz teorema ==<br /> <br /> Za dani jezik ''L'' definirajmo relaciju ''R&lt;sub&gt;L&lt;/sub&gt;'' nad nizovima znakova pravilom ''x R&lt;sub&gt;L&lt;/sub&gt; y'' ako ne postoji '''istaknuta ekstenzija''' ''z'' sa sa svojstvom da točno jedan od nizova znakova ''xz'' i ''yz'' jest element skupa ''L''. Lako se pokazuje da je ''R&lt;sub&gt;L&lt;/sub&gt;'' relacija ekvivalencije nad nizovima znakova, te stoga dijeli skup svih konačnih nizova znakova u jednu ili više klasa ekvivalencije.<br /> <br /> Myhill-Nerode teorem kaže da je broj stanja u najmanjem [[Teorija automata|automatu]] koji prihvaća ''L'' jednak broju klasa ekvivalencije u ''R&lt;sub&gt;L&lt;/sub&gt;''. Intuicija koja leži iza ovog iskaza jest ta da, ukoliko započnemo sa takvim minimalnim automatom, tada bilo koji nizovi znakova ''x'' i ''y'' koji ga vode u isto stanje će biti u istoj klasi ekvivalencije; te ako započnemo sa particijom u klase ekvivalencije, lako možemo konstruirati automat koji koristi svoje stanje u svrhu praćenja klase ekvivalencije koja sadrži dio niza znakova koji je dotad pročitan.<br /> <br /> == Uporaba i posljedice ==<br /> <br /> Posljedica Myhill-Nerode teorema jest da jezik ''L'' je regularan (tj. prihvaća ga [[konačni automat]]) ako i samo ako je broj klasa ekvivalencije ''R&lt;sub&gt;L&lt;/sub&gt;'' konačan.<br /> <br /> Direktan korolar koji slijedi jest da, ukoliko jezik definira beskonačan skup klasa ekvivalencije, tada on ''nije'' regularan. Baš ovaj korolar se često koristi prilikom dokaza neregularnosti jezika.<br /> <br /> Na primjer, jezik koji se sastoji od binarnih brojeva djeljivih sa 3 je regularan. Postoje 3 klase ekvivalencije - brojevi koji daju ostatke 0, 1 i 2 pri dijeljenju sa 3. Minimalni automat koji prihvaća ovaj jezik bi imao tri stanja koja korespondiraju klasama ekvivalencije.<br /> <br /> == Vanjske poveznice ==<br /> <br /> *[http://www-cad.eecs.berkeley.edu/~tah/172/7.pdf Detaljnije objašnjenje Myhill–Nerode teorema] [pdf]<br /> [[Kategorija:Formalni jezici]]</div>

WikiSysop