关于二元延迟3步前馈逆有限自动机的结构

摘要

前馈逆有限自动机的结构是有限自动机可逆性理论中的基本问题.对延迟步数≥3的前馈逆结构的刻划,则是一个长期的未解决问题.研究了二元延迟3步前馈逆有限自动机的结构.对于自治有限自动机Ma的状态图为圈的二元延迟3步弱可逆半输入存储有限自动机C(Ma,f ),给出了其长3极小输出权分别为1,2,8三种情形下结构的一种刻画.由于C(Ma,f )延迟3步弱可逆当且仅当它是延迟3步弱逆,因此,得到了二元延迟3步前馈逆有限自动机结构的一种部分刻画.%The structure of feedforward inverses is a fundamental problem in the invertibility theory of finite automata. The characterization of the structure of feedforward inverses with delay steps ≥3 is a long-term unsolved problem. This paper deals with this topic. For a binary weakly invertible semi-input memory finite automaton C(Ma,f) with delay 3, where the state graph of Ma is cyclic, the characterizations of the structures are given when its minimal 3-output weight is 1, 2, and 8, respectively. Because C(Ma,f) is weakly invertible with delay 3 iff it is weakly inverse with delay 3, a partial characterization of the structure of binary feedforward inverses with delay 3 is obtained.