Конечные автоматы. Пишем ДКА

в 19:24, , рубрики: perl, конечный автомат, Программирование, теория автоматов, метки: , ,

Если вы когда-нибудь пытались написать своего бота, программу-переговорщик (negotiator), интерпретатор протокола связи и тому подобные вещи, то наверняка сталкивались с конечными автоматами. Данная тема в принципе не представляет большой сложности, но если вдруг у вас не было курса «теории автоматов», милости прошу под кат.

Сегодня мы попытаемся создать простой детерминированный конечный автомат. Мне вдруг захотелось написать его на Perl'е, но так как мы не будем использовать никаких специфических трюков, перенести общую концепцию на любой другой императивный язык не составит большого труда.

Введение

Не будем сильно углубятся в теорию, для этого есть специальная литература, гугл и википедия ;). Рассмотрим самую базу. Давайте разберемся что такое конечный автомат.

В электронике, да и в программировании, в простейшем случае мы имеем дело с так называемыми «переключательными функциями». Это относительно примитивная абстракция не имеющая собственной памяти: мы на вход аргумент, она на выход некое значение. Выходное значение всегда зависит только от входного.

А если нам необходимо, чтобы последующее значение функции зависело от предыдущего? От нескольких предыдущих? Тут мы уже приходим к некой абстракции с собственной памятью. Это и будет автомат. Выходное значение на автомате зависит от значения на входе и текущего состояния автомата.

Конечный автомат соответственно потому так называется, что число его внутренних состояний конечно. А, наверное, самым простейшим из конечных автоматов является детерминированный: для каждого входного сигнала существует лишь одно состояние, в которое автомат может перейти из текущего.

Таким образом, наш автомат определяется следующим:

  • начальным состоянием;
  • входным алфавитом (набором возможных входных сигналов);
  • множеством состояний;
  • и таблицей переходов.

Собственно вся суть автомата определяется последним пунктом. Таблица переходов (также изображается как диаграмма переходов) состоит из 3-х столбцов: входной сигнал (символ), текущее состояние, следующее состояние. Все станет ясно на примере.

Базовый класс

Итак, реализуем наш базовый класс. Мы уже определились, что нам нужно начальное состояние, текущее состояние и таблица переходов. Алфавит входных символов определяется задачей, поэтому также нам потребуется нормализация (упрощение) ввода. Роль выходных сигналов будут выполнять исполняемые методы класса потомка. Для упрощения себе жизни, искусственно добавим в алфавит символ "*" — любой другой символ. 

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->{CURRENT};
	$rawSymbol = $self->normalize($rawSymbol);
	my $symbol = $rawSymbol->{SYMBOL};
	
	print STDERR "Current state " . $state . ", got symbol " . $symbol . "n";
	if (!exists $self->{STATES}->{$state}->{$symbol} && exists $self->{STATES}->{$state}->{'*'}) {
		print STDERR "Unrecognized symbol " . $symbol . ", using *n";
		$symbol = "*";
	}
	
	# Do some action!
	$self->{STATES}->{$state}->{$symbol}->{ACTION}($self, $rawSymbol)
		if ref $self->{STATES}->{$state}->{$symbol}->{ACTION};
	
	# Switch state
	if (exists $self->{STATES}->{$state}->{$symbol}->{NEXT}) {
		$self->{CURRENT} = $self->{STATES}->{$state}->{$symbol}->{NEXT};
	} else {
		die "Don't know how to handle symbol " . $rawSymbol->{SYMBOL};
	}
	
	return $self;
}

1;

Я полагаю что названия всех методов говорят сами за себя. Остановиться пожалуй стоит на методах normalize и process. Первый преобразует входную строку в хэш, содержащий поле SYMBOL с упрощенным до алфавита автомата входным символом. А process собственно осуществляет «тактирование» процессов перехода между состояниями, обрабатывая очередной сигнал.

Пример

Давайте попробуем что-нибудь реализовать. Пускай это будет некое подобие чат-бота.
Положим в его основу следующие правила:

  • Перед выполнением команд надо сначала представиться (login)
  • По команде memorize будем запоминать все что вводит пользователь, окончание по команде exit
  • По команде say N выводить запомненную фразу номер N
  • Завершение сеанса будет происходит по команде exit

Итак, составим таблицу переходов для этого примера:

Символ Состояние Следующее состояние Действие
LOGIN INIT SESSION Открываем сессию
* INIT INIT -
* SESSION SESSION -
SAY SESSION SESSION Выводим строку номер N
EXIT SESSION INIT -
MEMORIZE SESSION STORE -
* STORE STORE Сохраняем строку в буфер
EXIT STORE SESSION -

Итого, алфавит автомата состоит из символов (LOGIN, MEMORIZE, SAY, EXIT, *), автомат имеет 3 состояния (INIT, SESSION и STORE).

Что ж, давайте его реализуем. В первую очередь зададим в конструкторе таблицу переходов, где необходимо — добавим ссылки на вызываемые методы. Никаких сложностей :)

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}]. "n";
	} else {
		print "No recordn";
	}
	return $self;
}

sub doRemember {
	my ($self, $symbol) = @_;
	push @{ $self->{SESSION}->{$self->{LOGIN}} }, $symbol->{RAW};
	return $self;
}

sub doQuit {
	my ($self, $symbol) = @_;
	print "Bye bye!";
	exit;
	return $self;
}

1;

Напишем простейшую программку с использованием этих классов. 

use ChatBot;

$bot = ChatBot->new();
while(<>) {
	$bot->process($_);
}

Ну и простенькая проверка. На ввод дадим следующую последовательность.

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

Что же мы получим на выходе?

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

В общем, попробуйте сами.

Заключение

Таким образом мы реализовали простейший конечный автомат. Вроде бы ничего сложного? Где это может пригодиться? Ну с чат-ботами все понятно. Примерно тоже самое получается если на другой стороне будет не человек, а железка — передавая команды и слушая ответы мы можем написать бота, крутящего настройки маршрутизатора, например. Интерактивные командные интерфейсы? Да мы собственно его сейчас и реализовали! Хотите подключиться к сервису, использующему протокол с набором состояний? Нет ничего проще!

Надеюсь, моя статья была хоть кому-нибудь полезна. Да, реализация примитивная, существует великое множество уже готовых. Но ведь интересно попробовать сделать что-то с нуля, неправда ли?

Буду рад любым комментариям.

Автор: divanikus

* - обязательные к заполнению поля

Главная   |  Архив новостей  |   Android  |   Google  |   Apple  |   Microsoft  |   Информационная безопасность  |   Веб – разработка
Публикации RSS  |  Комментарии RSS
https://ajax.googleapis.com/ajax/libs/jquery/3.4.1/jquery.min.js