不以 ba 结尾的有限自动机字符串

Question

问题：构建一个只接受那些不以 ba 结尾的单词的 FA。我想为这个问题绘制 DFA，但我不明白我该怎么做请帮我画这个

Answer 1

对于不以 ba 结尾的语言，RE 是 (a+b)*(aa+bb+ab)

此处语言结束于 aa 或 bb 或 ab

从 RE 制作 DFA 你可以使用这个希望对你有帮助 https://cyberzhg.github.io/toolbox/nfa2dfa

在此给定的 DFA 中..它接受长度为 2 或大于 2 但不以 ba

结尾的字符串

Answer 2

我们需要跟踪我们是否看到了 ba 的子字符串，如果我们看到了整个东西，请确保我们当时不处于接受状态。

----->(q0)--b-->(q1)--a-->(q2)

这里，(q0) 接受，(q1) 接受，(q2) 不接受。 (q0) 对应于没有看到字符串 ba 的任何部分，状态 (q1) 对应于看到第一个符号，而 (q2) 对应于看到整个字符串。因此，缺少的转换应该是：

q0 到 q0 符号 a，因为如果我们还没有开始看到 ba，a 就没有帮助；我们需要一个 b
q1 到 q1 在符号 b 上，因为如果我们看到 b，我们总是至少看到 ba 中的第一个符号
由于上述原因，符号 a 上的 q2 到 q0 和符号 b 上的 q1。

整个 DFA 看起来像这样：

                /--|--b----\
                b  |       |
                |  V       |
----->(q0)--b-->(q1)--a-->(q2)
      |  ^                 |
      a  |                 |
      \--|-----------------/

Answer 3

步骤：

绘制以“ba”结尾的DFA。
反转状态即
制作最终状态，非最终状态。
非最终状态，最终状态

IMAGE：不以“ba”结尾的字符串的 DFA：

不以 ba 结尾的有限自动机字符串

Finite Automata string not ending with ba

finite-automata