文档下载 文档下载导航
设为首页 | 加入收藏
搜索 请输入内容:  
 导航当前位置: 文档下载 > 所有分类 > IT/计算机 > 用Java语言实现NFA到DFA的等价变换-桂日培1
侵权投诉

用Java语言实现NFA到DFA的等价变换-桂日培1

用Java语言实现NFA到DFA的等价变换

姓名:桂日培

单位:湖北工业大学计算机学院02计算机1班

学号:0212002123

时间:2005年10月31日

一、实验目的

1、理解什么是NFA和什么是DFA;

2、掌握NFA和DFA之间的等价变换;

3、了解程序设计语言Java的语言机制。

二、实验小组(按姓氏拼音排序):陈超、桂日培

三、术语解释

1、DFA

确定的有穷自动机(DFA)M是一五元组

M=(Q,∑,δ,q0,Z),

其中:

(1) Q是一有穷状态集;

(2) ∑是有穷输入字母表;

(3) δ是从Q×∑ Q的映射函数,称为状态变迁函数,定义式δ(q1,a)=q2表示在q1

状态下读入字母a后,转到状态q2;

(4) q0∈Q是唯一的初态;

(5) Z包含于Q是终态集。

2、NFA

如果δ(q1,a)的值不唯一,而是一个状态子集的话,那么这样的FA是不确定的,称为不确定的有穷自动机(NFA)。NFA和DFA定义的主要差别是它们的映射函数不一样,NFA的δ函数定义为:

δ:Q×∑ ρ

其中:ρ∈2Q,即ρ是Q的任意子集,2Q是Q的幂集。

四、实验步骤与内容

1、实验环境:

操作系统:Microsoft Windows XP

编译平台:Borland JBuilder 2006 Enterprise

2、步骤与内容:

(1)启动JBuilder,新建一个名为:NFA_To_DFA的工程,模板为默认类型(Default project)。

(2)打开新建的工程。

(3)在工程里添加一个名为NfaDemo的Java文件。

(4)打开NfaDemo文件,编辑源代码。

(5)按“Ctrl+F9”对源文件进行编译。

(6)按“Ctrl+Shift+F9”对目标文件进行连接。

(7)点击工具栏上的“Run Run “NfaDemo.java” using defaults”运行。

运行情况如下(以《程序设计语言编译方法》大连理工大学出版社(第三版)29页2.6(3为例)):

D:\Borland\JBuilder2006\jdk1.5\bin\javaw -classpath "E:\Java工程

第1页

你可能喜欢

热门文档

相关文档

  • NFA转化为DFA的转换算法及实现

    的由NFA转化为DFA的算法设计和实现 技术:主要包括NFA转化为与其等价的DFA所使用的子集构造算法以及把DFA化简 的算法,实现词法分析,最后使用Visual C++语言加以实现。...

  • NFA到DFA的转换

    NFA到DFA的转换_电力/水利_工程科技_专业资料。NFA到DFA的转换2.2.3 NFA到DFA的转换定义2.26 有限自动机的等价 对于给定的限自动机M1和 M2,如果有 L(M1...

  • NFA到DFA的转换过程

    NFA到DFA的转换过程_IT/计算机_专业资料。希望对大家有帮助啊1.具有ε动作的 NFA 状态转换表 .具有ε 0 1 2 3 4 5 6 7 8 9 a ΦΦ 3 ΦΦΦΦ ...

  • NFA如何转换成等价的DFA

    NFA如何转换成等价的DFA_工学_高等教育_教育专区。NFA如何换成等价的DFA编译原理 4.3 NFA转换为等价的DFA 主讲:陈小娟 西南大学荣昌校区信息管理系 4.3.1 ...

  • NFA到DFA转化

    理解和掌握子集法的相关知识和应用,编程 实现对输入 NFA 转换成 DFA 输出的...功能上来说是等价的, 也就是说,我们能够从: NFA M’ 使得 DFA L(M)=L(...

  • 【论文】一类NFA到DFA的直接转化方法

    而且在确定化过程中对于NFA状态集存在ε-closure重复计算和由于对非ε转换的判断而引起的重复计算等问题.本文描述了一种将一类NFA直接转化为DFA的方法.在本方法中,...

  • 从NFA到DFA的转化实验报告

    理解和掌握子集法的相关知识和应用,编程 实现对输入 NFA 转换成 DFA 输出的...功能上来说是等价的, 也就是说,我们能够从: NFA M’ 使得 DFA L(M)=L(...

  • NFA到DFA的转换过程

    NFA到DFA的转换过程 隐藏>> 1.具有ε 动作的 NFA 状态转换表 0 1 2 3 4 5 6 7 8 9 a ΦΦ 3 ΦΦΦΦ 8 ΦΦ b ΦΦΦΦ 5 ΦΦΦ 9 ...

  • [NFA到DFA的转化][liliwen919][doc]

    理解和掌握子集法的相关知识和应用,编程 实现对输入 NFA 转换成 DFA 输出的...给定如图 2 所示的 NFA: 0 ε b 2 b a 1 a b 3 4 图2 与之等价...

  • NFA到DFA的转换过程

    NFA到DFA的转换过程_IT/计算机_专业资料。NFA到DFA的转换过程1.具有ε动作的 NFA 状态转换表 0 1 2 3 4 5 6 7 8 9 a ΦΦ 3 ΦΦΦΦ 8 ΦΦ ...

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