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

    2016-04-16 20:20:00
    NFA 任意正则表达式都存在一个与之对应的NFA,反之亦然. 正则表达式 ((A*B|AC)D)对应的NFA(有向图), 其中红线对应的为该状态的ε转换, 黑线表示匹配转换 我们定义的NFA具有以下特点: 正则...
    NFA

    任意正则表达式都存在一个与之对应的NFA,反之亦然.

    正则表达式 ((A*B|AC)D)对应的NFA(有向图), 其中红线对应的为该状态的ε转换, 黑线表示匹配转换

    clipboard

    我们定义的NFA具有以下特点:

    • 正则表达式中的每个字符在NFA中都有且只有一个对应状态,NFA的其实状态为0,并包含一个虚拟的接收状态
    • 正则表达式中的字母所对应的状态都有一条从它指出的黑色的边,并且一个状态只能有一条指出的黑色边
    • 正则表达式中的元字符所对应的状态至少含有一条指出的红色的边

    ε转换

    不需要扫描匹配文本中的任意字符,自动机就可以从一个状态转换到另一状态

    使用 NFA模拟匹配过程:

    • 首先获取初始状态通过ε转换可以到达的所有状态集合,上图为0,1,2,3,4,6
    • 顺序扫描匹配文本中的字符,如果状态集合中找到匹配该字符的状态(可以使多个),自动机就可以扫过该字符并由黑色的边转到下一个状态,这种转换成为匹配转换,由下一状态及下一状态的的ε转换生成新的状态集合,继续扫描下一个字符
    • 扫描完所有字符后,如果最终到达的所有状态中包含接受状态,则匹配该字符串

    源代码namespace NFA
    {
        public class IntList : List<int>
        {
        }
    
        public class Digraph
        {
            public int E { get; set; }
            public int V { get; set; }
            public IntList[] Adjs { get; set; }
    
            public Digraph(int v)
            {
                this.V = v;
                this.E = 0;
                Adjs = new IntList[v];
                for (int i = 0; i < v; i++)
                {
                    Adjs[i] = new IntList();
                }
            }
    
            public void AddEdge(int from, int to)
            {
                Adjs[from].Add(to);
                E++;
            }
    
            public IntList Adj(int index)
            {
                return Adjs[index];
            }
        }
    
        public class DirectedDFS
        {
            public bool[] Marked;
            public DirectedDFS(Digraph g, int s)
            {
                Marked = new bool[g.V];
                Dfs(g, 0);
            }
    
            public DirectedDFS(Digraph g, List<int> source)
            {
                Marked = new bool[g.V];
                source.ForEach(x =>
                    {
                        if (!Marked[x])
                        {
                            Dfs(g, x);
                        }
                    });
            }
    
            public void Dfs(Digraph g, int v)
            {
                Marked[v] = true;
                g.Adjs[v].ForEach(x =>
                    {
                        if (!Marked[x])
                        {
                            Dfs(g, x);
                        }
                    });
            }
        }
    }
    
    namespace NFA
    {
        public class NFA
        {
            private string regex;
            //NFA的ε转换有向图
            private Digraph G;
    
            public NFA(string reg)
            {
                this.regex = reg;
                Stack<int> ops = new Stack<int>();
                int M = regex.Length;
                G = new Digraph(M+1);
                //循环状态
                for (int i = 0; i < M; i++)
                {
                    int lp = i;
                    if (regex[i] == '(' || regex[i] == '|')
                    {
                        ops.Push(i);
                    }
                    else if (regex[i] == ')')
                    {
                        int or = ops.Pop();
                        if (regex[or] == '|')
                        {
                            lp = ops.Pop();
                            G.AddEdge(lp, or + 1);
                            G.AddEdge(or, i);
                        }
                        else
                        {
                            lp = or;
                        }
                    }
                    if(i<M-1 && regex[i+1] == '*')
                    {
                        G.AddEdge(lp,i+1);
                        G.AddEdge(i + 1, lp);
                    }
                    if (regex[i] == '(' || regex[i] == '*' || regex[i] == ')')
                    {
                        G.AddEdge(i, i + 1);
                    }
                }
            }
    
            public bool Recognize(string txt)
            {
                List<int> pc = new List<int>();                   
                DirectedDFS dfs = new DirectedDFS(G, 0);
    
                for (int i = 0; i < G.V; i++)
                {
                    if (dfs.Marked[i])
                    {
                        pc.Add(i);
                    }
                }
    
                for (int i = 0; i < txt.Length; i++)
                {
                    List<int> match = new List<int>();
                    foreach (int v in pc)
                    {
                        if (v < regex.Length)
                        {
                            if (regex[v] == txt[i] || regex[v] == '.')
                            {
                                match.Add(v + 1);
                            }
                        }
                    }
                    pc = new List<int>();
                    dfs = new DirectedDFS(G, match);
    
                    for (int v = 0; v < G.V; v++)
                    {
                        if (dfs.Marked[v])
                        {
                            pc.Add(v);
                        }
                    }                
                }
                foreach (int v in pc)
                {
                    if (v == regex.Length)
                    {
                        return true;
                    }
                }
                return false;
            }
        }
    }
    posted on 2016-04-16 20:20 哨兵 阅读( ...) 评论( ...) 编辑 收藏

    转载于:https://www.cnblogs.com/phenixyu/p/5399243.html

    展开全文
  • NFA032:NFA032-源码

    2021-06-15 10:47:14
    NFA032 练习 NFA032
  • 本代码包含NFA与DFA的表示,NFA 转 DFA,DFA最小化,NFA与DFA语言子集等。
  • Java把一个正则表达式转化为不确定的有穷自动机NFA算法
  • NFA019-源码

    2021-03-29 01:58:31
    NFA019
  • 用JAVA写的一个将正则表达式转换为NFA的代码,基于Thompson算法的思想,递归构建NFA。jar为源码文件。 输出非确定有限自动状态机的有向图。如正则表达式: c(a|b)NFA为:0-c->1-ep->2-a->3-ep->7 ,0-c->1-ep->4-b->5-...
  • NFA算法

    千次阅读 2019-04-27 19:59:16
     NFA 和 DFA浅析---要深入了解正则表达式,必须首先理解有穷自动机。 有穷自动机(Finite Automate)是用来模拟实物系统的数学模型,它包括如下五个部分: 有穷状态集States 输入字符集Input symbols 转移...

    1、问题概述

      NFA 和 DFA浅析---要深入了解正则表达式,必须首先理解有穷自动机。

    有穷自动机(Finite Automate)是用来模拟实物系统的数学模型,它包括如下五个部分:

      • 有穷状态集States
      • 输入字符集Input symbols
      • 转移函数Transitions
      • 起始状态Start state
      • 接受状态Accepting state(s)(终止状态)

      下图为一台有穷自动机

      

      可以看到,该自动机包含四个状态(有限状态)q0, q1, q2, q3,两个输入字符a, b,转移函数如图所示,起始状态为q0,接受状态为q3。

      有穷自动机,按照转移函数的不同,又可分为确定型有穷自动机(Determinism Finite Automate, DFA),与非确定型有穷自动机(Non-determinism Finite Automate, NFA)
      非确定有穷自动机容许转移函数不确定,换句话说,对任意状态,输入任意一个字符,可以转移到0个,1个或者多个状态。

      下图是一台非确定有穷自动机,可以看到,对状态q0输入字符a,既可以转移到q0,也可以转移到q1,这就是“非确定”的意义所在。

      对某个自动机来说,如果从起始状态,接受一系列输入字符,可以转移到接受状态,即认为这一系列字符可以被自动机接受。
      如果两台自动机能够接受的输入字符串(或者叫做“正则语言”Regular Language)完全相同,则这两台自动机是等价的。可以证明,对于每一个非确定有穷自动机,都存在与之等价的确定型有穷自动机(证明略)。

      正则表达式就是建立在自动机的理论基础上的:用户写完正则表达式之后,正则引擎会按照这个表达式构建相应的自动机(可能是NFA,也可能是DFA,但它们必定是等价的),若输入一串文本之后,自动机抵达了接受状态,则这串文本可以“匹配”用户指定的正则表达式。

      下面是同一个正则表达式 a|ab 对应的NFA和DFA

      

      在Mastering Regular Expression中,Friedl首先分析了NFA和DFA的区别,DFA比较快,但不提供Backtrack(回溯)功能,NFA比较慢,但提供了Backtrack功能

      在分析两种引擎的匹配过程时,Friedl指出,NFA是基于表达式的(Regex-Directed),而DFA是基于文本的(Text-Directed)。

      举例来说,对于正则表达式 to(nite|knight|night),NFA在匹配最开始两个字符(to)之后,剩下的三个组件(component)是 nite, knight 和 night,于是正则引擎会依次尝试这三个选择分支(每次尝试一个);而DFA在匹配最开始两个字符之后,会将剩下的三个选择拆分作字符,并行尝试,也就是说,匹配 to 之后,先匹配 k 或者 n ,如果 k 不能匹配,则放弃 knigth 所在的分支,再匹配 i ,再匹配 t 或 g ……这样继续下去,直到匹配结束。

      不幸的是,Friedl对匹配过程的分析,是完全错误的——引擎的不同,是指构建的自动机的不同,而不是匹配算法的不同!

      DFA引擎在任意时刻必定处于某个确定的状态,而NFA引擎可能处于一组状态之中的任何一个,所以,NFA引擎必须记录所有的可能路径(trace multiple possible routes through the NFA),NFA之所以能够提供Backtrack的功能,原因就在这里。
      传统的NFA匹配算法是带回溯的深度优先搜索(backtracking depth-first search,就是上文所说的Regex-Based过程),而新的PCRE算法提供了效率更高的广度优先搜索,可以同时保持所有可能的NFA状态(请参考http://www.cl.cam.ac.uk/Teaching/current/RLFA/,尤其是Lecture Notes的section 2.2)。

      Friedl的错误就在这里,他混淆了应用PCRE算法的NFA与DFA的匹配过程。需 要指出的是,即使应用PCRE算法,NFA的速度仍然低于DFA,这是由NFA需要同时保存多种可能的性质决定的。从理论上说,如果我们不需要应用 Backtrack,完全可以从NFA构造出等价的DFA,再进行匹配,这样能大大提高速度——代价是,DFA需要更多的空间。

    原文地址:http://www.cnblogs.com/u2usoft/archive/2006/06/06/419003.html

    endl;

    参考网址:

      http://blog.csdn.net/yukuninfoaxiom/article/details/6057736

    标签: DFT/NFT

    展开全文
  • Rexg2NFA.zip

    2021-04-16 12:44:19
    正规式转NFA程序 平台:qt4.0,ubuntu18.04 语言:c++ 全中文注释过程。
  • NFA 到正则表达式 将 NFA 转换为 RE 的程序 由 Amir Hosein Fadaei 和 Shayan Sadr-Ol-Eslami 撰写 这是一个将 NFA 转换为正则表达式的非常简单的演示... 图形:使用SFML 2.1。 有关更多信息,请参阅 电子邮件:
  • RE2NFA-Lisp 将正则表达式转换为NFA的通用Lisp程序
  • 基于Java实现了DFA,NFA,DFA最小化,NFA转化为DFA以及正则表达式转化为NFA的算法,对于初学者来说,是学习词法分析的一份不错资源
  • 实验室1_NFA 实验室1-计算机理论 申请NFA 该组的每个成员都将在Branches文件夹中创建一个分支,并在该文件夹中创建将使用的文件。 Seguir los siguientes pasos: Instalar git: https://git-scm.com/downloads/ Ir...
  • 从具有epsilon的不确定有限状态自动机(NFA)得到一个无Epsilon 的NFA。 2.思路 Epsilon-NFANFA的目标主要是产生一个没有Epsilon边的,跟原状态图等价的新状态图。过程不复杂,首先从起始状态开始,寻找所有...

    1.任务要求

    从具有epsilon的不确定有限状态自动机(NFA)得到一个无Epsilon 的NFA。

    2.思路

    Epsilon-NFA到NFA的目标主要是产生一个没有Epsilon边的,跟原状态图等价的新状态图。过程不复杂,首先从起始状态开始,寻找所有Epsilons边到达的对象的集合,然后复制这个集合的所有状态包含的非Epsilon状态。其实状态做完之后,寻找所有能够产生非Epsilon边的状态然后重复这个过程,最后NFA就出来了。

    其本质就是使用无Epsilon的状态转换函数中的条件去替换有Epsilon的状态转换函数中的Epsilon,不断循环,最终实现NFA中的条件无Epsilon。

    global nfa
    nfa = parser.parse_fa()
    closures = parser.parse_closures()
    # TODO: implement this
    
    print(",".join(nfa['states']))
    print(",".join(nfa['alphabet']))
    print(nfa['start'])
    print(",".join(nfa['final']))
    
    global dfa
    dfa = {}
    dfa['delta'] = []
    dfa['final'] = nfa['final']
    
    start = nfa['start']
    start_e = closures[start]
    
    begin = nfa['start']
    alpha = nfa['alphabet']
    delta = nfa['delta']
    final = nfa['final']
    
    
    # seach all relations can arrive from a ,and m  is means the intermediate variable
    # it means if a->b and b->c, then we van get a->c
    def search(a, m, delta, closures):
        for re in closures[a]:
            for relation in delta:
                s, c, t = relation
                if re == s:
                    if ((a, c, t)) not in h:
                        h.append((a, c, t))
    global h
    # get others delta by adding a search function
    for relation in delta:
        s, c, t = relation
        if c:
            dfa['delta'].append((s, c, t))
            
    h = dfa['delta']
    
    for a in nfa['states']:
        search(a, a, dfa['delta'], closures)
    
    for a in nfa['states']:
        for re in h:
            s, c, t = re
            if s == a:
                print("{},{},{}".format(s, c, t))
                
    print("end")
    
    

    4.结果

    输入:

    在这里插入图片描述

    输出:

    在这里插入图片描述

    展开全文
  • NFA转DFA-源码

    2021-03-02 19:38:16
    NFA转DFA 该项目用于构建可以将NFA转换为DFA的计算机。 还提供了示例输入和输出文件。
  • NFA转DFA实验代码

    2018-12-10 14:21:30
    该DFA使用它的状态去记录在NFA读入一个输入符号后可能到达的所有状态,也就是说,在读入符号串a1a2a3…an之后,该DFA处在这样一个状态,该状态表示这个NFA的状态的一个子集T,而T是从NFA的开始状态沿着某个标记为a1a2a3...
  • NFA构造DFA

    2013-10-28 08:29:11
    想法是将编译原理课程中由正规式到DFA转化,由于时间关系只做了NFA到DFA的转换,最主要的特色是将NFA和DFA的状态转化图画出来,还有转化过程的表格展示
  • DFA,NFA实现

    热门讨论 2014-03-24 23:01:59
    实现了DFA,NFA算法,DFA最小化,NFA转化为DFA以及正则表达式转化为NFA的算法,是有限状态自动机的初学者很不错的学习资源
  • NFA确定化,NFA转DFA

    2010-04-26 09:44:09
    用C++写的NFA到DFA的转换过程,有详细的步骤及必要的注释。
  • DFA NFA

    2018-11-10 13:23:00
    如果不用 DFA, NFA,我觉得也是可以处理编译过程的,一个字符一个字符的读入,并结合上下文,来确定 token 转载于:https://www.cnblogs.com/sky-view/p/9939126.html...

    如果不用 DFA, NFA,我觉得也是可以处理编译过程的,一个字符一个字符的读入,并结合上下文,来确定 token

    转载于:https://www.cnblogs.com/sky-view/p/9939126.html

    展开全文
  • NFA构造及NFA转化为DFA

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

    万次阅读 热门讨论 2018-02-08 12:26:38
    NFA转DFA的算法在编译原理的课本上都有,只不过课本上的算法太拗口,不好记!我在这里边说的都很通俗,只要看得懂字的都会懂。在本篇文章里用一个例子来说明怎么实现NFA转DFA与DFA简化,NFA转DFA会讲的比较细,DFA...
  • BUPT 自动机实验,NFA转化DFA,java代码加实验报告
  • Nfa-To-Dfa-源码

    2021-03-27 22:55:30
    Nfa至Dfa
  • 正则表达式转NFA

    2015-07-09 17:40:39
    课程设计 正规式构造nfa.这是编译原理的一个实验, 是把一个正则表达式转化为不确定有穷自动机NFA的算法程序,朋兴趣的朋友可以下载来看看哦。
  • lex输入文件解析,正则转化为NFANFA转化为1DFA
  • NFA转换DFA的C++程序

    2017-12-30 14:30:53
    输入为NFA的转换表,输出DFA的转换表,c++实现,子集构造算法。 输入为NFA的转换表,输出DFA的转换表,c++实现,子集构造算法。 输入为NFA的转换表,输出DFA的转换表,c++实现,子集构造算法。 输入为NFA的转换表,...
  • NFA确定化为DFA

    2015-10-28 22:33:48
    使用JAVA实现编译原理的NFA确定化为DFA的文档报告和java源代码
  • NFA--DFAmin

    2013-09-01 17:04:01
    用Thompson算法实现正则表达式到NFA的转化 这里使用了示性函数来表示NFA的转换矩阵 再由NFA >DFA 最后进行DFA的最小化
  • DFA和NFA

    2018-11-09 00:19:25
    DFA和NFA

空空如也

空空如也

1 2 3 4 5 ... 20
收藏数 7,362
精华内容 2,944
关键字:

NFA