Размещено на http://www.allbest.ru/

Содержание

Введение

Глава 1. Теоретические аспекты автоматного программирования

1.1 Основные принципы и понятия автоматного программирования

1.2 Понятия конечного автомата

1.3 Виды конечных автоматов

Глава 2. Конечный автомат как элемент автоматного программирования

2.1 Описание конечного автомата

2.2 Примеры конечных автоматов

Заключение

Библиографический список



Введение

Автоматное программирование является одним из стилей программирования

Актуальность работы

В настоящее время многие программисты и ученые в этой сфере обсуждают проблему. Чаще программисты практики, которые сетуют на то, что современная система форма и стиль программирования находится на высоком уровне. Но, несмотря, на то, что система настолько идеализирована ее пользователями, все же большинство проектов заканчиваются неудачно. Именно тут и появляется такое понятие как автоматное программирование. Упрощенная трактовка автоматного программирования состоит в том, что это стиль программирования, при использовании которого поведение программ предлагается описывать автоматами, которые в дальнейшем преобразуются в код. При этом отметим, что автоматы давно и успешно применяются в программировании, например, при построении компиляторов Автоматы используются также и при решении многих других задач, например, при реализации протоколов.

Цель работы: Рассмотреть и определить основные понятия автоматного программирования, проанализировать принципы построения конечных автоматов.

Исходя из цели, можно установить такие задачи:

1) Обосновать теоретическое понятие автоматного программирования

2) Рассмотреть основные понятия автоматного программирования

3) Проанализировать основные виды конечных автоматов

4) Показать пример конечного автомата используемого в жизни.

В работе использованы такие методы:

1) Аналитический;

2) Теоретический.

Предмет курсовой работы: конечные автоматы.

Объект курсовой работы: применение автоматного программирования в жизненной практике

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



Глава 1. Теоретические аспекты автоматного программирования

1.1 Основные принципы и понятия автоматного программирования

Основным понятием в автоматном программировании является состояние.

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

При этом справедливо соотношение: "Состояния + входные воздействия = конечный автомат без выхода". Справедливо также: "Автомат без выхода + выходные воздействия = автомат".

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

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

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

Понятность графов переходов достигается во многом за счет того, что состояния декомпозируют множество всех входных воздействий соответствующего автомата на группы, каждая из которых определяет переходы из рассматриваемого состояния.

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

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

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

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

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

Следующее преимущество автоматного подхода - эффективность верификации автоматных программ на основе метода Model Checking (верификация на модели). Это объясняется тем, что модель для верификации программ этого класса может строиться автоматически по графу переходов и иметь относительно небольшой размер, так как в графах переходов используются только управляющие состояния.

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

1.2 Понятия конечного автомата

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

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

(1)

где: - конечное множество состояний автомата;- начальное (стартовое) состояние автомата ();

- множество заключительных (или допускающих) состояний, таких что ;

У - допустимый входной алфавит (конечное множество допустимых входных символов), из которого формируются строки, считываемые автоматом;

д - заданное отображение множества во множество подмножеств Q:

(2)

(иногда д называют функцией переходов автомата).

Автомат начинает работу в состоянии q0, считывая по одному символу входной строки. Считанный символ переводит автомат в новое состояние из Q в соответствии с функцией переходов. Если по завершении считывания входного слова (цепочки символов) автомат оказывается в одном из допускающих состояний, то слово "принимается" автоматом. В этом случае говорят, что оно принадлежит языку данного автомата. В противном случае слово "отвергается".

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

Другие способы описания

Диаграмма состояний (или иногда граф переходов) - графическое представление множества состояний и функции переходов. Представляет собой нагруженный однонаправленный граф, вершины которого - состояния КА, ребра - переходы из одного состояния в другое, а нагрузка - символы, при которых осуществляется данный переход. Если переход из состояния q1 в q2 может быть осуществлен при появлении одного из нескольких символов, то над дугой диаграммы (ветвью графа) должны быть надписаны все они.

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

Детерминированность

Конечные автоматы подразделяются на детерминированные и недетерминированные.

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

Недетерминированный конечный автомат (НКА) является обобщением детерминированного. Недетерминированность автоматов достигается двумя способами:

Если рассмотреть случай, когда автомат задан следующим образом:

, (3)

