首页 > 代码库 > 编译原理学习
编译原理学习
编译原理学习笔记----
不确定有穷自动机（NFA）
一个不确定的有穷自动机T是一个五元组，M={K，∑，f,S,Z}
⒈K是一个有穷集他的每一个元素称作一个状态。
⒉∑是一个字母表，他的每一个元素称为一个输入符号。
⒊f是一个从Kx∑*到K的子集映射即K*∑*->2^K，其中2^K表示K的幂集。
⒋S包含于K集，是一个非空初态集合。
⒌Z包含于K是一个非空的终态集合。
确定有穷自动机（DFA）
一个确定的有穷自动机M是一个五元组：M=（K， ∑，f，S，Z）其中，
1)K是一个有穷集，他的每个元素称为一种状态。
2） ∑是一个有穷字母表，他的每个元素称为一个输入符号，所以∑称为输入符号表。
3）f是转换函数，是KX∑-->K 上的映像，例如f（ki，a）=kj这就意味着，当前状态为k，输入字符a后，将转换到下一状态kj，我们把kj称为ki的一个后继状态；
4）S属于K，是唯一的一个出态。
5）Z属于K，是一个终态，终态也称为可接受状态或结束状态。
例如：
这个DFA可以表示一个状态图：
也可以用状态矩阵显示，行表示状态，列表示输入符号，终态在表的右端标1，非终态在表的右边标0。
编译原理学习
声明：以上内容来自用户投稿及互联网公开渠道收集整理发布，本网站不拥有所有权，未作人工编辑处理，也不承担相关法律责任，若内容有误或涉及侵权可进行投诉： 投诉/举报 工作人员会在5个工作日内联系你，一经查实，本站将立刻删除涉嫌侵权内容。