Detail publikace
Controlled Finite Automata
Zemek Petr, Ing., Ph.D.
konečné automaty, řízené přijímání, řídící jazyky, přijímací síla, výpočetní úplnost, redukce
Článek diskutuje konečné automaty regulované řídícími jazyky definovanými nad stavy a přechodovými pravidly. Dokazuje, že s oběma typy řízení konečné automaty řízené regulárními a bezkontextovými jazyky definují třídu regulárních respektive bezkontextových jazyků. Taktéž ustanovuje podmínky, za kterých je možné konečné automaty řízené stavy transformovat na ekvivalentní konečné automaty řízené přechodovými pravidly a naopak. Článek dále demonstruje blízký vztah mezi těmito automaty a programovanými gramatikami. Dokazuje, že konečné automaty řízené jazyky generovanými programovanými gramatiky s kontrolou na výskyt bez vymazávacích pravidel jsou výpočetně úplně. Ve skutečnosti je ukázáno, že jejich výpočetní úplnost platí i v případě, kdy mají tyto automaty omezený počet stavů.
@article{BUT111479,
author="Alexandr {Meduna} and Petr {Zemek}",
title="Controlled Finite Automata",
journal="Acta Informatica",
year="2014",
volume="51",
number="5",
pages="327--337",
doi="10.1007/s00236-014-0199-5",
issn="0001-5903",
url="http://link.springer.com/article/10.1007/s00236-014-0199-5"
}