问题标签 [automata-theory]
For questions regarding programming in ECMAScript (JavaScript/JS) and its various dialects/implementations (excluding ActionScript). Note JavaScript is NOT the same as Java! Please include all relevant tags on your question; e.g., [node.js], [jquery], [json], [reactjs], [angular], [ember.js], [vue.js], [typescript], [svelte], etc.
automata - 为字符串 {0,1} 设计一个 DFA,当它反转时相当于 2 mod 7?
为字符串{ 0,1 }设计一个DFA,当反转时它 相当于 2 mod 7的十进制?
regular-language - 当且仅当它是有限的 100 => n <= 0 时,语言 a^nb^2n 怎么可能是正则的?
当且仅当它是有限的 100 => n <= 0 时,语言 a^nb^2n 怎么可能是规则的?
我知道当 n=>0 时( a^nb^n )这种形式的语言是不规则的,因为我们需要一个临时内存来跟踪 a 和 b 的数量,而且我知道每一种有限语言都是常规的,但我不明白是什么使类似形式的有限语言成为常规的?我们如何证明呢?我需要一些线索,除了能够获得其等效的正则表达式之外,我还需要一些更详细的解释..
谢谢
finite-automata - 可以设计的 dfa 数量
我们能不能计算出在以下约束条件下可以设计的 dfa 的总数(即最大数量):|Q|=2{No. 状态数为 2},|Ɛ|=2{No. 字母} 和 |F|=1{No. 最终状态} ?
opengl - OpenGL是“状态机”吗?
OpenGL 通常被描述为“状态机”,因为据我所知,它由可以通过其 API 设置的全局变量组成,并且它们可以更改/定义其行为。例如,可以设置当前颜色或变换矩阵。许多状态变量具有连续的取值范围。
但是,据我了解,计算机科学中的“状态机”或“有限状态机”被定义为状态(作为节点)和转换(作为有向边)的有向图。
用于描述 OpenGL 的“状态机”术语是否与一般计算机科学中定义的“状态机”相同。
finite-automata - FA 用于形成 AGP 的语言
假设一组输入符号 Σ={a,b} , L={ε,a,abbb,aabbbbbbbbb,aaabbbbbbbbbbbbbbbbbb,...}
那么上述语言的有限自动机(即形成一个简单的算术几何级数)将是?
computer-science - 给定一个文件,如何生成一个只接受文件中存在的单词的 NFA?
给定任何文档,我希望能够生成一个仅接受文档中存在的单词的 NFA。基本上,我想编写一个能够从任何文档动态生成 NFA 的函数。是否有任何预先存在的算法已经这样做了?
computation - L={a^(n)b^(n)c^(n)|n>=1} 的下推自动机 (PDA)
我正在为非上下文无关语言 L={a^(n)b^(n)c^(n)|n>=1} 构建一个下推自动机,并想到了两种方法。
第一种方法:-
我认为对于字符串中的每个“a”,我会将 3 个“a”推入堆栈,对于字符串中的每个“b”,我现在将为字符串中的每个“c”从堆栈中弹出 2 个“a”我堆栈中仍会有 1 个“a”。
第一种方法的问题:-生成的语言变成这样 L={a^(p)b^(m)c^(n)| p>=1 并且无法确定如何定义 m 和 n }
第二种方法:-
我们知道 L={ a^(n)b^(m)c^(m)d^(n) | n>=0 } 是上下文无关语言,L={ wxw | w∈(a,b)* } 也是上下文无关语言。
所以,我认为 L={ a^(n)b^(m)b^(m)c^(n) | n>=1 和 m=floor((n+1)/2) }
第二种方法的问题:-不知道我们是否可以在不干扰堆栈元素的情况下在 PDA 中计算 floor(n+1/2)。
请帮助确定如何在第一种方法中定义 m 和 n 以及如何在 PDA 中找到 floor((n+1)/2) 。
如果需要,两者都可以使用 JFLAP 文件。
context-free-grammar - 这个语法上下文是免费的吗?
正如我所说的,第一个生产规则是无上下文的(因为左侧小于右侧),但对于第二个生产规则,它不是(因为左侧长度等于右侧)。
好吧,我们可以在这个陈述中对这个语法说些什么。它是否与上下文无关?
computation-theory - 如何为 { x#y | 构建 PushDown 自动机 x, y ∈ {0,1}* 和 x≠y }?
谁能解释为什么这是一种上下文无关语言以及如何为此构建下推自动机?我在链接解决方案上找到了解决方案 但我无法理解该语言。