Теория автоматов

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

СОДЕРЖАНИЕ

• 1. Автоматы
• 1.1 Основные понятия и определения
• 1.2 Способы задания автоматов
• 1.3 Понятие стационарной и динамической среды
• 1.4 Понятие целесообразности поведения автоматов
• 1.5 Детерминированный автомат
• 1.6 Вероятностный автомат
• 1.7 Автомат с переменной структурой
• 2. Автомат Мили и Мура
• 3. Конечные автоматы
• 3.1 Автоматы первого и второго рода
• 3.2 Способы задания конечных автоматов
• 3.3 Минимизация конечных автоматов


1. Автоматы

1.1 Основные понятия и определения

Предположим, что существует несколько логических переменных u₁…u_r, и будем рассматривать их как вектор U. Пусть f -- логическая функция от этих переменных, образующая некое сложное логическое высказывание

q=f(U)

Будем рассматривать q как выходную величину РКС, реализующую логическую функцию f. автомат детерминированный вероятностный

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

Будем считать, что РКС осуществляет логические операции мгновенно, т.е. если в момент времени t на вход схемы поступает вектор U, то соответствующее значение q=f(u) получится на выходе в тот же самый момент времени. Для описания работы РКС во времени удобно ввести понятие дискретного времени. Т.е. физическое понятие бесконечно, равномерно, и непрерывно текущего времени мы заменим точечными моментами времени, считая, что все изменения происходят именно в эти моменты, и между ними не происходит никаких изменений. Более того, считаем, что длина этих промежутков настолько мала, что этим значением можно пренебречь. На оси t отметим моменты, в которые входная величина может претерпеть изменения t₁, t₂, …, t_n. Эти величины называются тактами. Уравнения q[n]=f(u(n)], где n --n-тый такт, описывает работу РКС во времени. РКС является простейшим видом конечных автоматов -- конечный автомат без памяти.



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

Другим способом задания конечного автомата, обеспечивающим большую наглядность, является задание автомата с помощью направленного графа. Вершины графа -- это возможные состояния автомата. Вершины i,k соединяются дугами тогда и только тогда, когда существует сигнал, переводящий автомат из состояния i в состояние k, при этом дуга помечается значением сигнала U и в скобках указывается значение выходного сигнала q.

Сигнал U мы будем называть влиянием среды. Среда описывается вероятностью выпадания того или иного события. Т.е. среда Е описывается множеством своих состояний D и вероятностью наступления именно этого состояния Р. Будем считать.

1.2 Способы задания автоматов

Табличный способ

При этом способе автомат Мили описывается двумя таблицами: таблицей переходов и таблицей выходов.



Таблица переходов

xj\aj	a0	…	an
x1	d(a0,x1)	…	d( an,x1)
…	…	…	…
xm	d( a0,xm)	…	d( an,xm)

Таблица выходов

xj\aj	a0	…	an
x1	l(a0,x1)	…	l( an,x1)
…	…	…	…
xm	l( a0,xm)	…	l( an,xm)

Строки этих таблиц соответствуют входным сигналам x(t), а столбцы - состояниям. На пересечении столбца ai и строки xj в таблице переходов ставится состояние as = d[ ai,xj], в которое автомат перейдет из состояния ai под воздействием сигнала xj; а в таблице выходов - соответствующий этому переходу выходной сигнал yg = l[ ai,xj].

Совмещенная таблица переходов и выходов автомата Мили:

xj\ai	a0	…	an
x1	d(a0,x1)/ l(a0,x1)	…	d(an,x1)/ l(an,x1)
…	…	…	…
xm	d(a0,xm)/ l(a0,xm)	…	d(an,xm)/ l(an,xm)

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

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

Отмеченная таблица переходов автомата Мура:

yg	l(a0)	…	l(an)
xj\ac	a0	…	an
x1	d(a0,x1)	…	d(an,x1)
…	…	…	…
xm	d(a0,xm)	…	d(an,xm)

xj\ai a0 a1 a2 a3 x1 a1/y1 a2/y3 А3/y2 a0/y1 x2 a0/y2 a0/y1 A3/y1 a2/y3

yg y2 y1 y1 y3 y2 xj\xj a0 a1 a2 a3 a4 x1 a2 a1 a3 a4 a2 x2 a3 a4 a4 a0 a1

