自动机的秩与工业自动化中的部件定向器设计问题和理论计算机科学中的?erny-Pin猜想密切相关。确定计算自动机的秩可以归结于查找自动机的终结字,由于秩不相同的自动机性质差异较大,一般自动机的终结字查找算法研究难度较高。Rystsov于1992年提出了一个时间复杂度为O(|A|~4)的自动机终结字查找算法,该算法是至今仅有的专门用于查找自动机的终结字的算法。由于涉及的理论基础比较复杂,性能不高,Rystsov算法并不适合实际应用。首先,相较于Rystsov算法,本文希望能够更快地找到自动机的一个终结字,或者能够找到一个更短的终结字。虽然自动机终结字查找算法数量稀少,但是它的特殊情形-同步自动机的同步字查找算法可谓成果丰富。本文以现有同步字查找算法为蓝本,设计了几种查找自动机较短终结字的新算法,对这些算法的复杂度进行了理论分析,并设计了相关实验测试了这些算法的效率。更进一步的,本文希望找到自动机的最短终结字。已经有文献证明,查找同步自动机最短同步字是一个NP完全问题,作为上述问题的一般化,查找自动机最短终结字也是一个NP完全问题。本文以现有最快的最短同步字查找算法为蓝本,设计了一种自动机最短终结字查找算法,对该算法的时间复杂度进行了理论分析,分析表明,该算法是一个指数级算法。此外,本文也设计了相关实验测试了该算法的性能,为了提高算法的运行效率,在实验过程中应用了大量优化。实验结果表明,新算法能在较短的时间内找到大部分自动机的最短终结字,这些优化也非常有效。