Publication Details

Controlled Finite Automata

MEDUNA Alexander and ZEMEK Petr. Controlled Finite Automata. Acta Informatica, vol. 51, no. 5, 2014, pp. 327-337. ISSN 0001-5903. Available from: http://link.springer.com/article/10.1007/s00236-014-0199-5
Czech title
Řízené konečné automaty
Type
journal article
Language
english
Authors
Meduna Alexander, prof. RNDr., CSc. (DIFS FIT BUT)
Zemek Petr, Ing. (DIFS FIT BUT)
URL
Keywords

finite automata, controlled accepting, control languages, accepting power, computational completeness, reduction

Abstract

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.

Published
2014
Pages
327-337
Journal
Acta Informatica, vol. 51, no. 5, ISSN 0001-5903
Publisher
Springer Verlag
DOI
10.1007/s00236-014-0199-5
UT WoS
000339103700003
EID Scopus
2-s2.0-84903900178
BibTeX 
@ARTICLE{FITPUB9893,
   author = "Alexander Meduna and Petr Zemek",
   title = "Controlled Finite Automata",
   pages = "327--337",
   journal = "Acta Informatica",
   volume = 51,
   number = 5,
   year = 2014,
   ISSN = "0001-5903",
   doi = "10.1007/s00236-014-0199-5",
   language = "english",
   url = "https://www.fit.vut.cz/research/publication/9893"
}
Back to top