Publication Details
Controlled Finite Automata
Zemek Petr, Ing., Ph.D.
finite automata, controlled accepting, control languages, accepting power,
computational completeness, reduction
This paper discusses finite automata regulated by control languages over their
states and transition rules. It proves that under both regulations,
regular-controlled finite automata and context-free-controlled finite automata
characterize the family of regular languages and the family of context-free
languages, respectively. It also establishes conditions under which any
state-controlled finite automaton can be turned into an equivalent
transition-controlled finite automaton and vice versa. The paper also
demonstrates a close relation between these automata and programmed grammars.
Indeed, it proves that finite automata controlled by languages generated by
propagating programmed grammars with appearance checking are computationally
complete. In fact, it demonstrates that this computational completeness holds
even in terms of these automata with a reduced number of states.
@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"
}