1回答
我已经进入了自动机理论，编译器和CS的基本原理，但有一些基本的东西，我不明白。
我已经看到了Chomsky语言的层次结构，不同类型的语言具有不同的表达能力，它们与同等强大的自动机“相关联”。
维基百科：
语法语言自动机
可递归枚举图灵机( machine-Type-2 Type-0 )类型-1上下文敏感的线性有界的图灵上下文无关的非确定性下推automatonType-3正则有限状态自动机
我已经看到，每种编程语言都是图灵完整的，编程语言的语法规范(用BNF格式，等等)可以用上下文无关语法来表达。
上下文无关文法没有等效的“关联”图灵机。
在解释/编译过程中，用编程语言编写的程序源代码的字符串
浏览 2提问于2021-04-21得票数 1
回答已采纳
字母表{a, b, c, d}上的字符串，其中没有c紧跟a，也没有d紧跟b。
这将是上下文无关的，而不是常规的，对吗？
浏览 1提问于2012-02-01得票数 0
1回答
我需要将一个表达式(字符串)分成几个部分，然后从它的组件中调用一个递归函数。表达式类似于：(a或b)，或((a和b)或c)，或((a和b)或(c或d)) (或任何其他表达式，无论它有多少个括号。运算符and和or表示两个函数(留尼旺岛和交叉点)。
对于"((a和b)或(c或d ) )“，我必须调用Union( F( "(a和b") )，F( "(c或d)”))。F( "(a和b)“)将是交集(”a“，"b") ...诸若此类。
我设法拆分了由两部分组成的表达式( "a和b“)，但我不能处理更大的表达式。
提前感谢！
浏览 0提问于2012-10-27得票数 0
回答已采纳
因此，我有一个问题是上下文无关的语法，我没有设法解决。不是为了年级什么的所以别担心。
问题是这样的：
有一种上下文无关的语法看起来
S -> S1 = S2
S1 -> aS1B区B
S2 -> S2aB区B
B -> bS \b
任务是编写一个函数(在任何编程语言中) count_words(n)。函数需要返回长度为"n“的单词数，这些单词在这种上下文中是自由的。
*假设我用count_words( 3 )调用函数，函数必须返回长度为3的可能单词数(在上下文无关语言中)，即: bab、abb、abb等。
有人能帮我吗？我不知道在all...suppos
浏览 5提问于2012-08-23得票数 4
回答已采纳
1回答
我在JSON规范中找到了这个数字
这张图表的类型叫什么？
我可以用这个图表来指定任何编程语言吗？
浏览 1提问于2017-02-25得票数 0
回答已采纳
想知道如何将这种不确定的FSA
一种确定性的方法，特别是表。
到目前为止，我已经得到了这一点，但被卡住了：
如何分配BHMQ？对于第一个州，不是有四位数吗？(C，I，N，R)？
浏览 0提问于2016-04-30得票数 2
1回答
我必须绘制一个接受以下字符串的有限自动机
Λ, a, aabc, acba and accb
在我看来，a(a+b+c)*可能是它的正则表达式，因为字符串是从a开始的，并且还包含一个空字符串。
现在我没有找到如下所示的绘制FA的逻辑
问题1:如果字符串以a开头，那么在FA中，我们正在从x迁移到y，同时阅读b为什么不在这里阅读a。
问题2:为什么我们在状态y和z上使用a，b循环
浏览 3提问于2012-11-06得票数 0
回答已采纳
1回答
我正在尝试寻找一种生成正则表达式((a+b∗c)d)∗所给出的语言的正则语法。有没有什么通用的技术可以用来将正则表达式转换成正则语法？
浏览 4提问于2016-01-20得票数 0
证明:设M是下面的NFA：
现在，如果x在L中，那么x= 0^(n)1^(n)。因此，当处理x时，M将在状态q0中开始，在状态q0中循环n次，然后在rst 1上转换到状态q1，并且在状态q1中跟随循环总共n-1次。因为它以q1状态结束，所以x将被接受。因此，M识别L中的每个字符串，因此L是NFA可识别的(根据Kleene定理，因此是正则的)。
浏览 3提问于2016-05-08得票数 1
1回答
我很好奇哪些(如果有的话)现实世界的编程语言有规则的语法(即所有语法正确的程序集都是规则的)。
另请参阅此问题：。
浏览 0提问于2011-04-11得票数 8
回答已采纳
9回答
我喜欢自动机理论和形式语言的课程，所以我自然而然地开始浏览互联网，了解自课程所基于的书籍编写以来发生了什么。
我发现，我不熟悉的东西清单似乎很短。例如，从该主题的维基百科条目中的自动机列表中，该课程涵盖了一半，另一半主要与该课程未涵盖的一种语言有关。
此外，在研究该理论的应用时，我得到的结果基本相同:编程语言语法、编译器、文本搜索等等。事情就是这样。
那么它真的死了吗？或者它还在继续发展？这个理论有没有新的应用？
浏览 0提问于2010-06-04得票数 21
回答已采纳
4回答
我对编程比较陌生，我想写一种简单的脚本语言作为练习，并学习一点。我有使用Python、C和Ruby的经验，我想学习用Python编写脚本语言。我的第一步应该是什么？我该如何开始呢？
浏览 0提问于2011-04-27得票数 2
回答已采纳
我们的老师对这个问题的回答是错误的。
然而，我认为这必须是真的。拿这个接受西格玛星的DFA。
Q -> {s_1}
q_0 -> s_1
sigma -> {a，b}
F -> {s_1}
delta -> {s_1sigma -> s_1}
这意味着这种语言必然接受(西格玛星)星，这是所有语言的集合，包括像{a^nb^n \n> 1}这样的非规则语言。在我看来，非常规语言会被接受，因为它们是DFA描述的语言的子集。
在我看来，DFA会接受任何语言。
浏览 0提问于2019-01-19得票数 0
回答已采纳
1回答
许多编程语言和系统都是图灵完整的，它们可以模拟任何图灵机，因此也可以模拟任何有限状态机。
考虑以下非正式模式：
语言A定义了一组有限的NAND门，它们之间的连接，以及哪些门接收输入，哪些门被输出。
在该模型中，可以建立任何有限状态机。NAND可以形成锁存器、寄存器、总线和控制结构，并最终形成任何有限状态机，包括完整的计算机和其他系统。
然而，该模型无法模拟无限大的磁带，只有有限大小的磁带。它不能模拟任何图灵机，因为它可能没有内存。
语言A和所有其他可以模拟任何有限状态机的系统都被认为是完全的吗？他们是否有一个单独的类，或者有机会定义这样的类？
浏览 3提问于2017-05-30得票数 0
回答已采纳
假设我们有fsa，如下所示：
fsa = {0:{'a': 1, else: 2},1:{'b': 1, else: 2},2:{else: 2}}
这意味着:在状态0，如果输入是'a'，它就进入状态1，否则它进入状态2；在状态1，如果输入是'b'，它进入状态1，否则它进入状态2；在状态2，对于任何输入，它进入状态2。
假设状态0是启动状态，状态1是接受状态，状态2是失败状态。这样，fsa就可以被翻译成正则表达式ab*。事实上，有几种将fsa转化为正则表达式的算法，例如Brzozowski代数方法。
我的问题是:上述表格中定义的f
浏览 3提问于2015-08-03得票数 2
回答已采纳
2回答
如果一种编程语言能够成功地模拟一个通用的TM，那么它就是图灵完备的语言。让我们以函数式编程语言为例。
在函数式编程中，函数比任何东西都有最高的优先级。您可以像传递任何原语或对象一样传递函数。这就是所谓的一级函数。
在中，您的函数不会产生副作用，即将字符串输出到屏幕上，在其作用域之外更改变量的状态。如果从外部传递对象，则每个函数都有自己的对象的副本，并且一旦函数完成其任务，复制的对象将被返回。每个函数都完全独立于它之外的任何东西，都是用函数样式编写的。这样，整个系统的复杂性就降低了。这被称为参考透明度。
在函数编程中，即使在函数退出之后，每个函数也可以保留其局部变量。这是由垃圾收集器完成的。该值
浏览 0提问于2012-06-17得票数 0
回答已采纳
5回答
我依稀记得我读过一篇关于在屏幕上绘制对象的编程练习。如果一个对象的邻居少于2个，它就会因为孤独而死亡，如果它有3个以上的邻居，它就会因为拥挤而死亡。如果邻居的数量是2或3，那么它将生成子对象。一般的想法是看看有多少代可以持续下去。
不管怎样，有没有人记得这个练习的名字以及完成这个练习的算法的名字？
浏览 13提问于2009-02-05得票数 1
回答已采纳
2回答
我只是想知道正则表达式是否符合什么是逻辑编程的定义。它是一组规则，给出一组事实，根据查询的询问方式产生结果。对我来说，这听起来应该属于逻辑编程的范畴，但我不确定。
谢谢!
浏览 2提问于2015-11-30得票数 3
回答已采纳
3回答
我对自动机理论感兴趣，以提高我对编程和编译器设计的理解(例如，我想在我自己的项目中创建一些简单的语法；L-Systems，AI，神经网络结构和智能对象-对象对话'AI对话框‘)，但在继续之前，我需要学习一些东西。
在学习自动机理论之前，我需要学习很多新的符号和数学概念，我不能复制和粘贴示例，因为这些符号，我没有必要的声誉来发布图像，以便听到维基文章的链接。
在“正确的CFG”的标题下，你可以看到一些定义。我不理解他们。有人能告诉我这个符号叫什么吗?这样我就可以在谷歌上搜索它了。任何其他的指针或信息也会有所帮助，但只需知道几个关键字就会有所帮助。此外，如果有人知道可以免费访问的综合资源
浏览 4提问于2014-06-18得票数 1
许多编程语言和操作系统都有提供动态内存的方法：new、malloc等。
如果:程序仅使用堆栈限制，且具有预定义(即编译时)大小，则堆栈不能动态增长或收缩。
所有数据都是“on”或"on"，这些堆栈。该程序由堆栈操作组成:给定合理数量的寄存器和操作(比如Intel IA-32，为了具体起见)。
使用这种假设系统的局限性是什么？(例如，哪些算法问题可以解决，哪些问题不能解决？)
例如:这个程序可以进行网络连接、I/O、加密或(G)UI吗？
浏览 2提问于2011-07-28得票数 0
回答已采纳
1回答
我们可以有一个没有最终状态的Deterministic Finite Automata (DFA)。不管是什么意思！没有最终状态的Deterministic Finite Automata (DFA)的含义是什么？
谢谢
浏览 3提问于2014-02-12得票数 3
回答已采纳
1回答
我正试图弄清楚如何在下推自动机(PDA)中做算术表达式，例如，L=W|W=An，Bm，Cn，我想做的是按下推B，然后按C或B推送，这取决于剩下的是什么。例如，aaabbc (推动aaa，然后弹出与Bs，bba，然后弹出A与C或B与C取决于哪一个更大。
浏览 2提问于2015-10-30得票数 0
2回答
我有一个问题，需要找出以下语言是常规的还是上下文无关的或其他语言。{a^(2i+3j) | i>0，j>0}
我怀疑它是一种常规的或上下文无关的语言，因为它没有模式。
浏览 17提问于2020-07-03得票数 0
我正在阅读计算理论。我没有编程编译器的实际经验。
因此，我突然想到，C或Java编译器是否使用庞大的DFA来验证程序( TOC术语中的字符串)？
编译器是DFA的实际实现吗？
浏览 4提问于2015-09-30得票数 4
回答已采纳
我试图使自己熟悉不同类型的语言，以了解其中每一种语言都非常擅长的领域。到目前为止，我已经接触过C--一种过程语言、C++ & java --静态类型的面向对象语言和groovy --一种动态类型化的面向对象语言。
每一种编程语言都可能已经开始满足需求。我认为每一种语言都是非常好的，至少有一件事是因为它在特定的领域或领域成为一个标准。像C一样，C++已经成为浏览器或游戏开发领域的标准。Python在Linux世界中由于其易于编写脚本的能力，Java在企业世界等。
现在，我有兴趣学习一种函数式编程语言，如Clojure或Lisp。那么，在实际场景中，函数编程语言在哪里使用呢？我不认为人们会
浏览 0提问于2012-02-06得票数 9
在状态机中，据说它只保存有关当前状态的信息，并根据输入转换到下一个状态。
如果有其他条件，比如：
状态A(输入X) ->状态B
状态B
(input X) AND (SomeValue>=100) ---> State C
(input X) AND (SomeValue < 100) ---> State D
这仍然是一个状态机吗？
浏览 1提问于2017-04-24得票数 5
5回答
在乔姆斯基的层次结构中，没有定义递归语言集。我知道递归语言是递归枚举语言的子集，并且所有递归语言都是可判定的。
我感兴趣的是递归语言与上下文敏感语言的比较。我是否可以假设上下文敏感语言是递归语言的严格子集，因此所有上下文敏感语言都是可判定的？
浏览 27提问于2010-06-17得票数 6
1回答
正则表达式维自动机理论
、、、、
是否有人知道以下语言的正则表达式：
以000开头但不以11结尾的所有字符串的集合。
以111结尾的具有奇数字符串长度的所有字符串的集合
L6是以00结尾并包含子字符串11的所有字符串的集合。
我非常感谢任何人能在这件事上帮助我。
从给定的案例中找出3个正则表达式，以及如何从给定语言中找到正则表达式
浏览 8提问于2022-11-08得票数 -2
2回答
我需要一个库，它将接受两个正则表达式并确定它们是否同构(即，精确匹配同一组字符串集)，例如a|b与ab同构
据我所知，正则表达式可以转换为NFA，在某些情况下，NFA可以有效地转换为DFA。然后可以将DFA转换为最小DFA，如果我理解正确的话，它是唯一的，因此可以比较这些最小DFA是否相等。我意识到并不是所有的正则表达式NFA都可以有效地转换为DFA(特别是当它们是从Perl Regexp生成的，而Perl Regexp不是真正的“正则”)，在这种情况下，理想情况下，库只会返回一个错误或一些其他指示，表明转换是不可能的。
我在网上看到了大量关于这样做的文章和学术论文(甚至还有一些要求学生这样做
浏览 0提问于2012-03-08得票数 25
回答已采纳
2回答
定义在Σ= {A，B，C}上的所有字符串的语言，以B开头，以A结尾，最小长度为3，并为语言绘制有限自动机。
请用正则表达式和语言图表来解释这一点。定义在Σ= {X，Y，Z}上的所有字符串的语言，其中Y是第三个字母，Z是最后一个字母
浏览 5提问于2015-05-18得票数 2
回答已采纳
1回答
正则表达式的最小化
、、、
我是编程领域的新手。我正在尝试创建一个通用的正则表达式，它只匹配给定的字符串列表，仅此而已。
例如，给定以下列表
List = ['starguide,'snoreguide','snoraguide','smarguides']
它应该创建一个如下所示的正则表达式- s(((tar|nor(e|a))(guide))|marguides)
我实现了一个trie。我只能设法获取s(marguides|nor(aguide|eguide)|targuide)
我希望我的正则表达式被缩短(公共后缀绑定在一起)。有没有更好的方法来缩短我从tri
浏览 0提问于2018-10-22得票数 0
2回答
我已经编程几年了，顺便看过Bison这个名字，但从来没有费心去问为什么需要它。Bison如何影响我的编程方式，它能让我的C/C++代码更快吗？
浏览 1提问于2012-08-25得票数 0
回答已采纳
6回答
我知道这更像是一个数学/正式语言/自动机/计算机科学问题，而不是一个编程问题，但我希望我能在可理解的教科书(而不是一本无法解读的专著)上获得一些关于命题和谓词演算以外的形式逻辑的建议。我对一元二阶逻辑和Büchi Automata特别感兴趣。
目前，我只找到了巴哈迪尔·库萨诺夫( Bakhadyr Khoussainov，Anil Nerode )的。题名/责任者:eds L.还有 Benedikt Bollig....Way在我头上。
浏览 10提问于2009-06-16得票数 13
8回答
最近，我一直在考虑有限状态机(FSM)，以及如何在软件中实现它们(编程语言并不重要)。
我的理解是确定性状态机被广泛使用(分析器/词汇器、编译器等等)，但是非确定性状态机有什么问题呢？
我知道，可以将所有非确定性状态机转换为确定性状态机(甚至以编程方式)。这不是我想说的。我还设想，非确定性状态机的实现要复杂得多。
无论如何，实现非确定性状态机是否使有任何意义？有什么我不知道的特殊应用吗？这样做的理由是什么？也许优化和专门化的非确定性状态机更快？
浏览 11提问于2008-10-13得票数 8
回答已采纳
3回答
我想用C/C++编写正则表达式库。什么是好的起点，任何书籍或文章。
我知道有很多可用的库，但我想写我自己的版本。
浏览 0提问于2011-04-17得票数 0
回答已采纳
1回答
我需要一些帮助来解决一个泵送引理问题。
L = { {a,b,c}* | #a(L) < #b(L) < #c(L) }
这就是我到目前为止得到的：
y = uvw is the string from the pumping lemma.
设y= abbc^n，n是pumping引理的长度。Y在L中是因为a:s的数量小于b:s的数量，而b:s的数量小于c:s的数量。
设u= a，v= bb，w= c^n。|uv| < y，如pumping引理所述。如果我"pump“(bb)^2，那么我会得到
y = abbbbc^n which violates the rule
浏览 0提问于2012-11-16得票数 5
回答已采纳
1回答
哪种有限自动机支持从状态A到状态B的事务条件集？例如，if (a && B && c)则A -> B。
更难的是，假设我们一次只接收一个条件。
当然，这可以使用DFA完成，但这将导致状态爆炸
浏览 0提问于2018-02-12得票数 0
1回答
我对自动机有一点了解，它在词法分析和词法分析阶段中起着一定的作用。但让我困惑的是，到底是在哪里，在什么地方，怎么做。我认为，由我们的高级语言代码构成的标记被某些语言分类或识别，如果我们甚至可以称之为RE定义的“语言”的话，那就是“语言”。那CFG呢？那么有限自动机呢。我们在自动机类、状态、语言和字符串中生成的图表。计算机能识别那些状态图吗？
浏览 5提问于2018-10-30得票数 2
回答已采纳
为什么不能构造一个有限的状态机来精确地识别语言中的这些序列
其中A的字母表是{0,1}..
我只是不明白为什么这不是possible...Maybe，我没有看到一些东西，因为我是新手。
浏览 2提问于2014-11-18得票数 2
通过将具有到最终状态的一些路径的M的所有这样的状态添加到新的DFA M‘的最终状态集合中，是否可以安全地概括地说，如果我们给出一个DFA，例如M，我们可以获得前缀语言的DFA (注意，给定语言的前缀语言由所有字符串u组成，使得uv是L的一个元素，v是文本[\ $$ \ $$ {*}]textsuperscript的元素)。此M‘将接受L的前缀语言。
浏览 4提问于2019-08-21得票数 1
回答已采纳
如果一个PDA ()对于其语言中的任何字符串w至多将其堆栈的方向转动k次，则称其为k-转弯。此外，众所周知，语言L是线性的当且仅当被1圈PDA接受。那么，常规语言是不是真的是0转PDA所接受的语言呢？
浏览 2提问于2012-12-14得票数 3
3回答
确定两个自动机之间的等价性的最佳或最简单的方法是什么？
也就是说，如果给定两个有限自动机A和B，我如何确定两者是否识别相同的语言？
它们都是确定性的，或者都是非确定性的。
浏览 11提问于2011-08-02得票数 8
回答已采纳
1回答
我需要帮助，我正在使用语言和自由上下文语法，我需要知道是否有一个算法或程序可以帮助解决成员资格问题，这意味着给出一个字符串"w“和一个FCG G，决定这个字符串是否在语言中。
我正在寻找一个库或程序，可以做这件事，以便稍后将字符串转换为自动机。
浏览 0提问于2015-12-01得票数 0
扫码
添加站长 进交流群
领取专属 10元无门槛券
手把手带您无忧上云
相关资讯
热门标签
云服务器
ICP备案
对象存储
腾讯会议
实时音视频活动推荐
腾讯云开发者
