迟晓晴，王玉涵，王艳慧

山东科技大学 数学与系统科学学院，山东 青岛 266590

1 引言

自动机是计算理论中最简单的数学模型[1]。它不仅是计算机科学理论的基础，而且与神经网络和模型论等领域密切相关[2-3]。有限自动机在软件工程、句法分析、形式语言和程序语言等多个领域得到了有效的应用[4-6]。由于自动机具有固定的内在状态、记忆能力和识别判断能力或决策能力，因此它适宜于作为一切信息系统的数学模型[7-9]。特别的，在形式语言方面，自动机提供了一种处理语言的可靠工具[10-11]。自动机可识别语言[12-14]是形式语言与自动机理论研究的一个重要领域[15-16]。

从图论的角度讲，自动机可看作一个有向图。利用图的邻接矩阵可研究图中的路及图中任意两个结点间的可达性等问题。对于一个字符集Σ上的有限自动机M，一个字w∈Σ*（Σ*是Σ上有限字符串的集合）可被M识别当且仅当在w的作用下，按照状态转移函数，自动机由初始状态到达终止状态。这表明，如果把自动机看作一个有向图，可利用其邻接矩阵，研究该自动机可识别的语言。因此，本文利用有向图的邻接矩阵研究有限自动机可识别语言的基数问题。

2 有向图的邻接矩阵

简单回顾有向图及其邻接矩阵的相关知识，详见文献[18]。

一个图是一个三元组 V(G),E(G),φ(G)，其中V(G)是一个非空的结点集合，E(G)是边集合，φ(G)是从边集合E到结点元序偶（有序偶）集合上的函数。若把图中的边e∈E(G )看作总是与两个结点关联，那么一个图亦可简记为G=V,E ，其中V是非空结点集，E是连接结点的边集。……