问题标签 [pushdown-automaton]

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 投票
3 回答
1674 浏览

language-theory - 我如何设计这个下推自动机的转换函数?

我正在学习 PDA 上的测试,我想知道如何设计一个识别以下语言的下推自动机:

如何设计一个转换函数来识别是否n-m大于0

如果你有一些课程材料解决了这个级别的练习,请放一个链接。

0 投票
3 回答
2008 浏览

yacc - 从 BNF 文法导出状态机

我正在尝试整理 XSS 安全字符串插值方案的概念证明。

给定一个带有替换的字符串,

我想把它分解成文字部分和替换("Hello<b>" planetoid "</b>!"),然后在文字部分上从左到右运行一个状态机。当我达到一个插值(planetoid在上面)时,我需要能够从状态到一个适当的转义函数。

有谁知道如何使用 lex/yacc/bison 派生状态机并能够将语法中的标签与输出状态相关联的任何示例?我想派生一个我可以在 javascript 中使用的状态机,并尝试替换 PHP 的底层字符串实现。

这里描述了我这样做的原因。

干杯,迈克

0 投票
2 回答
226 浏览

turing-machines - 可判定性问题

可以有一个 NFA 决定实数吗?

0 投票
1 回答
3359 浏览

c# - 如何在 C# 中实现下推自动机?

我想为 PDA 编写代码。我将如何在 C# 中做到这一点?

0 投票
1 回答
1416 浏览

pushdown-automaton - (a^nb^n)^mc^m 的下推自动机

我一直在为这个自动机构建转换功能。

我想我应该为每个 a 堆叠一个 1 并为每个 b 取消堆叠它

c 的数量等于 ab 对的数量,所以我认为我应该为遇到的每个 b 堆叠一个 0。问题是:我如何同时取消堆叠 1 和添加 0?

0 投票
2 回答
3093 浏览

context-free-grammar - 设计一个下推自动机来计算字符数

字母:a、b、c 我正在尝试定义一个接受

我认为可以接受的一些字符串是:#abc#; #aabbcc#; #aaabbbccc#; #abbccc#; #aaabbc# 等 a、b 和 c 的数量不一定相等。

在最右边的黑色空间上启动下推自动机的头部。

通常我把我的 PDA 写成列:

等等...

0 投票
1 回答
2566 浏览

regex - 下推自动机,可产生字符串的翻转和反转

字母表:0、1

考虑一个翻转,翻转每个字符:0 -> 1;1 -> 0 所以如果 w = 0011 那么 w-flip = 1100

考虑反向是颠倒顺序的字符所以如果 w = 01101 那么 w-reverse = 10110

现在我正在尝试制作一个 PDA,它采用字符串 w,然后打印 w,打印(w-flip-reversed)

所以这将打印:“011001”

考虑 # 是一个空白字符。所以一个字符串会开始 #011#

转换表如下所示:

等等

有任何想法吗?

0 投票
4 回答
7966 浏览

context-free-grammar - 将上下文无关语言转换为下推自动机的程序?

我在网上找不到任何小程序或程序来将上下文无关语言转换为下推自动机......任何帮助将不胜感激。

0 投票
3 回答
713 浏览

turing-complete - 是否可以编写一个自我解释的 FSM 或下推自动机?

对于这个新手问题,我很抱歉,但如果可能的话,我需要一个快速的答案来告诉朋友。

0 投票
4 回答
11257 浏览

dfa - DFA 到 PDA 转换

我正在寻找一种将确定性有限自动机转换为下推自动机的算法。

任何帮助表示赞赏。

谢谢!