Автомат МилиАвтомат Мура

В этой таблице каждому столбцу приписан, кроме состояния ai, еще и выходной сигнал y(t) = l(a(t)), соответствующий этому состоянию. Таблица переходов автомата Мура называется отмеченной потому, что каждое состояние отмечено выходным сигналом.

Приведем примеры табличного задания автоматов Мили и Мура:

По этим таблицам можно найти реакцию автомата на любое входное слово. Например.

Для автомата Мили: Для автомата Мура:

x1x2x2x2x1…x1x2x2x2x1…

a0a1a0a0a0a1 a0a2a4a1a4

y1y1y2y2y1 y2y1y2y1y2

Графический способ задания автомата

(задание автомата с помощью графа).

Этот способ основан на использовании ориентированных связных графов. Вершины графов соответствуют состояниям автомата, а дуги - переходам между ними. Две вершины графа ai и as соединяются дугой, направленной от ai к as, если в автомате имеется переход из ai в as, т.е. as = d(ai, xj). В автомате Мили дуга отмечается входным сигналом xj, вызвавшим переход, и выходным сигналом yg, который возникает при переходе. Внутри кружочка, обозначающего вершину графа, записывается состояние. Например, для автомата Мили, приведенного выше, граф имеет вид а), а для автомата Мура вид б).

а) б)

1.3 Понятие стационарной и динамической среды

Прежде чем начать конструировать и описывать какие-либо автоматы, определим такое фундаментальное понятие теории простейших автоматов, как понятие среды. В отличии от естественных наук, в теории простейших автоматов среде интересует нас только с одной точки зрения: реакции на действие нашего автомата. Значение оценок действий автомата описывается некоторым конечным множеством D = {d₁, d₂, …d_n}. Если наш автомат может сделать на i-том такте одно из m действий, то среда описывается матрицей вероятностей А(m, n). В которой А(i. j) = вероятности выпадения j -- той реакции среды (d_j) на i -- тое действие автомата. Если с течением времени значение матрица А остаются неизменными, то среда называется стационарной.

Такую интересную трактовку поведения биологических организмов и описания условий существования этих организмов предложил блестящий советский математик и инженер М.Л. Цетлин. Суть гипотезы простоты Цетлина сводится к тому, что любое достаточно сложное поведение слагается из совокупности простых поведенческих актов. Их совместная реализация и простейшее взаимодействие со средой приводят в результате к весьма сложным поведенческим процессам.

Приведем один из простейших биологических экспериментов, на основе изучения результатов которых Цетлин и создавал свои первые автоматы. В биологии эти опыты известны как опыты Йеркса. В начале опыта дождевой червь помещался на ярко освещенную площадку «Т-образного» лабиринта. Червь начинал движение с целью найти более комфортные условия существования. Там где коридор имел разветвление, червь имел выбор из двух альтернатив. Конечно, червь не мог знать, что по дороге в левом коридоре включено электрическое поле, а заканчивается коридор раздражающей червя солевой ванночкой. В то время как правый коридор приводит червя в затемненную влажную камеру, где он чувствовал себя превосходно.

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



С точки зрения Цетлина общая схема этого опыта выглядит таким образом.

Каким же образом описывается этот автомат и его среда обитания. У нашего автомата есть два возможных действия: {«Направо», «Налево»}, среда также имеет две реакции:{«Наказание», «Поощрение»}. Матрица вероятностей будет выглядеть так:

	Наказание	Поощрение
Направо	0	1
Налево	1	0

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

	Наказание	Поощрение
Направо	Рп	1 - Рп
Налево	Рл	1 - Рл

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

С описанием более сложных сред обитания и «жизни» автоматов связано понятие динамической среды. Поскольку законы изменения параметров внешней среды могут быть очень различными. Мы рассмотрим самый простой способ описания динамической среды. Будем рассматривать динамическую среду как набор конечного числа стационарных сред, описанных уже известным нам способом, Е₁ , Е₂ … Е_k . И будем считать, что каждая из этих сред представляет собой моментальную фотографию состояния динамической среды. Эти фотографии, меняясь, как кадры кинофильма, воссоздают нам динамическую среду.

Коммутатор как бы подключает автомат к той или иной стационарной среде. Как характеристики этих сред, так и законы работы коммутатора автомату заранее неизвестны. Адаптация состоит не только в оценке вероятностей Р_i^m, где верхний индекс означает среду Е_m , а и в определении закономерности смены сред.

