What finite-state machine captures binary strings

I need help designing a finite state machine that accepts 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.

Any guidance would be welcome.

回答1:

What is the language in question?

[...] 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.

The language defined by your specs is in fact none other than the set composed of

the empty string,
all strings that start and end with the same character.

The empty string is accepted because it contains zero occurrences of either pattern; easy. To understand why all non-empty accepted strings must start and end with the same character, instead of coming up with a formal proof, let's take a look at a couple of examples. I'll use

-- to highlight occurrences of the 01 pattern, and
** to highlight occurrences of the 10 pattern.

String `10001010`

This string contains

2 occurrences of 01, and
3 occurrences of 10,

as shown below:

10001010
**  ****
   ----

Therefore, it is not accepted. Note that it doesn't start and end with the same character.

String `11001111`

This string contains

1 occurrence of 01, and
1 occurrence of 10,

as shown below:

11001111
 **--

Therefore, it is accepted. Note that it starts and ends with the same character (1).

You get the idea...

A finite-state machine that describes the language in question

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

Here is an FSM that describes the language in question:

To convince yourself that it does indeed describe the language of interest here, you can think of

s0 as the state that accepts only the empty string;
s1 as the state that accepts only strings that start and end with a 0;
s2 as the state in which the next character needs to be a 0 for the input string so far to get accepted;
s3 as the state that accepts only strings that start and end with a 1;
s4 as the state in which the next character needs to be a 1 for the input string so far to get accepted.

Bonus!

Here the LaTeX code I wrote for drawing the FSM above.

\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}

回答2:

You may need to be more precise in your question with the language that describes your language, because this to me sounds a lot like the classic trick question to create a FSM that recognizes L={0^n1^n: n is a positive integer} or, in plain speak, some pattern followed by the same number of a different pattern.

This cannot be done with a Deterministic or nondeterministic finite state machine because to count N you would need an infinite (or non finite) state machine.

A Grammar can solve this issue. It would be as follows: S-> 01S10 S-> (epsilon) (goes away, in other words)