finite-automata

0热度

2回答

有K个状态的NFA接受字符串的长度<= k

是否有可能构造一个N状态，其中k个状态可识别所有长度为< = k的字符串并拒绝长度大于k的所有字符串？

0热度

1回答

当r和r的DFA被确定时，发现r *的DFA

我想要说明当定义r的r和DFA时，找到r *的DFA的方法的例子。以及如何思考？我读了一本教科书，但我不明白。谢谢。

1热度

2回答

证明具有k <2^n个状态的任何DFA不接受具有奇数个字符的字符串

让语言L_n具有字符集Sigma = {a_1，...，a_n}。 L_n恰好包含那些包含一些奇数次字符的单词。等价地，如果L_n^i是每个包含奇数个a_i的字的语言，则L_n = L_n^1 union ... union L_n^n。我已经产生了接受L_n和2^n状态的DFA的NFA，我现在需要证明这是接受此语言的最小DFA。我给出的提示假设有为k < 2^n种状态，它接受L_N的DFA，

1热度

1回答

让A，B，C成为时尚。考虑方程X = AX + BX + C。解答X必须是时尚吗？

让A，B，C成为时尚。考虑方程X = AX + BX + C。解答X必须是时尚吗？你能帮我解决这个问题吗？ fad是一种常用语言

2热度

1回答

DFA可以识别多少种语言？

根据Sipser的“计算理论导论”：如果A是机器M接受的所有字符串的集合，我们说A是机器M的语言并且写L（M）= A。 M识别A ...机器可以接受多个字符串，但它总是只识别一种语言。以及我们说M如果A = {w | M接受w}。我猜这个问题已经被回答了，但是我想知道是否有人有任何想法，如果有什么有趣的话我们可以说关于常规语言的子集，如果我们可以说，原始DFA可以识别它们，并且原始DFA与识别

2热度

1回答

DFA构造为L = {（NA（w）的-nb（W））模3> 0}

作为每标题： L = {（N 一个（W）-n b （W））模3> 0} 字母表= {A，b} 我发现两个答案，这一问题：在这种所以我们的语言被接受。然而， w = b 被接受为好。在未来的解决方案：我们的 w = b 问题在这里解决，但 w = aaab 是不能接受的。我该如何解决这个问题？我无法在互联网上找到合适的答案。

2热度

1回答

从字母{a，b，c}构建DFA

在字母{a，b，c}上构建一个DFA，接受具有三个连续相等字母的所有字符串的集合。因此，它可以接受：AAA，BBB，CCC，AB | BB，caaac，ccbbbcc，aaabbbc .. 我已经尝试了很多不同的方式，这是一个巨大的图我在想，如果有一个更优雅的方式在做这个吗？

1热度

1回答

理论：怎么能是这是从计算书的理论采取机M1

识别的语言：如果下面的图表示机器M1，怎么能A，语言机器M1识别，描述为： A = {w |当字符串011被机器M1接受时，w包含至少一个1和偶数个0，后面跟着最后一个} 。 011实际上包含至少一个1，但偶数个0不跟随最后1. 然后，说“和偶数个0跟随最后1”是不是不正确？

0热度

1回答

是基于有限自动机还是递归回溯的v8/firefox RegExp实现？

我遇到了这个文档：https://swtch.com/~rsc/regexp/regexp1.html 声称Perl，Java和许多其他语言使用基于递归回溯的“慢”RegExp，但grep和awk（也是Go）使用更快的有限自动机。即正则表达式转换为FA然后执行。该论文还声称，所有语言都应该切换到FA技术，尽管其实施更为复杂。我很好奇，如果当前的JavaScript实现有这样或那样的方式。

0热度

1回答

DFA中的空间含义？

这是由工具生成的DFA的正则表达式（A | B）* abaabb（A | B）* 什么是空间中的图片是什么意思？你认为这是完全正确的，因为它没有显示字符串abaabb的其他可能性。例如如果字符串中间的b得到a，该怎么办？