где:- множество стартовых состояний автомата, такое что ;

Тогда появляется третий признак недетерминизма - наличие нескольких начальных (стартовых) состояний у автомата.

Существует теорема, гласящая, что "Любой недетерминированный конечный автомат может быть преобразован в детерминированный так, чтобы их языки совпадали" (такие автоматы называются эквивалентными). Однако, поскольку количество состояний в эквивалентном ДКА в худшем случае растёт экспоненциально с ростом количества состояний исходного НКА, на практике подобная детерминизация не всегда возможна. Кроме того, конечные автоматы с выходом в общем случае не поддаются детерминизации.

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

1.3 Виды конечных автоматов

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



Особенностью автомата Мили является то, что функция выходов является двухаргументной и символ в выходном канале y[t] обнаруживается только при наличии символа во входном канале x[t]. Функциональная схема не отличается от схемы абстрактного автомата.

Рис. 2. Функциональная схема автомата Мили.

В автомате Мура функция j определяет значение выходного символа только по одному аргументу - состоянию автомата. Эту функцию называют также функцией меток, так как она каждому состоянию автомата ставит метку на выходе. Математическая модель и схема рекуррентных соотношений автомата Мура имеют вид:

Особенностью автомата Мура является то, что символ y[t] в выходном канале существует все время пока автомат находится в состоянии q[t].



Рис. 3 Функциональная схема автомата Мура.

Объединение автоматов Мили и Мура представляет С-автомат, для которого схема рекуррентных соотношений имеет вид:

Потребность такого автомата возникает при формировании автоматных сетей.

Рис. 4. Функциональная схема С-автомата.

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

Пусть X=Ж. Тогда математическая модель и система рекуррентных соотношений имеют вид:



Рис. 5. Функциональная схема порождающего автомата.

Особенностью функционирования такого автомата является генерация последовательности символов выходного слова только в зависимости от последовательности состояний автомата. Такие автоматы называют порождающими или автономными. С помощью такого автомата генерируется последовательность управляющих команд на какие-либо объекты внешней среды.

Пусть Y=Ж. Тогда математическая модель и система рекуррентных соотношений имеют вид:

Рис. 6. Функциональная схема распознающего автомата.

Особенностью функционирования такого автомата является распознавание в последовательности изменений аргумента функции переходов значения (qi[t];xi[t]) и перевод автомата в заключительное состояние qk. С помощью такого автомата обнаруживают заданные возмущения со стороны объектов внешней среды или распознают заданную последовательность входных символов. Поэтому такие автоматы называют распознающими. Часто и автомат Мура представляют автоматом без выхода, так как его выходной сигнал эквивалентен состоянию автомата.

Пусть Q=Ж. Тогда математическая модель и система рекуррентных соотношений имеют вид:



Рис. 7. Функциональная схема комбинационного автомата.

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



Глава 2. Конечный автомат как элемент автоматного программирования

2.1 Описание конечного автомата

Автоматы удобно описывать с помощью таблиц, а для наглядности использовать графы. При табличном описании задают две таблицы, одна из которых раскрывает функцию переходов y:--(QДX)®--Q а другая - функцию выходов j:--(QДX)®--Y Число строк таблиц m равно числу состояний автомата, т.е. m = кQ--к. Число столбцов таблиц n равно числу символов входного алфавита, т.е. n = кX--к. В позиции первой таблицы записывают значения очередных состояний автомата q[t+1]ОQ, в которые он переходит для каждой пары (q[t];x[t])О(QДX). В позиции второй таблицы записывают значения символов выходного алфавита y[t]ОY, которые генерирует автомат для каждой пары (q[t];x[t])О(QДX). Если в таблицах 1 и 2 определены значения q[t+1]ОQ--?--y[t]ОY для каждой пары (q[t];x[t])О(QДX), то есть заполнены все позиции таблиц, то дано описание детерминированного автомата.

Таблица 1



Таблица 2

Обычно эти таблицы совмещают в одну, которая раскрывает оператор поведения (y;j):--(QДX)--®--(QДY) В позициях этой таблицы записывают пары (q[t+1];y[t]) для каждой пары (q[t];x[t]).

Таблица 3



Таблица 4

