Myhillova–Nerodova věta

Z Wikipedie, otevřené encyklopedie
(přesměrováno z Myhillova-Nerodova věta)
Skočit na navigaci Skočit na vyhledávání

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 s určitými vlastnostmi (popsanými dále v textu). Myhillova-Nerodova věta je rozšířením Nerodovy věty o část týkající se prefixové ekvivalence.

Přesná formulace[editovat | editovat zdroj]

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

a kongruence ~ je konečného indexu, má-li rozklad konečně mnoho tříd (množin prvků, které jsou v rámci třídy 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 taková, že L je sjednocením vybraných tříd rozkladu

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

  • Relace prefixové ekvivalence má konečný index

Neformální popis Nerodovy věty[editovat | editovat zdroj]

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.

Příklad

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 (, když slova u a v odpovídající konečný automat uvedou do stejného stavu).