Computer Engineering and Applications ›› 2007, Vol. 43 ›› Issue (23): 43-47.

• 学术探讨 • Previous Articles     Next Articles

Decomposition of weakly invertible quasi-(r,r)-order memory linear finite automata

WU Cheng-lai,DENG Pei-min,YI Zhong   

  1. College of Mathematics,Guangxi Normal University,Guilin,Guangxi 541004,China
  • Received:1900-01-01 Revised:1900-01-01 Online:2007-08-11 Published:2007-08-11
  • Contact: WU Cheng-lai

弱可逆拟(r,r)阶存贮线性有限自动机的分解

吴成来,邓培民,易 忠   

  1. 广西师范大学 数学科学学院,广西 桂林 541004
  • 通讯作者: 吴成来

Abstract: This paper studies the output weight of the weakly invertible quasi-(r,r)-order memory linear finite automata,then gives a fact that the r-output weight of any given states of the weakly invertible quasi-(r,r)-order memory linear finite automata is 1.For a n-ary quasi-(r,r)-order memory linea finite automata M,whether M is weakly invertible with delay r,a necessary and sufficient condition is obtained,that M can be decomposed into a weakly invertible finite automata M0 with delay 0 and a weakly invertible quasi-(0,r)-order memory linear finite automata M1 with delay r.

Key words: quasi-order memory linear finite automata, decomposition, weakly invertible, output weight

摘要: 通过对延迟r步弱可逆拟(r,r)阶存贮线性有限自动机输出权的研究,得出对延迟r步弱可逆拟(r,r)阶存贮线性有限自动机的任意一个状态,它的长r的输出权都是1;任何一个n元拟(r,r)阶存贮线性有限自动机M延迟r步弱可逆的充分必要条件是M都可以分解为一个延迟0步弱可逆有限自动机M0和一个延迟r步弱可逆拟(0,r)阶存贮线性有限自动机M1。

关键词: 拟存贮有限自动机, 分解, 弱可逆, 输出权