Construction of Automaton Observer Based on Matrix Semi-Tensor Product
Zhaohe An, Yongyi Yan, Jumei Yue, Xiaobo Li · 2025
The Finite State Machine (FSM) is a foundational model in computer science and formal language theory, with extensive applications in pattern recognition, compiler design and natural language processing. However, the conversion of Nondeterministic Finite Automata (NFA) to Deterministic Finite Automata (DFA) particularly in the presence of$\varepsilon$-transitions, presents a computationally intensive challenge. This paper introduces a novel approach utilizing matrix representation, specifically employing semi-tensor products and matrix operations, to construct observers for$\varepsilon$-transition NFAs. This method is applicable to automata where states exhibit transitions via both character inputs and$\varepsilon$-transitions. By formulating a block matrix model and implementing the semitensor product algorithm, this approach enables a systematic and efficient treatment of$\varepsilon$-transition NFAs. The results demonstrate that the proposed method enhances both conversion efficiency and accuracy, particularly when processing large-scale state sets and NFAs with frequent$\varepsilon$-transitions. Furthermore, this method offers theoretical innovation and exhibits substantial applicability. Future research will explore the extension of this methodology to accommodate more complex NFA structures.