Каталог решений - Сборка автомата (с примерами)

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

Чуть-чуть теории.

Конечные автоматы  принято определять как пятерку множеств A=(S, X, Y, δ, λ) : внутренние состояния, входной и выходной алфавит, функции переходов и выходов. Две ключевые  характеристики —  это  состояние S и входной алфавит X . Для ДКА это означает, что автомат работает дискретно и на каждом такте t, находясь в (одном) состоянии s(t) и в зависимости от входного воздействия x(t), переходит в (одно) состояние s(t+1) , генерируя при этом некоторое выходное воздействие y(t).

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

Где  это  может пригодиться

Главный критерий, определяющий, стоит или нет применять автоматный подход в разработке программы — это сложность поведения той системы, которой необходимо управлять (объекта  управления). Конечно, можно написать автомат, складывающий 2+2, но особого смысла в этом нет).  Пожалуй, самый сложный и творческий этап в процессе конструирования — определить необходимый уровень абстракции. Число состояний автомата должно быть конечным и обозримым (простым для восприятия), в тоже время  содержать в себе всю логику объекта управления.  Основной   задачей   автоматных программ  является  отделение логики  программы от ее семантики и в этой связи  они  практически всегда сопровождаются поддерживающими диаграммами или таблицами.

Немного схем.

Как уже было сказано, ДКА принято изображать в одном из двух представлений: в виде таблицы переходов и выходов или в виде ориентированного графа состояний. Второй способ нагляднее, поэтому немного порисуем.

Примечание: Все схемы и примеры в этой статье будут очень простыми. Кроме того, они не соответствуют каким либо стандартам (если таковые имеются) и не являются единственно правильными. Любой автомат может быть построен разными способами , главное, чтобы он отвечал на вопрос «Что делает система».

1. Начнем с чего нибудь простого, например, с обычной лампочки. Наш автомат будет считывать положение тумблера и отображать состояния. Схема такого автомата будет выглядеть примерно так.

2. Теперь представим, что нас попросили сотворить маленькое чудо для детского новогоднего утренника. Когда дети будут кричать «Елочка, гори» — лампы на елочке должны загореться, а когда будут кричать «Елочка, не гори» — потухнуть. Допустим, устройство, которое умеет различать голосовые команды, запоминать состояния и включать/ выключать лампочки, у нас уже есть. Осталось только задать его логику.

На схеме видно, что помимо нескольких переменных X, задающих логику переходов, появились еще выходные воздействия Y. Если вы обратили внимание, петли на вершинах S1 и S3 не обозначены. В коде они просто пропускаются по умолчанию :

Если X1 Тогда ..
// ИначеЕсли  !X1

но подразумевается, что они есть, и автомат находится в некотором «устойчивом» состоянии.

3. Условия третьей задачи : Если кто-то балуется  со светом , а точнее  включает и выключает свет > 3 раз в течение 3 сек, программа должна среагировать и выдать предупреждающее сообщение. Задача несложная,  решается на раз и без всяких автоматов. Автоматная реализация в бесплатной обработке ниже (*см. комментарии) , пока будете скачивать, открывать и щелкать вкл/выкл, подумайте, как бы вы составили этот алгоритм.

4. И напоследок специально для тех, кто любит задачи из практики.

Недавно потребовался инструмент для удобного редактирования независимого регистра сведений. Регистр состоит из 4 измерений(Номенклатура,ПередаточноеЧисло,МощьностьЭД, Комплектующее) и одного ресурса (Количество). В итоге получилось вот это:

Подробнее о том, как эта штуковина работает (с gif анимацией) можно посмотреть здесь

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

