Controlled finite automata

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-fre...

Full description

Bibliographic Details
Published in:Acta Informatica, Vol. 51, No. 5 (2014), p. 327-337
Main Author: Meduna, Alexander
Other Involved Persons: Zemek, Petr
Format: electronic Article
Language:English
ISSN:1432-0525
Physical Description:Online-Ressource
DOI:10.1007/s00236-014-0199-5
Subjects:
QR Code: Show QR Code
LEADER 01750nma a2200277 c 4500
001 SPR011752025
003 DE-601
005 20150324070419.0
007 cr uuu---uuuuu
008 150313s2014 000 0 eng d
024 7 |a 10.1007/s00236-014-0199-5  |2 doi 
024 8 |a s00236-014-0199-5 
035 |a s00236-014-0199-5 
040 |b ger  |c GBVCP 
041 0 |a eng 
100 1 |a Meduna, Alexander 
245 1 0 |a Controlled finite automata  |h Elektronische Ressource 
300 |a Online-Ressource 
520 |a 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. 
653 |a OriginalPaper 
700 1 |a Zemek, Petr  |e verfasserin  |4 aut 
773 0 8 |i in  |t Acta Informatica  |d Berlin : Springer  |g Vol. 51, No. 5 (2014), p. 327-337  |q 51:5<327-337  |w (DE-601)SPR011737581  |x 1432-0525 
856 4 1 |u http://dx.doi.org/10.1007/s00236-014-0199-5  |3 Volltext 
912 |a GBV_SPRINGER 
951 |a AR 
952 |d 51  |j 2014  |e 5  |c 08  |h 327-337