字符 状态 aUQUQ bVvQQ Q 状态转换表
字符 状态 a b S U V U Q V V U Q Q Q Q 状态转换表
DFA接受的字符串 ●对于∑*中的任何字符串t,若存在一条从初始 结点到某一终止结点的路径,且这条路上所 有弧的标记符连接成的字符串等于t,则称t 可为DFAM所接受(识别) DFAM所能接受的字符串的全体记为L(M)
DFA接受的字符串 ⚫ 对于*中的任何字符串t,若存在一条从初始 结点到某一终止结点的路径，且这条路上所 有弧的标记符连接成的字符串等于t,则称t 可为DFA M所接受（识别）。 ⚫ DFA M 所能接受的字符串的全体记为L(M)
DFA的确定性 ●初始状态唯 转换函数fSSx∑>SS是一个单值函数,也就 说,对任何状态s∈SS,和输入符号a∈∑ f(s,a)唯一地确定了下一个状态。即转换函 数至多确定一个状态。 ●没有空边。即没有输入为8()
DFA的确定性 ⚫ 初始状态唯一。 ⚫ 转换函数f:SS→SS是一个单值函数，也就 是说，对任何状态SSS,和输入符号a , f(S,a)唯一地确定了下一个状态。即转换函 数至多确定一个状态。 ⚫ 没有空边。即没有输入为（）
DFA的实现1 ●状态转换表的形式:(数组T存放转换函数) 1.当前状态 State置为初始状态 2.读一个字符→ Current char 3.如果 Cur rentcha≠0f并且 T(State, CurrentChar)terror 则当前状态转为新的状态 T(State, Current), 读下一字符。重复第3步工作。 4.如果当前字符为Eof并且当前状态属于终止状态, 则接受当前字符串,程序结束。否则报错 特点: 程序短小,但占用存储空间多
DFA的实现1 ⚫ 状态转换表的形式：（数组T存放转换函数） 1.当前状态State置为初始状态 2.读一个字符 → CurrentChar 3.如果CurrentCharEof并且 T(State,CurrentChar)error 则当前状态转为新的状态T(State,Current)， 读下一字符。重复第3步工作。 4.如果当前字符为Eof并且当前状态属于终止状态， 则接受当前字符串，程序结束。否则报错 ⚫ 特点： 程序短小，但占用存储空间多
DFA的实现2 ●状态转换图的形式: 每个状态对应一个带标号的case语句 转向边对应goto语句 Li: case Currentchar of goto Li b k b goto Lk other Error( ●特点: 程序长,但占用存储空间少
b DFA的实现2 ⚫ 状态转换图的形式： ⚫ 每个状态对应一个带标号的case语句 ⚫ 转向边对应goto语句 ⚫ 特点： 程序长，但占用存储空间少 i j k a Li: case CurrentChar of a ：goto Lj b : goto Lk other : Error( )