dfa

0热度

1回答

对于Σ= {a，b，c，d，e，...，z}，考虑单词w的集合L，使得w的最后一个符号没有出现过。例如，苹果，谷歌，k和ε这两个词在L中，但马铃薯和营养词不在L.假设我们要为这种语言构建一个DFA。它会有多少个州（最低限度）？简洁地描述DFA：不要尝试绘制它，而是使用合适的数学符号解释它的形式定义（例如状态和转换）。我不需要整个定义，只是一个开始，它会有多少个状态以及为什么。从那里我很聪明，我可

0热度

1回答

所有最终状态都可以从DFA的起始状态中获得吗？

假设DFA D是有效的DFA。这意味着从初始状态到最终状态的可达性是什么？我可以假设这样的： $ \三角洲^ *（Q_0，W）= F $，其中$ W \中\西格玛$和$ F \在F $

4热度

1回答

如何在设计NFA时直观地思考如何设计NFA

我不知道这个问题是否适合被问到，但我绝对认为它应该被问到。当然，我确实看到了很多很好的和内容丰富的问题，关于互联网和StackOverflow本身的文章。但我发现所有问题或文章都遵循特定的规则或模式来解释该主题。我的意思是，当在NFA，DFA或正则表达式中提出问题时，遵循这些主题的定理/规则（计算理论）提出了一个解决方案。 But what I feel is that, as most of

2热度

1回答

自动机理论：将上下文无关语法转换为DFA

如何将无上下文语法转换为DFA？这很容易，如果我们有如 A-> a B的转换。但是当我们将转换作为A-> a B c时。那么我们应该如何将它表示为DFA

2热度

1回答

没有最终状态的DFA

我们可以有没有最终状态的Deterministic Finite Automata (DFA)。是否意味着！没有最终状态的Deterministic Finite Automata (DFA)是什么意思？谢谢

0热度

1回答

建设有限自动机

你会同意，在正则表达式： ((a|b)*(e|c)*)* 是A，B的任意组合，和c的？或者你会说c总是在a和b之后出现。

0热度

1回答

识别语言{ε，a，b}的DFA

如何证明存在无限多个DFA，每个DFA都可以识别语言{ε，a，b}。

1热度

2回答

查找DFA

创建一个DFA，使得L下标4 = {0,1} * - {0,01} *并按字典顺序列出前五个字符串。我无法推导出L下标4的含义，它是否是长度为4的字符串的语言？此外，当我们减去两种语言时，我们能否选择从空字符串中减去的字符串“1”，意思是可以选择第一个{0,1} *从长度为0的{0,01} *减去长度1 ？

-1热度

1回答

将电源状态映射到唯一编号NFA到DFA

我正在编写将NFA转换为DFA的代码，如果我们有电源状态{1,2,4}，则必须将其转换为某个唯一编号，例如x 。我也必须做反向映射，这样我得到x，我必须返回电源状态为{1,2,4} 我想出了具有集合1,2,4的字符串表示形式的HashMap并具有独特的价值。但随着代码的增长，我可能有（1,2,4）和（2,1,4）都是相同的设置，但不是相同的字符串。然后我想到排序状态字符串并将其用作映射键。但似乎我

0热度

1回答

直接从正则表达式的时间复杂度DFA构造

我想直接使用龙书中的algo 3.36从正则表达式中了解DFA构造的时间复杂度。我很困惑外循环将执行多少次？正如在算法中提到的Dstates，它们是否等于正则表达式中的操作数？还有多少工作将在内完成循环执行等于|Σ|次？谢谢。