uvw-теорема или ...?

Поле: Теоретична информатика, Дискретна математика

Здравейте,

съществува една теорема (или лема) за регулярните езици, наречена uvw-теорема (съответно uvwxy-теорема за безконтекстните езици). Общо взето тя гласи, че ако един език е регулярен, то тогава всяка една дума, с дължина по-голяма от дадена константа n, може да се разложи на три поддуми u, v и w (|uv| <= n, |v| > 0), като важи следното:

* за всяко естествено число i : u(v^i)w принадлежи на езика

На английски тази лема се нарича Pumping lemma (от помпене), на немски - Pumping-Lemma, uvw-Theorem, Schleifenlemma, Iterationslemma.

На български ми е известно названието uvw-теорема (uvwxy-теорема). Съществуват ли други?

----
Свободната енциклопедия - сподели знанията си...