问题标签 [automaton]

鉴于语言

大号₁ ={(i|l)p(f|g)n(f|h)m(f|i)r(l|m)p : n + m > r > 0, p >= 0}

和

大号₂ =(f|g)*(h|i)+

_{为 L 1} ∪ L ₂和（另一个） L ₁ ∩ L ₂制作一个自动机。

我知道 L ₁是 CFL 并且您需要 PDA 来解析它，我知道 L ₂是 RL 并且要使用 DFA。
我的问题是：你如何建立交叉点（和联合）？也就是说，你制作自动机的实际语言 L ₃ = L ₁ ∩ L ₂是什么，你如何计算它？

在大学里，他们要求我使用语法和下推自动机来检查部分 Java 代码的语法。由于我以前没有使用过这个自动机，所以我对它们的工作原理有所了解，我认为这个自动机在检查代码语法方面不是很有用，因为下推自动机用于验证任何标记之间具有一定比例的语法像“0^n 1^2n | n >= 0”。

代码语法中不存在令牌之间的这种比例，因此我认为下推自动机在这种情况下没有用。

• 我是正确的？
• 我必须抱怨他们要求我做的这项工作吗？

我正在使用 Django 并尝试为有限自动机创建一个模型，这就是我到目前为止想出的：

现在我想对转换函数进行建模，每个自动机都有一个：

示例：我们可以使用 symbol1 从 state1 转到 state2

我不确定如何处理，任何帮助将不胜感激！

你会如何用 Java 设计一个分布式滑动窗口算法？我有一个用于模式检测的自动机。它要么处于接受状态，要么处于无效状态。

假设我正在寻找的模式是年龄：20，然后是年龄：30。该模式是具有两个值（20、30）的 LinkedList。自动机一次接受一条记录。它保持 LinkedList 的状态，以了解到目前为止它匹配了多少。它一次接受一条记录，当记录与 LinkedList[i] 匹配时，它会执行 i++。否则，它无效，这意味着 i=0。

自动机将让所有记录流过它，并可靠地识别 20 和 30 的所有模式。

当从滑动窗口调用自动机时，情况会变得更加复杂。滑动窗口是基于时间的。首次调用时，会设置一定的持续时间，例如 10 秒。窗口保存当前时间戳，每次调用自动机时，它首先检查保存的时间戳与当前时间。如果它早于 10 秒，则窗口会重置时间戳并使自动机无效[因为自动机匹配的任何内容都可能早于 10 秒。我说可能是因为在某些情况下，只是窗口中的一些记录较旧，而其他记录还可以，但是状态仍然无效。窗口是一个近似值]。

现在，真正的挑战是利用多台 PC 使用滑动窗口和自动机来查找数据中的模式。我发现了许多提到算法的论文，例如这里http://www.softnet.tuc.gr/~minos/Papers/vldbj15.pdf，但我想将现有算法重用于具有模式的分布式基于时间的滑动窗口检测（或与其他自动机）。

你会如何设计它，或者你能推荐 Java 中的任何算法吗？基本上，这种情况是有大量数据以高速到达，因此需要使用多台 PC。数据需要在多个节点上进行分区，并且这些节点需要成功检测模式。

或者，将接受任何以 Java 或其他语言实现任何分布式滑动窗口算法的答案。

有人可以帮我找到语言 L 的 DFA：

使用开源 Java 自动机库，例如：org.apache.lucene.util.automaton 或 dk.brics.automaton，如何构建自动机进行前缀匹配？

例如：从字符串集 ["lucene", "lucid"] 创建的自动机，在给定 "luc" 或 "luce" 时将匹配，但在给定 "lucy" 或 "lucid dream" 时不匹配。

请帮我制作以下条件的DFA：

L = { w: n _a (w) mod 3 > n _b (w) mod 3 },

其中 n _a (w) 表示ain w 的出现次数，n _b (w) 表示bin w 的出现次数。

鉴于语言

我知道这是常规语言，可以用 PDA 来表示。L1L2

但我不明白答案L是什么。这个解决方案是如何计算的？{a2nb6n|n≥1}

鉴于这种：

我想知道是否有一种方法可以创建一种算法来自动执行此操作：

我正在考虑创建两个列表（事件和状态）以这种方式使用这些值：

on(Events.valueOf(EventsList.get(0))).to(States.valueOf(EventsList.get(0)).trans it(

...

但是，我不确定哪个是迭代的模式。

我真的很感激任何建议。

谢谢

//////////////////////////// 更新///////////////////// //////////////

基于@Dukeling 建议的解决方案

}

对于 Σ = {0, 1, 2} 上的上下文无关文法 G，起始变量 S：
S → 0S0 | 1S1 | 2S2 | Y
Y → 22

我如何把它变成一个等效的下推自动机