Seminár z teoretickej informatiky - Viliam Geffert (13.12.2024)

v piatok 13.12.2024 o 11:00 hod. v miestnosti I 9

10. 12. 2024 22.24 hod.
Od: Rastislav Královič

Prednášajúci: Viliam Geffert (UPJŠ Košice)

Názov: Konverzie medzi binárnymi a unárnymi konečnostavovými automatmi

Termín: 13.12.2024, 11:00 hod., I 9

Abstrakt:
Ak L je jazyk nad binárnou abecedou {0,1}, tak jeho unárne kódovanou verziou L'= num(L) je jazyk nad unárnou abecedou {a} taký, že a^x patrí do L' vtedy a len vtedy ak nejaká binárna reprezentácia x patrí do L. (Pretože pridávaním núl na začiatok binárneho reťazca sa hodnota reprezentovaného čísla nemení, takých binárnych reprezentácii môže byť viac.) Opačne, binárne kódovanou verziou unárneho L’ je jazyk L= bin(L'), taký že num(L)= L'. Bude prezentovaná procedúra pre konverziu konečnostavového automatu rozpoznávajúceho unárny jazyk L’ na automat pre L= bin(L'), ako aj procedúra pre konverziu v opačnom smere. Konverzia v opačnom smere nie je vždy garantovaná, keďže existujú také binárne regulárne jazyky, pre ktoré ich unárne kódované verzie nie sú dokonca ani bezkontextové. (V takom prípade sa procedúra zastaví s hlásením že konečnostavový automat pre jazyk L’=num(L) neexistuje, keďže L' nie je regulárny.) Rozdiel v počte stavov v automate pre binárny jazyk L a v automate pre jeho unárne kódovanú verziu L’ môže byť až exponenciálny.