问题标签 [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.
context-free-grammar - What is the relationship between derivation and derivation trees?
It was written in ullmans book but i did not under stand well how it works. Can anybody explain even in simple context? I'd be really glad.
automata - 为什么我们不能将寄存器自动机简化为符号自动机?
在考虑自动机时,它们通常被认为是有限字母表。以下是两种类型的自动机,它们可以处理无限字母表上的单词(为清楚起见,包括定义)。
分别附加在单词开头和结尾的符号 [ 和 ] 是分隔符,不在字母表中。也就是说,自动机处理形式为w = [ v ] 的单词,其中v是字母表的一个元素。
字母表上的k 寄存器自动机A 是一个 5 元组 (Q, q_0, F, t_0, P),其中:
Q 是一组有限状态;
Q 中的 q_0 是初始(或开始)状态;
F(Q 的子集)是最终(或接受)状态的集合;
t_0 : {0,1,...,k}--> 字母联合 {[,]} 是初始寄存器分配;和,
P 是形式为 (i, q)-->(q', d) 或 q-->(q', i, d) 的有限转换集,其中 i 在 {0,1,...,k }, q, q' 在 Q 和 d 在 {Stay, Left, Right}。
符号有限自动机 (SFA) M 是一个 5 元组 ( A , Q, q_0, F, d),其中:
- A 是一个有效的布尔代数(字母表);
- Q 是一组有限状态;
- Q 中的 q_0 是初始(或开始)状态;
- F(Q 的子集)是最终(或接受)状态的集合;和,
- d(Q x Y_A x Q 的子集)是有限的转换集。
研究表明,对于寄存器自动机,等价是不可判定的,但在符号自动机中,等价是可判定的。我的问题是为什么?这两种自动机类型的工作结果相似,那么为什么我们不能将一种归约到另一种呢?
有人告诉我这是一个非常简单的问题,但我似乎无法在任何地方找到答案,所以感谢您的帮助!:)
我目前的想法是,SFA 要求他们的字母表是有效的布尔代数,而 RA 可以处理任何事情,因此他们的字母表不必遵循布尔代数的规则。我不知道如何正确地将这个想法转化为任何有用的东西。
finite-automata - 给出生成以下语言的上下文无关文法
给出生成以下语言的上下文无关文法。在所有部分中,字母 ∑ 是 {x,s}。{w| w 以不同的符号开始和结束}
automata-theory - 正则表达式,其中字母 b 从未三倍
我需要有关正则表达式的帮助。我想要一个正则表达式,其中字母 b 永远不会增加三倍。这意味着其中没有任何单词包含子字符串 bbb。语言只包含字母 {a,b}
c++ - C++ 中 NFA 到 DFA 的实现
标题说明了一切。我需要一些想法。nfa 输入看起来像这样,并且没有 epsilon 移动。
等等,这意味着 1 和 2 是最终状态,而使用“a”我可以从状态 0 到状态 2。
我用
保存数据,其中 v[i] 是包含从状态 i 出发的所有路径的向量。 当有多个状态时,我需要一个关于如何命名新状态的想法
因为我无法创建状态 123 或类似的东西。 我如何检查一个多重集是否已经转换为一个状态?
regular-language - 自动机理论中的正则表达式?
我有以下语言及其正则表达式
{w ∈ {a, b}* : w 以 bab 为前缀,以 babaa 为后缀}
回答:
正则表达式 = bab(a ∪ b)*babaa ∪ babaa ∪ bababaa
为什么需要加粗部分?
c# - c#中如何在数组之间传输?
我有一个自动机理论项目,我想将算法转换为编程语言(不管用什么编程语言来解决这个问题)
嗯,我有这些命令
我们输入一个字符串,然后将其转换为 char 以便我们进行比较,
例如我们输入了这个输入
01001
为了清楚起见,我将添加更多输入以了解我的意思,
01000001
{有效输入}
{错误输入}
0
{错误输入}
我们将检查第一个数字是否为0,如果是,我们将此字符串复制到另一个数组1,然后将其转换为1,如果相同则将其复制到数组2,然后在这里我们需要使用for或进入一个循环foreach,我们想检查下一个值是否为 0(没有最后一个字符),所以我使用 a.length-1 来确保它不会使用最后一个,当我们看到新值 1 时,我们移动到最后一个数组,必须为 1。我们将使用 Console.WriteLine(""); 程序遵循顺序
我做了类似的东西(在 C# 中):
如何制作新数组并复制并使用它来签出
regular-language - DFA 可以识别多少种语言?
根据 Sipser 的《计算理论导论》:如果 A 是机器 M 接受的所有字符串的集合,我们说 A 是机器 M 的语言,写成 L(M) = A。我们说 M 识别 A ...一台机器可以接受多个字符串,但它总是只能识别一种语言。并且我们说如果 A = {w| 则 M 识别语言 A M 接受 w}。
我想这个问题已经得到了回答,但我想知道是否有人对此有任何想法,如果我们可以说关于常规语言的子集有什么有趣的事情,是否可以说原始 DFA 识别它们并且原始 DFA 和识别较小语言的 DFA 之间是否存在任何有趣的关系