文档下载 文档下载导航
设为首页 | 加入收藏
搜索 请输入内容:  
 导航当前位置: 文档下载 > 所有分类 > 高等教育 > 工学 > 编译原理nfa-dfa
侵权投诉

编译原理nfa-dfa

基本定义

NFA,也称不确定的有穷自动机,是由一个五元式定义的数学模型,特点是它的不确定性,即在当前状态下,读入同一个字符,可能有多个下一状态。 DFA,也称确定的有穷自动机,也是由一个五元式定义的数学模型,相对的特点是它的确定性,即在当前状态下,读入同一个字符,最多有一个后继状态。 NFA与DFA的矩阵表示

一个NFA或者DFA还可以用一个矩阵[5]表示,矩阵也可以说是状态转换表,它的优点是可以快速访问给定的状态在给定的输入字符时能转换到的状态集。矩阵,每个状态一行,每个输入符号和ε(如果有需要的)各占一列,表的第i行中与输入符号a对应的表项是一个状态集合,表示NFA或者DFA在状态i输入a时所能到达的状态集合(DFA的集合唯一),即δ(i,a)(7)

如图可用表表示:

NFA状态转换表

编译原理nfa-dfa

[6]

。

DFA状态转换表

编译原理nfa-dfa

NFA向DFA的转换的思路

从NFA的矩阵表示中可以看出,表项通常是一状态的集合,而在DFA的矩阵

第1页

你可能喜欢

热门文档

相关文档

  • 编译原理3.3.3-1 NFA

    编译原理3.3.1-补充-正规... 编译原理3.3.2-DFA 编译原理3.3.3-2 NFA的确...1/2 相关文档推荐 编译原理3.3.3-2 NFA的确... 21页 免费 编译原理...

  • 编译原理NFA转DFA

    编译原理NFA转DFA_IT/计算机_专业资料。编译原理实验报告 实验名称 不确定有限状态自动机的确定化 实验时间 院系 计算机科学与技术学院 班级 学号 姓名 1.试验目的...

  • 编译原理(2)词法_2(NFA、DFA的确定化和化简)

    编译原理(2)词法_2(NFA、DFA的确定化和化简)_计算机软件及应用_IT/计算机_专业资料。西北农林科技大学本科教程 第 3 讲主讲教师:赵建邦 本讲目标 ? 第二章...

  • 编译原理 NFA转DFA

    编译原理 NFA转DFA_工学_高等教育_教育专区。编译原理课程实验报告实验一:利用子集法构造 DFA 一.实验目的掌握将非确定有限自动机确定化的方法和过程。 二.实验要求...

  • 编译原理实验词法分析器VS2010C实现

    编译原理 词法分析器 实验课题:正则表达式->NFA->DFA->简化,最后输入一字符串并检测该字符串是否能到达最终状态 开发环境:Visual Studio 2010 使用方法: 现在 ...

  • 编译原理3.3.2-DFA

    编译原理3.3.2-DFA_IT/计算机_专业资料。编译原理课件第三章 词法分析 3.1 ...DFA和NFA 和 1、确定的有穷自动机 DFA 、 (Deterministic Finite Automaton) ...

  • 编译原理与技术

    编译原理与技术 词法分析 (2) 2013-7-11 《编译原理与技术》讲义 1 有限自动机 ? 有限自动机(Finite Automata-FA)是种更 一般化的状态转换图。分为NFA和DFA...

  • 编译原理-词法分析

    编译原理-词法分析_IT/计算机_专业资料。编译 原理第三章 词法分析赵建华 南京大学...步骤:– 正则表达式到NFA – NFA到DFA NFA到DFA(子集构造法)(1) ? 基本...

  • 编译原理课程设计-NFA的确定化

    Keywords: finite automata; deterministic finite automaton (DFA), nondeterministic finite automaton (NFA). -3- 《编译原理》课程设计 -- NFA 的确定化设计 ...

  • -编译原理-DFA

    [,]DFA={{' ','A'},{'A','B'},{'C','B'},{'A','D'},{'C...编译原理(9) 20页 免费 编译原理(2)词法_2(NFA、... 28页 免费...

站点地图 | 文档上传 | 侵权投诉 | 手机版
本站所有资源均来自互联网,本站只负责收集和整理,均不承担任何法律责任,如有侵权等其它行为请联系我们.
文档下载 Copyright 2013 doc.guandang.net All Rights Reserved.  -  email