Мы рассмотрим только один, наиболее хорошо изученный, частный случай работы коммутатора. Будем считать, что коммутатор производит переключение сред, руководствуясь некоторой квадратной матрицей. Назовем ее вероятностной матрицей переключения сред Т. Т_ij -- вероятность перехода от Е_i к Е_j на следующем шаге. По законам теории вероятностей

"i У_jТ_ij = 1

Такую динамическую среду еще называют переключающейся.

1.4 Понятие целесообразности поведения автомата

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

Лиса вернулась с богатой добычей. Часть ее насытила лисий выводок, а оставшуюся пищу лиса прячет «на черный день». Тщательно роет яму, кладет в нее мясо и засыпает ее землей. Наблюдая за поведением лисицы, можно прийти к выводу, что цель действий лисицы порождена ее «интеллектом». Столь целесообразно и «разумно» ее поведение.

Но судьба нашей героини оказалась не очень счастливой. Она попала в западню и стала жительницей зоопарка. Теперь ей уже не приходится тратить силы на добывание пищи. Ее кормят служители. Но что делать лисице, когда пищи избыток? Конечно, прятать! И лиса скребет когтями бетонный пол вольера, а через некоторое время, когда «яма» готова, «прячет» в нее мясо. И после этого перестает замечать остаток трапезы, который, конечно, так и остается лежать на полу вольера. Лиса просто игнорирует его, не видит «зарытое» мясо. То, что в привычной для животного среде выглядело целесообразным, в условиях другой реальности становится лишенным каких-либо черт разумности.

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

Как же оценивать целесообразность поведения искусственно сконструированных автоматов? Для этого заменим наш автомат устройством равновероятного выбора действий. На каждом шаге своего функционирования этот механизм, никак не учитывая приходящих на его вход сигналов «штраф» - «поощрение», с одинаковой вероятностью, равной 1/n, выбирает одно из доступных ему действий.

При бесконечном повторении опыта с механизмом равновероятного выбора действий, будет накоплен некоторый суммарный штраф. Его величина определяется как математическое ожидание штрафа по формуле, хорошо известной из теории вероятностей:

Значение М^* позволяет интерпретировать понятие целесообразного поведения следующим образом. Будем говорить, что автомат ведет себя целесообразно, если накопленный ею суммарный штраф меньше, чем в случае использования механизма равновероятного выбора действий. А нецелесообразным будем считать такое поведение, при котором этот суммарный штраф больше или равен М^* .

Пусть, например, в опыте Трондайка Р_п = 0,9, а Р_л = 0,4. Если бы крыса заранее знала эти вероятности, то она, конечно, всегда бы предпочитала бежать в левый коридор. Если при наших значениях вероятностей штрафов за действия крысу поставить в условия равновероятностного выбора, то суммарное значение штрафа для нее будет равно

М = 0,5*0,9 + 0,5*0,4 = 0,65

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

М = 0*0,9 + 1*0,4 = 0,4

Опишем структуру технических устройств, обеспечивающих целесообразное поведение в любой априорно неизвестной стационарной среде.

1.5 Детерминированный автомат

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

Нарисуем граф переходов этого автомата. Состояние 1 -- плясать, состояние 2 -- плакать. Наша среда так же может вы давать только две ответные реакции: «Бить» или «Не бить». Сплошной чертой мы обозначим реакцию нашего автомата на поощрение (реакция «Не бить»); пунктирной линией -- на наказание (реакция «Бить»).

Составим для этого примера таблицу переходов.

Строки -- это состояние автомата, в момент времени t

U --это состояние окружающей среды. Обе эти переменные двоичны.

	1 (свадьба)	0 (похороны)
1 (плакать)	2	1
2 (петь)	2	1

Значения переменной Х -- "1" -- плакать

"2" - петь

Значения переменной U -- "0" -- похороны

"1" - свадьба

Выходом этого автомата будем считать сведения о смене состояния автомата. "0" -- если не меняет состояние

"1" -- если меняет.

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

