精华内容
下载资源
问答
  • NFA转化DFA

    千次阅读 2012-09-06 22:51:17
    NFA转化DFA NFA既然和DFA等价,那么,它们之间就存在对应关系,DFA到NFA的转化是自明的:没有空转移,把返回的单个state编程仅包含一个state的集合,就是一个形式上的NFA。但是,NFA到DFA的转化就不是那么简单了,...

    NFA转化DFA

    NFA既然和DFA等价,那么,它们之间就存在对应关系,DFA到NFA的转化是自明的:没有空转移,把返回的单个state编程仅包含一个state的集合,就是一个形式上的NFA。但是,NFA到DFA的转化就不是那么简单了,实际上,在计算理论中,它属于ExpSpace问题,是一类比NP问题更难的问题。

    往简单了说,因为NFA的转移函数的返回值是个state集合,如果NFA的state数目为n,那么这个state集合的集合,就是整数[0,n)的幂集,这个幂集的元素数目是 2^n ,不错,在最坏情况下,包含n个状态的NFA对应的DFA有 2^n 个状态。虽然这个 让人很悲观,但是在实际情况中,大部分(除了那些精心构造的)NFA对应的DFA远远小于 2^n,并且往往只是O(n)。

    具体的转化算法,叫做“子集构造法”,其实翻译成“幂集构造法”应该更合适。在实现该算法的过程中,有两点值得注意:

    l  ε闭包,在把一个新的NFA状态加入子集时,不是只要加入这个NFA状态,而是要加入该状态的整个ε闭包(需要用DFS或者BFS去计算)

    l  对每个NFA状态子集按状态号排序,得到一个有序数组,再去重,然后把该数组作为Key,创建一个子集的集合(set of subset),即幂集(power set)

     

    我实现该算法时,使用了adjacent difference 技术,即整个power set 是一个大数组,然后一个下标数组,每个下标指向一个subset的起始位置,两个下标想减即是subset的尺寸,这样内存用量更少。进一步的优化可以对subset使用差分编码(因为是有序的),即除了第一个状态号,后面的整数仅保存和前一项的差,再使用变长整数编码。

    和 MinADFA_onfly一样,在这个算法的实现中用到了gold_hash_tab,不过这里对对gold_hash_map的使用非常trick,但的确同时优化了memory和speed!有兴趣的可以看一下代码


    展开全文
  • BUPT 自动机实验,NFA转化DFA,java代码加实验报告
  • C++builder编写的NFA转化DFA程序,有界面 考虑到了多个终态的情况,且能够输出转化集合
  • <编译原理>NFA转化DFA 及 DFA的化简

    万次阅读 多人点赞 2017-12-03 21:37:00
    正则表达式-->NFA--->DFA--->最简DFA DFA(有限自动机,每个状态的下一步都是确定的,没有空。只有一个开始状态,只有一个结束状态) NFA(有可能转到多个状态,可能有空) ※由正则表达式转到NFA: 基本...

    正则表达式-->NFA--->DFA--->最简DFA

    DFA(有限自动机,每个状态的下一步都是确定的,没有空。只有一个开始状态,只有一个结束状态)

    NFA(有可能转到多个状态,可能有空)


    ※由正则表达式转到NFA

    基本可以分成3种:

    AB(连接)

    A|B(或)

    A*(0到多个A)


    例:正则表达式(a|b)*(aa|bb)(a|b)*NFA


    NFADFA匹配串的时间空间复杂度


    ※NFA的确定化:NFADFA

    空闭包,子集法

    原理:有些状态是在做同样的工作,他们的工作完全可以用一个状态来做,把这些相同功能的状态组合成一个集合,并把它重新命名为一个状态。

    :

    将以下NFA转换为DFA


    按下表不断构建,直到Ia,Ib中出现的集合,全部都出现在I中。并且将他们重新编号

    (终态是那些有Y的集合,Y为原先NFA的终态)


    转成DFA的结果:


    ※DFA化简成最简DFA

    1.划分终态,非终态: P={{4,5,6,7},{1,2,3}}

    2.{4,5,6,7}内部能识别ab,不再划分,(成一个大的部门处理相同的事情

    3.{1,2,3} 根据识别a的能力,划分为{1,3}{2}1,3识别a都转到3

      根据识别b的能力,划分为{1} {3} {2}

    4.(此例不用考虑这条)删除死循环(即一个对所有输入符号都有到自身转换的非终态)和不可达状态

    结果P={{4,5,6,7},{1},{2},{3}}

    给四个划分再重新命名 变成1,2,3,4

    结果是:


    展开全文
  • 我们知道NFADFA的区别最主要的就是一个状态和一个inputsymbol是否能够确定一个状态的问题,对于NFA,它将确定一个组状态,而DFA将确定一个状态,因此,我们有一个很好的办法就是把NFA的状态集对应每个DFA的状态,...

    1. 子集构造(Subset Construction)

    这是一个转换NFA到DFA的算法。我们知道NFA和DFA的区别最主要的就是一个状态和一个input

    symbol是否能够确定一个状态的问题,对于NFA,它将确定一个组状态,而DFA将确定一个状态,因此,我们有一个很好的办法就是把NFA的状态集对应每个DFA的状态,这就是subset

    construction的思想,不过这只是大概泛泛而论,我们需要更加明确的认识

    1) NFA在任何一个input

    symbol下,映射的状态集(通过move函数,这个集合通常用T字母表示)应该被知道

    2) 必须保证1)中状态集都对应了DFA中的一个状态

    具体算法:

    Input : 一个NFA N

    Output : 接受相同语言的DFA D

    Method : 为D构架一个transition table(转换表)

    Dtran,每个DFA的状态是一个NFA的状态集合(这里一定要注意前面说过的1)2)两点)。我们定义一些操作:

    s 表示NFA的状态,T 表示NFA的状态集合,a表示一个input symbol

    ε-transition(ε转换)就是说input symbol为ε时的transition(转换)

    操作(operation)

    描述(description)

    ε-closure(s)

    从NFA的状态s出发,只通过ε-transition到达的NFA的状态集合

    ε-closure(T)

    NFA的集合T中的状态p,只通过ε-transition到达的NFA的状态集合,再求这些集合的交集。用数学表达就是 {p|p

    属于 ε-closure(t) , t属于T}

    move(T,a)

    NFA的集合,这个集合在input symbol为a,状态为T中任意状态情况下,通过一个转换得到的集合

    注意一下,所有的操作都是针对NFA的状态或者状态集合,得到的时NFA的状态集合,或者说是DFA看为一个状态

    Subset Construction

    初始Dstates,它仅仅含有状态(D的状态)ε-closure(s0),并且状态未被标记,s0表示开始状态,注意,Dstates放的是D的状态

    双击代码全选

    1

    2

    3

    4

    5

    6

    7

    8

    9

    while( Dstates 有未标记的状态 T ) {// T是D中的一个状态,也是N中一个状态集

    标记 T;

    for( input symbol a ){// 遍历所有的input symbol

    U = ε-closure(move(T, a));// move为NFA的move函数

    if( U 不在 Dstates 中 )

    把U作为尚未标记的状态加入Dstates;

    Dtran[T, a] = U

    }

    }

    注意,状态s,ε-closure(s)一定包含s

    我们先来熟悉上面的操作operation,再来看上面的算法

    a4c26d1e5885305701be709a3d33442f.png

    双击代码全选

    1

    2

    3

    4

    5

    6

    7

    8

    ε-closure(0) = {0, 1, 2, 4, 7}// 从0状态出发的,input symbol为ε的所有状态的集合

    ε-closure(3) = {1, 2, 3, 4, 6, 7}

    ε-closure(8) = {8}

    ε-closure( {3, 8} ) = ε-closure(3) U ε-closure(8) = {1, 2, 3, 4, 6, 7, 8}

    move(0,a) = 空

    move(7,a) = {8}

    move(8,b) = {9}

    move( {0, 1, 2, 4, 7}, a) = move(0,a) U move(1,a) U move(2,a) U move(4,a) U move(7,a) = {3, 8}

    现在可以回去理解一下算法了。

    这里再说说求ε-closure(T)的算法:

    双击代码全选

    1

    2

    3

    4

    5

    6

    7

    8

    9

    10

    11

    把T的所有状态压入stack(栈);

    ε-closure(T)的初始值为 T 中的所有元素 ;// 也就是一定包含他们本身

    while( 栈非空 ) {

    弹出栈顶元素 t ;

    for( 每个属于 move(t, ε) 的状态 u ){

    if( u 不在 ε-closure(T) 中 ){

    u 加入 ε-closure(T);

    把 u 入栈;

    }

    }

    }

    下面对上图如何使用Set Construction算法来构建DFA做一个详细的描述:

    1. 初始化Dstates 把集合 ε-closure(s0) = {0, 1, 2, 4, 7}作为第一个状态,设此状态为

    A

    2. 现在转化,input symbol {a, b},因此,求:

    ε-closure(move(A, a));

    ε-closure(move(A, b));

    这里会得到2个状态

    ε-closure(move(A, a)) = {1, 2, 3, 4, 6, 7, 8},设其为 B

    ε-closure(move(A, b)) = {1, 2, 4, 5, 6, 7}, 设其为C

    B,C放入Dstates

    改写 Dtrans

    最终得到的 Dtrans 为:

    A = {0, 1, 2, 4, 7}

    B = {1, 2, 3, 4, 6, 7, 8}

    C = {1, 2, 4, 5, 6, 7}

    D = {1, 2, 4, 5, 6, 7, 9}

    a4c26d1e5885305701be709a3d33442f.png

    因此,NFA转化成为DFA:

    a4c26d1e5885305701be709a3d33442f.png

    展开全文
  • 编译原理 从 NFADFA 的转换(非子集法)编译原理 | 从 NFADFA 的转换(非子集法)词法分析:从 NFADFA 的转换解题方法1. 写出 K’K’ 是 K 的全部子集,其中空集 Ø 可以剔除掉(即 K’ 为 K 的幂集)。注意...

    编译原理 从 NFA 到 DFA 的转换(非子集法)

    编译原理 | 从 NFA 到 DFA 的转换(非子集法)

    词法分析:从 NFA 到 DFA 的转换

    解题方法

    1. 写出 K’

    K’ 是 K 的全部子集,其中空集 Ø 可以剔除掉(即 K’ 为 K 的幂集)。注意这里 { } 要换成 [ ]。

    2. 求 VT’

    VT′=VT

    V_{T'}=V_TVT′?=VT?

    3. 求 S’

    S′=[S]

    S' = [S]S′=[S]

    4. 求 M’

    M′([S1,S2,…,Si],a)=[R1,R2,…,Rj]a∈VT

    M'([S_1,S_2,\dots\ ,S_i],a) = [R_1,R_2,\dots\ ,R_j] \quad a \in V_TM′([S1?,S2?,…,Si?],a)=[R1?,R2?,…,Rj?]a∈VT?

    看上去有点复杂,好像看不懂。没关系,看下面例题就懂了。

    5. 求 Z’

    Z′={[S1,S2,...,Sn]∣[S1,S2,…,Sn]∈K′且{S1,S2,…,Sn}∩Z≠?}

    Z' = \{[S_1,S_2,...,S_n] | [S_1,S_2,\dots\ ,S_n] \in K' 且 \{S_1,S_2,\dots\ ,S_n\} \cap\ Z \neq\ \varnothing\ \}Z′={[S1?,S2?,...,Sn?]∣[S1?,S2?,…,Sn?]∈K′且{S1?,S2?,…,Sn?}∩Z??=?}

    看上面公式很复杂,其实就是求 K’ 中含有 Z 的集合。

    6. 改写

    把 M’ 中的状态重命名一下,改写一下,画出 (DFA)M’ 的状态转换图。

    例题

    设 (NFA) M = ( {A, B}, {a, b}, M, {A}, {B} ) ,其中 M 定义如下:M (A, a) = {A, B} M (A, b) = {B} M (B, a) = ø M (B, b) = {A, B} 请构造相应确定有穷自动机 (DFA) M’。

    解:

    1. 写出 K’

    K’ 的元素是 [A] [B] [A, B]

    2. 求 VT’

    VT′={a,b}

    V_{T'}=\{a, b\}VT′?={a,b}

    3. 求 S’

    S′=[A]

    S' = [A]S′=[A]

    4. 求 M’

    由于 M(A, a)={A, B},故有 M’([A], a)=[A, B]

    同样 M’([A],b)=[B]

    M’([B],a)= ø

    M’([B],b)=[A,B]

    由于 M({A,B},a)= M(A,a)U M(B,a)= {A,B}U ø= {A,B}

    故 M’([A,B],a)= [A,B]

    由于 M({A,B},b)= M(A,b)U M(B,b)={B}U {A,B} = {A,B}

    故 M’([A,B],b)= [A,B]

    5. 求 Z’

    终态集 Z’={[A,B],[B]}

    6. 改写

    重新定义:令0=[A] 1=[B] 2=[A, B],则DFA如下所示:

    d7e54792340c3ce486bb69cb91b0db5f.png

    编译原理 从 NFA 到 DFA 的转换(非子集法)相关教程

    展开全文
  • NFA转化DFA

    2011-10-18 16:23:33
    NFA转化DFA可视化C++代码,用到OPENCV的东西
  • NFA转化DFA编译原理课程设计
  • NFADFA转化程序

    2016-10-29 11:25:49
    NFADFA转化程序,Java
  • 已知一个正则表达式,把它转化为nfa,nfa转化dfa,dfa最小化 用vc6.0完成的,可以立马用,很好很强大!
  • NFA构造及NFA转化DFA

    万次阅读 2014-03-25 13:29:39
    在前一篇文章DFA算法的实现与最小化中介绍了DFA,这篇文章将介绍NFA。 1. NFADFA的区别 NFADFA的主要区别如下: 1) 对于一个特定的符号输入,DFA只会跳转到一个状态;而NFA则可能跳转到多个状态。 2) NFA中一个...
  • NFA转化DFA

    千次阅读 2018-08-02 14:28:17
    NFA转化DFA  NFA转化DFA的一种常用方法是子集法。我是参照《编译原理及实践教程》来实现的。这里, 引用该书中内容来加以阐述。      直接看这些概念应该会很无聊,下面,引用该书中的一个例子,来加以...
  • 编写程序读取nfa.txt,构造出NFA的数据结构,并编写算法实现NFADFA转化
  • NFADFA转化

    万次阅读 多人点赞 2015-01-06 12:09:43
    首先将初始态的转换闭包ε-closure(0)设为状态A,即A={0,1,2,4,7},注意这里的状态A是DFA中的,和前面的状态0,1,2,3,4,5没有关系 接着写出状态A经过上面转换图中所有转换条件得到的状态, 后继状态里面不包括自身...
  • NFA构造DFA

    2013-10-28 08:29:11
    想法是将编译原理课程中由正规式到DFA转化,由于时间关系只做了NFADFA的转换,最主要的特色是将NFADFA的状态转化图画出来,还有转化过程的表格展示
  • 编译原理 NFA–>DFA 转载:
  • 从txt读取状态转换矩阵,输出DFA矩阵
  • 编译原理老师讲完NFA_DFA布置的作业,因为我是搞ACM的,这个题目用到的算法自己经常用,于是我就用bfs+dfs+状态压缩乱搞搞弄出个代码来,功能ok,100%原创,仅仅提供大家参考。这个是输出的表格部分,我们的程序还...
  • NFADFA转换

    2012-06-05 22:43:36
    NFADFA转换 存储NFADFA,编程实现子集构造法将NFA转换成DFA。 (1)确定NFADFA的存储格式,为3个以上测试NFA准备好存储文件。 (2)用C或JAVA语言编写将NFA转换成DFA的子集构造法的程序。 (3)经测试无误。...
  • NFA转化DFA的程序

    2008-10-27 12:52:32
    在编译原理中的fa转化算法及其程序!在文本中有我和前辈们的辛苦和汗水!希望大家喜欢,更希望能够对大家有一定的帮助!
  • NFADFA转化过程

    千次阅读 2021-04-07 16:29:12
    1.分别求ε-closure ε-closure(0) = {0,1,2,4,7} ε-closure(1) = {1,2,4} ... 注意:如果状态转换图中不含有ε,则无需求ε-closure,直接将NFA的开始状态集合作为DFA的开始状态,对于字母表中的字符进行标记即可。
  • PS:手边有离散数学的书,所以把离散数学那部分也看了一下,他那个转化 就是举了一个例子,其实那个例子并不是很好,就是他的NFA的起始状态就只有一个。 不过在看的过程中我就有疑问就是为什么转变成DFA之后,每一...
  • 不确定有穷自动机转换成确定的有穷自动机(NFADFA) 1.代码实现 __author__='PythonStriker' global NFA_StautsMatrix,DFA_StautsMatrix,StartWorld,EndWorld,\ StatusNumber,EnterNumber,EnterWorld,NFA_...
  • NFADFA之间的转化

    2019-09-30 10:53:59
    利用子集法,可以将NFA转化为与之等价的DFA。 记状态机$A$为 $$A = ( V,\sum,\delta,V_{N},V_{T} )$$ $\epsilon \_CLOSURE$的求法 假设我们要构造状态$I$的$\epsilon$_闭包,即$\epsilon \_CLOSURE(I)$。 基础:...
  • i want to write a program that convert nfa to dfa ,user draw a graph then Program convert it to dfa .how can i do it?解决方案You may want to take a look at this previous question for incites.as ...
  • 编译原理实验——将NFA转化DFA

    千次阅读 2011-12-08 18:32:42
    NFA转化DFA 1.实验目的 输入: 非确定有限(穷)状态自动机。 输出: 确定化的有限(穷)状态自动机 2.实验原理 采用子集对NFA转DFA。 (1) 若NFA的全部初态为S1,S2,…,Sn,则令DFA的...
  • (一)NFADFA(2小时) 实验目的 学习和掌握将NFA转为DFA的子集构造法。 实验任务 (1)存储NFADFA; (2)编程实现子集构造法将NFA转换成DFA。 实验内容 (1)确定NFADFA的存储格式。要求为3个以上测试NFA...
  • 编译原理NFA转化DFA

    千次阅读 2018-07-12 12:21:09
    使用列表法对文法进行转化将这个表作为程序的输入。输入样例为P117第六题。 #include&amp;amp;lt;bits/stdc++.h&amp;amp;gt; using namespace std; struct GRAM { //$代表空 string a; string b; ...
  • 简单记录一下,自动机课上的一个实验,用C语言实现NFADFA转化,使用的是子集构造法。 子集构造法相信大家都会,直接甩代码。 先是把NFA和DAF的转移表存储在数据结构里,这里用了二维字符数组,先是定义了一个...

空空如也

空空如也

1 2 3 4 5 ... 20
收藏数 1,113
精华内容 445
关键字:

nfa转化dfa