问题标签 [computation-theory]

我不知道它是怎么称呼的：否定、互补或倒置。这个概念是这样的。例如有字母“ab”

在这个简单的例子中，它应该是这样的

这样的正则表达式如何调用？我记得在我的研究中，有一种计算方法，但它很复杂，而且通常很难手工制作。是否有一个不错的在线工具（或常规软件）可以做到这一点？

我和一个朋友正在考虑一个有趣的计算机科学问题。

你有一个简单的二维数组：

现在取这个数组并打乱数组中的所有元素：

一开始是一个相当简单的概念。但是，如果我们再迈出一步呢？现在，打乱原始数组，使新数组中的任何元素都不会与它们在原始数组中在基本方向上相邻的项相邻。

我们的第一次洗牌失败，因为 1 在 2 旁边，并且在原始数组中也在 2 旁边。

这是一个工作示例：

还不算太糟糕。现在到了真正的问题！

再次对原始数组进行洗牌，使数组中的任何元素都不会与它们在基数方向或对角线相邻的元素相邻。

我们的工作示例失败了，因为 1 对角线靠近 5，并且在原始数组中靠近 5。

一些想法：

1. 甚至可以确定一个数组吗？
2. 它取决于数组的大小吗？
3. 阵列是否需要对称？
4. 数组是否需要有偶数/奇数个元素？
5. 解决方案是否适用于所有大小为M乘N的数组？
6. 如果存在解决方案，找到新阵列的运行时间是多少？

你怎么看？

编辑

我很惊讶地发现我的问题被关闭为“离题”。根据常见问题解答，如果我的问题“......通常涵盖特定的编程问题......”那么它可以被问到并且不是“离题”。

我问的底线问题是：

“你能拿一个二维数组并打乱它，这样新数组中的成员就不会彼此相邻，包括对角线”。

这不是一个好的编程问题吗？我强烈认为我的问题不应该结束。

我试图弄清楚如何描述 56 个字符串来测试字母表 {ab} 上的三态 FA 是否具有有限语言。

数字 56 来自一个定理，即如果一台机器有 N 个状态，而一个字母表有 m 个字母，那么总共有 m^N + m^(N + 1) + m^(N + 2) +。 ..+ m^(2N-1) 范围内的不同输入字符串 N<= 字符串长度 < 2N。因此 2^3 2^4 2^5 = 56 个字符串。

我知道我们可以通过在机器上运行它们来测试它们，如果有任何被接受，则语言是无限的，如果没有被接受，则语言是有限的。

我只是不确定如何描述这些字符串。任何帮助是极大的赞赏！

对于我正在从事的项目，我希望能够生成和执行随机算法（相信我，这是有充分理由的！）根据 Alan Turings 的原始论文，每个 TM 都可以分配一个唯一的编号（更多现代理解这一点的方式是，每个程序都编译成一些唯一的二进制大长数字）。

假设我有这么长的号码。我现在如何执行这对应的程序？

语言在这里并不重要，如果它包含使这更容易的机制，我很乐意选择某种语言而不是另一种语言。如果无论您选择哪种语言都很难，那么我最精通Java。

如果您建议另一种生成随机算法的方法也可以，但请记住，我最终会更改逻辑以使用一些启发式方法而不是纯随机性来选择算法。

我正在研究计算分配理论。

我有一个问题，让 p ∈ N, p > 4。我们有一个 DFA A = (Σ, Q, δ, 0, F)，Q = {0, 1, . . . , k}, k ≥ p，并且存在一个 ∈ Σ，使得我们有 δ(q, a) = q + 1 mod p，对于所有状态 q ∈ Q。在这些条件下： (a) 通过对 n 的归纳显示对于所有 n ≥ 0 且 q < p，δ(q, a^(n·p)) = q；

我很困惑，因为 q + 1modp ....这不只是 1 吗？如果是这样，这似乎使我的问题无法证明

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

我知道如何处理诸如 (a|b)* 之类的基本内容：

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

在形式语言的乔姆斯基分类中，我需要一些Non-Linear, Unambiguous and also Non-Deterministic上下文无关语言（N-CFL）的例子吗？

1. 线性语言：线性语法是可能的（⊆ CFG），例如
   L ₁ = {a ⁿ b ⁿ | n≥0}

2. 确定性上下文无关语言（D-CFG）：确定性下推自动机（D-PDA）是可能的，例如
   L ₂ = {a ⁿ b ⁿ c ^m | n ≥ 0, m ≥ 0 }
   L ₂是明确的。

非线性的 CF 文法是非线性的。
L _nl = {w: n _a (w) = n _b (w)} 也是非线性 CFG。

-- 3. Non-Deterministic Context Free Language(N-CFG) :only Non-Deterministic Push-Down-Automata(N-PDA)可能的例如
L ₃ = {ww ^R | w ∈ {a, b} ^* }
L ₃也是线性CFG。

--4。模棱两可的 CFL : only ambiguous CFG is possible
L ₄ = {a ⁿ b ⁿ c ^m |的 CFL n ≥ 0, m ≥ 0 } U {a ⁿ b ^m c ^m | n ≥ 0, m ≥ 0 }
L ₄既是非线性又是模糊 CFG 和每个模糊 CFL \subseteq N-CFL。

我的问题是：
是否所有非线性、非确定性 CFL 都是模棱两可的？如果不是，那么我需要一个非线性、非确定性 CFL 且明确的示例？

给定下面的维恩图：

也在这里问

在 CLRS 的第 264 页底部，作者说获得后r0 = 17612864，14 个最高有效位r0产生哈希值h(k) = 67。我不明白为什么它给出 67，因为二进制的 671000011是 7 位。

编辑 在教科书中：例如，假设我们有k = 123456, p = 14, m = 2^14 = 16384, and w = 32. 采用 Knuth 的建议，我们选择 A 作为s/2^32最接近的形式的分数(\sqrt(5) - 1) / 2，因此A = 2654435769/2^32。然后k*s = 327706022297664 = (76300 * 2^32) + 17612864，等等r1 = 76300 and r0 = 17612864。14 个最高有效位r0产生该值h(k)=67。

我有一个任务，我正在编写一堆基本的原始递归函数，其中一个是减法。我没有得到前任的定义，我认为我不太可能将其定义为eval Pred [x] = x-1. 下面是我对 PR 的定义，我还定义了几个其他函数，例如时间、AND、OR、NOT、pow、true、false 和 ite。是否可以只用我这里的东西来定义减法？如果是这样，有人可以给我一些指导。我目前的想法是我可以做类似的事情，给定minus[x,y]递归y时间然后 return P 2。如果y > x我应该返回零。以下是我对 PR 的定义。

编辑; 我发现我的问题在于定义正确的基本情况。PR (P 3) (P 1)Returns P 1 - 1，这是朝着正确方向迈出的一步，但是，我需要递归P 3时间。我在想类似的东西PR (PR Z (P 3)) (P 1)会做到这一点。这当然是不正确的，但想法是每次递减从到递归P 3。ZP 1

我对 If Then Else 定义中的预测有疑问。它实际上是作为 If-Else-Then 执行的。

如果我尝试交换P 3并且P 4它完全中断（每次返回'then'值）。ite[0,2,3]应该返回3并且ite[1,2,3]应该返回2。相反，正在发生相反的情况。我该如何纠正？