摘要
自动机理论是计算机科学理论的重要组成部分。论文研究了布尔代数上的线性自动机,证明了任意一个线性有限自动机是函数布尔代数上的一个内动机。定出了有限布尔代数上的一类可逆线性内动机,给出并证明了有限布尔代数上内动机图型为下向森林的充分必要条件,给出了树型内动机中每一层节点数的计算公式,进而证明了有限布尔代数上的非可逆内动机图型为恰等叉支下向树的充分必要条件。
Automata theory is an important component of computer science.This paper considers the linear autonomous automata over finite Boolean algebra.In fact,any finite automaton over finite field can be regarded as a Boolean function-matrix automaton.h presents a reversible linear autonomous automaton over finite Boolean algebra.A necessary and sufficient condition is given and proved for an automaton to be a forest.Thirdly,a formula counting the nodes of tree is put forward.Finally, A necessary and sufficient condition is given and proved for an autonomous automaton to be a equal-branch-tree.
出处
《计算机工程与应用》
CSCD
北大核心
2006年第10期25-27,125,共4页
Computer Engineering and Applications
基金
国家自然科学基金资助项目(编号:60234030)
湖南省教育厅项目(编号:02C589)
关键词
布尔函数矩阵
线性有限内动机
森林
恰等叉支树
Boolean function-matrix,linear finite autonomous automaton, forest, equal-branch-tree