本文对自动机理论的研究主要是两个方面:自动机的极小化和极小化的时间复杂性。在自动机的状态集合上定义等价关系,引入等价类,将等价的状态合并成一个状态,生成新的状态数较小的自动机。新生成的自动机与原自动机识别的语言不变,也就是说它们是等价的。这就是树图分割法的思想。利用树图分割法可以进行确定型有穷自动机的极小化。本文的重点内容是构造了一类非确定型有穷自动机,即连接型有穷自动机。这类有穷自动机是由两台确定型有穷自动机连接而成的。利用两台确定型有穷自动机状态集合上的等价关系可以构造出连接型有穷自动机状态集合上的等价关系。这类非确定型有穷自动机也可以利用树图分割法来极小化。还可以得到连接后再极小化的自动机的状态数不大于极小化后再连接的自动机的状态数。非确定型有穷自动机的情况比较复杂。往往比较大的有穷自动机没有等价状态,但将其中某两个或者几个状态进行合并并不改变它们的语言。本文给出了非确定型有穷自动机状态合并的条件。找到了非确定型有穷自动机极小化状态的临界条件。自动机极小化的时间复杂性,有效的验证了极小化算法是否有效。一般地,多项式时间内能完成的就认为该算法是有效的。确定型有穷自动机和连接型有穷自动机利用树图分割法进行极小化,它们都在状态的三次方时间内就可以完成。本文的最后给出了非确定型有穷自动机极小化算法。