| Abstrakt: | V práci skúmame vplyv prídavnej informácie na zložitosť automatov rozpoznávajúcich nejaké jazyky. "Prídavná informácia" znamená to, že automatu dovolíme predpokladať, že vstup patrí do nejakého poradného jazyka. V práci skúmame jazyky rozpoznávané deterministickými zásobníkovými automatmi s regulárnym poradným jazykom. V prvej časti sa zaoberáme deterministickými bezkontextovými jazykmi z pohľadu zložitosti. Skúmame rôzne spôsoby definovania zložitosti zásobníkových automatov a jazykov ktoré oni rozpoznávajú, hľadáme tesné odhady zložitosti niektorých tried jazykov a ukazujeme konštrukciu normálneho tvaru "automat vždy dočíta vstup", ktorá nevyžaduje pridanie exponenciálneho počtu stavov. V druhej časti využívame tieto poznatky na skúmanie vplyvu regulárnej prídavnej informácie na zložitosť. Dokazujeme existenciu nekonečnej podtriedy deterministických zásobníkových jazykov, pre ktoré vhodná regulárna prídavná informácia umožní zjednodušiť deterministický zásobníkový automat pre ich akceptovanie. Dokážeme aj existenciu nekonečnej triedy deterministických bezkontextových jazykov, obsahujúcej ľubovoľne zložité jazyky, pri ktorých žiadna regulárna prídavná informácia neumožní znížiť zložitosť deterministického zásobníkového automatu pre ich akceptovanie.
|
|---|