Таблицы абстрактного автомата совпадают с таблицами автомата Мили. Поэтому таблица 3 описывает поведение автомата Мили. Таблица автомата Мура (см. таблицу 4) несколько отличается от таблицы автомата Мили, так как j:Q®Y. Значение выходного символа приписывают, как метку, состоянию автомата. Описание С-автомата есть объединение таблиц 3 и 4. Так как в таблицах 3 и 4 определены все позиции, то такими таблицами дано описание детерминированных автоматов.

В практике проектирования автоматов встречаются случаи, когда функции переходов и/или выходов не определены для некоторых значений символов входного алфавита. В этом случае говорят, что автомат недетерминированный или частично определенный. При описании таких автоматов неопределенные позиции таблиц помечаются символом "*". Например, в таблицах 5, 6, 7 и 8 приведено описание недетерминированных автоматов.

Поведение автомата удобно анализировать с помощью графов, вершинами которого являются элементы множества qОQ. Тогда вершина-исток есть образ текущего состояния q[t], а вершина-сток - образ очередного состояния q[t?1]. Дуги отображают переход автомата из одного состояния в другое (q[t];q[t+1]) под воздействием x[t]ОX. Для описания автомата с помощью графов удобно воспользоваться таблицами соединений состояний автомата. Строки и столбцы такой таблицы представляют символы qОQ. Следовательно, число строк и столбцов таблицы равно m. Строки этой таблицы характеризуют текущее состояние, т.е. q[t], а столбцы - очередное, т.е. q[t?1]. Позиции таблицы заполняют значениями пары (x[t]/y[t]) для соответствующего перехода автомата из текущего состояния в очередное.

Таблица 5

Таблица 6



Таблица 7

Таблица 8

Таблицей 9 дано описание соединений состояний автомата Мили, а таблицей 10 - автомата Мура. Для автомата Мили на дугах графа указывают пару (входной символ/выходной символ). Для автомата Мура на дугах графа указывают только входной символ, определяющий переход автомата из одного состояния в другое, а выходной символ y, приписывают к каждой вершине графа.

При начертании графа детерминированного автомата следует соблюдать следующие условия:1) для каждого символа xОX есть дуга, исходящая из вершины qОQ; 2) каждый символ xОX у каждой вершины-истока qОQ принадлежит только одной дуге; 3) если между двумя вершинами qОQ существует несколько дуг, что может быть обусловлено переходом автомата из состояния qsОQ в состояние qtОQ при различных символах на входе, то есть xi xj, то эти дуги могут быть заменены одной дугой с указанием дизъюнктивной связи этих состояний (например, если yuyv, то на дуге следует указать (xi/yuЪxj/yv);.если yu=yv=y, то - (xiЪxj)/y).

Таблица 9

Таблица 10



2.2 Примеры конечных автоматов

Пример 1.

Детерминированный автомат Мили задан таблицей 11.

Таблица 11.

Детерминированный автомат Мили (y;j):--(QДX)--®--(QДY)
текущее состояние q?Q	символы входного алфавита xi?X
	x1	x2	x3	x4
q1	q2;y1	q3;y1	q4;y1	q1;y3
q2	q3;y3	q4;y1	q1;y2	q2;y2
q3	q2;y1	q3;y2	q1;y1	q2;y3
q4	q4;y2	q1;y1	q2;y2	q1;y1

Составить таблицу соединения состояний автомата и начертить граф. Найти генерируемые автоматом слова b? для различных начальных состояний,?если на входе автомата задано слово a = (x1x2x3x4x4x3x2x1).

Для формирования таблицы соединения состояний автомата находим по таблице 11 число строк и столбцов. Это число равно 4. Имена строк и столбцов заданы именами элементов множества qОQ. В позициях таблицы будут значения (x/y), соответствующие переходу из состояния q[t] в состояние q[t?1]. Следует обратить внимание, что переход из состояния q3 в q2 обусловлен двумя входными символами (x1 и x4), а для каждой пары (q3;x1) и (q3;x4) автомат генерирует в выходном канале особый символ (y1 и y3). Поэтому на дуге (q3;q2) следует указать (x1/y1Ъx4/y3). Переход из состояния q4 в q1 обусловлен также двумя входными символами (x2 и x4), но автомат генерирует только один символ на выходе y1. Поэтому на дуге (q4;q1) следует указать (x2Ъx4)/y1. Остальные переходы автомата обусловлены появлением только одного входного символа. Таблица 12 представляет таблицу соединений состояний автомата Мили, а рис. 8 - его граф.

