问题标签 [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 投票
8 回答
130270 浏览

context-free-grammar - 正则文法与上下文无关文法

我正在为我的计算语言测试而学习,并且有一个想法是我遇到了问题。

我明白常规语法更简单,不能包含歧义,但不能完成编程语言所需的大量任务。我还理解上下文无关语法允许歧义,但允许一些编程语言所必需的东西(如回文)。

我遇到的问题是通过知道常规语法非终结符可以映射到终结符或非终结符后跟终结符或上下文无关的非终结符映射到终结符和非终结符的任何组合来了解我如何推导出上述所有内容.

有人可以帮我把所有这些放在一起吗?

0 投票
10 回答
23235 浏览

regex - 计算机是否可以通过用户提供的示例“学习”正则表达式?

计算机是否可以通过用户提供的示例“学习”正则表达式?

澄清:

  • 不想学习正则表达式。
  • 我想创建一个程序,该程序从用户交互式提供的示例中“学习”正则表达式,可能是通过从文本中选择部分或选择开始或结束标记。

是否可以?是否有算法、关键字等可供我使用 Google 搜索?

编辑:感谢您的回答,但我对提供此功能的工具不感兴趣。我正在寻找理论信息,比如论文、教程、源代码、算法名称,这样我就可以为自己创造一些东西。

0 投票
2 回答
376 浏览

java - 我可以确定正则表达式匹配的第一个字符集吗?

我希望能够计算所有字符的集合,这些字符可能与给定java.util.regex.Pattern. 更正式地说,给定 DFA 等价于某个正则表达式,我想要从起始状态开始的所有传出转换的集合。

一个例子:

该集合first应包含以下元素:

有任何想法吗?我很清楚我可以自己构建 DFA 并以这种方式确定相关状态,但我想避免这种麻烦(阅读:这对我来说不值那么多)。请注意,我的宿主语言实际上是 Scala,因此我可以访问所有核心 Scala 库(值得一提)。

0 投票
14 回答
1741 浏览

puzzle - 代码高尔夫:自动机

我使用这些规则制作了终极笑声发生器。你能用你最喜欢的语言巧妙地实现它吗?

规则:

在每次迭代中,都会发生以下转换。

0 投票
2 回答
2149 浏览

theory - 乔姆斯基的层次结构和图灵机应该如何影响语言设计?

我目前正在学习离散数学测试,我们正在学习乔姆斯基的层次结构和识别层次结构每个级别的自动机类型。我被告知大多数计算机语言都属于层次结构的“第 2 级和第 1 级”,但不准确。

我的问题是:

  1. 每个级别都有哪些功能?

  2. 这仅仅是理论基础吗?我想知道像 Dennis Ritchie 和 James Gosling 这样的语言设计师在设计 C 和 Java 时是否必须考虑到这一点。他们有吗?有人会如何应用这个?

  3. 我们被告知图灵机可以识别层次结构的第 0 级。如果有,是否有属于 0 级的语言特征?我猜这可能是自然语言处理,是吗?

0 投票
6 回答
2899 浏览

math - 高级形式逻辑/自动机理论教科书

我知道这更像是一个数学/形式语言/自动机/计算机科学问题,而不是一个编程问题,但我希望我能得到一些关于除了命题和谓词微积分之外的形式逻辑的易于理解的教科书(不是难以理解的专着)的建议。我对一元二阶逻辑Büchi Automata特别感兴趣。

目前,我只发现 了 Bakhadyr Khoussainov 和 Anil Nerode 的自动机理论及其应用。自动机、逻辑和无限游戏作者:Erich Grädel、Thomas Wilke(编)。和通信系统的形式模型:语言、自动机和一元二阶逻辑Benedikt Bollig ......在我头上。

0 投票
6 回答
15142 浏览

grammar - 如何构建生成这种语言的语法?

我正在学习有限自动机和语法测试,但我遇到了这个问题:

我相信我的作品应该遵循以下原则:

我的 C 产品如何记住 m 和 n 的数字?我猜这一定是一个上下文无关的语法,如果是这样,它应该是怎样的?

0 投票
2 回答
641 浏览

turing-machines - 我在哪里可以找到示例自动机和图灵机?

我正在学习一门非常基于 jflap 的课程的自动机测试。问题是我们没有太多的文档,而且我在 jlap 上找到的示例自动机,例如thisthis,不足以为即将到来的测试做准备。

我在哪里可以找到更多信息?任何其他具有示例图灵机的资源都显示为带有转换的图表,这也会有所帮助。

0 投票
4 回答
174 浏览

php - 通过 PHP 为搜索创建索引

你怎么能用 PHP 只搜索唯一的词,这样我就可以学习进行搜索的基础知识?

我在为问题制作多维数组时遇到了一些问题。

我的第一次不成功的尝试如下。

#1

这段代码的问题在于它结合了每个问题中的单词。似乎我不能使用explode,因为它似乎只制作一个一维数组。

我还运行以下代码尝试获取 question_id unsuccessfully

#2

0 投票
1 回答
420 浏览

wpf - WPF 上的元胞自动机

目前我正在攻读计算机科学的硕士学位课程,我想在 WPF 中实现一个元胞自动机。渲染性能必须足以显示包含 200,000 个单元的格子(网格)。

由于在 WPF 中更新视觉效果非常慢(由于视觉和逻辑树),也许最好使用旧的好 Picturebox (GDI+) 进行渲染和 WPF 来实现其余的软件。第二种选择是使用像素着色器 (HLSL),但我不知道 WPF 是否支持多通道着色器。

让我知道你的想法。