标签: computation-theory

我找到了维基百科的图灵机等效列表文章.但是,它没有说明如何确定给定机器是否与图灵机等效的方法.

我是否需要使用图灵机的定义来证明它？你举个例子吗？

谢谢.

我正在研究无上下文语法,我很好奇带有星形的箭头和没有星形的箭头在f和g部分中的含义:

• f是假的.
• g是真的.

任何人都可以为我概述一个算法,可以将任何给定的正则表达式转换为一组等效的CFG规则吗？

我知道如何处理基本的东西,如(a | b)*:

S -> a A
S -> a B
S -> b A
S -> b B
A -> a A
A -> a B
A -> epsilon
B -> b A
B -> b B
B -> epsilon
S -> epsilon (end of string)

但是,我遇到了一些问题,将其形式化为适当的算法,特别是对于可以具有许多嵌套操作的更复杂的表达式.

我在http://lambda-the-ultimate.org/node/2064看到了这个术语“Glushkov NFA”。搜索引擎返回对使用 glushkov nfa 的文章的引用，但没有关于 glushkov nfa 本身的具体信息。

什么是格卢什科夫 NFA？它与 Thompson Construction 创建的 NFA 有什么不同？

我需要的形式的执行计算a 2^m / b,其中a/b接近1,a和b接近2^m和m较大(大于1000).我需要商和余数.我可以用Java做到这一点

BigInteger[] computeScaledRatio(BigInteger a, BigInteger b, int m) {
    return a.shiftLeft(m).divideAndRemainder(b);
}

成本大约是将2m位数除以m位数的成本.

有没有办法让这更快？

如果可能的话,我想将成本降低到大约分割两个m位数的成本.

我不在乎结果代码是否更复杂和/或是否需要一些外部库.

我绝望地尝试了以下代码.毫不奇怪,这种表现令人沮丧.

static final double LOG2_10 = Math.log(10) / Math.log(2);
static final BigDecimal TWO = BigDecimal.valueOf(2);
BigInteger[] computeScaledRatio(BigInteger a, BigInteger b, int m) {
    int percession = (int) Math.ceil((2 * m) / LOG2_10);
    BigDecimal t = new BigDecimal(a).divide(new BigDecimal(b),
            new MathContext(percession));
    t = t.multiply(TWO.pow(m));

    BigInteger q = t.toBigInteger();
    BigInteger r …

在我的一门计算机科学课程中，他们提到上下文无关语法和上下文相关语法之间的区别在于，在 CSG 中，产生式规则的左侧必须小于或等于右侧。

因此，他们给出的一个例子是上下文相关语法不能有空字符串，因为这样就无法满足第一个规则。

但是，我知道常规语法包含在上下文无关中，上下文无关包含在上下文相关中，上下文相关包含在递归可枚举语法中。

因此，例如，如果语法是递归可枚举的，那么它也是上下文相关、上下文无关和常规类型。

问题是，如果发生这种情况，那么如果我有一个包含空字符串的上下文无关语法，那么它就不能满足算作上下文相关的规则，但是就会出现矛盾，因为每个上下文相关是上下文无关的。

我想为以下语言设计一个上下文无关语法：

L = { 我们 {(, )}* | w 是平衡的}

我提出了以下语法：

S -> (S)S | 乙

而讲座中提出的解决方案是：

S->（S）| SS | 乙

我无法弄清楚我的解决方案可能存在什么问题。我针对各种情况运行了语法，例如：

（（）（））， （）（）（）， 和 （（））（）

并且 CFG 都接受这些字符串。

有人可以帮忙吗，我的 CFG 不涵盖哪些情况。或者说它们都是等价的。或者达到最终状态所需的转换次数不同。

如果L1和L2是语言,我们有一种新语言

INTERLACE(L1, L2) = {w1v1w2v2 . . . wnvn | w1w2 . . . wn ? L1, v1v2 . . . vn ? L2}.

例如,if abc ? L1和123 ? L2thena1b2c3 ? INTERLACE(L1, L2)

我怎样才能证明INTERLACE:

1. 可判定的？
2. 可识别？

我知道如何显示这种语言是正常的.对于可判定的我不太确定..

这就是我的想法:

为了表明在操作中关闭可判定语言的类INTERLACE需要表明如果A和B是两种可判定的语言,那么有方法可以找到INTERLACE语言是否可判定.假设A,B可判定语言M1,M22 TM谁决定,分别.

在我想我必须说如何构建识别语言的DFA之后？

我试过这个

S -> e(Epsilon)

S -> SASBS

S -> SBSAS

一个->一个

B -> b

有人可以验证这是否正确。

我一直在试图了解其中"5"来自于中位数算法的中位数,但似乎无法找到它是如何得出的简单描述,以及为什么它是最佳的.

例如,为什么不说7是一个可行的选择？

我可以看到5的唯一优势是它在中间的每一侧有2个项目,对5个项目进行排序,这是一个不超过3个交换的简单情况.