如何利用有穷自动机来处理字符串

    有穷自动机可分成确定型的有穷自动机和非确定型的有穷自动机。

确定型自动机简称DFA，它包含一个有穷的状态集合Q,一个有穷的输入符号集合∑，一个转移函数T，一个初始状态q₀ ，一个终结状态或接受状态的集合F。通常可用一个五元组来表示，如:

A={Q，∑，T，q₀ ，F}

非确定型自动机简称NFA，和DFA一样，也可用这个五元组表示，和DFA唯一的区别就是NFA的转移函数T返回值的类型不同，在DFA的情况下，T返回值勤是单个状态；而在NFA状态下，返回值是一个状态的集合。

先来看下DFA如何处理字符串：

DFA的语言是这个DFA接受的所有的串的集合。假设a₁a₂...a_n是输入符号序列，让这个DFA从初始状态q₀开始运行。查询转移函数为T，如T(q_0, a₁)= q₁ ,以找出DFA A在处理了第一个输入符号a₁ 之后进入的状态。处理下一个输入符号a₂，再求T(q_1, a₂)的值，如果这个状态是q₂ ，以这种方式继续找下去，找出状态q_3, q₄ ,q_5… q_n ，使得每个i ,都有T(q_i-1, a_i)= q_i 。如果q_n 属于F，则接受输入a₁a₂...a_n, 否则就拒绝。从而就完成了一个字符串的匹配过程。

由于NFA和DFA具有等价性，故所有在NFA处理字符串的问题都可以转换为DFA处理字符串问题。这里不再说明。

评论

1 楼 careprad 2008-10-15  

何不也图解一下？