computer-science - 创建确定性有限自动机

Question

我需要通过具有以下属性的语言 {a,b,c} 创建一个非空 DFA：

1. 第一个符号是a。
2. 有偶数个b。
3. 最后一个符号是c。

我只是想知道，我应该创建 3 个单独的自动机，然后使用交叉点将它们组合起来，还是应该只创建一个，如果是这样，它怎么会有偶数个 b？我知道我可以交替使用这些状态，但不知道如何将它们结合起来。

谢谢

Answer 1

这是你的自动机（假设 0 是偶数，因此 0 b 是可以的）：

[start](a) -> [1]
[start](b,c,<eoi>) -> [reject]

[1](a) -> [1]
[1](<eoi>) -> [reject]

[1](c) -> [2]
[1](b) -> [3]

[2](<eoi>) -> [accept]
[2](c) -> [2]
[2](a) -> [1]
[2](b) -> [3]

[3](<eoi>) -> [reject]
[3](a,c) -> [3]
[3](b)->[1]

“输入结束”在哪里。

状态1：偶数个b，最后处理的符号不是c。状态2：偶数个b，最后处理的符号是c。状态3：奇数个b。