从NFA到DFA的转换正确吗？

文章/答案/技术大牛

发布

3回答

NFA相对于DFA的优势/劣势，反之亦然

finite-automata、dfa、state-machine、nfa

DFA和NFA的相对优势和劣势是什么？我知道DFA比NFA更容易实现，NFA比DFA到达接受状态的速度更慢，但是有没有其他明确的，众所周知的优点/缺点呢？

浏览 1提问于2011-05-11得票数 3

回答已采纳

1回答

dfa、nfa、automaton

我正在为一次考试而复习，并完成了图片中的这项任务。通常，从NFA到DFA的转换对我来说很容易。我从NFA创建了一个转换表，对于每个“新的”组合状态，我创建了一个新的列，依此类推(查看我的try可以更好地解释它) ? ? 不知何故，我对q3的单一状态持怀疑态度。由于任何状态都不能达到单个q3，这有意义吗？

浏览 21提问于2019-08-23得票数 3

1回答

与NFA和DFA并行正则匹配？哪个更快？

regex、parallel-processing、computer-science、dfa、nfa

我读过关于NFA和DFA的文章，似乎实现regex匹配器的最流行和最快的方法是从regex创建NFA，将其转换为DFA，最小化DFA，以任何语言实现它并使用它。DFA是一个比NFA更好的选择，因为它只有一个输入的转换，而NFA可以有很多。因此，DFA只有一条路可走，而NFA

浏览 2提问于2016-06-17得票数 3

回答已采纳

1回答

转换给定的NFA

automata、dfa、nfa

问题)Σ={a，b}和NFA如下图所示：我为nfa和dfa做了一个转换表，但是不知道q2应该去哪里，或者是q0，或者创建一个名为q4的新状态

浏览 0提问于2019-05-21得票数 1

1回答

NFA DFA和Regex转换表

regex、dfa、nfa

我一直在寻找一些算法，它输入了正则表达式或字符串，并将其转换为NFA，然后转换为DFA，并实际打印出相应的最终DFA的转换表。因此，我想知道是否已经有一个算法、C或Python库可以这样做，或者您是否可以使用我可以实现的算法建议。谢谢。

浏览 2提问于2013-10-20得票数 5

回答已采纳

1回答

NFA在编译器设计中的意义

compiler、theory

在我研究编译器设计的时候，它告诉我，在设计像DFA或NFA这样的词法分析器时，我们需要“有限自动机”。因此，我想知道NFA是否只用于(正则表达式转换为NFA，然后转换为DFA)。实现NFA是可能的吗？或者NFA的使用是因为它比DFA更有效？

浏览 0提问于2014-11-15得票数 0

1回答

在非确定性有限自动机中，ɛ-跃迁是如何工作的？

automata、nfa

如果存在ɛ转换，自动机会直接进入下一个状态吗？假设我有一个自动机，由三个状态a、b和c组成(其中a是初始状态，c是接受状态)，字母表{0,1}。以下内容是如何工作的？a----ɛ--->(b----0---->a)接受字符串"1“吗？如果我们有？字符串"1“会被接受吗？

浏览 3提问于2015-01-09得票数 2

回答已采纳

3回答

NFA到DFA转换的简洁描述？

algorithm、finite-automata、dfa、nfa

有人能比我简单地向SO社区描述NFA到DFA转换算法吗？(最好是500字或以下。)我见过图表和讲座，这只会让我以为我曾经知道的东西变得混乱。我对从状态图生成初始NFA转换表很有信心，但在那之后，我在epsilons和子集中丢失了DFA。 1)在转换(delta)表中，哪一列表示新的DFA状态？它是生成状态的第一列吗？( 2)在下

浏览 4提问于2010-12-15得票数 8

回答已采纳

1回答

DFA还是NFA？

automata、dfa、nfa

NFA与DFA类似，但有以下其他特性：这个说法正确吗?如果是的话，那么当我们已经有DFAs时，NFAs的需要是什么呢？

浏览 3提问于2017-08-27得票数 1

2回答

库来检查两个正则表达式是否相等/同构

c++、python、c、regex、nfa

