问题标签 [computation-theory]

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

需要用图灵机的定义来证明吗？你能举个例子吗？

谢谢。

我正在复习（不是家庭作业）一些计算理论并遇到了这个问题：

您如何证明常规语言集是上下文无关语言集的适当子集。

现在我知道一种语言是规则的，如果它被有限自动机接受。

而且我知道一种语言是无上下文的，前提是它被下推自动机接受。

但我不确定解决方案是什么。

试图复习计算理论，但不确定解决方案：

我有一种感觉，这可能与找到一个 NP 问题并找到一个减少因子 α 的问题有关。

试图做一些修改，但不确定这个：

证明有限字母表上所有语言的集合是不可数的。

我觉得它需要使用Cantor Diagonalization方法 - 但我不确定你将如何使用它来解决这个问题。

我正在上自动机理论课，现在我们正在学习抽水引理。有一个练习题要求我们“设计一种语言 L，使得 L 和它的补码都没有无限的正则子集？” 但我不明白这个问题。什么是无限正则子集？我应该如何找到可以满足此要求的语言？

任何人都可以对这个问题有所了解吗？

谢谢！

包含任意数量的磁带符号的图灵机 M 可以由仅包含三个磁带符号的 M' 模拟：{0, 1, B}（B = 空白）。

M 可以用只有两个磁带符号的 M" 来模拟，比如 {1, B}？

在语言中，n 是力量，但我不知道怎么写。

我不确定我是否理解有限状态机和状态机之间是否有区别？我是不是想太多了？

用字母 { a }定义语言L如下

L = { 一个^nk | k > 0 ; n 是一个正整数常数 }

DFA 中识别L所需的状态数是多少？

在我看来它应该是 k+1 但我不确定。

请给我一些关于如何去做的想法

画一个图灵机（使用 Sipser 表示法），它至少有 4 个非平凡（即非拒绝）状态和至少 6 个非平凡（即，非拒绝状态）转换。