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, . +more).

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

Kategorie:Formální jazyky Kategorie:Matematické věty a důkazy