Таблица 1.12.

Соединение состояний автомата Мили (y;j):--(QДX)--®--(QДY)
текущее состояние q?Q	очередное состояние q?Q
	q1	q2	q3	q4
q1	x4/y3	x1/y1	x2/y1	x3/y1
q2	x3/y2	x4/y2	x1/y3	x2/y1
q3	x3/y1	(x1/y1)?(x4/y3)	x2/y2	--
q4	(x2?x4)/y1	x3/y2	--	x1/y2

Рис. 8. Граф детерминированного автомата Мили.

Для поиска слов b при различных начальных условиях необходимо проследить всю последовательность изменения состояний автомата для каждого очередного символа слова a:

пусть q1=q0, тогда

a[t]:--x1[1]--x2[2]--x3[3]--x4[4]--x4[5]--x3[6]--x2[7]--x1[8]

q[t+1]:--q1[1]--q2[2]--q4[3]--q2[4]--q2[5]--q2[6]--q1[7]--q3[8]--q2[9]

b[t]:y1[1]--y1[2]--y2[3]--y2[4]--y2[5]--y2[6]--y1[7]--y1[8],

то--есть--b=(y1y1y2y2y2y2y1y1);

пусть--q2=q_,--тогда



a[t]:x1[1]--x2[2]--x3[3]--x4[4]--x4[5]--x3[6]--x2[7]--x1[8]

q[t+1]:q2[1]--q3[2]--q3[3]--q1[4]--q1[5]--q1[6]--q4[7]--q1[8]--q2[9]

b[t]:y3[1]--y2[2]--y1[3]--y3[4]--y3[5]--y1[6]--y1[7]--y1[8],

то--есть--b=(y3y2y1y3y3y1y1y1);

программирование--конечный--автомат--анализатор

пусть--q3=q_,--тогда

a[t]:x1[1]--x2[2]--x3[3]--x4[4]--x4[5]--x3[6]--x2[7]--x1[8]

q[t+1]:q3[1]--q2[2]--q4[3]--q2[4]--q2[5]--q2[6]--q1[7]--q3[8]--q2[9]

b[t]:y1[1]--y1[2]--y2[3]--y2[4]--y2[5]--y2[6]--y1[7]--y1[8],

то--есть--b=(y1y1y2y2y2y2y1y1);

пусть--q4=q_,--тогда

a[t]:x1[1]--x2[2]--x3[3]--x4[4]--x4[5]--x3[6]--x2[7]--x1[8]

q[t+1]:q4[1]--q4[2]--q1[3]--q4[4]--q1[5]--q1[6]--q4[7]--q1[8]--q2[9]

b[t]:y2[1]--y1[2]--y1[3]--y1[4]--y3[5]--y1[6]--y1[7]--y1[8],

то--есть--b=(y2y1y1y1y3y1y1y1).

Анализ показывает, что при различных начальных состояниях реакция автомата на одинаковые слова различна. Это подтверждает необходимость указания начального состояния qi=q0. Только в этом случае каждому слову на входе автомата найдется единственный образ на выходе.

Пример 1.2.

Детерминированный автомат Мура задан таблицей поведения (см. таблицу 13).



Таблица 13.

Детерминированный автомат Мура y:--(QДX)®--Q;--j:--Q®Y
текущее состояние qОQ	символы входного алфавита xОX	Выход yОY
	x1	x2	x3	xn
q1	q2	q3	q4	q1	y1
q2	q3	q4	q1	q2	y3
q3	q2	q3	q1	q2	y2
qm	q4	q1	q2	q1	y1

Составить таблицу соединения состояний автомата и начертить граф. Найти генерируемые автоматом слова b ?для различных начальных состояний,?если на входе автомата задано слово a = (x1x2x3x4x4x3x2x1).

