第一范文网 - 专业文章范例文档资料分享平台

编译原理_复习重难点

来源:用户分享 时间:2025/5/24 18:04:49 本文由loading 分享 下载这篇文档手机版
说明:文章内容仅供预览,部分内容可能不全,需要完整文档或者需要复制内容,请下载word后使用。下载word有问题请添加微信号:xxxxxxx或QQ:xxxxxx 处理(尽可能给您提供完整文档),感谢您的支持与谅解。

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 的终态; 中;

搜索更多关于: 编译原理_复习重难点 的文档
编译原理_复习重难点.doc 将本文的Word文档下载到电脑,方便复制、编辑、收藏和打印
本文链接:https://www.diyifanwen.net/c2ttwx7jboq52amx9ksuj_3.html(转载请注明文章来源)
热门推荐
Copyright © 2012-2023 第一范文网 版权所有 免责声明 | 联系我们
声明 :本网站尊重并保护知识产权,根据《信息网络传播权保护条例》,如果我们转载的作品侵犯了您的权利,请在一个月内通知我们,我们会及时删除。
客服QQ:xxxxxx 邮箱:xxxxxx@qq.com
渝ICP备2023013149号
Top