Вот как выглядит граф переходов такого автомата. Сплошной стрелкой мы показали переход при наказании, пунктирной -- при поощрении. В нашем примере определено по три устойчивых состояния для каждого действия автомата. Будем считать, что состояния 1, 2, 3 -- обозначают действие «плакать» нашего Иванушки, а состояния 4, 5, 6 -- действие «петь». Это число называется глубиной памяти конечного автомата или степенью его инерционности. Покажем, что такой автомат достаточно быстро найдет лучшее для статической среды действие, и будет выполнять только его. Поясним эту мысль. Пусть в начале наш автомат находится в состоянии 3. А влияние среды описывается (0,9;0,1) т.е. с вероятностью 0,9 встретится свадьба и с вероятностью 0,1 -- похороны. Понаблюдаем за поведением нашего Иванушки. С вероятностью 0,9 встретится свадьба, и Ивана побьют, он перейдет в состояние 4, он станет петь и опять с вероятностью 0,9 на свадьбе. По теории вероятностей, вероятность получения от среды двух свадеб подряд равна 0,81, Двух похорон подряд 0,01, а вероятность одной свадьбы и одних похорон = 0,18. Следовательно, после двух тактов взаимодействия с вероятностью 0,01 автомат окажется в состоянии 1, с Р=0,18 в прежнем положении, и с Р=0.81 в состоянии 5. С ростом числа взаимодействий качественно картина не изменится. Вероятность покинуть группу 6-4 неуклонно падает, а вероятность остаться в ней -- растет.

Что произойдет дальше? С Р=0,9 наш автомат получит поощрение и перейдет в состояние 6 и т.д. Вероятность покинуть группу 4-6 все время будет уменьшаться. Этот процесс очень похож на процесс обучения, после которого наш автомат "достаточно адекватно" ведет себя в данной статической среде. "Достаточно адекватно" потому, что существует очень малая, но ненулевая вероятность покинуть группу наиболее благоприятного поведения ( т.е. поведения когда сумма штрафов минимальна).

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

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

Подчеркнем еще раз, повышение глубины памяти улучшает показатель целесообразности поведения автомата с линейной тактикой для статических сред. Более того, Цетлин показал, что если min P_i <0,5 то при увеличении глубины памяти q автомата с линейной тактикой мы получим последовательность автоматов с линейной тактикой со все увеличивающейся глубиной памяти, которая является асимптотически оптимальной. Это означает, что при q >? М(q, Е) > М_min -- минимальный суммарный штраф. Т.о. конструкция, предложенная Цетлиным, обеспечивает при достаточно больших значения q поведение, сколь угодно близкое к наилучшему в любых стационарных случайных средах.

Рассмотрим еще пару конструкция автоматов с линейной тактикой.

Эта конструкция предложена В.И. Кринским. Мы будем называть «доверчивым». Вот как выглядит его граф переходов.

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

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

Может сложиться ощущение, что любые меры по увеличению числа инерционности автомата, улучшает показатель целесообразности поведения автомата.

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

1.6 Вероятностный автомат

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

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

Такой автомат, как правило, задается системой матриц, в которых на пересечении i - того столбца и k -той строки указывается Р перехода из i - того состояния в k-тое. В частном случае, когда такие матрицы содержат только "0" и "1", описывается уже знакомый нам детерминированный автомат.

Выписывание таких матриц слишком громоздкая процедура, поэтому покажем вид этих матриц для автомата, показанного на рисунке.

Эти матрицы определяют детерминированную структуру нашего автомата. П+ - матрица переходов при поступлении сигнала поощрения, а П- при поступлении сигнала штрафа.

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

Приведем наглядный пример такого автомата.

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

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

1. Бабочка начинала двигаться в сторону, противоположную прежнему движению.

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

3. Бабочка начинала хаотическое движение, т.е. переходит на такую траекторию полета, которая максимально затрудняет для нападающего предсказание следующей точки на этой траектории.

На рисунке изображен граф смены состояний вероятностного автомата. Его особенность состоит в том, что для каждой группы состояний (они обведены на рисунке пунктиром) существует ненулевая вероятность перейти в особое состояние, описывающее гибель автомата. Состояние 1 можно интерпретировать следующим образом: 1 - с Р=0,3 летучая мышь обнаруживает бабочку, а с Р=0,7 - пропускает ее. 2 - мышь определяет направление своего движения и с р= 0,8 цель при этом не теряется. 3 - летучая мышь настигает бабочку и уничтожает ее с Р=0,95. Что может противопоставить преследователю бабочка? Для простоты изложения будем рассматривать каждую из групп состояний автомата, как определенную среду, задаваемую стратегией бабочки. Е1 - это прямой полет. Е2 - изменение направления движения в горизонтальной или вертикальной плоскости, а Е3 - хаотическое движение. Действия бабочки сводятся к смене сред, переключению их. При этом автомат может реализовывать действие только в состоянии 2 или 3. На рисунке это показано двойными стрелками переходов.

