| Abstrakt: | Finite automata with an additional ability to perform some kind of input transformations shall be considered in the thesis. Such automata have already been studied by Bordihn, Holzer, and Kutrib for several particular transformations, such as input reversal or revolving. Building upon this line of research, we shall provide a general mathematical basis for the study of automata with input transformations and mainly focus on computational power of automata that apply their input transformations at most some fixed constant number of times. We shall describe several examples of input transformations, which enable finite automata to accept languages from different levels of the Chomsky hierarchy (and beyond). Moreover, we shall prove a necessary and sufficient condition, under which an input transformation preserves regularity when applied at most a constant number of times by a finite automaton.
|
|---|