Myhillova-Nerodova věta

Z Wikipedie, otevřené encyklopedie

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 čtyři třídy:

  • 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).

V jiných jazycích