-
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/说, α 相当... -
0 votesanswersviews
非确定性有限自动机 - Epsilon过渡
我想知道非确定性有限自动机是否可以在计算所有给定输入后使用epsilon转换到达接受状态?在一个简单的例子中,非接受状态s1有一个标记为1的箭头和一个指向接受状态s2的epsilon标记箭头,给定输入111,自动机能够像(s1,111)那样处理它(s1) ,11)(s1,1)(s1,空字)(s2,空字)因此接受输入? 任何帮助将不胜感激 . 谢谢 -
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
自动机理论中语言的定义
我现在正在参加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 ... -
1 votesanswersviews
导出有限自动机识别的语言的常规语法
我无法找到有限自动机识别的语言的常规语法 . 我面临的关键问题是常规语法和无上下文语法之间的混淆 . 我似乎无法区分它们之间的差异,我发现它们在某些方面非常相似,例如歧义 . 任何人都可以解释如何获得FA认可的语言的常规语法? -
0 votesanswersviews
如何确定无上下文语法是否描述了常规语言?
给定一个任意的无上下文语法,我如何检查它是否描述了常规语言? 我不是在寻找考试“技巧” . 我正在寻找一个可以编码的万无一失的机械测试 . 如果它有帮助,这是我作为输入可能会收到的CFG示例 . 具体来说,注意答案必须比寻找左或右递归复杂得多,因为另一种类型的递归的存在并不会自动暗示语法是不规则的 . S: A B C D X A: A a A: B: b B B: C: c C c C: c D... -
3 votesanswersviews
学习计算模型的好资源?
出于好奇,我试图确定我使用的系统的计算模型在功能上是等价的,并证明了等价性 . 我花在这个问题上的时间越长,我越怀疑系统不是图灵相当的 . 我对图灵机和递归可枚举语言的理解很好,但我不太了解具有较小功能的自动机(例如下推自动机),所以我不知道如何继续 . 首先,任何人都可以推荐一个很好的资源来学习不同的计算模型吗?我对语法,语言和自动机感兴趣,以及如何证明它们之间的等价和差异 . 理想情况下,资源...