Для формирования таблицы соединения состояний автомата находим по таблице 13 число строк и столбцов. Это число равно 4. Имена строк и столбцов заданы именами элементов множества qОQ. Элементами таблицы соединения состояний автомата будут значения x, соответствующие переходу из состояния q[t] в состояние q[t?1]. Переход из состояния q3 в q2 обусловлен двумя входными символами (x1 и x4). Поэтому на дуге (q3;q2) cледует указать (x1Ъx4). Переход из состояния q4 в q1 обусловлен также двумя входными символами (x2 и x4). Поэтому на дуге (q4;q1) следует указать (x2Ъx4). Таблица 14 представляет таблицу соединений состояний автомата Мура, а рис.9 - его граф.

Таблица 14

Соединение--состояний--автомата--Мура--y:--(QДX)®--Q;--j:--Q®Y
текущее состояние q?Q	очередное--состояние--qОQ	Выход--yОY
	q1	q2	q3	q4
q1	x4	x1	x2	x3	y1
q2	x3	x4	x1	x2	y3
q3	x3	(x1?x4)	x2	--	y2
q4	(x2?x4)	x3	--	x1	y1



Рис. 9 Граф детерминированного автомата Мура.

Для поиска слов b при различных начальных условиях необходимо проследить всю последовательность изменения состояний автомата для каждого очередного символа слова a:

пусть q1=q0, тогда

a[t]:x1[1]--x2[2]--x3[3]--x4[4]--x4[5]--x3[6]--x2[7]--x1[8]

q[t+1]:q1[1]--q2[2]--q4[3]--q2[4]--q2[5]--q2[6]--q1[7]--q3[8]--q2[9]

b[t]:y1[1]--y3[2]--y1[3]--y3[4]--y3[5]--y3[6]--y1[7]--y2[8],

то--есть--b=(y1y3y1y3y3y3y1y2);

пусть--q2=q_,--тогда

a[t]:x1[1]--x2[2]--x3[3]--x4[4]--x4[5]--x3[6]--x2[7]--x1[8]

q[t+1]:q2[1]--q3[2]--q3[3]--q1[4]--q1[5]--q1[6]--q4[7]--q1[8]--q2[9]

b[t]:y3[1]--y2[2]--y2[3]--y1[4]--y1[5]--y1[6]--y1[7]--y1[8],

то--есть--b=(y3y2y2y1y1y1y1y1);

пусть--q3=q_,--тогда



a[t]:x1[1]--x2[2]--x3[3]--x4[4]--x4[5]--x3[6]--x2[7]--x1[8]

q[t+1]:q3[1]--q2[2]--q4[3]--q2[4]--q2[5]--q2[6]--q1[7]--q3[8]--q2[9]

b[t]:y2[1]--y3[2]--y1[3]--y3[4]--y3[5]--y3[6]--y1[7]--y2[8],

то--есть--b=(y2y3y1y3y3y3y1y2);

пусть--q4=q_,

тогда

a[t]:x1[1]--x2[2]--x3[3]--x4[4]--x4[5]--x3[6]--x2[7]--x1[8]

q[t+1]:q4[1]--q4[2]--q1[3]--q4[4]--q1[5]--q1[6]--q4[7]--q1[8]--q2[9]

b[t]:y1[1]--y1[2]--y1[3]--y1[4]--y1[5]--y1[6]--y1[7]--y1[8]

то--есть--b=(y1y1y1y1y1y1y1y1).

Этот пример также подтверждает необходимость указания начального состояния q=q0.

Пример 1.3.

Недетерминированный автомат Мили задан таблицей поведения (см. таблицу 15).

Составить таблицу соединения состояний автомата и начертить граф. Найти генерируемые автоматом слова b? для различных a и различных начальных состояний.

Элементами таблицы соединения состояний автомата будут значения (x/y), соответствующие переходу из состояния q[t] в состояние q[t?1].

Следует обратить внимание, что не определены переходы из состояния q2 для входного символа x1, из состояния q3 для входного символа x2 и из состояния q4 для входного символа x4.

Не определены также значения символов на выходе для состояния q1 и входного символа x2, для состояния q2 и входного символа x4 и для состояния q3 и входного символа x2.

Таблица 16 представляет таблицу соединений состояний недетерминированного автомата Мили, а рис.10 - его граф.

Таблица 15.

Недетерминированный--автомат--Мили--(y;j):--(QДX)--®--(QДY)
текущее--состояние--qОQ	символы--входного--алфавита--xiО--X--
	x1	x2	x3	x4
