关于DFA中δ的解释 δ一状态转换函数，是在SX∑→S上的单值映射 定义形式：δ(si,a)=sj,其中s:∈S,sj∈S 含义：在当前状态为s1,输入符号为a时，将转换为 下一状态sj,我们把s称为s的一个后继状态 状态图： 状态—结点 表示在状态s1, 转换函数—有向边 n是∑中符号的 读入符号a后， 输入符号一 边上标记个数 状态将转换到sj 注意：在DFA中每个结点最多可以射田n条弧与别 的结点相连接，每条弧用∑中的一个符号做标记 25.4.2 ☒16
25.4.2 16 关于DFA中δ的解释 δ— 状态转换函数，是在S×→S上的单值映射 定义形式:δ(si，a)=sj，其中si∈S，sj∈S 含义: 在当前状态为si，输入符号为a时，将转换为 下一状态sj，我们把sj称为si的一个后继状态 状态图: a si sj 表示在状态si， 读入符号a后， 状态将转换到sj 状态——结点 转换函数——有向边 输入符号——边上标记 注意:在DFA中每个结点最多可以射出n条弧与别 的结点相连接,每条弧用∑中的一个符号做标记 n是∑中符号的 个数
DFA识别过程p48 设DFAM=(S,∑，8，So,F) 定义：若S1aS1,则s1aSj,表示在状态s:下输入符号a a 可到达状态s;,或s到s有通路，通路上字符串为a 定义：若Si台§ Sj,Sj 8 .Sk,则s1gsk,表示S到st 有通路，通路上字符串为oa。 例如 a a 1.状态0到状态3有通路， 通路上字符串为aa。 2.状态0到状态3有通路， b 通路上字符串为babba。 问题：请证明baab可为DFAM所接受。 25.4.2 ☒7
25.4.2 17 DFA识别过程 p48 设 DFA M =（S，，δ ，s0 ，F ) 定义：若 a 1 0 b 3 2 a a b b a,b a sj sk sj a si 定义：若 sj si a si sj sk a si 例如 1.状态0到状态3有通路， 通路上字符串为aa。 2.状态0到状态3有通路， 通路上字符串为babba。 ，则 ，表示在状态si下输入符号a 可到达状态sj ，或si到sj有通路，通路上字符串为a ， ，则 ，表示si到sk 有通路，通路上字符串为a。 问题：请证明baab可为DFA M所接受
DFA可识别符号串 设DFAM=(S,∑，6，S0,F) 定义：若a∈∑*，s0→Sj,且sj∈F 则称a可为DFAM所接受（识别，读出） 含义：若对于∑*中的任何字a,若存在一条从初态结 点so到某一终态结点的通路，且这条通路上所有弧的标 记符连接成的字等于a,则称a可为DFAM所识别（读 出或接受) 特别地，若初态结点同时又是终态结点，则空字 e可为DFAM所识别 25.4.2 ☒18
25.4.2 18 DFA可识别符号串 ▪设 DFA M =（S，，δ ，s0 ，F ) 定义：若α∈ ∑* ， sj s0 ，且sj ∈F ， 则称α可为DFA M所接受（识别，读出） 含义：若对于∑*中的任何字α，若存在一条从初态结 点s0到某一终态结点的通路，且这条通路上所有弧的标 记符连接成的字等于α，则称α可为DFA M所识别（读 出或接受） 特别地，若初态结点同时又是终态结点，则空字 ε可为DFA M所识别
DFA可识别符号串 DFAM所能接受的字符串的全体为 L(M)={a|s0Sj且s)∈F} 特别地： 若so∈F,即有s0马s0,则e可为M所接 受，即e∈L(M) 若F=本，则L(M)=Φ 25.4.2 国219
25.4.2 19 DFA可识别符号串 特别地： ▪若s0∈F，即有 s0 s ε 0 ▪DFA M 所能接受的字符串的全体为 sj L（M）={α| s0 且sj ∈F } ，则ε可为M所接 受，即ε∈ L(M) ▪若F=φ，则 L(M)=φ
DFA的行为很容易用程序模拟 DFAM=(S,∑，δ，So,F)的行为的模拟程序： 0S:=S0; oc:=getchar; while c<>eof do ▣ {S:=δ(S,c); 0 c:=getchar; ▣ }; oif S is in F then return（‘yes') else return（‘no’） 节目录 25.4.2 ☒220
25.4.2 20 DFA的行为很容易用程序模拟 DFA M=（S，Σ，δ，s0，F）的行为的模拟程序： S:=s0； c:=getchar; while c<>eof do {S:=δ(S,c); c:=getchar; }; if S is in F then return (‘yes’) else return (‘no’) ▪ 节目录