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

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

Portály: Matematika