Meno: | Andrej
|
---|
Priezvisko: | Ravinger
|
---|
Názov: | Usefulness of information for non-unary languages
|
---|
Vedúci: | prof. RNDr. Branislav Rovan, PhD.
|
---|
Rok: | 2023
|
---|
Kľúčové slová: | Užitočnosť informácie, Rozložiteľnosť, Deterministické konečné automaty, Stavová zložitosť, Ohraničené jazyky
|
---|
Abstrakt: | Táto práca pokračuje vo výskume pojmu užitočnosti informácie. Prídavná informácia niekedy zjednoduší riešenie problému. Toto sa dá formalizovať pomocou formálnych jazykov, deterministických konečných automatov a rozkladu jazyka. Deterministická rozložiteľnosť unárnych regulárnych jazykov bola už skúmaná [1] a my pokračujeme vo výskume deterministickej rozložiteľnosti regulárnych jazykov ohraničených a*b* (jazykov, ktoré sú podmnožina a*b*). Skúmame dva typy rozložiteľnosti: do takých regulárnych jazykov, ktoré sú ohraničené a*b* a do ľubovoľných regulárnych jazykov. Definujeme podtriedu jazykov ohraničených a*b*, ktoré charakterizujeme vzhľadom na rozložiteľnosť do jazykov ohraničených a*b*. Uvádzame tiež niektoré postačujúce podmienky na rozložiteľnosť pre ostatné jazyky ohraničené a*b* a nejaké postačujúce podmienky pre rozložiteľnosť do ľubovoľných jazykov.
|
---|