Извините за каракули и корявый почерк.  Работает  так: в  каждой итерации читается  очередная строка таблицы и набор записей регистра (отбор по заполненным значениям ). Я установил 4 входящих события X1 – X4 и 5 команд : Y1- ничего не делать, Y2- удалить из регистра, Y3- изменить только измерения набора данных, Y4 — записать новый набор данных , Y5 изменить измерения и ресурс(Количество) . Двойной обводкой обозначены финальные состояния. Ну и сам код.

	Для Каждого СтрокаТЗ Из ТЗ Цикл
		НаборЗаписей=РегистрыСведений.ПередаточныеЧислаМощьностьЭД.СоздатьНаборЗаписей();
		НовыеЗначенияИзмерений=Новый Структура;
		НовыеЗначенияИзмерений.Вставить("Номенклатура",Объект.Номенклатура);
		Отбор=НаборЗаписей.Отбор;
		Отбор.Номенклатура.Установить(Объект.Номенклатура);
		ВыбраноИзмерений=0;
		Для Каждого КолонкаТЗ Из ТЗ.Колонки Цикл
			Если Найти(КолонкаТЗ.Имя,"Удалить")>0
				ИЛИ Найти(КолонкаТЗ.Имя,"Количество")>0
				ИЛИ Прав(КолонкаТЗ.Имя,1)="N"Тогда 
				Продолжить;
			КонецЕсли;
			Если ЗначениеЗаполнено(СтрокаТЗ[КолонкаТЗ.Имя]) Тогда
				Отбор[КолонкаТЗ.Имя].Установить(СтрокаТЗ[КолонкаТЗ.Имя]);
				НовыеЗначенияИзмерений.Вставить(КолонкаТЗ.Имя,СтрокаТЗ[КолонкаТЗ.Имя+"N"]);
				ВыбраноИзмерений=ВыбраноИзмерений+1;
			КонецЕсли;	
		КонецЦикла; 
		НаборЗаписей.Прочитать();
		ЛокальныеПеременные=Новый Структура();
		ЛокальныеПеременные.Вставить("П1",НаборЗаписей.Количество()>0);
		ЛокальныеПеременные.Вставить("П2", СтрокаТЗ.Удалить);
		ЛокальныеПеременные.Вставить("П3",Не СтрокаТЗ.Удалить  И ВыбраноИзмерений=3 И НЕ СтрокаТЗ.КоличествоN=0);
		ЛокальныеПеременные.Вставить("П4", ВыбраноИзмерений=3);
		ЛокальныеПеременные.Вставить("П5", СтрокаТЗ.КоличествоN=0);
		ОбновитьРегистр(НаборЗаписей,СтрокаТЗ.КоличествоN,НовыеЗначенияИзмерений,ЛокальныеПеременные);
	КонецЦикла;


Процедура ОбновитьРегистр(НаборЗаписей,НовоеКоличество,НовыеЗначенияИзмерений,ЛокальныеПеременные)
	Состояние=0;
	Сч=0;
	Пока Сч<5 Цикл
		Если Состояние=0 Тогда
			Состояние=?(ЛокальныеПеременные.П1,1,2);
		ИначеЕсли Состояние=1 Тогда 
			Состояние=?(ЛокальныеПеременные.П2,4,3);
		ИначеЕсли Состояние=2 Тогда
			Состояние=?(ЛокальныеПеременные.П3,5,6);
		ИначеЕсли Состояние=3 Тогда
			Состояние=?(ЛокальныеПеременные.П4,8,7);
		ИначеЕсли Состояние=4 Тогда
			//удалить данные регистра
			НаборЗаписей.Очистить();
			НаборЗаписей.Записать();
			Прервать;
		ИначеЕсли Состояние=5 Тогда
			//Записать новые данные
			МенеджерЗаписи = РегистрыСведений.ПередаточныеЧислаМощьностьЭД.СоздатьМенеджерЗаписи();
			Для Каждого Элемент Из НовыеЗначенияИзмерений Цикл
				МенеджерЗаписи[Элемент.Ключ]=Элемент.Значение;
				МенеджерЗаписи.Количество=НовоеКоличество;
			КонецЦикла;
			МенеджерЗаписи.Записать();
			Прервать;
		ИначеЕсли Состояние=6 Тогда
			// Ничего не делаем
			Прервать;
		ИначеЕсли Состояние=7 Тогда
			// изменить регистр только Измерения
				тДанные=НаборЗаписей.Выгрузить();
				НаборЗаписей.Очистить();
				НаборЗаписей.Записать();
				НовыйНабор=РегистрыСведений.ПередаточныеЧислаМощьностьЭД.СоздатьНаборЗаписей();
				НовыйНабор.Отбор.Номенклатура.Установить(Объект.Номенклатура);
				Для Каждого Элемент Из НовыеЗначенияИзмерений Цикл
					НовыйНабор.Отбор[Элемент.Ключ].Установить(Элемент.Значение);
					тДанные.ЗаполнитьЗначения(Элемент.Значение,Элемент.Ключ);
				КонецЦикла;
				НовыйНабор.Загрузить(тДанные);
				НовыйНабор.Записать();
			Прервать;
		ИначеЕсли Состояние=8 Тогда
			// изменить регистр
			Если ЛокальныеПеременные.П5 Тогда
				Состояние=4;
			Иначе
				тДанные=НаборЗаписей.Выгрузить();
				НаборЗаписей.Очистить();
				НаборЗаписей.Записать();
				НовыйНабор=РегистрыСведений.ПередаточныеЧислаМощьностьЭД.СоздатьНаборЗаписей();
				НовыйНабор.Отбор.Номенклатура.Установить(Объект.Номенклатура);
				Для Каждого Элемент Из НовыеЗначенияИзмерений Цикл
					НовыйНабор.Отбор[Элемент.Ключ].Установить(Элемент.Значение);
					тДанные.ЗаполнитьЗначения(Элемент.Значение,Элемент.Ключ);
				КонецЦикла;
				тДанные.ЗаполнитьЗначения(НовоеКоличество,"Количество");
				НовыйНабор.Загрузить(тДанные);
				НовыйНабор.Записать();
				Прервать;
			КонецЕсли;	
		КонецЕсли;
		//	Сообщить("=>"+Состояние);
		Сч=Сч+1;
	КонецЦикла;
КонецПроцедуры