State machines. We write DKA
If you ever tried to write your bot, the negotiating program (negotiator), the interpreter of the communication protocol and the like, then you probably faced with the state machines. This topic is in principle not a big deal, but if suddenly you didn’t have a course on the theory of automata, you are welcome under cat.
Today we will try to create a simple deterministic state machine. I suddenly wanted to write it in Perl, but since we will not use any specific tricks, transferring the general concept to any other imperative language will not be difficult.
We will not go deep into the theory, for this there is a special literature, Google and Wikipedia;). Consider the very base. Let's see what a state machine is.
In electronics, and in programming, in the simplest case, we are dealing with so-called "switching functions". This is a relatively primitive abstraction that does not have its own memory: we are an input to the argument, it is some kind of output. The output value always depends on the input.
')
And if it is necessary for us, that the subsequent value of function depended on previous? From the previous few? Here we come to a certain abstraction with its own memory. This will be automatic. The output value on the automaton depends on the input value and the current state of the automaton.
A finite state machine, respectively, is therefore called that the number of its internal states is finite. And, probably, the simplest of finite automata is deterministic: for each input signal there is only one state into which the automaton can go from the current one.
Thus, our machine is defined as follows:
Actually the whole essence of the machine is determined by the last item. The transition table (also depicted as a transition diagram) consists of 3 columns: the input signal (symbol), the current state, the next state. Everything will become clear with an example.
So, we implement our base class. We have already decided that we need the initial state, the current state and the transition table. The alphabet of input characters is determined by the task, so we also need to normalize (simplify) the input. The output signals will be executed by the descendant class's executable methods. To simplify your life, artificially add to the alphabet the symbol "*" - any other symbol.
I believe that the names of all the methods speak for themselves. Perhaps you should stop at the normalize and process methods. The first converts the input string to a hash containing the SYMBOL field with an automaton-simplified input symbol. And the process itself performs the “clocking” of the state transition processes, processing the next signal.
Briefly consider how it works. The heart of the class is the STATES transition table, which is a hash of hashes hashes :). The idea here is simple, on the first level we have a list of states (STATE) and related attributes. Since the transition is determined only by the input symbol (SYMBOL), respectively, these attributes will be the actual signals valid for this state. Well, by the signal we can already determine the next state (NEXT) and, in the appendage, the action performed (ACTION), which is just a reference to the method.
Those. by process, we first get the character of the input alphabet from the input string ( normalize ), then we get the current state from the list of states. We look, whether the entering character is defined for it. If it is not defined, then we consider that "*" has flown to us - any other symbol. Next, we look whether the action is defined for the state-signal pair. If defined, execute. And go to the next state, if it is defined (change the variable CURRENT). If not defined, then in fact it is a fatal error for our machine.
For educational purposes, of course, we display information about the switching of the automaton in STDERR, I think it will not be difficult for you if you need to wrap this output in a log for debug or the like.
Let's try to implement something. Let it be some kind of chat bot.
We base it on the following rules:
So, we create the transition table for this example:
Total, the automaton alphabet consists of symbols (LOGIN, MEMORIZE, SAY, EXIT, *), the automaton has 3 states (INIT, SESSION and STORE).
Well, let's implement it. First of all, we will set the transition table in the constructor, where necessary - add references to the methods being called. No difficulties :)
The transition diagram is as follows.
The transition table in this case will have the following form:
We write the simplest program using these classes.
Well, a simple check. On input we will give the following sequence.
What do we get at the output?
In general, try it yourself.
Thus, we implemented the simplest finite state machine. It seems to be nothing complicated? Where can it come in handy? Well, with chat bots everything is clear. Approximately the same thing happens if on the other side there is not a person, but a piece of iron - by transmitting commands and listening to the answers, we can write a bot that tweaks the router, for example. Interactive command interfaces? Yes, we actually implemented it now! Want to connect to a service using a stateful protocol? Nothing is easier!
I hope my article was at least helpful to someone. Yes, the implementation is primitive, there are a great many ready-made ones. But it's interesting to try to do something from scratch, right?
I would welcome any comments.
Today we will try to create a simple deterministic state machine. I suddenly wanted to write it in Perl, but since we will not use any specific tricks, transferring the general concept to any other imperative language will not be difficult.
Introduction
We will not go deep into the theory, for this there is a special literature, Google and Wikipedia;). Consider the very base. Let's see what a state machine is.
In electronics, and in programming, in the simplest case, we are dealing with so-called "switching functions". This is a relatively primitive abstraction that does not have its own memory: we are an input to the argument, it is some kind of output. The output value always depends on the input.
')
And if it is necessary for us, that the subsequent value of function depended on previous? From the previous few? Here we come to a certain abstraction with its own memory. This will be automatic. The output value on the automaton depends on the input value and the current state of the automaton.
A finite state machine, respectively, is therefore called that the number of its internal states is finite. And, probably, the simplest of finite automata is deterministic: for each input signal there is only one state into which the automaton can go from the current one.
Thus, our machine is defined as follows:
- initial state;
- input alphabet (set of possible input signals);
- many states;
- and transition table.
Actually the whole essence of the machine is determined by the last item. The transition table (also depicted as a transition diagram) consists of 3 columns: the input signal (symbol), the current state, the next state. Everything will become clear with an example.
Base class
So, we implement our base class. We have already decided that we need the initial state, the current state and the transition table. The alphabet of input characters is determined by the task, so we also need to normalize (simplify) the input. The output signals will be executed by the descendant class's executable methods. To simplify your life, artificially add to the alphabet the symbol "*" - any other symbol.
package FSM; use strict; use Carp; use vars qw($AUTOLOAD); # Create new object sub new { my $self = {}; my ($proto, $initial) = @_; my $class = ref($proto) || $proto; # Init ourselves $self->{INITIAL} = $initial; $self->{CURRENT} = $initial; $self->{STATES} = {}; bless ($self, $class); return $self; } sub setInitialState { my ($self, $initial) = @_; $self->{INITIAL} = $initial; return $self; } sub setCurrentState { my ($self, $current) = @_; $self->{CURRENT} = $current; return $self; } sub getCurrentState { my ($self, $current) = @_; return $self->{CURRENT}; } sub reset { my $self = shift; $self->{CURRENT} = $self->{INITIAL}; return $self; } sub addState { my $self = shift; my %args = @_; $self->{STATES}->{$args{STATE}}->{$args{SYMBOL}} = {NEXT => $args{NEXT}, ACTION => $args{ACTION}}; return $self; } sub removeState { my $self = shift; my %args = @_; if (exists $args{SYMBOL}) { delete $self->{STATES}->{$args{STATE}}->{$args{SYMBOL}}; } else { delete $self->{STATES}->{$args{STATE}}; } return $self; } # Be sure to override in child sub normalize { my ($self, $symbol) = @_; my $ret = {}; $ret->{SYMBOL} = $symbol; return $ret; } sub process { my ($self, $rawSymbol) = @_; my $state = $self->{STATES}->{$self->{CURRENT}}; $rawSymbol = $self->normalize($rawSymbol); my $symbol = $rawSymbol->{SYMBOL}; print STDERR "Current state " . $self->{CURRENT} . ", got symbol " . $symbol . "\n"; if (!exists $state->{$symbol} && exists $state->{'*'}) { print STDERR "Unrecognized symbol " . $symbol . ", using *\n"; $symbol = "*"; } # Do some action! $state->{$symbol}->{ACTION}($self, $rawSymbol) if ref $state->{$symbol}->{ACTION}; # Switch state if (exists $state->{$symbol}->{NEXT}) { $self->{CURRENT} = $state->{$symbol}->{NEXT}; } else { die "Don't know how to handle symbol " . $rawSymbol->{SYMBOL}; } return $self; } 1; I believe that the names of all the methods speak for themselves. Perhaps you should stop at the normalize and process methods. The first converts the input string to a hash containing the SYMBOL field with an automaton-simplified input symbol. And the process itself performs the “clocking” of the state transition processes, processing the next signal.
Briefly consider how it works. The heart of the class is the STATES transition table, which is a hash of hashes hashes :). The idea here is simple, on the first level we have a list of states (STATE) and related attributes. Since the transition is determined only by the input symbol (SYMBOL), respectively, these attributes will be the actual signals valid for this state. Well, by the signal we can already determine the next state (NEXT) and, in the appendage, the action performed (ACTION), which is just a reference to the method.
Those. by process, we first get the character of the input alphabet from the input string ( normalize ), then we get the current state from the list of states. We look, whether the entering character is defined for it. If it is not defined, then we consider that "*" has flown to us - any other symbol. Next, we look whether the action is defined for the state-signal pair. If defined, execute. And go to the next state, if it is defined (change the variable CURRENT). If not defined, then in fact it is a fatal error for our machine.
For educational purposes, of course, we display information about the switching of the automaton in STDERR, I think it will not be difficult for you if you need to wrap this output in a log for debug or the like.
Example
Let's try to implement something. Let it be some kind of chat bot.
We base it on the following rules:
- You must first log in before executing the commands.
- By the command memorize, we will memorize everything that the user enters, the end by the command exit
- At the command say N, display the memorized phrase number N
- The end of the session will be the exit command
So, we create the transition table for this example:
| Symbol | condition | Next state | Act |
|---|---|---|---|
| LOGIN | INIT | SESSION | Opening session |
| * | INIT | INIT | - |
| * | SESSION | SESSION | - |
| SAY | SESSION | SESSION | Print line number N |
| EXIT | SESSION | INIT | - |
| MEMORIZE | SESSION | STORE | - |
| * | STORE | STORE | Save string to buffer |
| EXIT | STORE | SESSION | - |
Total, the automaton alphabet consists of symbols (LOGIN, MEMORIZE, SAY, EXIT, *), the automaton has 3 states (INIT, SESSION and STORE).
Well, let's implement it. First of all, we will set the transition table in the constructor, where necessary - add references to the methods being called. No difficulties :)
package ChatBot; use FSM; @ISA = ("FSM"); use strict; use Carp; use vars qw($AUTOLOAD); sub new { my $proto = shift; my $class = ref($proto) || $proto; my $self = $class->SUPER::new("INIT"); $self->addState(STATE => "INIT", SYMBOL => "*", NEXT => "INIT", ACTION => \&doIntroduce); $self->addState(STATE => "INIT", SYMBOL => "LOGIN", NEXT => "SESSION", ACTION => \&doLogin); $self->addState(STATE => "INIT", SYMBOL => "EXIT", NEXT => "INIT", ACTION => \&doQuit); $self->addState(STATE => "SESSION", SYMBOL => "*", NEXT => "SESSION"); $self->addState(STATE => "SESSION", SYMBOL => "EXIT", NEXT => "INIT"); $self->addState(STATE => "SESSION", SYMBOL => "SAY", NEXT => "SESSION", ACTION => \&doSay); $self->addState(STATE => "SESSION", SYMBOL => "MEMORIZE",NEXT => "STORE"); $self->addState(STATE => "STORE", SYMBOL => "*", NEXT => "STORE", ACTION => \&doRemember); $self->addState(STATE => "STORE", SYMBOL => "EXIT", NEXT => "SESSION"); $self->{SESSION} = {}; $self->{LOGIN} = ""; return $self; } sub normalize { my ($self, $symbol) = @_; my $ret = {}; if ($symbol =~ /^(\S+)(.*)$/) { $ret->{SYMBOL} = uc $1; $ret->{DATA} = $2; $ret->{RAW} = $symbol; } else { $ret->{SYMBOL} = "*"; $ret->{DATA} = $symbol; $ret->{RAW} = $symbol; } return $ret; } sub doIntroduce { my $self = shift; print "Please introduce yourself first!\n"; return $self; } sub doLogin { my ($self, $symbol) = @_; print "Welcome," . $symbol->{DATA} . "\n"; $self->{LOGIN} = $symbol->{DATA}; $self->{SESSION}->{$self->{LOGIN}} = () unless exists $self->{SESSION}->{$self->{LOGIN}}; return $self; } sub doSay { my ($self, $symbol) = @_; if (defined $self->{SESSION}->{$self->{LOGIN}}->[$symbol->{DATA}]) { print $self->{SESSION}->{$self->{LOGIN}}->[$symbol->{DATA}]; } else { print "No record\n"; } return $self; } sub doRemember { my ($self, $symbol) = @_; push @{ $self->{SESSION}->{$self->{LOGIN}} }, $symbol->{RAW}; return $self; } sub doQuit { my ($self, $symbol) = @_; print "Bye bye!\n"; exit; return $self; } 1; The transition diagram is as follows.
The transition table in this case will have the following form:
{ 'INIT' => { '*' => { 'ACTION' => \&doIntroduce, 'NEXT' => 'INIT' }, 'LOGIN' => { 'ACTION' => \&doLogin, 'NEXT' => 'SESSION' }, 'EXIT' => { 'ACTION' => \&doQuit, 'NEXT' => 'INIT' } }, 'STORE' => { '*' => { 'ACTION' => \&doRemember, 'NEXT' => 'STORE' }, 'EXIT' => { 'NEXT' => 'SESSION' } }, 'SESSION' => { 'SAY' => { 'ACTION' => \&doSay, 'NEXT' => 'SESSION' }, '*' => { 'NEXT' => 'SESSION' }, 'MEMORIZE' => { 'NEXT' => 'STORE' }, 'EXIT' => { 'NEXT' => 'INIT' } } } We write the simplest program using these classes.
use ChatBot; $bot = ChatBot->new(); while(<>) { $bot->process($_); } Well, a simple check. On input we will give the following sequence.
hello world! login %username% hello world! say 3 memorize hey, do you really remember everything i would say? let's check exit say 0 exit hello login %username% say 1 exit What do we get at the output?
Please introduce yourself first! Welcome, %username% No record hey, do you really remember everything i would say? Please introduce yourself first! Welcome, %username% let's check In general, try it yourself.
Conclusion
Thus, we implemented the simplest finite state machine. It seems to be nothing complicated? Where can it come in handy? Well, with chat bots everything is clear. Approximately the same thing happens if on the other side there is not a person, but a piece of iron - by transmitting commands and listening to the answers, we can write a bot that tweaks the router, for example. Interactive command interfaces? Yes, we actually implemented it now! Want to connect to a service using a stateful protocol? Nothing is easier!
I hope my article was at least helpful to someone. Yes, the implementation is primitive, there are a great many ready-made ones. But it's interesting to try to do something from scratch, right?
I would welcome any comments.
Source: https://habr.com/ru/post/141503/
All Articles