This paper discusses n-island finite automata whose transition graphs can be expressed as n-member sequences of islands i1,i2,…,in, where there is a bridge leaving ij and entering ij+1 for each 1≤j≤n−1. It concentrates its attention on even computation defined as any sequence of moves during which these automata make the same number of moves in each of the islands. Under the assumption that these automata work only in an evenly computational way, the paper proves its main result stating that n-island finite automata and Rosebrugh-Wood n-parallel right-linear grammars are equivalent. Then, making use of this main result, it demonstrates that under this assumption, the language family defined by n-island finite automata is properly contained in that defined by (n+1)-island finite automata for all n≥1. The paper also points out that this infinite hierarchy occurs between the family of regular languages and that of context-sensitive languages. Open questions are formulated in the conclusion.
In this paper, the static output feedback stabilization (SOFS) of deterministic finite automata (DFA) via the semi-tensor product (STP) of matrices is investigated. Firstly, the matrix expression of Moore-type automata is presented by using STP. Here the concept of the set of output feedback feasible events (OFFE) is introduced and expressed in the vector form, and the stabilization of DFA is defined in the sense of static output feedback (SOF) control. Secondly, SOFS problem of DFA is investigated within the framework of STP, including single-equilibrium-based SOFS, multi-equilibrium-based SOFS, and further limit cycle-based SOFS. Then the necessary and sufficient conditions for the existence of the three types SOFS are proposed respectively. Meanwhile the efficient and systematic procedures based on the matrix theory to seek the corresponding SOF controller are provided for the three types SOFS problem. Finally, two examples are presented to illustrate the effectiveness of the proposed approach.
We present an overview of four approaches of the finite automata use in stringology: deterministic finite automaton, deterministic simulation of nondeterministic finite automaton, finite automaton as a model of computation, and compositions of finite automata solutions. We also show how the finite automata can process strings build over more complex alphabet than just single symbols (degenerate symbols, strings, variables).