DFA和NFA的区别
1.DFA没有epsilon transaction （必须读入字符）
2.对每一个确定的状态和读入字符，最多只能到一个下个状态，（不能有多的选择）
Recognition
input position: 0-n
initial configuration:(q0,0)
agenda: a set of configurations, initial empty
如何计算一个新的configuration
从 agenda 中取出 如（q,i）
比如 i 位置的之后会读入 a， 找到所有的（q,a,q'）
将 （q',i+1） 加入agenda
同时也找下（q,Epsilon,q''）
将（q'',i+1）加入
BFS:FIFO
DFS:FILO
Sequential transducer
对input 来说是确定的
在output string 可以有epsilon 但是 input 不可以
Minimum dist
像p33 speech and language processing 那样画一个表，表中的值为
左加一
下加一
斜下加2（字符不同） 或 加0（字符相同）
其中最小的那个
可以加入backtrack 记住自己的值从哪里计算得来。
网友评论