Myhillova-Nerodova věta

Nerodova věta popisuje regulární jazyky, když říká, že formální jazyk nad konečnou abecedou je regulární, právě když „dělí“ množinu všech slov nad danou abecedou na konečně mnoho podtříd. Myhill-Nerodova věta je rozšířením Nerodovy věty o část týkající-se prefixové ekvivalence.

[editovat] Přesná formulace

Nechť X je konečná abeceda a ~ je relace ekvivalence na $X *$ (množině všech slov nad X). Potom ~ je pravá kongruence, jestliže

$\forall u,v,w \in X^*: u\sim v \Rightarrow uw\sim vw$

a kongruence ~ je konečného indexu, má-li rozklad $X^*/\sim$ konečně mnoho tříd (množin prvků, které jsou vzájemně kongruentní). Pak Nerodova věta samotná říká, že máme-li jazyk L nad konečnou abecedou X, jsou následující dvě tvrzení ekvivalentní:

L je rozpoznatelný konečným automatem (tedy jde o regulární jazyk))

Existuje pravá kongruence ~ konečného indexu na $X *$ taková, že L je sjednocením vybraných tříd rozkladu $X^*/\sim$

Myhill-Nerodova věta přidává k předchozím ekvivalentním tvrzením další:

Relace prefixové ekvivalence má konečný index

[editovat] 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. Např. jazyk obsahující slova {aba, bba} rozděluje kongruence na 5 tříd:

e přiřetězíme buď aba nebo bba
a, b jsou kongruentní - přidáním slova ba se lze dostat k cílovému slovu, v jiném případě do některé z následujících tříd
ab, bb jsou kongruentní - přidáním slova a se lze dostat k cílovému slovu, v jiném případě mimo jazyk
aba, bba jsou kongruentní - jsou to cílová slova a přidáním jakéhokoliv neprázdného slova se nevyhnutelně ocitneme mimo jazyk
všechny ostatní slova jsou vzájemně kongruentní - přidáním jakéhokoliv dalšího slova již tuto třídu nelze opustit

Obvykle se jako kongruence bere rovnost stavů v konečném automatu ( $u\sim v$ , když slova u a v odpovídající konečný automat uvedou do stejného stavu).

Tento matematický článek je příliš stručný nebo neobsahuje důležité informace.
Pomozte Wikipedii tím, že jej vhodně rozšíříte.

Myhillova-Nerodova věta v jiných jazycích: Deutsch, English, עברית, Hrvatski, Italiano, 日本語, 中文

Tento článek je převzat z české wikipedie - otevřené encyklopedie, originální článek naleznete na adrese: „http://cs.wikipedia.org/wiki/Myhillova-Nerodova_v%C4%9Bta“
Stránka byla naposledy upravena v Stránka byla naposledy editována 30. 6. 2008 v 22:01.
Veškerý text je dostupný za podmínek GNU Free Documentation License (Autorské právo pro podrobnosti).