b'\n_START_ARTICLE_\nTwierdzenie Myhilla-Nerode\xe2\x80\x99a\n_START_PARAGRAPH_\nTwierdzenie Myhilla-Nerode\xe2\x80\x99a \xe2\x80\x93 twierdzenie w teorii j\xc4\x99zyk\xc3\xb3w formalnych podaj\xc4\x85ce konieczne i dostateczne warunki na to, by dany j\xc4\x99zyk by\xc5\x82 regularny. Zosta\xc5\x82o udowodnione w 1958 roku przez Johna Myhilla i Anila Nerode\xe2\x80\x99a.\n_START_SECTION_\nTwierdzenie\n_START_PARAGRAPH_\nNiech  b\xc4\x99dzie j\xc4\x99zykiem nad alfabetem . Zdefiniujmy relacj\xc4\x99 sufiksowej nieodr\xc3\xb3\xc5\xbcnialno\xc5\x9bci  nast\xc4\x99puj\xc4\x85co:  wtedy i tylko wtedy, gdy dla ka\xc5\xbcdego s\xc5\x82owa u  wtedy i tylko wtedy, gdy ._NEWLINE_Twierdzenie Myhilla-Nerode\xe2\x80\x99a orzeka, \xc5\xbce j\xc4\x99zyk L jest regularny wtedy i tylko wtedy, gdy relacja  dzieli  na sko\xc5\x84czenie wiele klas abstrakcji. Dodatkowo, je\xc5\x9bli L jest regularny, to liczba stan\xc3\xb3w minimalnego deterministycznego automatu sko\xc5\x84czonego rozpoznaj\xc4\x85cego L jest r\xc3\xb3wna liczbie klas abstrakcji relacji ._NEWLINE_Nieformalnie, je\xc5\x9bli j\xc4\x99zyk L jest regularny, to klasy abstrakcji relacji  odpowiadaj\xc4\x85 stanom automatu sko\xc5\x84czonego rozpoznaj\xc4\x85cego L. Innymi s\xc5\x82owy  \xe2\x80\x9eskleja\xe2\x80\x9d ze sob\xc4\x85 s\xc5\x82owa, kt\xc3\xb3rych \xe2\x80\x9eprzysz\xc5\x82o\xc5\x9bci\xe2\x80\x9d z punktu widzenia zachowania automatu s\xc4\x85 identyczne. Intuicyjnie, je\xc5\x9bli klas abstrakcji jest niesko\xc5\x84czenie wiele, to automat rozpoznaj\xc4\x85cy L musia\xc5\x82by mie\xc4\x87 niesko\xc5\x84czenie wiele stan\xc3\xb3w, co jest niemo\xc5\xbcliwe.'