非确定有限自动机小FA ●定义2:设A是一个NA,A=(SS,S,f,TS) 则定义L(A为从任意初始状态到任意终止状 态所接受的字符串。 L(A)={β|s→Ps’,s0∈Ss∈TS ●定义3:设A1和A2是同一个字母表上的自动机, 如果有L(A1)=(A2),则称A和A2等价。非确定有限自动机NFA ⚫ 定义2：设A是一个NFA，A= (,SS,S0,f,TS) ⚫ 则定义L(A)为从任意初始状态到任意终止状 态所接受的字符串。 L(A)={|s0s’, s0 S0 s’TS} ⚫ 定义3：设A1和A2是同一个字母表上的自动机， 如果有L(A1)=L(A2),则称A1和A2等价