This paper refers to:

  • Talk about the state machine
  • Introduction to the Theory of Computation: Lecture 1 (Stonehill College)
  • Introduction to the theory of computation
  • Where are finite state machines usually used?
  • Softwareengineering.stackexchange.com/questions/4…

Introduction to the

This is the first in the Theory of Computing 101 series, and we’ll start with the most basic finite state machine. The main courses and books for reference are: Introduction to the Theory of Computation 3rd Edition Stonehill College CS Introduction to the Theory of Computation .

Why study “computational theory”?

As Shai Simonson, Professor of Computer Science at Stonehill College, said, this is probably the most abstract Computer course in the world, But it is at least one that any computer scientist (and, I think, anyone who really loves CS) needs to know. This course will not teach you how to write code or how to build a computer. Instead, it will focus on the word “science” in “computer science” to understand the ideas that have been shining for decades in the development of computer science.

There is something else, which I think is also very important, that is the pure joy of learning new things.

Ok, blah blah blah blah blah blah blah blah blah blah blah blah blah blah blah blah blah

What is a finite state machine

As a programmer, I understand it as a machine with limited memory and functions defined to jump from one state to another. Mathematically, a finite state machine can be defined as a quintuple, as shown in the following figure (Introduction to the Theory of Computation 3rd Edition P35) :

You can visualize this visually: In the state machine below, the circles indicate the possible states, with the possible input values of 0 and 1. The swap function is the arrow that starts q1 and accepts Q2 (represented by the double circles).

The definition of a finite state machine is really that simple.

Finite state machine applications

One of the most obvious features of a finite state machine is that it has too little memory to remember all of its historical inputs, so the number of problems it can solve is limited. As to what can and can’t be solved, we’ll see later. Let’s take a look at finite state machines.

Embedded area: automatic doors

This is an example from the Book Introduction to the Theory of Computation 3rd Edition.

In the figure below, there are two sensors at the door and the back of the door (front for the door, rear for the back). There are two control switches on a door: OPEN and CLOSED. There are four control switches on a door: FRONT, REAR, BOTH and NEITHER.

There is a graph that shows the state transition process as follows:

A little explanation:

  • The pad is in the CLOSED state. The pad is opened only when it detects a human being and changes from CLOSED to OPEN. In other cases, the pad remains in the CLOSED state.
  • When in the OPEN state, the state switches to CLOSED only when no one is detected on either side.

I have my doubts about the design of the door. When the door is CLOSED, shouldn’t the REAR PAD detect that the person is OPEN? Perhaps I understand where is wrong, there are children shoes know welcome to point out. But this does not affect our understanding of finite automata.

In fact, the automatic door can be regarded as a simplest computer, it only has a bit of storage space, can record the current door state is OPEN or CLOSED. Similar elevators, beverage machines and so on.

In fact, in the beginning, we computer scientists were faced with a similar situation, with extremely limited storage space. Many of today’s embedded devices also have very limited memory, so finite state machines are still useful.

Programming area: Regular expressions

Regexper.com/ is a website that can be used to restore regular expressions to a Finite State machine very intuitively. The open source address is as follows: gitlab.com/javallone/r… .

Here are a few examples of regular expressions:

Matches: phone number / ^ 1 (3 4 5 | | | | 7 8) \ d {9} $/ :

Matching email: ^ ([a zA – Z0-9 _ \ – \] +) @ ([a – zA – Z0-9 _ \ – \] +) \. ([a zA – Z] {2, 5}) $

Match the IP address: ^ ((25 [0 to 5] | 2 [0 to 4] [0-9] | [01]? [0-9] [0-9]?) \.) {3} (25 [0 to 5] | 2 [0 to 4] [0-9] | [01]? [0-9] [0-9]?) $

I won’t go into the code layer here, or this article won’t be finished. If you’re interested, Google it and we’ll talk about it again later.

other

The stackexchange link mentioned a lot: softwareengineering.stackexchange.com/questions/4…

Design finite state machines

Instance of a

Design an FSM that can recognize binary strings divisible by 3. Accept 1001, reject 1101. First, we can think of all the possibilities of the remainder as states, namely, 0, 1, 2, where 0 is accept. And then analyze what state transitions look like? In binary numbers, adding a 0 to the end means multiplying by 2, and adding a 1 to the end means multiplying by 2 and adding 1. For the remainder, it is the same as multiplying by 2 or multiplying by 2 and adding 1, except that the remainder is carried.

  • Start from the initial state: there is no input at the beginning, that is, 0.
  • For state 0: If the input value is 0, it remains unchanged. If the input value is 1, the system jumps to 1.

  • For state 1, when the input is 0, the remainder is multiplied by 2 to become 2; When the input is 1, the remainder multiplied by 2 plus 1 becomes 0 (3).

  • For state 2: enter 0 times 2 to become 1 (4); Input 1 times 2 plus 1, which becomes 2 (5).

That’s it. Isn’t it easy to use FSM to solve a problem that is difficult to solve with ordinary algorithms? If we can design FSM that are divisible by 3, will we be able to design FSM that are divisible by 4, 5, 6, 7, 8? Here, there’s an even easier way to be divisible by 2^k(k=1,2,3,4) : switch to determining that there are at least k zeros at the end.

Start by drawing:

Example 2

Design an FSM that can recognize binary strings divisible by 4 (with at least two zeros at the end). I’m going to design the state so that I’ve received several zeros at the end so far, so there are three states: zero zeros, one zeros, and two zeros.

This can also be generalized to pattern string recognition, for example to recognize a particular substring, see the following example.

Examples of three

Design an FSM that can recognize the substring ABCAB.

For the sake of simplicity, the circle is omitted and the state transitions of some nodes in the middle are omitted.

  • Initially, the state is unmatched for any character.
  • In the initial state: Enter a to switch to A. The other input states remain unchanged.
  • In state A: Enter B to jump to AB. Input A remains unchanged; Enter other jump back to the start state.
  • In state ABC: enter a to switch to ABCA. Otherwise, jump back to the start state.
  • In the abCA state, enter B to switch to ABCAB, that is, accept. Type A to jump back to A (not to the start state, because this is abCAA, which is equivalent to a); Enter other to jump back to the start state.
  • In state ABCAB: whatever is entered remains the same because the match is currently successful.

To summarize

State machines are very succinct, but very powerful, and very interesting, right?

The code word is very hard, the picture and text is even more hard, point a praise to encourage ~

Welcome to pay attention to my wechat public number during commercial time. This article is available at github: github.com/liaochangji…