Rozsah možných stavových zložitostí pre operáciu zreťazenie a ich dosiahnuteľnosť

RNDr. Juraj Šebej, PhD.

Abstrakt

Dokážeme, že pre každú hodnotu m, n a α, kde 1 ≤ α ≤ f(m,n), pričom f(m,n) je stavová zložitosť operácie zreťazenie, existuje minimálny m-stavový deterministický konečnostavový akceptor A a minimálny n-stavový deterministický konečnostavový akceptor B, obe definované nad abecedou Σ, |Σ| ≤ 2n+4, také, že minimálny deterministický konečnostavový akceptor pre jazyk L(A)L(B) ma presne α stavov. Náš výsledok vylepšuje podobný výsledok, ktorý používal abecedu exponenciálnej veľkosti.