如何通过设计状态及其转移方法来实现一个分析器呢？当然，如果一个字符串仅仅包 含a或者b的话，那么分析器的状态只有四种：“奇数a奇数b”、“奇数a偶数b”、“偶数a奇数b”、“偶数a偶数 b”。我们把这些状态依次命名为aa、aB、Ab、AB。大写代表偶数，小写代表奇数。当工作还没开始的时候，分析器已经读入的字符串是空串，那么理所当 然的起始状态应当是AB。当分析器读完所有字符的时候，我们期望读入的字符串的a和b的数量都是偶数，那么结束的状态也应该是AB。于是我们给出这样的一 个状态图：
图3.1
检查一个字符串是否由偶数个a和偶数个b组成的状态图
在这个状态图里，有一个短小的箭头指向了AB，代表AB这个状态是初始状态。 AB状态有粗的边缘，代表AB这个状态是结束的可接受状态。一个状态图的结束状态可以是一个或者多个。在这个例子里，起始状态和结束状态刚好是同一个状 态。标有字符”a”的箭头从AB指向aB，代表如果分析器处于状态AB并且读入的字符是a的话，就转移到状态aB上。
我们把这个状态图应用在两个字符串上，分别是”abaabbba”和”aababbaba”。其中，第一个字符串是可以接受的，第二个字符串是不可接受的(因为有5个a和4个b)。
分析第一个字符串的时候，状态机所经过的状态是：
AB [a]aB[b]ab[a]Ab[a]ab[b]aB[b]ab[b]aB[a]AB
分析第二个字符串的时候，状态机所经过的状态是：
AB [a]aB[a]AB [b]Ab[a]ab[b]aB[b]ab[a]Ab[b]AB [a]aB
第一个字符串”abaabbba”让状态机在状态AB上停了下来，于是这个字符串是可以接受的。第二个字符串”aababbaba”让状态机在状态aB上停了下来，于是这个字符串是不可以接受的。
在机器内部表示这个状态图的话，我们可以使用一种比较简单的方法。这种方法仅仅把状态与状态之间的箭头、起始状态和结束状态集合记录下来。对应于这个状态图的话，我们就可以把这个状态图表示成以下形式：
起始状态：AB
结束状态集合：AB
(AB,a,aB)
(AB,b,Ab)
(aB,a,AB)
(aB,b,ab)
(Ab,a,ab)
(Ab,b,AB)
(ab,a,Ab)
(ab,b,aB)
用一个状态图来表示状态机的时候有时候会遇到确定性与非确定性的问题。所谓的确 定性就是指对于任何一个状态，输入一个字符都可以跳转到另一个确定的状态中去。确定性和非确定性的区别有一个直观的描述：状态图的任何一个状态都可以有不 定数量的边指向另一个状态，如果在这些边里面，存在两条边，它们所承载的字符如果相同，那么这个状态输入这个就字符可以跳转到另外两个状态中去，于是该状 态机就是不确定的。如图所示：
图3.2
正则表达式ba*b的一个确定的状态机表示
图3.3
正则表达式ba*b的一个非确定的状态机表示
图3.3中的状态机的起始状态读入字符b后可以跳转到中间的两个状态里，因此这个状态机是非确定的。相反，图3.2中的状态机，虽然功能跟图3.3的状态机一致，但却是确定的。我们还可以使用一种特殊的边来进行状态的转换。我们用ε边来表示一个状态可以不读入字符就跳转到另一个状态 上。下图给出了一个跟图3.3功能一致的包含ε边的非确定的状态机：
图3.4
正则表达式ba*b的一个带有ε边的非确定的状态机