| Meno: | Andrej
|
|---|
| Priezvisko: | Ravinger
|
|---|
| Názov: | Usefulness of information for bounded regular languages
|
|---|
| Vedúci: | prof. RNDr. Branislav Rovan, PhD.
|
|---|
| Rok: | 2025
|
|---|
| 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] V našej bakalárksej práci [2] sme začali výskum deterministickej rozložiteľnosti regulárnych jazykov ohraničených a^*b^* (jazykov, ktoré sú podmnožina a^*b^*) a v tejto práci pokračujeme v tomto výskume. 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. Uvádzame niektoré postačujúce podmnienky na rozložiteľnosť pre každý z typov. Uvádzame tiež nejaké nutné podmienky na rozložiteľnosť pre druhý typ rozložiteľnosti. Pre špecifický typ rozložiteľnosti do jazykov ohraničených a^*b^* tiež charakterizujme podtriedu jazykov
ohraničených a^*b^* vzhľadom na rozložiteľnosť.
|
|---|