Составьте сами таблицу состояний этого автомата.

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

1.7 Автомат с переменной структурой

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

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

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

Пусть для определенности в начальный момент времени автомат находился в состоянии 1, и совершил действие 1, соответствующее этому состоянию. С помощью равновероятного выбора по матрице П+ перешел в состояние 4. И пусть после этого он получил сигнал штраф. Получение такого сигнала заставляет автомат считать свой переход 1 - 4 ошибкой. Эта информация фиксируется следующим образом. Вероятность П⁺₁₄ уменьшается на , а все остальные элементы строки увеличиваются на /3. Для удобства положим = 0.03. Тогда после этого шага матрица П- не изменится, а матрица П+ будет выглядеть так:

На очередном шаге автомат делает действие 2, соответствующее состоянию 4, и выбирает очередное состояние на основании матрицы П- (т.к. в текущем акте общения со средой он находится в условиях последнего сигнала от среды - штрафа).

Пусть он выбрал переход 4 - 4 и вновь получил штраф. Теперь меняется матрица П-, а матрица П+ остается неизменной.

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

Рассмотрением этой конструкции автомата мы и ограничимся.

Скажем только, что существует очень большое множество классов конечных и бесконечных автоматов, активно используемых в технике. И более подробно об этих объектах вы будете говорить в курсах теории автоматического управления. Я же хочу обобщить сказанное. С математической точки зрения автомат задается А - входным алфавитом, В - выходным алфавитом, S - алфавитом состояний автомата и двумя функциями - функцией переходов и - функцией выходов.

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

Следует четко понимать, что функция отображает множество SxА в S; а - отображает множество SxА в В.



2. Автомат Мили и Мура

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

Автомат 1-го рода или автомат Мили.

Автомат 2-го рода или автомат Мура.

Структура автомата Мили представлена на рис. 1.5.

Автомат Мили представляется в виде двух комбинационных схем и памяти, состоящей из отдельных элементов памяти.

Первая комбинационная схема (в дальнейшем будем обозначатьее КС1) имеет две группы входов. Одна группа входов является входами автомата в целом (x₁, x₂, …, x_{n ).} На другую группу входов поступают сигналы из памяти автомата (q_t¹, q_t², …, q_t^k _)., т.е. состояние автомата. По отношению к автомату в целом эти сигналы являются внутренними. На выходах схемы КС1 формируются сигналы (q_t+1¹,q_t+1²,…,q_t+1^k)_, которые поступают на входы элементов памяти (ЭП_r).



Рис. 1.5

После записи в память эти сигналы в следующем такте будут представлять собой следующее состояние автомата (Q_t+1). Таким образом схема КС1 является схемой формирования следующего состояния автомата.

Вторая комбинационная схема (КС2) называется выходным преобразователем и служит для формирования выходных сигналов автомата (y₁, y₂, …, y_{m ).} На ее входы поступают те же сигналы, что и на входы схемы КС1. Поэтому выходные сигналы в автомате Мили зависят как от состояния, так и от входных сигналов, поступающих в данном такте. Обобщенная структура автомата Мили имеет вид, представленный на рис.1.6.



Рис. 1.6

Работа автомата Мили описывается в общем виде уравнениями переходов и выходов:

Y_t = Y( X_t, Q_t ) ; (1.4)

Q_{t + 1} = Q( X_t, Q_t).

Уравнение (функция) переходов Q_t+1=Q(X_t, Q_t) определяет условия перехода автомата из одного состояния в другое. Это уравнение задает логику работы комбинационной схемы КС1.

Уравнение (функция) выходов Y_t=Y(X_t,Q_t ) определяет условия формирования определенных выходных сигналов. Это уравнение задает логику работы комбинационной схемы КС2.

Анализ уравнений (1.4) показывает, что логика работы автомата Мили совпадает с логикой работы автомата обобщенной структуры, представленной на рис. 1.4.

