问题标签 [automata]

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.

0 投票
5 回答
20528 浏览

automata - PDA 接受包含 a 多于 b 的字符串语言

制作 PDA 以识别以下语言:a 多于 b 的字符串语言

我已经为这个问题苦苦挣扎了好几天了,我似乎已经完全陷入了精神障碍。任何人都可以为我如何解决这个问题提供一些指导或指导吗?

0 投票
1 回答
1748 浏览

automata - 在 PDA 和 CFL 中抽取引理

我有一个引理问题,我完全坚持...

L = {w ∈ {a, b, c}∗ : na (w) < nb (w) < nc (w)}

是不是节能灯?

我要求它不是 CFL,因为只有一个堆栈来记住所有这些条件是不够的。你可以记住 na (w) < nb (w) 或 na (w)< nc (w),nb (w) < nc (w) 但不是 na (w) < nb (w) < nc (w)。另外,我认为如果语言是 a^pb^2pc^3p 而不是我打气 |vy| p 次 L 不是 CF 但是你有可能抽 p 次吗?

或者对解决方案有什么想法?

0 投票
2 回答
1118 浏览

regex - 三进制数,正则表达式

我正在寻找一些正则表达式/自动机帮助。我仅限于+或 Kleene Star。解析表示三进制数的字符串(如二进制,只有 3),我需要能够知道结果是否为 1 小于 4 的倍数。

所以,例如120 = 0*1+2*3+1*9 = 9+6 = 15 = 16-1 = 4(n)-1

即使是指向模式的指针也会非常有帮助!

0 投票
2 回答
2116 浏览

java - 如何在java中绘制自动机

我想画一个带有边缘和循环状态的自动机,像这样 http://pop-art.inrialpes.fr/~girault/Cours/Automates/td5.html,你有一个例子

0 投票
1 回答
1666 浏览

complexity-theory - 上下文无关语言中的联合

上下文无关语言集合的联合总是上下文无关的吗?证明你的答案......

我知道答案是肯定的,但我该如何证明呢?

0 投票
4 回答
4343 浏览

java - 哪些是实施 DFA 的最佳方式?

我知道可以使用 if-else 方法和图形方法来实现 DFA,但是还有其他实现它们的方法吗?实际上,我正在为正则表达式创建一个 JavaCode 生成器,到目前为止,我已经完成了两种可能的方法(if-else 和图形方法),但我想提供更多可能的方法。我认为也许它可以使用一些数据结构作为转换的 Set 或 Map 来实现。

0 投票
1 回答
1231 浏览

compiler-construction - 如何处理作为有限自动机实现的词法分析器中的空格?

我为一种简单的编程语言创建了词法分析器。现在我使用确定性有限自动机代替正则表达式(Java 中的 RegEx)。自动机工作得很好,但它不会报告错误,例如,如果我在源代码中有 moduleclouds(模块和云都是关键字)。相反,它将创建两个名为 KW_MODULE 和 KW_CLOUDS 的令牌。有人可能会争辩说,如果自动机处于 KW_MODULE 的最终状态,我可以提前寻找空白。但这并不能解决问题,因为在语言中我可以有类似 8-6 的东西(不被空格分隔),它可以正确地翻译成标记 INT DASH INT。

我知道在解析器的语法中处理空格不是一个好主意。

我的自动机实现为矩阵(行是状态,列是字母表中的字符,单元格是过渡状态)。当自动机进入最终状态时,我将自动机重置为从开始状态开始。

我认为问题在于这种编程语言不使用分号。例如:

模块; 云;

相反,它使用空白来分隔线条:模块云

提前致谢。

问候。

0 投票
2 回答
1181 浏览

sql - SQL 是否有任何有限状态机定义?

有谁知道是否有 SQL 的有限状态机定义,例如 PL/SQL、SQL92 或 SQL99..

不知道有没有sql的语法定义。。

0 投票
3 回答
1314 浏览

regex - 显示带有 count(1s) = count(0s) 的位串是不规则的

令 L 为由字母表 {0,1} 上的字符串组成的语言,其中包含相等数量的 1 和 0。

例如:

你如何证明 L 不是常规语言?

0 投票
1 回答
1826 浏览

numbers - 如何为偶数十进制数构建有限自动机?

我必须做这个练习,我完全不知道怎么做。我之前构建了一些 FA,但使用的是二进制数。除了十进制数字,我怎么能做到这一点?