-
-1 votesanswersviews
任何人都可以给我关于图灵机设计的帮助
我遇到了一个基于基本图灵机的新算法非常棘手的情况 . 我知道图灵机的定义及其工作原理 . 但我真的不知道这个算法在说什么 . 有人可以帮我解决以下问题，还是给予任何可能的帮助？ 由图灵机执行的三阶段算法是非正式描述的 . 机器的输入字母是{a，＃}，磁带字母是{a，A，＃，B，＃，□}，它在磁带上的初始输入采用^ m＃a ^ n的形式，空白之后 . 准备阶段：从右扫描到第一个空白符号B并用□替换它... -
13 votesanswersviews
高级形式逻辑/自动机理论教科书
我知道这更像是一门数学/形式语言/自动机/计算机科学问题，而不是编程问题，但我希望我能在关于命题和谓词微积分之外的形式逻辑上得到一些关于 comprehensible textbook （不是难以理解的专着）的建议 . 我对 monadic second order logic 和 Büchi Automata 特别感兴趣 . 现在，我只找到了Bakhadyr Khoussainov，Anil N... -
76 votesanswersviews
常规vs上下文免费语法
我正在攻读我的计算机语言测试，并且我有一些问题 . 我知道常规语法更简单，不能包含歧义，但不能完成编程语言所需的大量任务 . 我也理解无上下文语法允许模糊，但允许编程语言（如回文）所需的一些东西 . 我遇到的问题是通过了解常规语法非终结符可以映射到终端或非终结符后跟终端，或者无上下文非终结符映射到终端和非终结符的任意组合，从而理解我如何得出以上所有内容 . 有人可以帮我把所有这些放在一起吗？ -
3 votesanswersviews
学习计算模型的好资源？
出于好奇，我试图确定我使用的系统的计算模型在功能上是等价的，并证明了等价性 . 我花在这个问题上的时间越长，我越怀疑系统不是图灵相当的 . 我对图灵机和递归可枚举语言的理解很好，但我不太了解具有较小功能的自动机（例如下推自动机），所以我不知道如何继续 . 首先，任何人都可以推荐一个很好的资源来学习不同的计算模型吗？我对语法，语言和自动机感兴趣，以及如何证明它们之间的等价和差异 . 理想情况下，资源... -
2 votesanswersviews
Epsilon闭合和自动机
我认为在确定非确定性自动机的语言时，我并不完全理解epsilon转换的概念 . 例如在这个自动机中： 语言是：' a 的双重序列或 b 的双重序列，其中可能存在 baa 序列' . 但是， a 这个词也属于自动机，不是吗？ （也是 b ， aaa 等等......） -
0 votesanswersviews
是ε和NFA的空集语言吗？ （非确定性有限自动机）
我有这样的NFA：enter image description here 问题是： 是ε，空集，这个NFA的语言？ -
4 votesanswersviews
非线性，非确定性和非确定性CFL的例子？
在正式语言的乔姆斯基分类中，我需要一些 Non-Linear, Unambiguous and also Non-Deterministic Context-Free-Language（N-CFL）的例子？ Linear Language ：对于which Linear grammar是可能的（⊆CFG），例如L1 = {anbn | n≥0} Deterministic Context... -
0 votesanswersviews
具有Epsilon转换的下推自动机是NDPA吗？
让我们假设我们有这个PA： -> q0 (e, e -> $) --> q1 哪里： q0 是最终的初始状态; e 是epsilon（空）;而q1是另一种状态 . 如果自动机要读取 e 字，它可以转换到q1或停止在q0 . 那么，这个PA是非确定性的吗？ 我的老师说它不会，因为实际上，自动机只有一条路径可以遵循：由于这个词是空的，所有的符号都已经在q0中被消耗了，所以它不会有任... -
0 votesanswersviews
自动机理论中语言的定义
我现在正在参加Automata Theory课程，虽然仍然在有限自动机中，但我发现它既有趣又有挑战性 . 我们正在使用Hopcroft的“自动机理论导论......”，并在其中讨论了DFA： A =（Q，Σ，δ，q 0，F） Q =状态集 Σ=输入符号，即字母表 δ=过渡 q 0 =开始状态 F =最终/接受状态 这很好，但是，然后，我们的教授给了我们一些练习（可能不在书中... -
0 votesanswersviews
为所有具有相同数量的as和bs的字符串创建确定性下推自动机
正如 Headers 所说，我试图为所有具有相同数量的as和bs的字符串创建一个确定性的下推自动机 . 这对我来说非常棘手的是确定性部分 . 例如，对于第一个ab之后的字符串“abab”，有两个可能的结果，或者字符串结束，所以我接受下面的过渡Z | Z或字符串继续，那些是可能的过渡Za | ZA，Za | ZB . 当我有一个具有这些转换的状态时，PDA变得不确定 . 这就是我现在所拥有的： Z ... -
0 votesanswersviews
在第一个符号左转的图灵机
我有一台图灵机，下表给出了转换 我正在输入字符串aaaa . 因此，如果我查看状态A中的第一个符号“a”，它表示用X替换它，进入状态B，然后向左移动 . 这是我困惑的地方 . 如果我正在查看第一个输入符号，怎么能向左移动？我只是去一个空白的符号？ 谢谢！ -
3 votesanswersviews
设计图灵机的状态表
如果您已经拥有算法的伪代码，它们是否有助于描述图灵机的功能？ 我正在学习复杂性理论课程，我需要一段时间来描述一个决定或接受某种语言（状态，转换等）的图灵机器，即使我知道如何用C或甚至汇编这样的代码来编写它 . 我想我只是没有足够的图灵机练习（工作），但我很感激任何建议 . edit 我不想制作图灵机模拟器，我想在纸上描述图灵机（字母，状态，过渡）来决定某种语言 . 这是一个简单的例子，我的意思是，... -
-2 votesanswersviews
图灵机的数量？
你对这个问题有什么看法吗？我不知道它问的是什么 . 具有状态设置（Q-start，Q2，Q3，Q4，Q5，Q6，Q-accept，Q-reject），输入字母（0,1）和磁带字母（0）的图灵机数量是多少？ ，1，x，U）其中U是空白符号？启动，接受和拒绝状态是具有适当名称的状态 . 展示你的作品 . -
0 votesanswersviews
这个语法上下文是否免费？
G: S ---> aSb S ---> λ 根据我的要求，第一个 生产环境 规则是无上下文的（因为左侧小于右侧）但是对于第二个 生产环境 规则，它不是（因为左侧长度等于右侧） . 那么，在这个陈述中我们可以对这个语法说些什么呢 . 是否没有上下文？ -
1 votesanswersviews
导出有限自动机识别的语言的常规语法
我无法找到有限自动机识别的语言的常规语法 . 我面临的关键问题是常规语法和无上下文语法之间的混淆 . 我似乎无法区分它们之间的差异，我发现它们在某些方面非常相似，例如歧义 . 任何人都可以解释如何获得FA认可的语言的常规语法？ -
5 votesanswersviews
有人可以给出一个简单但非玩具的上下文敏感语法示例吗？ [关闭]
我正在尝试理解上下文敏感的语法，我理解为什么语言会像 {ww | w是一个字符串} {an bn cn | a，b，c是符号} 不是上下文，但我想知道一个类似于无类型lambda演算的语言是否与上下文相关 . 我想看一个简单但非玩具的例子（我考虑上面的玩具示例），一个上下文敏感语法的例子，对某些 生产环境 规则，例如，告诉一些符号串是否可以目前处于范围内（例如，在生成函数体时） . 上下文敏感... -
0 votesanswersviews
从语言到无上下文语法[关闭]
鉴于语言K = {e ^ h f ^ i | 2h> i> h}我需要生成一个无上下文语法 我想出的一些 生产环境 规则是：S - > eeTfff和T - > eTff | ε 它们仅在n = m 1时起作用，但我不知道如何在2h> i> h中为每个组合生成任何规则 . -
1 votesanswersviews
这种语言的上下文无关语法
我正在研究一些测试准备材料并坚持这个问题 . Show a context free grammar for L = {w e {a,b}*: w = wR and every a is immediately followed by a b}. wR反过来了 . 因此，在英语中，一个回文，每个“a”后跟一个“b”，使用任意数量的a和b . 到目前为止，我得到了相反的部分，但我无法弄清楚如何合并每...