Автомат Мура имеет структуру, показанную на рис. 1.7.



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

Эта структура внешне очень незначительно отличается от структуры автомата Мили. Как видно на рис.1.7, это отличие заключается в том, что в автомате Мура входной сигнал не поступает на комбинационную схему КС2 (схему формирования выходов).

Работа автомата Мура описывается следующими уравнениями переходов и выходов:

Y_t = Y( Q_t ) ; (1.5)

Q_{t + 1} = Q ( X_t, Q_t).

Из уравнений (1.5) видно, что выходной сигнал автомата Мура зависит только от текущего состояния и не зависит от входного сигнала в данном такте. Следует особо отметить, что выходной сигнал зависит от входных сигналов, поступивших в предыдущих тактах, поскольку от них зависит текущее состояние. Таким образом, выходной сигнал автомата Мура задержан на один такт по отношению к входному сигналу

Иногда выходные сигналы автомата Мура совпадают с сигналами состояний. В этом случае автомат не имеет комбинационной схемы КС2 и называется автоматом без выходного преобразователя. Обобщенная структура такого автомата показана на рис. 1.8.



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

Алгоритм работы автомата Мура без выходного преобразователя описывается следующими уравнениями переходов и выходов:

Y_t = Q_t ; (1.6)

Q_{t + 1} = Q ( X_t, Q_t).



3. Конечные автоматы

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

Конечный автомат является частным случаем машины Тьюринга <A₁, Q₁, S>, а именно:

· внешний алфавит конечного автомата А₁=АВ, АВ=, где А - входной алфавит, В - выходной алфавит;

· внутренний алфавит Q₁=Q (т.е. D={dл,dп,dн}=);

соответствие S вход-выход конечного автомата QAQB, Dom S QA , Jm S QB.

В этом плане конечный автомат U₃ = <A, Q, B, S> в общем случае (как трансдъюсер) является частичным (т.е. не всюду определенным) и недетерминированным.

Автомат U₃=<A,Q,B,Г>, где Г - отображения, будем называть всюду определенным недетерминированным конечным автоматом.

Автомат U₃=<A,Q,B,Г_f>, где Г_f - функциональное отображение, называется всюду определенным детерминированным конечным автоматом.

Далее будем рассматривать инициальные автоматы, в которых Г_f есть характеристические функции перехода и выхода , т.е: U₃(q₀)=<A,Q,B, q₀,,>, q₀Q, : QA Q, : QA B

3.1 Автоматы первого и второго рода

Автомат первого рода (автомат Мили) - синхронный конечный автомат, поведение которого задается парой функций:



t=1,2,3,...

Здесь q(t-1), q(t) - соответственно предшествующее и последующее состояния автомата.

Автомат второго рода - конечный автомат описываемый аналитической функциональной моделью вида

q(t)= (q(t-1), а(t))

b(t)= (q(t), a(t)) t= 1,2,3,...

Замечание:

1) для каждого автомата 2-г о рода существует эквивалентный ему автомат 1-го рода. Действительно:

Т.е. для эквивалентного автомата функция выходов (q(t), a(t))= ₁(q(t-1), а(t))

2) Между автоматами первого и второго рода существует взаимно-однозначное соответствие (изоморфизм).

Автомат Мура (правильный автомат второго рода) - аналитическая функциональная модель синхронного конечного автомата вида

q(t)= (q(t-1), а(t))

b(t)= (q(t)) t= 1,2,3,...

В этом автомате выходная буква b есть функция только одного аргумента состояния q (т.е. не зависит от входной буквы). Иначе, (q(t), a_i(t))= (q(t), a_j(t₁))=(q(t))=м(д(q(t-1),a)), (здесь м- функция отметок),

: QB

Автомат Мура <A,Q,B,,> называют автономным (без входов) автоматом или генератором, если функция переходов не зависит от букв входного алфавита, т.е. < Q,B,,>, : QQ, или (q_i, а_j)= (q_i, а_e)= (q_i)

Конечный автомат называется переходной системой, если Q=B и для всякого q_iQ имеет место (q_i, а)= q_i

В этом случае имеем модель <A,Q,>

3.2 Способы задания конечных автоматов

Задание (представление) автомата - вариант описания его программы, поведения или функционирования при известных алфавитах.

