Independent study of circuit design. Synthesis of automata on triggers. Part 1
Hello.
In continuation of the subject of self-study of circuitry, I bring to your attention an article related to the synthesis of automata on triggers.
And it all starts like this:
“A peasant needs to carry a wolf, a goat and a cabbage across the river. But the boat is such that only a peasant can fit in it, and with it either one wolf, or one goat, or one cabbage. But if you leave a wolf with a goat, then the wolf will eat the goat, and if you leave the goat with cabbage, the goat will eat cabbage. How did the peasant carry his cargo? ”
')
Let's a little distract from the task and recall what we already know:
So. There are 2 ways to solve this problem:
To move from verbal descriptions to tables, graphs and diagrams, I propose to encode game states as follows:
Select four binary digits. Each level is responsible for what kind of creatures on which bank of the river are located. If 1 is stored in this discharge, then the creature is on the first (source) bank, if 0 - on the second. For clarity, I will demonstrate this in the following figure:
From the condition of the task it becomes clear that without the supervision of the peasant they cannot be together:
Hence, the following four combinations are losing:
Now, as we all remember, it is necessary to go from a verbal description to a graphical description - a graph. It should be easy.
We note the initial state of Sst - our game will begin with it and end with it. It is thought that a certain button "START" switches the machine from the state "0000" to the state "1111". So I encode the output words, but the state will have to encode in another way. So, you have to enter the combinational circuit, which will deal with the formation of output words.
To control the farmer and the other entities, four input words are needed:
So. Input and output words are named, states are indicated. Graph machine Moore. Let's start drawing:
Let's reflect these two facts on the graph:
We reason further:
Add this to our picture:
It's okay for now.
Now you have to choose who to take to the second bank: cabbage or a wolf. It would be nice to consider both options (I’ll give a partial picture so that it is easier to understand):
That is, it is clear that either cabbage or a wolf will remain on the first bank after this movement.
Here you go! I told you that it is not difficult! If we continue the reasoning in the same way, then we can come to such a simple scheme:
Pay attention: when trying to move to the other side in 3, 4, 5 and 8 states of a peasant, the goat remains unattended near a wolf or cabbage, which is fraught and leads to the end of the game. Well, or just look at the table of invalid states above. When you try to go to them, the game ends.
Now let's remember how transition / output tables are built. I recommend to open this article here and see if you suddenly forgot, and I just give the table:
Here you go. Now almost everything is ready for the synthesis of the automaton on the triggers. Very soon we will be able to play this toy on the emulator, and then on the assembled model.
I intend to publish the second part of the article on June 14-15.
In continuation of the subject of self-study of circuitry, I bring to your attention an article related to the synthesis of automata on triggers.
And it all starts like this:
“A peasant needs to carry a wolf, a goat and a cabbage across the river. But the boat is such that only a peasant can fit in it, and with it either one wolf, or one goat, or one cabbage. But if you leave a wolf with a goat, then the wolf will eat the goat, and if you leave the goat with cabbage, the goat will eat cabbage. How did the peasant carry his cargo? ”
')
Let's a little distract from the task and recall what we already know:
So. There are 2 ways to solve this problem:
- You have to start with a goat. The peasant, having transported the goat, returns and takes the wolf, which he carries to the other shore, where he leaves him, but he takes the goat and takes it back to the first shore. Here he leaves her and transports cabbage to the wolf. Then, after returning, he transports the goat, and the crossing ends safely.
- In the beginning, the peasant again transports the goat. Then you can take a cabbage, take it to the other side, leave it there and return the goat to the first bank. Then transport the wolf to the other side, return for the goat and again take it to the other side. In this case, the number of flights (7) is exactly the same as in the first variant.
To move from verbal descriptions to tables, graphs and diagrams, I propose to encode game states as follows:
Select four binary digits. Each level is responsible for what kind of creatures on which bank of the river are located. If 1 is stored in this discharge, then the creature is on the first (source) bank, if 0 - on the second. For clarity, I will demonstrate this in the following figure:
From the condition of the task it becomes clear that without the supervision of the peasant they cannot be together:
- Goat and cabbage;
- Goat and wolf.
Hence, the following four combinations are losing:
Now, as we all remember, it is necessary to go from a verbal description to a graphical description - a graph. It should be easy.
We note the initial state of Sst - our game will begin with it and end with it. It is thought that a certain button "START" switches the machine from the state "0000" to the state "1111". So I encode the output words, but the state will have to encode in another way. So, you have to enter the combinational circuit, which will deal with the formation of output words.
To control the farmer and the other entities, four input words are needed:
So. Input and output words are named, states are indicated. Graph machine Moore. Let's start drawing:
- From the zero state, the game is transferred to the initial position after the arrival of any word.
- It is obvious that only when the peasant takes the goat first (a1) the game can be continued, otherwise (a2, a3, a4) you have to start all over again.
Let's reflect these two facts on the graph:
We reason further:
- If we now apply the words a2 or a3 to the input, then it is clear that the peasant will not be able to smuggle a wolf or cabbage, so the state of the game will not change. However, he can take the goat back and the game will return to its initial state.
- So the only non-dead end action will be the return of the peasant to the first shore.
Add this to our picture:
It's okay for now.
Now you have to choose who to take to the second bank: cabbage or a wolf. It would be nice to consider both options (I’ll give a partial picture so that it is easier to understand):
That is, it is clear that either cabbage or a wolf will remain on the first bank after this movement.
Here you go! I told you that it is not difficult! If we continue the reasoning in the same way, then we can come to such a simple scheme:
Pay attention: when trying to move to the other side in 3, 4, 5 and 8 states of a peasant, the goat remains unattended near a wolf or cabbage, which is fraught and leads to the end of the game. Well, or just look at the table of invalid states above. When you try to go to them, the game ends.
Now let's remember how transition / output tables are built. I recommend to open this article here and see if you suddenly forgot, and I just give the table:
Here you go. Now almost everything is ready for the synthesis of the automaton on the triggers. Very soon we will be able to play this toy on the emulator, and then on the assembled model.
I intend to publish the second part of the article on June 14-15.
Source: https://habr.com/ru/post/95745/
All Articles