什么有限状态机捕获具有相同数量的“01”和“10”的二进制字符串？

我需要帮助设计一个有限状态机，该状态机接受包含尽可能多的模式出现的二进制字符串01作为模式的出现10.

我有点很难准确理解哪些字符串应该被接受，哪些字符串应该被拒绝。

欢迎任何指导。

有问题的语言是什么？

[...] 包含尽可能多的模式出现的二进制字符串01作为模式的出现10。我有点很难准确理解哪些字符串应该被接受，哪些字符串应该被拒绝。

您的规范定义的语言实际上正是由以下内容组成的集合：

• 空字符串，
• 所有以相同字符开头和结尾的字符串。

空字符串被接受，因为它包含任一模式的出现次数为零；简单的。 为了理解为什么所有非空接受的字符串必须以相同的字符开头和结尾，而不是提出正式的证明，让我们看几个例子。我会用

• --来突出显示01图案，以及
• **来突出显示10图案。

String 10001010

该字符串包含

• 出现 2 次01, and
• 出现 3 次10,

如下所示：

10001010
**  ****
   ----

因此，不予受理。请注意，它不以相同的字符开头和结尾。

String 11001111

该字符串包含

• 出现 1 次01, and
• 出现 1 次10,

如下所示：

11001111
 **--

因此，予以接受。请注意，它以相同的字符开头和结尾 (1).

你明白了...

描述相关语言的有限状态机

我需要帮助设计有限状态机 [...]

这是描述相关语言的 FSM：

为了让自己相信它确实描述了这里感兴趣的语言，您可以考虑

• s0 为仅接受空字符串的状态；
• s1 作为仅接受以 a 开头和结尾的字符串的状态0;
• s2 作为下一个字符需要为 a 的状态0到目前为止输入的字符串被接受；
• s3 作为仅接受以 a 开头和结尾的字符串的状态1;
• s4 作为下一个字符需要为 a 的状态1到目前为止输入字符串被接受。

Bonus!

这是我为绘制上面的 FSM 而编写的 LaTeX 代码。

\documentclass{standalone}

\usepackage{tikz}
\usetikzlibrary{
  automata,
  positioning,
}

\begin{document}
  \begin{tikzpicture}[
    node distance=2cm,
    on grid,
    auto,
    scale=.8,
    transform shape,
  ]
    \node[state, initial, accepting] (s0)                     {$s_0$};
    \node[state,          accepting] (s1) [above right=of s0] {$s_1$};
    \node[state                    ] (s2) [right      =of s1] {$s_2$};
    \node[state,          accepting] (s3) [below right=of s0] {$s_3$};
    \node[state                    ] (s4) [right      =of s3] {$s_4$};

    \path[->] (s0) edge              node        {0}    (s1)
              (s1) edge [bend left]  node        {1}    (s2)
                   edge [loop above] node        {0}    ()
              (s2) edge [loop right] node        {1}    ()
                   edge [bend left]  node        {0}    (s1);
    \path[->] (s0) edge              node [swap] {1}    (s3)
              (s3) edge [bend right] node [swap] {0}    (s4)
                   edge [loop below] node        {1}    ()
              (s4) edge [loop right] node        {0}    ()
                   edge [bend right] node [swap] {1}    (s3);
  \end{tikzpicture}
\end{document}