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. Myhillova-Nerodova věta je rozšířením Nerodovy věty o část týkající se prefixové ekvivalence.

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

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.

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