Myhillova-Nerodova věta

Z Wikipedie, otevřené encyklopedie
Skočit na: Navigace, Hledá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. 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 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í tři 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

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