首先,这不是要求算法将NFA转换为DFA的问题.
众所周知(并且证明)NFA的等效DFA最多有2 n个状态,即使大多数时候它与NFA的状态数或多或少相同.
我如何预测NFA等效DFA所具有的州数量？哪种特定类型的NFA需要等效DFA才能拥有2 n个状态？
我之所以提出这个问题,是因为能够"发明"一些肯定会产生的NFA,而不考虑最小化,2 n - 1个状态加上"死态".
我在掌握机器识别和决定语言意味着什么方面遇到了一些麻烦.我认为我接近定义但不对.
当有人说图灵机T识别语言L在哪里时
L = { <A> | A is a DFA }
其中DFA =确定性有限自动机
我的理解是,它意味着可以构建一个图灵机,给出任何类型的输入(字符串,汽车,人,等等!)将能够告诉你,你给它作为输入的东西是否是DFA .我的意思是,我将始终接受DFA,并始终拒绝非DFA输入.
也就是说,如果该输入是其成员L.另一个例子就是说X家是他父亲的认可者,无论你摆在他面前的是什么,他都能告诉你他面前的是他父亲是不是他的父亲.它是否正确？哪部分不正确？
另一方面,一种decider语言似乎永远不会是图灵机loops,也就是说,对于任何输入,它总是会在接受或拒绝状态下停止.这与我上面关于识别器的解释是不是相似或相同？
谢谢
我需要一个CFG,它会生成除了回文之外的字符串.已提供解决方案,如下所示.(计算理论导论 - Sipser)
R -> XRX | S
S -> aTb | bTa
T -> XTX | X | <epsilon>
X -> a | b
我对这个语法的工作方式有了一般的了解.它要求插入一个子串,该子串在其两半上通过生产具有相应的不相等的字母S -> aTb | bTa,从而确保永远不会产生回文.
我将按照我的理解写下前两部作品的语义,
S 生成不能成为回文的字符串,因为它们的第一个和最后一个字母不相等R由至少一个S作为子串组成,确保它永远不是回文.我不完全理解第三个产品的语义,即.
T -> XTX | X | <epsilon>
X -> a | b
我看到它的方式,T可以生成a和b的任意组合,即{a,b}*.为什么它不会像
T -> XT | <epsilon>
X -> a | b
这不是两个相同的？由于后者更直观,为什么不使用它？
以下语言的最小抽水长度是多少？
(01)*10(11*0)*01011011 ü 0*1*这是我的解决方案.如果我错了,请纠正我.
01是可以泵送的最短字符串10100是可以泵送的最短字符串0可以泵送字符串我不确定我的答案,所以任何帮助都表示赞赏.非常感谢!
computer-science compiler-theory computation-theory regular-language
在计算理论中,可证明和可判断的术语是可互换的吗？他们的意思是一样的吗？
例如,您经常会看到一个问题是否可证明是一个决策问题(Das Entscheidungsproblem).
众所周知,C++模板是图灵完备的,CSS是turing-complete(!),C#重载分辨率是NP-hard(即使没有泛型).
但是C#4.0(具有co/contravariance,泛型等)编译时图灵是否完整？
我在期中考试时遇到了一个问题.任何人都可以澄清答案吗？
问题A:给定一个完整的加权图G,找到一个最小权重的汉密尔顿游.
问题B:给定一个完整的加权图G和实数R,G是否具有最多R的哈密顿巡回训练？
假设有一台机器可以解决B.我们可以多少次调用B(每次给出G和实数R),用该机器解决问题A？假设G中边缘的总和达到M.
1)我们不能这样做,因为有无数的状态.
2)O(| E |)次
3)O(lg m)次
4)因为A是NP-Hard,这是不可能做到的.
我想知道递归和递归可枚举语言之间的区别在于停止和图灵机.我知道递归可枚举语言是递归语言的一个子集,但我不确定除此之外的差异.
theory computer-science turing-machines computation-theory formal-languages
这是一个关于理论计算的问题.我遇到了类似下面的问题;
考虑具有以下功能单元的项目:
假设所有复杂度调整因子和权重因子均为平均值,项目的功能点将为;
答案是672.这是如何计算的？