我需要一个库，它将接受两个正则表达式并确定它们是否同构(即，精确匹配同一组字符串集)，例如a|b与ab同构据我所知，正则表达式可以转换为NFA，在某些情况下，NFA可以有效地转换为DFA。然后可以将DFA转换为最小DFA，如果我理解正确的话，它是唯一的，因此可以比较这些最小DFA是否相等。我意识到并不是所有的正则表达式NFA都可以有效地转换为<

浏览 0提问于2012-03-08得票数 25

回答已采纳

1回答

如何用相同的西格玛索引对其键定义一定的值？

python

如果σ的某些指标等于转换的值，则在dfa字典中用σ键设置开始状态值的转换。Q1 = []print(Q1) if nfa

浏览 5提问于2021-12-31得票数 0

1回答

将正则表达式转换为有限状态机

python、regex、state-machine、fsm

你对将任何正则表达式转换成有限状态机的算法有什么建议吗？例如，解析regexp并将状态适当地添加到fsm的算法？有什么参考或更深层次的想法吗？感谢并致以问候

浏览 2提问于2012-07-11得票数 5

回答已采纳

2回答

为什么使用NFA而不是DFA

regex、dfa、computation-theory、compiler-theory、nfa

我目前正在研究一些计算理论，正如所暗示的那样，这是非常理论的。我可以很容易地将正则表达式转换为NFA，我可以理解这一点。但是由于所有的NFA都可以转换为DFA，并且(我非常确定) UNIX中的grep命令使用正则表达式来确定匹配的字符串，那么最常用的有限自动机、DFA还是NFA是什么呢？根据我的经验(不是很多)，DFA在表示常规语言时通常要简单

浏览 7提问于2015-10-21得票数 3

1回答

具有多个启动状态的NFA到DFA转换

regex、dfa、nfa

因此，我可以采取一个给定的NFA与一个单一的开始状态，并将它转换成一个等价的DFA相当容易，然而，当我遇到一个NFA与多个启动状态。由于DFA只能有一个开始状态(如果我是正确的)，那么我如何知道NFA中的两个开始状态中的哪一个会成为DFA中唯一的开始状态。作为参考，这是我试图转换的NF

浏览 2提问于2014-06-02得票数 3

回答已采纳

3回答

“{a，b}上字符串的奇数语言”的正则表达式

regex、regular-language、finite-automata、dfa

我想做正则表达式，其中有偶数的b's和奇数的a's，也有DFA和NFA，因此我在DFA下面做了问题：我做的是正确的DFA<

浏览 4提问于2015-04-27得票数 1

1回答

比较非确定性和FA、PDA和TM的确定性表达能力

computation-theory、deterministic、non-deterministic

非确定性FA，PDA，TM确定性FA，PDA，TM:这是我感到困惑的地方。作为一个整体：？DFA = NFA = e-NFA = RE < DPDA < NPDA = NCFL = DCFL < NTM = DTM? 请纠正我，还是我是对的？

浏览 10提问于2017-12-14得票数 0

1回答

语言的NFA到*DFA的转换(111+11111)

regular-language、finite-automata、computation-theory、dfa、nfa

 我已经为该语言(111+11111)*构建了NFA。之后，我试图将其转换为DFA，但我被卡住了。请任何人都可以提供给定的NFA到DFA的一步一步的转换。

浏览 0提问于2018-03-25得票数 0

1回答

将此从NFA转换为DFA

dfa、nfa

构造一个与以下NFA等价的DFA (字母为{a，b})：我的转换如下，但它似乎是错误的，你能帮我解释一下为什么吗？ 

浏览 0提问于2018-09-23得票数 0

1回答

这个NFA到DFA的转换让我很困惑。

finite-automata

我想把这个NFA转换成DFA。我有NFA和DFA的过渡表：然后，我尝试为空字符串设置不同的状态。但无论我做什么，我都会得到一个不适用于原始NFA的DFA。我有点过分绕圈了，有人能告诉我我做错了什么吗？

浏览 2提问于2017-03-12得票数 1

3回答

有限状态自动机的构造

compiler、grammar、regular-expressions

问题是：A-Z+"_"A-Z+"

浏览 0提问于2013-01-03得票数 5

点击加载更多

NFA相对于DFA的优势/劣势，反之亦然