Способ описания автомата зависит от подхода к его пониманию (абстрактный автомат или структурный автомат).

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

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

Напоминание:

1)Конечный инициальный автомат с поведением называют трансдьюсером (преобразователем).

2)Конечный инициальный автомат с поведением

L_F={А*: (q₀, _a)= ((q₀, )a)= q_i q_e q_z, q_nQ, q_zFQ}

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

3) Конечный инициальный автомат с поведением f()=(q₀, )= b_i b_j b_p (это множество значений словарной функции f() или т.н. перечислимое множество) называют порождающие конечным автоматом.

3.3 Минимизация конечных автоматов

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

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

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

Определение.

Пусть М = (Q, q₀, F) конечный автомат, а q₁ и q₂ два его различные состояния. Будем говорить, что цепочка х различает состояния q₁ и q₂, если (q₁, х)?^?(q₃, е), (q₂, х)?^?(q₄ ,е) и одно из состояний q₃ и q₄ принадлежит F. Будем говорить, что q₁ и q₂ k- неразличимы, и писать q₁q₂, если не существует такой цепочки х, различающей q₁ и q₂, у которой |x|k. Будем говорить, что состояния q₁ и q₂, неразличимы и писать q₁?q₂, если они k - неразличимы для любого k0.

Состояние qQ называется недостижимым, если не существует такой входной цепочки х, что (q₀, х)?^?(q, е).

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

Пример. Рассмотрим конечный автомат М с диаграммой (рис. 3.4).

Рис. 3.4. Диаграмма автомата М

Чтобы сократить М, заметим сначала, что состояния F и G недостижимы из начального состояния А, так что их можно устранить. Пока качественно, а позже строго мы установим, что классами эквивалентности отношений являются {A}, {B, D} и {C, E}. Тогда, взяв представителями этих множеств p, q и r, можно получить конечный автомат вида (рис. 3.5).

Рис. 3.5. Приведенный конечный автомат



Перед тем, как построить алгоритм канонического конечного автомата, введём лемму:

Лемма.

Пусть М = (Q, q₀, F) конечный автомат с n состояниями. Состояния q₁ и q₂ неразличимы тогда и только тогда, когда они (n-2) - неразличимы, т.е. если два состояния можно различить, то их можно различить с помощью входной цепочки, длина которой меньше числа состояний автомата.

Алгоритм построения канонического конечного автомата.

Вход.

Конечный автомат М = (Q, q₀, F).

Выход.

Эквивалентный конечный автомат М'.

Метод.

Шаг 1. Применив к диаграмме автомата ^ М алгоритм нахождения множества вершин, достижимых из данной вершины ориентированного графа, найти состояния достижимые из q₀. Установить все недостижимые состояния.

Шаг 2. Строить отношения эквивалентности ?⁰, ?¹ по схеме:

1. q₁ ?⁰ q₂ тогда и только тогда, когда они оба принадлежат, либо оба не принадлежат F;

2. q₁ q₂ тогда и только тогда, когда q₁ q₂ и (q₁, а) (q₂, а) для всех а.

Шаг 3. Построить конечный автомат

М'=(Q', ' q₀', F'),

где Q' - множество классов эквивалентности отношений ? (обозначим через [p] класс эквивалентности отношений, содержащий состояние р);

('[p], а) = [q], если (р, а) = q;

q₀' - это [q₀];

F' - {[q] | qF}.

Теорема.

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

Пример.

Найдём приведённый конечный автомат автомату М (рис. 3.6).

Рис. 3.6. Диаграмма автомата М

Отношения для к0 имеют следующие классы эквивалентности:

класс отношения ?⁰ {A, F}, {B, C, D, E};

класс отношения ?¹ {A, F}, {B, E}, {C, D};

класс отношения ?² {A,F}, {B,E}, {C,D}.

Так как ?² = ?¹ , то ? = ?¹ .Приведённый автомат М' будет ({[A],[B], [C], {a, b}, ', A, {[A]}}), где ' определяется следующей таблицей.

Таблица 3.4 - Приведенный конечный автомат

Состояние	a	b
[A]	[A]	[B]
[B]	[B]	[C]
[C]	[C]	[A]

[A] - выбрано для представления класса {A, F};

[B] - выбрано для представления класса {B, E};

[C] - выбрано для представления класса {C, D}.

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