Тема № 31

ФОНДОВАЯ ЛЕКЦИЯ

Минимизация автомата

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

. (13)

Автомат с наименьшим числом состояний, реализующий ограниченно-детерминированный оператор, называется минимальным автоматом оператора.

Построенный при доказательстве последней теоремы автомат – минимальный.

Теорема. Минимальный автомат единственен с точностью до обозначения состояний.

Из теоремы следует признак минимальности автомата: автомат будет минимальным, если для любых двух его состояний и реализуемые в этих состояниях остаточные операторы различны.

Задача минимизации автомата: для данного автомата построить минимальный автомат, реализующий ограниченно-детерминированный оператор. Рассмотрим алгоритм ее решения.

Пусть. В процессе работы алгоритма строятся разбиения множества на непересекающиеся классы:

.

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

1-й шаг. Состояния и отнесем к одному классу, если

.

Получим разбиение:

.

-й шаг. Пусть на -ом шаге получено разбиение:

.

Состояния и отнесем к одному классу нового разбиения, если выполнены два условия:

1) и входят в один класс предыдущего разбиения;

2) для каждого символа состояния и входят в один класс предыдущего разбиения.

Обозначим через класс, в который входит состояние. Тогда условия 1) и 2):

1);

2).

Алгоритм заканчивает работу, когда на некотором шаге не произойдет дальнейшего измельчения разбиения:. Последнее разбиение:

.

Тот факт, что алгоритм закончил работу можно выразить следующим образом:

.

Строим автомат:

,,,,.

Автомат реализует тот же словарный оператор, что и автомат, и является минимальным.

по дисциплине «Криминалистика»

«Методика расследования половых преступлений»

(специальность 030501 65 – Юриспруденция

специализация уголовно-правовая

ведомственная специализация – предварительное следствие в ОВД)

2 часа

(количество часов)

Орел

П Л А Н

Введение

Основные вопросы:

1. Криминалистическая характеристика и особенности квалификации изнасилований. Обстоятельства, подлежащие установлению при расследовании изнасилований.

2. Особенности раскрытия изнасилования по горячим следам и спустя определенное время после совершения преступления. Тактика проведения отдельных следственных действий.

Заключение

Литература

Лекция подготовлена преподавателем кафедры КиПР в ОВД майором полиции Бадиковым Д.А.

Лекция обсуждена и одобрена на заседании кафедры

28 марта 2012 г. Протокол № 6.1

Дата добавления: 2014-01-04