问题标签 [automaton]

假设我有一个正则表达式列表（从外部源读取 - 文件、数据库等）。我想检查字符串匹配这些正则表达式中的哪一个。

我可以创建遍历所有这些正则表达式并匹配它们，但列表可能很大，这是一个关键操作。

我可以将所有这些正则表达式组合成一个（在它们之间有 |），但问题是我只能识别第一个匹配的正则表达式，而不是全部。

另一个想法可能是为所有这些正则表达式创建一个自动机，并用相应的正则表达式的索引来标记最终状态。我正在查看http://cs.au.dk/~amoeller/automaton/，一个似乎能够使用正则表达式和自动机的库，但不确定它是否可以扩展来解决我的问题。

你还有其他建议吗？

为了澄清一些评论，我添加了一个代码示例：

将打印出来

如您所见，只有第一组匹配，而我看不到匹配其他两组的方法。

更多发现 - 使用上面的自动机库，问题将简化为：如果连接两个或多个自动机，如何识别最终状态与原始自动机中的哪一个对应？

我想知道元字符dk.brics.automaton支持什么。

它甚至不支持.运营商吗？当我给a.b它时，它会进入无限循环，直到Err: OutOfMemory.

有没有其他方法可以达到与 相同的目的.？

如果您对dk.brics.automaton支持哪些运营商有想法，请在此处帮助列出它们。

这是我正在研究的元胞自动机的代码：

这是我运行它时的错误消息：

有没有搞错？为什么我会收到此错误，我该如何解决？几个小时以来，我一直试图找出错误，如果我能得到帮助，那将是一件幸事。

这是我正在研究的元胞自动机的代码：

更新：

}

这是我在 3 个时间步输入规则 30 时收到的错误消息：

更新的错误消息：

代码中注明了相应的行。为什么我会收到此错误，我该如何解决？几个小时以来，我一直试图找出错误，如果我能得到帮助，那将是一件幸事。

我对 lr(0) 解析器有疑问。例如，我有以下语法：

如果我尝试构造 lr0 自动机的第一个状态，我会得到以下第一个状态：

所以在我看来，这是一个愚蠢的怀疑。因为我有“S ->”。在第一种状态下，这是 lr0 解析器中移位/减少的情况吗？导致解析器可以通过非终结符 S 转移动作，或者通过空转换减少动作（我认为）。

我已经在网上搜索了一个带有空转换的示例，但我没有找到。

我正在尝试解决 Peter Linz 的形式语言和自动机简介中的一些问题。在第 2.1 节（确定性有限接受器）中，我无法编写自动机，需要帮助来解决它。

问题 17-(f)，第 2 章：

na是a单词中 的字符nb数，是单词中的字符数b。

我有解决方案，但我不知道如何在这里绘制它。

我想知道如何证明具有顺序约束的语言是规则的。例如，如果您有 Σ = {1,2,3,4,5} 其中 L（Σ* 的子集）= (a1,a2,...an) 使得 an+1 大于 an你证明这是一种常规语言？

例如 α = (1,3,5) 会被接受，但 α = (1,4,5,2) 不会。

我正在尝试实现这个自动机示例：http ://www.javacodegeeks.com/2012/03/automaton-implementation-in-java.html 。

但是，在运行程序时一直显示错误：

我尝试修改导致错误的行，但没有任何改变。有人可以看看这个程序并帮助我找到解决方案吗？

我有以下 .java ：

状态.java：

注意：我不得不将原来的“public Stat next()”更改为“public State next(Input in);”

输入.java：

测试.java：

为了找到一个同步词，我总是使用反复试验，这对于小型 DFA 来说很好，但在大型 DFA 上就没那么有用了。然而，我想知道的是，是否存在一种用于确定同步词的算法，或者是否有一种方法能够判断一个同步词不存在。（而不是仅仅说“我找不到一个，因此一个不存在”，这绝不是一个证明）。

我已经在谷歌上环顾了一下，到目前为止，我只是遇到了一些方法来确定同步词长度的上限和下限将基于状态的数量，但这对我没有帮助。

我需要为这种语言创建一个 NFA（或 DFA，还不知道会是哪个）：

count(w, z) 定义字母 z 在单词 w 中出现的频率。在这种情况下，'a' 是 2 的倍数，'b' 是 3 的倍数。

有效单词示例：babab、aabbb、bbaab、bbbabbba

我努力为此创建一个自动机，所以我想我会先尝试为它创建一个正则表达式，然后使用这种方法将其转换为 NFA ，因为我可以在正则表达式测试站点上轻松地对其进行测试。但这也没有用。我最终得到了太多看似没有尽头的组合。

如果不使用某种计数机制，我不知道如何为此创建正则表达式。有人可以给我一个提示吗？