q1	q2;y1	q3;*	q4;y1	q1;y3
q2	*;y3	q4;y1	q1;y2	q2;*
q3	q2;y1	*;*	q1;y1	q2;y3
q4	q4;y2	q1;y1	q2;y2	*;y1

Таблица 16.

Соединение--состояний--автомата--Мили--(y;j):--(QДX)--®--(QДY)
текущее--состояние--qОQ	очередное--состояние--qОQ
	q1	q2	q3	q4
q1	x4/y3	x1/y1	x2/*	x3/y1
q2	x3/y2	x4/*	--	x2/y1
q3	x3/y1	(x1/y1)?(x4/y3)	--	--
q4	x2/y1	x3/y2	--	x1/y2

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

пусть q1=q0 и a= (x1x2x3x3x3x2x4x4), тогда

a[t]:x1[1]--x2[2]--x3[3]--x3[4]--x3[5]--x2[6]--x4[7]--x4[8]

q[t+1]:q1[1]--q2[2]--q4[3]--q2[4]--q1[5]--q4[6]--q1[7]--q1[8]--q1[9]

b[t]:y1[1]--y1[2]--y2[3]--y2[4]--y1[5]--y1[6]--y3[7]--y3[8],

то--есть--b=(y1y1y2y2y1y1y3y3);



Рис. 10. Граф недетерминированного автомата Мили.

пусть--q1=q_--и--a=--(x2x2x3x4x4x3x2x1),--тогда

a[t]:x2[1]--x2[2]--x3[3]--…

q[t+1]:q1[1]--q3[2]--*--…

--b[t]:*[1]--*[2]--…,

то--есть--b=--(*--*--…--и--автомат--"зависает"--на--третьем--символе--слова--a;

пусть--q1=q_--и--a=--(x2x2x3x4x4x3x2x1),--тогда

a[t]:x1[1]--x4[2]--x3[3]--x2[4]--x3[5]--x2[6]--x4[7]--x4[8]

q[t+1]:q1[1]--q2[2]--q2[3]--q1[4]--q3[5]--q1[6]--q3[7]--q2[8]--q2[9]

b[t]:y1[1]--*[2]--y2[3]--*--[4]--y1[5]--*--[6]--y3[7]--*--[8],

то--есть--b=(y1*y2*y*y*)--содержит--четыре--символа--"*";

пусть--q2=q_--и--a=--(x1x4x3x2x3x2x4x4),--тогда

a[t]:--x1[1]--x4[2]--…

q[t+1]:--q2[1]--*.[2]--…

b[t]:--y3[1]--…



то--есть--b=--(y3--…--и--автомат--"зависает" на втором символе слова a.

Анализ показывает, что недетерминированный автомат Мили может

1) генерировать на выходе последовательности символов, равные последовательностям символов на входе, но содержащие неопределенные символы "*", что разрушает образ слова a;

2) "зависать" в состоянии, для которого не определен переход в очередное состояние.

Пример 1.4.

Недетерминированный автомат Мура задан таблицей поведения (см. таблицу 17).

Таблица 17.

Недетерминированный--автомат--Мура--y:--(QДX)®--Q;--j:--Q®Y
текущее--состояние--qОQ	символы--входного--алфавита--xОX	Выход--yОY
	x1	x2	x3	xn
q1	q2	q3	q4	q1	y1
q2	*	q4	q1	q2	*
q3	q2	*	q1	q2	y2
qm	q4	q1	q2	*	y1

Составить таблицу соединения состояний автомата и начертить граф. Найти генерируемые автоматом слова b? для различных a и различных начальных состояний.

Элементами таблицы соединения состояний автомата будут значения x, соответствующие переходу из состояния q[t] в состояние q[t?1]. Следует обратить внимание, что не определены переходы из состояния q2 для входного символа x1, из состояния q3 для входного символа x2 и из состояния q4 для входного символа x4. Не определено также значение символа на выходе для состояния q2. Таблица 18 представляет таблицу соединений состояний недетерминированного автомата Мура, а рис. 11 - его граф.

Таблица 18.

Соединение--состояний--автомата--Мура--y:--(QДX)®--Q;--j:--Q®Y
текущее--состояние--qОQ	очередное--состояние--qОQ	Выход--yОY
	q1	q2	q3	q4
q1	x4	x1	x2	x3	y1
q2	x3	x4	*	x2	*
q3	x3	(x1?x4)	*	--	y2
q4	x2	x3	--	x1	y1

Рис. 11. Граф недетерминированного автомата Мура.

Для поиска слов b при различных начальных условиях необходимо проследить всю последовательность изменения состояний автомата для каждого очередного символа слова a:

пусть--q1=q_--и--a=--(x2x3x2x3x3x1x2x4),--тогда

a[t]:x2[1]--x3[2]--x2[3]--x3[4]--x3[5]--x1[6]--x2[7]--x4[8]

q[t+1]:q1[1]--q3[2]--q1[3]--q3[4]--q1[5]--q4[6]--q4[7]--q1[8]--q1[9]

b[t]:y1[1]--y2[2]--y1[3]--y2[4]--y1[5]--y1[6]--y1[7]--y1[8],

то--есть--b=--(y1y2y1y2y1y1y1y1);

пусть--q2=q_--и--a=--(x2x3x1x4x4x3x2x1),--тогда



a[t]:x2[1]--x3[2]--x1[3]--x4[4]--…

q[t+1]:q2[1]--q4[2]--q2[3]--*--[4]--…

b[t]:*--[1]--y1[2]--*--[3]--…,

то--есть--b=--(*y1*--…--и--автомат--"зависает"--на--четвертом--символе--слова--a;

пусть--q1=q_--и--a=--(x1x2x3x3x1x3x1x3),--тогда

a[t]:x1[1]--x2[2]--x3[3]--x3[4]--x1[5]--x3[6]--x1[7]--x3[8]

q[t+1]:q1[1]--q2[2]--q4[3]--q2[4]--q1[5]--q2[6]--q1[7]--q2[8]--q1[9]

b[t]:y1[1]--*[2]--y1[3]--*--[4]--y1[5]--*--[6]--y1[7]--*--[8],

то--есть--b=(y1*y1*y1*y1*)--содержит--четыре--символа--про"*";

пусть--q2=q_--и--a=--(x1x4x3x2x3x2x4x4),--тогда

a[t]:--x1[1]--x4[2]--…

q[t+1]:--q2[1]--*--[2]--…

b[t]:*--…,

то--есть--b=--(*--…--и--автомат--"зависает"--на--втором--символе--слова--a.

Анализ показывает, что для недетерминированного автомата Мура характерны такие же недостатки, как для недетерминированного автомата Мили



Заключение

Автоматное программирование, иначе называемое "программирование от состояний" или "программирование с явным выделением состояний" -- это метод разработки программного обеспечения, основанный на расширенной модели конечных автоматов и ориентированный на создание широкого класса приложений.

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

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

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



Библиографический список

1. Leveson N.G., Clark S.T. An Investigation of the Therac-25 Accidents. // IEEE Computer. 26(7):18-41, July 1993.

2. Дейкстра Э. Дисциплина программирования / Дал У., Дейкстра Э., Хоор К. Структурное программирование. М.: Мир. 2011.

3. Кларк Э., Грамберг О., Пелед Д. Верификация моделей программ: Model Checking. М.: МЦНМО, 2012. 416 с.

4. Pnueli A. The Temporal Logic of Programs // Proceedings of the 18th IEEE Symposium on Foundation of Computer Science. 2007.

5. Поликарпова Н., Шалыто А. Автоматное программирование. СПб.: Питер, 2009. 176 с.

6. Вельдер С.Э., Шалыто А.А. О верификации автоматных программ на основе метода Model Checking // Информационно-управляющие системы. 2012. №3, с. 27-38.

7. Васильева К.А., Кузьмин Е.В. Верификация автоматных программ с использованием LTL // Моделирование и анализ информационных систем. Ярославль: ЯрГУ. 2007. Т. 14, №1, с. 3-14.

8. Abran A., Swebok M.J. Guide to the Software Engineering Body of Knowledge. http://www.swebok.org/

9. Kaner C., Falk J., Nguyen Q. Testing Computer Software. NY: Wiley. 2009.

10. Бурдонов И.Б., Косачев А.С., Кулямин В.В. Неизбыточные алгоритмы обхода ориентированных графов. Детерминированный случай // Программирование. 2010, №5.

Размещено на Allbest.ru