Myhillova–Nerodova věta: Porovnání verzí
Smazaný obsah Přidaný obsah
m +Portál Matematika |
|||
Řádek 21:
=== Neformální popis Nerodovy věty ===
Dva prvky jsou v pravé kongruenci, pokud, přilepíme-li k oběma libovolné (stejné) slovo, výsledná slova budou také vzájemně kongruentní. Kongruence je konečného indexu, pokud existuje konečně mnoho skupin, do kterých můžeme různá slova dle kongruencí roztřídit.
'' Mějme abecedu ''X = {a, b}''. Mějme množinu všech slov ''X* = {a, b}*''. Definujme si relaci ''~'', která rozdělí ''X*'' do těchto pěti skupin:
* Prázdné slovo ''{λ}''
* Slova ''{a, b}''
* Slova ''{ab, bb}''
* Slova ''{aba, bba}''
* Všechna ostatní slova ''{ba, aa, baba, abbbabbb, ...}''
Pokud vezmeme dvě libovolná slova ze stejné třídy a cokoli k nim připojíme, dvě výsledná slova opět patří do společné třídy. Příklad: ''a ~ b'' jsou z druhé třídy, připojme k nim ''baba'', pak ''ababa ~ bbaba'' - patří do páté třídy.
Relace ''~'' je tedy pravá kongruence (to byl účel). Podobných pravých kongruencí na ''X*'' existuje spousta a s trochou šikovnosti si můžeme nalézt tu, kterou zrovna potřebujeme.
Z existence této pravé kongruence ''~'' plyne, že každá z pěti skupin je regulární jazyk, navíc sjednocení dvou i více skupin je regulární jazyk.
(''{a, b}'' je RJ, ''{aba, bba}'' je RJ, ''{a, b, ab, bb}'' je RJ, ''{λ}'' je RJ, ''X*'' je RJ, ...)
Obvykle se jako kongruence bere rovnost stavů v konečném automatu (<math>u\sim v</math>, když slova ''u'' a ''v'' odpovídající konečný automat uvedou do stejného stavu).
| |||