Как пишется дка

ДКА

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

Если вы когда-нибудь пытались написать своего бота, программу-переговорщик (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->{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;

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

Вкратце рассмотрим как это работает. Сердцем класса является таблица переходов STATES, представляющая из себя хэш хэшей хэшей :). Идея тут проста, на первом уровне мы имеем список состояний (STATE) и связанных с ними атрибутов. Так как переход определяется только входным символом (SYMBOL), то соответственно этими атрибутами будут собственно допустимые для этого состояния сигналы. Ну а по сигналу мы уже можем определить следующее состояние (NEXT) и, в довесок, выполняемое действие (ACTION), которое является всего лишь ссылкой на метод.

Т.е. по process мы сначала получаем символ входного алфавита из входной строки (normalize), затем получаем текущее состояние из списка состояний. Смотрим, определен ли для него входящий символ. Если не определен, то считаем что к нам прилетел «*» — любой другой символ. Далее, смотрим, определено ли действие для пары состояние-сигнал. Если определено, выполняем. И переходим на следующее состояние, если оно определено (меняем переменную CURRENT). Если не определено, то фактически это фатальная ошибка для нашего автомата.

В учебных целях конечно же мы выводим информацию о переключении автомата в STDERR, я думаю вам не составит труда при необходимости завернуть этот вывод в лог для дебага или т.п.

Пример

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

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

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

Итого, алфавит автомата состоит из символов (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}];
	} 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!n";
	exit;
	return $self;
}

1;

Диаграмма переходов выглядит следующим образом.

Таблица переходов в данном случае будет иметь следующий вид:

{
  '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'
                           }
               }
}

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

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

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

Заключение

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

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

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

ДКА (трёхбуквенная аббревиатура) может означать:

• Дом Красной армии (также Окружной дом офицеров), см. Дом офицеров.
• Названия спортивных клубов:
  • ДКА (футбольный клуб, Омск)
  • ДКА (футбольный клуб, Смоленск)

• носившие название ДКА:

• ДКА (баскетбольный клуб, Тбилиси)
• ДКА (футбольный клуб, Ленинград)
• ДКА (футбольный клуб, Новосибирск)
• ДКА (футбольный клуб, Свердловск)
• ДКА (футбольный клуб, Тбилиси)
• ДКА (футбольный клуб, Чита)

• Детерминированный конечный автомат.
• Десантный катер.
• ДКА — польский музыкальный исполнитель в жанрах хип-хоп и поп-рэп и легкоатлет.

См. также

• ОДО

Эта страница в последний раз была отредактирована 7 апреля 2022 в 06:02.

Как только страница обновилась в Википедии она обновляется в Вики 2.
Обычно почти сразу, изредка в течении часа.

ЛЕБЁДКА сценическая — механизм, служащий для натяжки тросов, горизонтального и вертикального перемещения тех или иных элементов оформления спектакля, приведения в действие разл.

А поскольку другие свойства ДКА и кортизола не являются взаимно противоречивыми (например, согласно рисунку, влияние кортизола на отложение гликогена в печени не подавляется ДКА ни при каких дозах), постольку их другие действия (скажем, поддержание кортикоидами жизнеспособности при недостаточности надпочечников) взаимно усиливаются.

Комиссар авиабригады — полковой комиссар ВОЕВОДИН на один из последних концертов в ДКА привел с собой л-та СТАЛИНА, причем раздел его не в общей раздевалке, а в кабинете начальника ДКА, где всегда раздевается и сам, посадил вместе с собой на 1-й ряд, отведенный для руководящего состава авиабригады.

1. Подбор слов
2. Значения слов
3. дка