腾讯云
开发者社区
文档
建议反馈
控制台
首页
学习
活动
专区
工具
TVP
最新优惠活动
文章/答案/技术大牛
搜索
搜索
关闭
发布
登录/注册
精选内容/技术社群/优惠产品,
尽在小程序
立即前往
文章
问答
(9999+)
视频
沙龙
2
回答
语言{⟨A⟩⟩A是NFA和L(A)={0,1}∗}可判定吗?可判定的?
computer-science
、
turing-machines
、
decidable
如何证明/否定语言{⟨A,⟩,⟩,A是NFA,L(A)={0,1}∗}是/不可判定的?
浏览 0
提问于2018-03-02
得票数 1
回答已采纳
1
回答
Knuth-Morris-Pratt
算法
中的
DFA
构造
string
、
algorithm
、
substring
、
dfa
、
knuth-morris-pratt
我指的是Sedgewick的书“
算法
”(第4版)中用于子字符串搜索的Knuth Pratt (KMP)
算法
的大纲。
dfa
[pat.charAt(0)][0] = 1; for (int c = 0; c < R;
浏览 3
提问于2015-05-30
得票数 13
回答已采纳
2
回答
KMP
DFA
重新启动状态
java
、
string
、
algorithm
、
dfa
、
knuth-morris-pratt
我指的是“Sedgewick &Wyane的
算法
第四版”第五章字符串匹配。public KMP(String pat) { this.pat = pat; int m = pat.length();
dfa
浏览 6
提问于2020-04-01
得票数 2
2
回答
DFA
最小化Brzozowski
算法
c++
、
algorithm
、
dfa
、
nfa
、
automaton
我正在尝试实现Brzozowski的
算法
来最小化我的
DFA
,下面是同样的
算法
。其中r()是NFA的反转,D()将NFA转换为
DFA
。任何其他简单的
算法
或C++实现,请让我知道链接。
浏览 0
提问于2011-05-05
得票数 3
回答已采纳
1
回答
这种基于
DFA
的KMP实现是否比标准实现更有效?
java
、
string
、
search
这个基于确定性有限状态自动机的KMP
算法
的复杂度是多少?它是否比标准的、非自动机版本的KMP
算法
更有效?class KMP { private int[][]
dfa
; this.R = 256;
dfa
=new int[R][M]; <
浏览 0
提问于2011-04-12
得票数 1
1
回答
确定非确定性有限自动机是否接受所有可能的字符串
math
、
computer-science
、
nfa
、
automaton
、
computer-science-theory
给定一个NFA,有没有一种方法可以确定它是否接受从它的字母表构造的所有字符串,而不必迭代可能的字符串的无限集合?
浏览 2
提问于2020-05-01
得票数 2
3
回答
检查两个最小
DFA
是否等效
regex
、
regular-language
、
finite-automata
、
automata
、
dfa
我有2个最小化的
DFA
,我需要检查它们是否等效。 如果它们是等价的,那么问题是要找到状态的有效比较,而不管不同的标签。在我的例子中,
DFA
是表,那么我需要找到匹配第一个
DFA
行和第二个
DFA
行的置换。我还想先对
DFA
进行广度搜索,然后创建状态的最小访问字符串,然后将第一个列表与第二个列表进行比较(这应该与特定的输入无关,例如: 001和110可以互换)。我对直接和低效
算法
以及更复杂的
算法
都很感兴趣。
浏览 4
提问于2015-04-23
得票数 1
回答已采纳
2
回答
如果一种语言(L)是由n状态NFA识别的,那么它是否也可以被状态不超过2^n的
DFA
识别?
deterministic
、
automata
、
dfa
、
nfa
我是这么认为的,因为上限是2^n,并且假设这两个机器都是有限的机器,那么n状态NFA和具有2^n或更少状态的
DFA
的交集将是有效的。 我说错了吗?
浏览 3
提问于2010-10-15
得票数 3
1
回答
关于自动机最小化的不确定性
minimize
、
finite-automata
我不得不最小化一些有限状态自动机,但我生来就有疑问:在这种转换之前,自动机必须证明是ε-productions?或者我可以离开他们?
浏览 1
提问于2014-08-10
得票数 0
3
回答
什么是McNaughton-Yamada
算法
?
algorithm
、
computer-science
、
finite-automata
、
dfa
我需要使用McNaughton-Yamada
算法
为CS类构造一个
DFA
。问题是
算法
是补充材料,我不清楚它到底是什么。它是一种在给定RegEx的情况下查找
DFA
的方法,还是查找
DFA
加上最小化它的方法?我之所以感到困惑,是因为我们在课堂上发现
DFA
后,我的导师展示的最小化例程似乎与我们的中描述的“分数”最小化没有任何不同。内森
浏览 4
提问于2011-03-10
得票数 2
回答已采纳
1
回答
如何确定一个正则表达式是否是另一个正则表达式的子集?
regex
、
computation-theory
、
fsm
给出两个正则表达式,A= 0*1* U1**和B= (01 U 10)*,如何确定其中一个是另一个的子集。我想一种方法是列举一些例子,看看它们是否有什么共同之处。在本例中,我看到字符串01、10在这两个集合中共享。所以他们不是彼此的子集??我如何知道一个正则表达式是另一个正则表达式的子集?一般来说,你是如何处理这样的问题的?
浏览 0
提问于2018-08-29
得票数 3
回答已采纳
2
回答
给定一系列符号,如何找到可以接受它的最小
DFA
?
regex
、
pattern-matching
、
regular-language
、
fsm
、
dfa
例如:给定下面的符号序列,可以接受它的最简单的
DFA
是由17个状态组成的链。而下面的正则表达式可以推导出上面的序列:并且相应的最小
DFA
具有8个状态。此外,正则表达式a ((b c)* (d)*)* e具有更小的4个状态的最小
DFA
。并且它可以接受示例序列。在上面的示例中,我只考虑了
DFA
运算符;更一般的情况下,也可以考虑使用运算符|来减小*大小。给定一系列符号,如何找到可
浏览 3
提问于2012-10-19
得票数 2
回答已采纳
1
回答
生成具有死态或多余状态的
DFA
的正则表达式
regex
、
dfa
、
nfa
我希望在我的lexer中实现一个
DFA
最小化器,但是我似乎不能产生一个看起来不像已经是表达式的最小
DFA
的
DFA
。那么,是否有任何“已知”正则表达式将生成一个
DFA
,这将为死状态消除和状态最小化提供一个很好的测试平台?当然,我可以破解一个奇怪的
DFA
并将
算法
应用到它上,但是它并不是一个真正合适的测试用例,对吗?
浏览 0
提问于2012-02-20
得票数 8
回答已采纳
3
回答
NFA相对于
DFA
的优势/劣势,反之亦然
finite-automata
、
dfa
、
state-machine
、
nfa
DFA
和NFA的相对优势和劣势是什么? 我知道
DFA
比NFA更容易实现,NFA比
DFA
到达接受状态的速度更慢,但是有没有其他明确的,众所周知的优点/缺点呢?
浏览 1
提问于2011-05-11
得票数 3
回答已采纳
1
回答
如何实现最大吞吐?
regex
、
parsing
、
unix
、
compiler-construction
、
flex-lexer
我正在进一步了解如何将正则表达式转换为NFA,然后将其转换为
DFA
,在那里可以快速地对其进行评估。 然而,我的问题是,最大吞咽规则是如何实现的?
浏览 2
提问于2013-11-22
得票数 6
1
回答
如何理解KMP
算法
中
DFA
的构造过程
algorithm
、
substring
、
automaton
我正在学习图书
算法
4中的KMP
算法
。我可以理解大部分的
算法
,但在
dfa
的建设过程中被困了几天。 例如,要决定在j=5不匹配时
DFA
应该做什么,对于ABABAC,我们使用
DFA
来了解完全备份将使我们处于BABA的状态3,这样我们就可以将
dfa
[][3]复制到
dfa
[][5]
浏览 1
提问于2016-04-30
得票数 3
回答已采纳
1
回答
flex/lex分析器发生器:
DFA
最小化
flex-lexer
、
lex
flex或lex是否执行
DFA
最小化? #include <stdio.h>a printf("a\n");%%{states: [0, 1, 2], {from: 0, char:
浏览 0
提问于2015-10-28
得票数 1
回答已采纳
4
回答
是否有一种
算法
可以确定一种常规语言是否与另一种常规语言匹配的输入匹配?
regex
、
computer-science
、
theory
假设我们有正则表达式:我希望最小化匹配任意输入所需的正则表达式的数量。Billy3
浏览 37
提问于2010-09-03
得票数 19
回答已采纳
1
回答
NFA
DFA
和Regex转换表
regex
、
dfa
、
nfa
我一直在寻找一些
算法
,它输入了正则表达式或字符串,并将其转换为NFA,然后转换为
DFA
,并实际打印出相应的最终
DFA
的转换表。因此,我想知道是否已经有一个
算法
、C或Python库可以这样做,或者您是否可以使用我可以实现的
算法
建议。 谢谢。
浏览 2
提问于2013-10-20
得票数 5
回答已采纳
1
回答
Knuth Pratt
算法
DFA
基于?
algorithm
、
dfa
、
knuth
我想学习Knuth Pratt
算法
是如何工作的。我看了普林斯顿大学的这篇教程。在这个视频中,他们使用一个表格,其中包含字母表的长度=行数和模式的长度=列数。将表作为
DFA
查看,
DFA
用于检测文本中的模式。我认为这种方法很有趣,但是Wikipedia说Knuth Pratt
算法
使用前缀表,前缀的长度只有一行。但是
DFA
版本需要更多的空间。但问题是哪一个是真正的Knuth Pratt
算法
,哪个是微分?
浏览 1
提问于2014-10-04
得票数 5
回答已采纳
点击加载更多
扫码
添加站长 进交流群
领取专属
10元无门槛券
手把手带您无忧上云
相关
资讯
js与算法
前端进阶: 总结几个常用的 JS 搜索算法和性能对比
柔性多模正则匹配引擎
百度AI算法LinearDesign已发表论文
js高级
热门
标签
更多标签
云服务器
即时通信 IM
ICP备案
对象存储
实时音视频
活动推荐
运营活动
广告
关闭
领券