问题标签 [automaton]

我正在尝试制作一个脚本来测试网络交换机和路由器的行为。这个想法是在具有连接到不同路由器端口的多个网络适配器的主机上运行基于 scapy 的脚本。该脚本将在一个端口上发送探测数据包，并观察探测数据包如何分发到其他端口。

过去，我使用多处理 python 包与 scapy 并行处理。在幕后多处理使用分叉进程并提供方便的进程间通信原语。我想这次我也可以这样做：创建一堆子进程，每个子进程都在自己的接口上进行嗅探，并将嗅探到的数据包推送到父进程的队列中。作为奖励，这种方法也允许在远程主机上运行嗅探器。

但是自从我上次玩多处理和 scapy 以来，我发现了 Automaton scapy 模块，如果可能的话，我更愿意使用它。这个模块有receive_condition方法装饰器，但我不知道怎么做

1. 设置 Automaton 模块嗅探的接口
2. 确定接收到的接口数据包

也很高兴知道数据包是入口还是出口，但我怀疑这可能是不可能的。

有什么建议么？

我有一个关于如何将正则表达式转换为自动机的问题？我听说过 Gluskov 算法，但我找不到关于它的正确文档。

示例：我有一个正则表达式(a*|b*) U (a*a|c*)*，我想用一个简单的算法在自动机中进行转换。

请帮我

I am struggling a bit with the meaning of determinism and nondeterminism. I get the difference when it comes to automata, but I can't seem to find an answer for the following: Is a NFA to DFA transformation deterministic?

If multiple DFAs can be constructed for the same regular language, does that mean that the result of a NFA to DFA transformation is not unique? And thus a nondeterministic algorithm?

I'm happy with any information you guys might be able to provide.

Thanks in advance!

我正在尝试开发一个在 Java 中执行非确定性有限自动机的模拟。第一个命令行参数是定义机器的文本文件。第二个参数是输入字符串。如果它接受字符串，它会打印到标准输出“accept”，然后是它可以结束的接受状态列表。如果它拒绝，它输出“reject”，然后是所有可能的结束状态的列表。

例如，文本：

看起来像：

输入字符串为 10 将输出

输入字符串 000 将输出

我需要关于使用什么数据结构的建议。我考虑过使用哈希图和集合，但我不确定。

我遇到了这个练习，我想了几个小时，但一无所获。

我们的字母表是{1...n}，我们的语言 Ln 包含下面的所有单词，Σ*因此语言中的每个单词都不包含字母表中的至少一个字母。

• 例如：如果 n=5，则该词w={111223432}在该语言中，因为'5'该词中缺少该词。这个词w={1352224}不在语言中，因为所有的字母1...n都在这个词中。

我需要为这种有n+1状态的语言设计一个 NFA。

再一次，我尝试了一些事情，但并不是一个好主意。

举个例子：

假设我想设计一个 PDA 来识别字母表 {1,0} 上所有非回文字符串的语言。如果我设计一个 PDA 可以识别 {1,0} 上所有回文字符串的语言，然后将所有接受状态交换为失败状态，反之亦然，我会得到所需的 PDA 吗？

编辑：无论哪种方式都有一个简单的正式证明吗？

我有这个家庭作业练习：

假设我们有一种语言 L。我们知道该语言pref(L)（ 的所有前缀L，包括L本身的所有单词）是一种常规语言。这是否意味着该语言L也是常规的？

我采用 NFApref(L)并将其（通过从 的 2 个 epsilon 转换q0）划分为 2 个单独的 NFA，分别为 1 个定义L和另一个定义pref(L)\L。

我实际上得到的是 NFA L，这意味着它是常规的。

我不确定这是正确的方式或是否合法。我很高兴有另一个线索。

提前致谢，

亚龙。

我将如何确定每个状态是否具有唯一的输入/输出序列？有没有标准化的技术或方法？我似乎无法在网上找到任何东西。

谢谢你的帮助！

over(0,1) 的有限自动机如何不接受任何字符串？我只能想到

最终状态 F 为空集。请问这是真的吗？

我有以下问题：有两个确定性有限自动机应该相交并转换为单个最小确定性有限自动机。有没有算法可以做到这一点？

我知道我可以通过创建两个自动机的笛卡尔积并将结果转换为 DFA 来创建 NFA，但这是一个耗时的过程。有没有更简单的方法来创建两个自动机的交集？

顺便说一句：这是解决方案：

我尝试了我下面描述的方法，但我无法想象如何获得解决方案：计算两个 DFA 的补码为我的两个新 DFA 提供了恰好两个接受状态。现在我必须将它们组合起来并最小化它们，但是我从哪里可以得到第三个接受状态呢？