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

Question

我需要帮助设计一个有限状态机，该机器接受包含与模式 10 出现次数一样多的模式 01 的二进制字符串。

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

欢迎任何指导。

Answer 1

有问题的语言是什么？

[...] binary strings containing as many occurrences of the pattern 01 as occurrences of the pattern 10. I kinda have a hard time understanding exactly which strings should be accepted and which should be rejected.

你的规范定义的语言其实就是由以下组成的集合

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

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

• -- 突出显示 01 模式的出现，以及
• ** 突出显示 10 模式。

字符串10001010

这个字符串包含

• 01 出现 2 次，并且
• 10 出现 3 次，

如下图:

10001010
**  ****
   ----

因此，不接受。请注意，它不会以相同的字符开始和结束。

字符串11001111

这个字符串包含

• 01 出现 1 次，并且
• 10 出现 1 次，

如下图:

11001111
 **--

因此，它被接受了。请注意，它以相同的字符 (1) 开始和结束。

你明白了......

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

I need help designing a finite state machine [...]

这是一个描述相关语言的 FSM:

为了说服自己它确实描述了这里感兴趣的语言，你可以想到

• s0为只接受空字符串的状态；
• s1 作为仅接受以 0 开头和结尾的字符串的状态；
• s2 作为输入字符串的下一个字符需要为 0 的状态才能被接受；
• s3 作为仅接受以 1 开头和结尾的字符串的状态；
• s4 作为输入字符串的下一个字符必须为 1 的状态才能被接受。

奖金!

这是我为绘制上面的 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}