编译原理_复习重难点

from成都信息工程大学软件工程学院

1. 正规式 正规文法 from成都信息工程大学软件工程学院

有限自动机【确定的有穷自动机DFA、不确定的有穷自动机NFA】

确定的有穷自动机DFA

DFA的意义： 对于Σ*中的任何字符串t，若存在一条从初态到终态的路径（该路径 上的字符串为t），则t 可为DFA M所接受（或说t 是该DFA可识别的）。 若初态结也是终态结，则空字可接受。 DFA M 所能接受的字符串的全体称为该自动机识别的语言，记为L(M)。 结论：Σ上的一个字符串集U是正规的，当且仅当存在一 个Σ上的确定的 有穷自动机DFA M，使U=L(M)。

from成都信息工程大学软件工程学院

不确定的有穷自动机NFA

NFA与DFA的等价性 2. NFA的确定化 定义：一个状态集合I 的ε—闭包 ε— closure(I) ： ① 若q∈I，则 q∈ε— closure(I)； ② 若q∈I，则 q经任意条ε弧而能到达的任何状态q : q ε— closure(I) 定义：一个状态集合I 的a弧转换为 Ia =ε— closure(J) 其中: J 是所有那些可以从 I 中的某一状态经过一条 a 弧而到达的状态的集合。 from成都信息工程大学软件工程学院

NFA与DFA的等价性 NFA M = ( Q ,Σ,δ, Q0 , Z ) DFA M ) = ( Q,Σ,δ, q0 , ZQ= ?； Z= ?； Q0 = —Closure (Q0 ) 将 Q0 Q While(QI) { 对每个a ∈Σ做 { 求Ia; 若Ia不在QQ 若Ia至少有一个是M的终态，则同时把Ia加入到Z } 给I加上标记； } 重新命名Q Q0 q0 即为DFA M Z 中的所有状态子集对应的新状态为DFA M 的终态； 中；