问题标签 [finite-automata]

我应该构建一个接受的 DFA

{ w | w 是一个单词，除了 'aa' 和 'aaa' }

这是正确的解决方案吗？粗线状态应该是结束状态。

编辑

抱歉，不知何故混合了两种不同的练习。已更正。

编辑 2

这是更正的解决方案（？）！

我得到了一个正则表达式，我想将其转换为 NFA，然后是 DFA。这是正则表达式：

a ( b | c )* a | aac* b

然后我使用汤姆森算法将其转换为 NFA：

这是DFA：

有人可以快速看一下让我知道我是错还是对？

我试图最小化这个 DFA：http: //img145.imageshack.us/img145/3006/dfac.png

这是我最小化的 DFA：http: //img195.imageshack.us/img195/4131/mdfa.png

我对么？谢谢

PS-这是作业。我们可以讨论家庭作业。我不是在问答案，我只是想知道我是否走在正确的轨道上，因为这是我第一次处理状态机。

我需要为 CS 类使用 McNaughton-Yamada 算法构建 DFA。问题是算法是补充材料，我不清楚它到底是什么。它是一种在给定 RegEx 的情况下找到 DFA 的方法，还是找到 DFA 并最小化它？我似乎找不到有关该主题的任何信息。

我很困惑，因为我们在课堂上发现 DFA 后我的老师展示的最小化例程似乎与我们书中描述的“标记”最小化没有任何不同。

感谢您的回复，

弥敦道

不太确定这是否是正确的论坛，但在理论计算机科学上建议我将它移到这里......

有限状态机的典型字母大小是多少？

我目前正忙于实现一个高性能的 FA 库，在继续之前需要做一些设计考虑。我的状态空间将按 2 147 483 647 ( Integer.MAX_VALUE) 的顺序排列，我觉得这已经绰绰有余，即使对于非一般用途也是如此。现在，剩下的就是字母空间。

假设字母表通常只由所有可显示的字符组成（在这种情况下，它可以存储为 abyte会带来非常好的性能），这有什么好处吗？还是应该将字母符号翻译成Strings，以便您拥有字母标签？在这种情况下，我需要保留一个将 aString转换为 a或的 Map int，具体取决于我想要制作的大小。shortbyte

DFA 必须具有以下四个属性：

• DFA 有 N 个节点

• 每个节点有 2 个传出转换。

• 每个节点都可以从其他每个节点访问。

• DFA 是从所有可能性中以完全一致的随机性选择的

这是我到目前为止所拥有的：

1. 从 N 个节点的集合开始。
2. 选择一个尚未选择的节点。
3. 将其输出连接到其他 2 个随机选择的节点
4. 将一个转换标记为 1，将另一个转换标记为 0。
5. 转到 2，除非已选择所有节点。
6. 确定是否存在没有传入连接的节点。
7. 如果是这样，从具有超过 1 个传入连接的节点窃取传入连接。
8. 转到 6，除非没有没有传入连接的节点

但是，这是算法不正确的。考虑图中节点 1 有两个连接到节点 2（反之亦然），而节点 3 有两个连接到节点 4（反之亦然）。那是这样的：

1 <==> 2

3 <==> 4

其中，<==> 我的意思是双向两个传出连接（因此总共有 4 个连接）。这似乎形成了 2 个派系，这意味着并非每个州都可以从其他州到达。

有谁知道如何完成算法？或者，有人知道另一种算法吗？我似乎隐约记得可以使用二叉树来构造它，但我不确定。

我发现元类的存在和使用可以通过为类创建过程提供一个优雅的句柄来使您免于编写大量代码。我在我的应用程序中使用它，其中实例化了几个交互服务器。详细说明：

每个设备都实例化一个特定于其操作的服务器类，它是（...的子类）的子类，最终是这一BaseServer类。现在，有些设备服务器需要一个ThreadedTCPserver，有些需要一个SimpleTCPServer（模块：）socketserver。它们不能都派生自同一个类，因为使用ThreadingMixin覆盖了SimpleTCPServer.

为了处理这个动态类配置，我创建了一个MetaServerType，它选择 BaseServer 的基类 as(SimpleTCPServer,)或 as (ThreadedTCPServer,)--> 生成我想要的动态配置的服务器类的结果！（呜呼）

现在，我的问题来了：我想使用一个存储参数的配置文件，这些参数默认由 MetaServerType 使用。例如：config.default_loglevel 或 config.default_handler 等。并且可以根据元类规范覆盖单个服务器（从命令行或其他方式）。

只有一个配置对象的实例通过程序流是一种好的设计实践吗？实现这一点的一种方法是在元类的类主体中初始化配置对象——但我的程序流程从其他地方开始，这意味着元类被多次调用，从而产生了各种配置实例。似乎在导入时调用了元类（？）

因此，非常欢迎您提供详细的答案：

1. 如何为元类提供配置信息？
2. 让单个配置实例通过程序流进行编辑、更新甚至最终编写的好方法是什么？
3. 元类的输入参数能否以某种方式扩展超出Metaclass.__new__(meta, name, bases, attrs)？
   4. 额外的问题：这是否让我们更接近（服务器的）有限状态机，以便状态（而不是实例）可以“暂停”或“恢复”？

我为这个电路画了一个有两种状态的mealey机器，但是我不能画一个摩尔机器状态图，我不明白怎么做。

电路如下：

该电路是具有一个二进制输入 X 和一个二进制输出 Y 的摩尔机器。输出 Y 取决于在最近的两个时钟脉冲处采样的两个 X 值。Y 应该始终是这两个输入值的 XOR 组合的结果。

因此，基本上，如果状态为 1，输入为 1，则变为 0。如果为 0，则变为 1，则变为 1。只要与状态相反，它就会变为 1 .

这在状态图上是如何表示的？转换表呢？

我有一个关于将正则表达式转换为非确定性有限状态自动机的问题：

将 (a*|b*)* 转换为 NFA。我的尝试如下：

我完全偏离标准了吗？还是有些地方？

NB E => ε

与彼此相比，DFA 和 NFA 的相对优缺点是什么？

我知道 DFA 比 NFA 更容易实现，并且 NFA 到达接受状态的速度比 DFA 慢，但是还有其他明确的、众所周知的优点/缺点吗？