1回答
自动机与可计算性
、、
一个程序打印n个命题符号的真值表需要多长时间？ (符号: P1，P2，...，Pn) 似乎不能破解这个问题，不太确定如何计算这个实例。
浏览 13提问于2020-04-09得票数 1
1回答
类似于私人论坛上的这个问题：
斯科特·阿伦森。6.045J自动机、可计算性和复杂性。2011年春季。
浏览 3提问于2021-09-30得票数 0
回答已采纳
8回答
如果计算机科学是关于算法开发的，因此并不局限于处理器供应商的想象力，而是所有实际上可计算的领域。那么，FPGA，几乎非常适合研究细胞自动机，不应该被认为是学习计算机科学的有效平台。我觉得当前的课程很弱的一个特别感兴趣的领域是并行性以及它与编程语言的集成。我认为编译器设计可以从让学生处理FPGA的显式并行性的课程中受益。
浏览 1提问于2009-07-29得票数 4
1回答
在我的可计算性和复杂性课程中，我刚开始学习自动机理论。我被分配了一项任务，要求我们根据一定的条件设计DFA。然而，我的一个作业问题是让我们写一个相反的DFA (假设我正确理解这个问题)。
浏览 2提问于2022-02-02得票数 0
2回答
我想知道什么是可计算的“简明”定义？我之所以这样问，是因为我对什么是可计算的，什么是不可计算的感到困惑。function foo(){}谢谢
浏览 0提问于2011-11-14得票数 0
回答已采纳
1回答
我正在研究可计算性和复杂性，我对此产生了怀疑。将一个问题减少到另一个问题的函数是图灵-可计算函数。我想知道它是否是一个一对一的函数(一个通信)，例如，查看顶点覆盖的->独立集约简，我看不出一个问题的实例与另一个问题的实例是否对应。
谢谢
浏览 3提问于2015-07-10得票数 0
回答已采纳
6回答
我知道这更像是一个数学/正式语言/自动机/计算机科学问题，而不是一个编程问题，但我希望我能在可理解的教科书(而不是一本无法解读的专著)上获得一些关于命题和谓词演算以外的形式逻辑的建议。
浏览 10提问于2009-06-16得票数 13
我到目前为止发现的是：我认为这只是从理论角度来看很有趣，因为它需要具有无限精确的神经元活动(以某种方式将状态编码为有理数)。Garzon，神经可计算性(请注意，试图指出这种理论结果与实践之间的问题。)
浏览 0提问于2010-06-07得票数 2
回答已采纳
9回答
我喜欢自动机理论和形式语言的课程，所以我自然而然地开始浏览互联网，了解自课程所基于的书籍编写以来发生了什么。此外，在研究该理论的应用时，我得到的结果基本相同:编程语言语法、编译器、文本搜索等等。
浏览 0提问于2010-06-04得票数 21
回答已采纳
1回答
我正在用Java进行项目(但我认为它不依赖于语言)，在那里，我在二进制字母表上生成小的(4状态最大)的非确定性有限状态自动机，我必须快速检查生成的自动机与前面的自动机的等价性。但它似乎在NFAs上产生了过多的与4种状态的碰撞。增加长度会使哈希码的计算速度太慢，无法实际使用。
另一种方法是拥有一组单词并测试自动机接受哪些词，但我认为找到正确的单词不是很简单。
浏览 0提问于2013-12-17得票数 3
回答已采纳
是否有一种算法(保证停止)具有如此大的时间复杂性，以至于它不能由可计算函数渐近地有界？我理解繁忙的海狸函数BB(x)比任何可计算函数增长得更快，但我也认为没有任何算法可以在Θ(BB(x))中运行，因为这样可以解决停止问题。
我认为答案是否定的，但我不知道如何证明这一点。
浏览 2提问于2014-05-08得票数 2
回答已采纳
2回答
我正在寻找一个确定性有限自动机的测试套件，用于测试DFA最小化算法的正确性。你能给我一些建议吗？或者，有没有算法/实现可以生成这样的自动机？要赢得奖金，您需要提交一个包含400个或更多不同大小和复杂性的非最小自动机的测试套件，其中至少20个包含超过2000个节点。
如果这里不适合问这个问题，请告诉我一些更好的地方。谢谢。
浏览 0提问于2012-01-18得票数 3
1回答
我的观点是所使用的算法与不同种类的自动机(状态机、图灵机、堆栈……)之间的相似性。
所以问题是:我在这里隐含地使用的是哪个自动机，它适合哪个形式语言家族？那么递归又是什么呢？我所说的“我隐式使用的自动机”是指“做同样工作的最小自动机”。
浏览 0提问于2010-05-24得票数 2
回答已采纳
我设法提取出准确的单词是否可以提取与给定的list_of_keywords具有良好相似性的单词“过敏”与“过敏”之间的余弦距离可计算如下Out[861]: 0.8432740427115677如何根据余弦相似性从句子中提取“过敏”？
浏览 3提问于2019-02-21得票数 2
回答已采纳
我记得，理论上，两个正则表达式(至少没有反向引用)的等价性可以通过生成它们的自动机并试图找到一个图双射来找到。但是，我看不到比较regexes的实例方法。有没有一种方法可以生成正则表达式的自动机，或者直接比较它们，最好是与标准库进行比较？
(我已经决定用不同的方法解决我的问题，但这仍然是我感兴趣的问题。)
浏览 1提问于2014-01-28得票数 11
回答已采纳
1回答
如果我们有一个没有最终/接受状态的有限自动机。所以F是空的。如何最小化它？在测试中，我被要求最小化一个自动机，但它有一个空的F，我不知道如何处理这个问题，因为自动机没有接受状态。一个初始状态的所有转换都是正确最小化的自动机吗？我认为，如果两个自动机A和B对于任何可能的输入，A返回与B完全相同的输出，那么它们肯定是等价的。因此，如果自动机没有最终状态，则它不接受任何输入或没有有效的输入，因此它必须与任何其他具有这种行为的自动机
浏览 4提问于2015-05-01得票数 0
发挥你的想像力，这是如何可能的，例如，它使用某种超空间连续体自动并行的任何东西是想要的，这样它就可以计算出任何可计算问题的答案，无论它的时间复杂性和实际的“逻辑步骤”的数目，一秒。然而，它只能在一秒钟内回答可计算的问题.所以我不是在假设一台“不可能”的机器(至少我不这么认为).例如，这台机器仍然无法解决停机问题。
这种机器的编程语言是什么样子的？我所知道的所有编程语言都必须对“算法复杂性”做出一些让步.不过，随着这一限制的消除，我希望我们所关心的只是编程语言的“表现力”。即它简明表达“可计算问题”的能力。
浏览 14提问于2009-05-28得票数 2
回答已采纳
2回答
正则表达式的计算复杂性
、、、、
我的目标是提高代码库的可维护性，因此对这些问题的回答可以帮助我们检测和修复复杂的代码：
是否有计算复杂性度量(类似于圈复杂度)包括正则表达式中固有的复杂性？
浏览 5提问于2019-02-14得票数 2
扫码
添加站长 进交流群
领取专属 10元无门槛券
手把手带您无忧上云
相关资讯
热门标签
云服务器
ICP备案
云直播
对象存储
实时音视频活动推荐
腾讯云开发者
