-
3 votesanswersviews
设计图灵机的状态表
如果您已经拥有算法的伪代码，它们是否有助于描述图灵机的功能？ 我正在学习复杂性理论课程，我需要一段时间来描述一个决定或接受某种语言（状态，转换等）的图灵机器，即使我知道如何用C或甚至汇编这样的代码来编写它 . 我想我只是没有足够的图灵机练习（工作），但我很感激任何建议 . edit 我不想制作图灵机模拟器，我想在纸上描述图灵机（字母，状态，过渡）来决定某种语言 . 这是一个简单的例子，我的意思是，... -
3 votesanswersviews
学习计算模型的好资源？
出于好奇，我试图确定我使用的系统的计算模型在功能上是等价的，并证明了等价性 . 我花在这个问题上的时间越长，我越怀疑系统不是图灵相当的 . 我对图灵机和递归可枚举语言的理解很好，但我不太了解具有较小功能的自动机（例如下推自动机），所以我不知道如何继续 . 首先，任何人都可以推荐一个很好的资源来学习不同的计算模型吗？我对语法，语言和自动机感兴趣，以及如何证明它们之间的等价和差异 . 理想情况下，资源... -
3 votesanswersviews
口译员理论，部分评估员和编制者
所以我一直在学习堆栈机器，解释器，编译器以及与编程语言及其一般理论相关的一些其他内容 . 我在书籍和网上找到的大多数东西都非常专业，并且谈论一个特定主题，例如：口译员，没有提及它与其他主题的关系，例如部分评估员 . 是否有任何良好的初学者资源来探索解释器，编译器和部分评估器之间的互连？通过良好的资源，我的意思是解释理论和具体实施 . 我越了解这些东西，我在日常工作中看到的地方越多，所有这些都可以应... -
0 votesanswersviews
软件工程计算机科学[关闭]
我正在学习软件工程，我的一些课程包括计算理论和分析算法 . 我发现很难将图灵机与软件工程或简单编程联系起来 . 所以我的问题是： 为什么包括在软件工程领域的计算机科学中发挥重要作用的理论主题？或者我如何应用PDA，TM，P，NP等知识开发软件？我没有看到两者之间的联系 . -
0 votesanswersviews
正则表达式简化问题
我因为信息冲突而失去了理智 . a+b: a or b ab: concatenation of a and b $: empty string α= (1+0)+(1+0)** （0 1）*（$ 0 1） β= (1+0)* （0 1）*（$ 0 1） https://ivanzuzak.info/noam/webapps/regex_simplifier/说， α 相当... -
1 votesanswersviews
导出有限自动机识别的语言的常规语法
我无法找到有限自动机识别的语言的常规语法 . 我面临的关键问题是常规语法和无上下文语法之间的混淆 . 我似乎无法区分它们之间的差异，我发现它们在某些方面非常相似，例如歧义 . 任何人都可以解释如何获得FA认可的语言的常规语法？ -
5 votesanswersviews
有人可以给出一个简单但非玩具的上下文敏感语法示例吗？ [关闭]
我正在尝试理解上下文敏感的语法，我理解为什么语言会像 {ww | w是一个字符串} {an bn cn | a，b，c是符号} 不是上下文，但我想知道一个类似于无类型lambda演算的语言是否与上下文相关 . 我想看一个简单但非玩具的例子（我考虑上面的玩具示例），一个上下文敏感语法的例子，对某些 生产环境 规则，例如，告诉一些符号串是否可以目前处于范围内（例如，在生成函数体时） . 上下文敏感... -
1 votesanswersviews
上下文敏感的语法可以有空字符串吗？
在我的一个cs类中，他们提到无上下文语法和上下文敏感语法之间的区别在于CSG，然后 生产环境 规则的左侧必须小于或等于右侧 . 因此，他们给出的一个例子是，上下文敏感的语法不能有空字符串，因为这样就不会满足第一个规则 . 但是，我已经理解常规语法包含在无上下文中，无上下文包含在上下文敏感中，并且上下文相关包含在递归可枚举语法中 . 因此，例如，如果语法是递归可枚举的，那么也是类型上下文敏感，无上下... -
12 votesanswersviews
是{w | w <> w ^ R}超过字母{0,1}一个无上下文的语言？
我真的很乐意帮助你决定是否所有单词的语言 {0,1} 无法以相同的方式从双方读取， { w | w <> wR } 是一种无上下文的语言（也就是说，它可以转化为具体的语法规则） . 我试图通过泵浦引理证明它不是一种无上下文的语言，但是我找不到会导致我矛盾的字符串 . 有什么建议？ -
0 votesanswersviews
为特定语言定义无上下文的语法
我有一种语言，语言中的每个字符串的偶数为0，如1（例如，0101,1010,1100,1211,10都在语言中） . 我希望定义一个描述这种语言的无上下文语法 . 在定义了无上下文语法之后，我想正式证明这种无上下文语法描述了这种语言 . 我想出了无上下文语法生成规则： S->0S1S S->1S0S S->ε 这是正确的上下文无关语法来定义这种语言吗？ 我有点难... -
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... -
6 votesanswersviews
计算理论中的重要主题
在大学学习期间，我必须学习很多关于计算理论的知识 . 我研究了三个学期的主题 . 我很难过，我不得不承认我忘记了很多 . 我想知道这是个人问题，还是我们只需要学习很多（或多或少）无用的东西 . 所以我的问题是：您认为计算理论领域中哪些主题最重要，哪些部分值得学习，以及您在正常工作中使用哪些主题？ 就我个人而言，我很高兴我听说theory of languages（特别是常规语言=>正则表达式...