Разработка недетерминированных программных систем на основе вероятных автоматов
Система цифровых автоматов: основные понятия и определения, классификация, способы задания. Структурная схема конечного автомата. Основные формулы комбинаторики. Предмет теории вероятностей. Дискретные распределения. Реализация вероятностного автомата.
| Рубрика | Программирование, компьютеры и кибернетика |
| Вид | дипломная работа |
| Язык | русский |
| Дата добавления | 05.11.2015 |
| Размер файла | 1,2 M |
Отправить свою хорошую работу в базу знаний просто. Используйте форму, расположенную ниже
Студенты, аспиранты, молодые ученые, использующие базу знаний в своей учебе и работе, будут вам очень благодарны.
Размещено на http://www.allbest.ru/
ВВЕДЕНИЕ
цифровой атомат вероятностный комбинаторика
Вычислительные системы существуют уже не один десяток лет. Целью их создания являлась возможность заменить человека, сделать за него трудоемкую работу, требующую сложных вычислений. С развитием теории больших систем, усиленное изучение функционирования биологических структур, исследование надежности систем, состоящих из большого числа элементов, поиски методов управления объектами, для которых неизвестна достаточно точная математическая модель их функционирования, привели к возникновению и интенсивному развитию специального раздела теоретической кибернетики -- теории вероятностных автоматов. Эта теория опирается, с одной стороны, на мощные методы и результаты теории конечных детерминированных автоматов, а с другой стороны, широко использует идеи и методы теории статистических решений и теории игр. Теория вероятностных автоматов еще не получила какого-либо окончательного завершения и терминологического оформления. Различные исследователи, работающие в этой области, используют различную терминологию, что существенно усложняет выработку единой точки зрения. Кроме того, как и в теории детерминированных автоматов, в теории вероятностных автоматов можно наметить два направления, различных по своим задачам и методам: абстрактная теория вероятностных автоматов занимается проблемами эквивалентности автоматов, представимостью тех или иных событий в вероятностных автоматах, алгебраическими задачами, связанными с моделями такого типа; структурная теория исследует другой круг проблем, в который входят задачи анализа работы имеющихся устройств, разработка методов синтеза вероятностных устройств, исследование их поведения в реальных средах, решение задач структурной надежности и т. д,
Актуальность. В последнее время одними из актуальных становятся задачи связанные с объектами или комплексами объектов, действующих в недетерминированных средах. Актуальность обуславливается развитием технологий, усложнением объектов, а также стремлением автоматизировать процессы, ранее производимые с помощью человека
Целью дипломной работы является: написание программы построения вероятностного автомата
Задачи, решаемые в дипломной работе, для достижения поставленной цели:
- исследование вероятностных автоматов;
- исследование классификации вероятностных автоматов;
- выбор представления вероятностных автоматов;
- выбор подходящей среды разработки программы;
- разработка программного обеспечения.
1. СИСТЕМА ЦИФРОВЫХ АВТОМАТОВ
1.1 Основные понятия и определения
В компьютере обрабатывается числовая информация, представленная в двоичной системе счисления, то имеется информация представлена в облике композиции нулей и единиц. Потому работу хоть какой схемы ЭВМ разрешено рассматривать как многофункциональный преобразователь с огромным количеством входов и выходов. При данном прибытие на входы некой очередности входных сигналов, состоящих из 0 и 1, вызывает появление на выходах полностью определенной последовательности выходных сигналов, также состоящей из нулей и единиц.
Все схемы ЭВМ можно поделить на 2 класса: Класс логических или комбинационных схем, класс конечных автоматов.
В логических и комбинационных схемах смысл выходных сигналов в эпизод времени t несомненно ориентируется значениями входных сигналов в момент времени t1t.
Технические вопросы синтеза комбинационных схем находят решение с помощью аппарата математической логики. При этом употребляется исключительно обычная часть математической логики, а конкретно, алгебра логики либо Булева алгебра. Главным понятием в алгебре логики, на котором базируется ее приложение к синтезу КС, считается понятие Булевой либо переключательной функции.
В вычислительной технике в основном употребляется схемы 2-ух классов: комбинационные схемы и цифровые автоматы. Характерной особенностью комбинационных схем считается наличие жесткой функциональной зависимости между выходным сигналом и входным: y(t)=f(х(t)). При этом при отсутствии входных сигналов выходные сигналы еще отсутствуют, поскольку эти схемы не имеют памяти. В отличии комбинационных схем схемы второго класса содержат в своем составе элементы памяти (запоминающие элементы). Данные схемы именуются цифровыми автоматами либо просто автоматами.
Автомат - дискретный преобразователь информации способный воспринимать разные состояния, переходить перед действием входных сигналов из 1-го состояния в иное и выдавать выходные сигналы. Если множество состояний автомата, а так же большого количества входных и выходных сигналов конечны, то автомат именуется конечным автоматом. Понятие состояния введено во взаимосвязи с тем, что часто появляется необходимость в описании поведения систем, выходные сигналы каких находятся в зависимости не только от состояния входов в этот момент времени, однако и от некоторых предысторий, то есть от сигналов, которые поступали на входы системы раньше. Состояния как раз и соответствуют некой памяти о прошлом, позволяя устранить время как явную переменную и выразить выходные сигналы как функцию состояний и входов в этот момент времени. [1]
Кодирование информации. Информацию, поступающую на вход автомата, а так же выходную информацию принято кодировать конечной совокупностью знаков. Эту совокупность именуют алфавитом, отдельные символы, образующие алфавит - буквами, а любые упорядоченные последовательности букв данного алфавита - словами в данном алфавите.
К примеру: в алфавите Х=(х1, х2), состоящем из двух букв, словами будут: х1, х2, х1х1, х1х2, х2х1,х2х2, х1х1х1 и т.д.
Математической моделью реального конечного автомата считается абстрактный автомат, который имеет один входной канал и один выходной канал (таблица 1).
Таблица 1. Математическая модель автомата
Автомат работает в дискретные моменты времени, интервал, между которыми Т именуется тактом. При этом в любой дискретный момент времени на вход автомата поступает 1 буква входного алфавита, автомат переходит из 1-го состояния в другое и выдается 1 буква выходного алфавита. В зависимости от того, как задается продолжительность такта Т, различают автоматы синхронного действия (T=соnst) и асинхронного действия (Tсоnst).
Автомат действует следующим образом: в любой момент времени t он располагаться в определенном состоянии а(t) из множества А вероятных состояний. При этом в начальный момент времени t=0 он всегда находится в состоянии а(t=0)=а0. В момент времени t автомат принимает входной сигнал х(t), выдает выходной сигналу y(t)=[а(t), х(t)] и переходит в последующее положение а(t+1)=[а(t), х(t)]. Иными словами абстрактный автомат каждой паре символов а(t) и х(t) ставит в однозначное соотношение пару символов а(t+1) и y(t). Эти автоматы именуют детерминированными. На преобразование информации в детерминированных автоматах наложены условия.
Условия преображения информации в детерминированных автоматах.
Любое входное слово, длинною l букв, преобразуется в выходное слово той же длины.
Если каждый раз перед подачей входных сигналов автомат располагаться в одном и том же состоянии, то при совпадении в 2-ух входных словах первых l1 букв, в выходных словах 1-ые l1 букв также совпадут.
Работа таких автоматов описывается уже матрицей переходов d, элементами которой считаются вероятности переходов из 1-го состояния в иное.
1.2 Классификация автоматов
Используемые на практике автоматы принято делить на 2 класса - это автоматы Мили и автоматы Мура, названные так по имени американских экспертов, которые в первый раз начали их изучать. Функционирование автоматов строго подчиняется конкретным законам законы - функционирования автоматов. Законы функционирования автоматов описываются системами уравнений. Рассмотрим каждый из автоматов подробней.
Законы функционирования автомата Мили описываются последующей системой уравнений, представленные в таблице 2.
Таблица 2. Автомат Мили
Функциональная схема автомата Мили представлена на рисунке 1.
Рисунок 1. Схема автомата Мили
Характерной особенностью автоматов Мили считается то, что их выходные сигналы находятся в зависимости, как от состояния автомата, так и от значения входного сигнала.
Законы функционирования автомата Мура описываются последующей системой уравнений, представленные в таблице 3.
Таблица 3. Автомат Мура
Функциональная схема автомата Мили представлена на рисунке 2.
Рисунок 2. Схема автомата Мура
1.3 Способы задания автоматов
Чтобы задать конечный автомат S, нужно описать все элементы множества S={А, Х, Y, , }. То есть нужно описать входной, выходной алфавиты и алфавит состояний, а также функции переходов и выходов . При этом среди большого количества А={а0,а1,…, аn} нужно отметить начальное состояния а0, в котором автомат располагаться в момент времени t=0. Существует некоторое количество способов задания работы автомата, однако наиболее часто используются табличный и графический.
Табличный способ. При табличном способе задания автомат Мили описывается 2-мя таблицами: таблицей переходов и таблицей выходов (таблицы 4,5).
Таблица 4. Таблица переходов
Таблица 5. Таблица выходов
Строки данных таблиц соответствуют входным сигналам х(t), а столбцы - состояниям. На пересечении столбца аi и строки хj в таблице переходов ставится состояние аs=[аi, хj], в которые автомат перейдет из состояния аi под действием сигнала хj; а в таблице выходов - соответствующий данному переходу выходной сигнал yg=[аi,хj]. Время от времени автомат Мили задают совмещенной таблицей переходов и выходов, она в некоторых вариантах более удобна (таблица 6).
Таблица 6.
Совмещенная таблица переходов и выходов автомата Мили
Задание таблиц переходов и выходов вполне описывает работу конечного автомата, поскольку задаются не только сами функции переходов и выходов, но еще и все 3 алфавита: входной, выходной и алфавит состояний. Так как в автомате Мура выходной сигнал однозначно определяется состоянием автомата, то для его задания требуется лишь 1 таблица, которая именуется отмеченной таблицей переходов автомата Мура (таблица 7).
Таблица 7.
Отмеченная таблица переходов автомата Мура
Примеры табличного задания автоматов Мили и Мура (таблицы 8,9).
Таблица 8. Автомат Мура
Таблица 9. Автомат Мили
По этим таблицам можно найти реакцию автомата на любое входное слово: для автомата Мура в таблице 10, для автомата Мили в таблице 11.
Таблица 10. Реакция автомата Мура
Таблица 11. Реакция автомата Мили
Графический способ. При графическом способе задание автомата осуществляется с помощью графа. Граф для автоматов Мили и Мура представлен на рисунке 3 и 4 соответственно.
Рисунок 3. Граф для автомата Мили
Рисунок 4. Граф для автомата Мура
Данный способ базируется на применении ориентированных связных графов. Вершины графов соответствуют состояниям автомата, а дуги - переходам между ними. 2 вершины графа аi и аs объединяются дугой, направленной от аi к аs, если в автомате имеется переход из аi в аs, то есть аs=(аi, хj).
1.4 Другие виды автоматов
Частичные автоматы. В инженерной практике нередко встречаются автоматы, на входы которых некоторые последовательности сигналов ни разу не подаются. Эти последовательности станем именовать запрещенными входными словами данного автомата, а сам автомат - частичным автоматом. У частичного автомата функции переходов и выходов определены не на всех парах аi, хj. На месте неопределенных состояний и выходных сигналов ставится прочерк. При синтезе традиционно производят до определение частичного автомата, чтоб его схемная осуществление вышла как можно легче. Пример переходов и выходов частичного автомата представлен в таблице 12.
Таблица 12.
Таблица переходов и выходов частичного автомата Мили
Элементарные автоматы. В настоящее время в вычислительной технике, как правило, употребляются элементарные автоматы, имеющие следующие особенности:
1) Элементарные автоматы считаются автоматами Мура с 2-мя внутренними состояниями;
2) Автомат выдает 2 различных выходных сигнала, соответственных двум его внутренним состояниям. В предстоящем состояния автомата и его выходные сигналы будем обозначать одной буквой Q и кодировать цифрами 0 и 1;
Элементарные автоматы имеют все шансы иметь в общем случае некоторое количество физических входов, на любой из которых могут подаваться сигналы, закодированные цифрами 0 и 1.
В качестве элементарных автоматов в вычислительной технике используются, в основном, триггеры разных типов (рисунок 5). Здесь рассмотрены некоторые из них.
Рисунок 5. Элементарный автомат
Т-триггером называют автомат Мура с двумя устойчивыми состояниями и одним входом Т, который изменяет свое состояние на противоположное всякий раз, когда на вход Т поступает входной единичный сигнал (таблица 13).
Таблица 13. Таблица переходов Т- триггера
Кроме того, любое состояние автомата отмечено отличным от остальных выходным сигналом. На практике наиболее комфортно за место указанных таблиц переходов воспользоваться так именуемыми матрицами переходов элементарных автоматов (таблица 14).
Таблица 14. Матрица переходов
Матрица переходов описывает значения сигналов на входах элементарного автомата, обеспечивающие любой их 4 вероятных переходов. Здесь Q(t) и Q(t+1) - состояния автомата в моменты времени t и t+1 соответственно. Так как Т-триггер владеет один вход, а количество вероятных переходов одинаково четырем, то матрица переходов имеет 4 строки.
D-триггером (триггером задержки) именуют элементарный автомат Мура с 2-мя устойчивыми состояниями и одним входом D таким, что Q(t+1)=D(t). Название D-триггера проистекает от английского слова «dеlаy» - задержка.
Матрица переходов для D-триггера представлена в таблице 15.
Таблица 15. Матрица переходов D-триггера
Обозначения асинхронного и синхронного D-триггеров представлено на рисунке 6:
Рисунок 6. Асинхронный и синхронный D-триггеры
Схема перехода состояний D-триггера представлена на рисунке 7.
Рисунок 7. Граф D-триггера
RS-триггером именуют автомат Мура с 2-мяустойчивыми состояниями, имеющий 2 входа R и S такие, что при S=1 и R=0 триггер воспринимает состояния 1, а при R=1 и S=0 состояние 0. В соответствие с состоянием, принимаемым триггером, вход S называет единичным входом, а вход R нулевым (таблица 16).
Таблица 16. Матрица переходов RS-триггера
Комбинация сигналов R=1 и S=1 считается запрещенной и поэтому переход в триггере при таких значениях входных сигналов не определен. Переход триггера из 0 в 0 вероятен при 2-ух комбинациях входных сигналов: R=0, S=0 и R=1, S=0. Поэтому в первой строке матрицы переходов RS триггера в столбце R поставлена переменная b1, которая имеет возможность воспринимать 2 значения 0 v 1.
Автоматы, которые имеют все шансы переходить из 1-го состояния в иное под действием нескольких комбинаций входных сигналов, именуются автоматами с лишней системой переходов. Избыточность можно применять в процессе синтеза для упрощения схемы, придавая переменным b1 и b2 эти значения, которые разрешают минимизировать количество элементов. Поэтому, если схемы 2-ух элементарных автоматов равноценны по сложности, то предпочтение отдают автомату, имеющему огромную избыточность системы переходов.
JK-триггером именуют автомат Мура с 2-мя устойчивыми состояниями и 2-мя входами J и K, который при условии J*K=1 исполняет инверсию предыдущего состояния (т.е. при J*K=1, Q(t+1)= Q(t)), а в других вариантах работают в соответствии с таблицей истинности RS триггера, при этом вход J эквивалентен входу S, а вход K - входу R. Данный триггер уже не имеет запрещенной комбинации входных сигналов и его таблица истинности, то имеется зависимость Q(t+1)=f[J, K, Q(t)] имеет вид (таблица 17).
Таблица 17. Таблица истинности JK-триггера
По таблице истинности JK-триггера можно построить матрицу переходов (таблица 18).
Таблица 18. Матрица переходов JK-триггера
В интегральной схемотехнике используются лишь синхронные JK триггера, которые при С=0 сохраняют свое состояние, а при С=1 действуют как асинхронные JK триггера.
Универсальный триггер. Триггер JK относится к уровню универсальных триггеров, так как на его основе путем легкой внешней коммутации разрешено построить RS-, D- и T- триггера. RS-триггер получается из триггера JK простым наложением ограничения на комбинацию входных сигналов J=K=1, так как данная комбинация считается запрещенной для RS триггера.
Вероятностные автоматы с e-переходами. В теории нередко рассматривается автоматы, именуемые автоматами с e-пере-ходами (с эпсилон - переходами). Эпсилон-переходом именуется переход между состояниями, который может существовать выполнен в отсутствии входного сигнала. Эти переходы классифицируются символом e. Внедрение эпсилон-переходов позволяет просто объединять некоторое количество автоматов в один.
Пускай требуется построить граф автомата, который должен распознавать двоичные, десятичные и шестнадцатеричные количества в обычном формате ассемблера. Автомат должен распознавать строчки, удовлетворяющие 1 из следующих критерий:
I строка состоит из одной или более цифр (0 - 9) и может заканчиваться символом «D» (например «1367» или «2345D»);
строка состоит из одного или более символов «0» или «1» и заканчивается символом «B» (например «01011B»);
строка состоит из одной или более десятичной цифр или символов от « А » до «F» и заканчивается символом «H» (например «9AD4H»).
Граф такого автомата представлен на рисунке 8.
В теории автоматов доказывается, что хоть какой вероятностный автомат имеет возможность быть заменен эквивалентным детерминированным (обычным) автоматом.
Вероятностные автоматы используются в тех вариантах, когда методика вероятностного автомата легче, чем методика эквивалентного детерминированного автомата. Вероятностные автоматы могут использоваться при моделировании умственной деятельности человека, к примеру при машинном переводе с 1-го языка на иной, в частности, при разработке трансляторов.
Рисунок 8. Граф эквивалентного детерминированного автомата имеет меньше состояний, но более сложную систему переходов.
1.5 Структурная схема конечного автомата
В структурной теории автомат предполагают в виде композиции 2-ух частей: запоминающей части, состоящей из частей памяти, и комбинационной доли, состоящей из логических элементов (рисунок 9).
Рисунок 9. Логическая схема конечного автомата
Комбинационная схема основывается на логических элементах, образующих функционально полную систему, а память - на элементарных автоматах, владеющих полной системой переходов и выходов.
Любое состояние абстрактного автомата аi, где i={0, n}, кодируется в структурных автоматах комплектом состояний частей памяти Qi,
r={1, R}. Так как в качестве элементов памяти употребляются обычные триггера, то любое состояние можно закодировать двоичным числом аi = Q1а1Q2а2... Qrаr. Здесь аi={0, 1}, а Q - состояние автомата (таблица 19).
Таблица 19. Матрица переходов JK-триггера
Общее число необходимых элементов памяти можно определить из следующего неравенства
|
(2) |
где (n+1) - число состояний.
Логарифмируя это неравенство получим:
|
(3) |
где ]С[ - значит, что нужно взять ближайшее целое число, большее или равное С.
В отличии от абстрактного автомата, имеющего один входной и один выходной каналы, на которые поступают сигналы во входном Х={х1,х2,...,хm} и выходном Y={y1, y2,..., yk} алфавитах, структурный автомат владеет L входных и N выходных каналов. Любой входной хj и выходной yj сигналы абстрактного автомата имеют все шансы существовать закодированы двоичным комплектом состояний входных и выходных каналов структурного автомата.
Очевидно, количество каналов L и N можно определить по формулам (4,5), подобным формуле для определения R.
|
(4) |
||
|
(5) |
Изменение состояния частей памяти происходит под действием сигналов U=(U1,U2,...,Ur), поступающих на их входы. Данные сигналы создаются комбинационной схемой II и именуются сигналами побуждения элементарных автоматов. На вход комбинационной схемы II, не считая входного сигнала хj, по цепи обратной взаимосвязи поступают сигналы Q=(Q1, Q2, ..., QR), именуемые функцией обратной взаимосвязи от памяти автомата к комбинационной схеме. Комбинационная схема I работает для формирования выходного сигнала yg, при этом в случае автомата Мили на вход данной схемы поступает входной сигнал хj, а в случае автомата Мура - сигнал хj, не поступает, так как yg не зависит от хj,.
Табличный метод структурного синтеза конечных автоматов. Структурный синтез конечных автоматов заключается в выборе типов элементарных автоматов, в составлении функции возбуждения всякого элементарного автомата и функций кодированных выходов заданного автомата.
Рассмотрим примеры синтеза, которые разрешают сформулировать совместный алгоритм структурного синтеза конечных автоматов. В качестве элементарных автоматов будем применять JK-триггера, а в качестве логических частей - элементы И, ИЛИ, НЕ. Итак, имеем А={а0,а1,а2}; Х={х1,х2}; Y={y1, y2, y3}. Здесь n=2, n+1=3; m=2, k=3.
Пусть нужно синтезировать автомата Мили, данный совмещенной таблицей переходов и выходов (таблица 20).
Таблица 20. Таблица переходов и выходов автомата Мили
Перейдем от абстрактного автомата к структурному, для чего определим численность частей памяти R и количество входных L и выходных N каналов. По формуле 1, 2, 3 получим следующую таблицу (таблица 21).
Таблица 21. Параметры абстрактного автомата
Таким образом, нужно иметь 2 элементарных автомата Q1 и Q2 (так как R=2), один входной канал О1 и два выходных канала Z1 и Z2.
Закодируем состояния автомата, входные и выходные сигналы совокупностью двоичных сигналов (таблица 22).
Таблица 22. Таблица кодирования
Так как автомат имеет 3 состояния, то комбинация состояний элементарных автоматов 11 не употребляется и считается запрещенной (автомат в это состояние никогда не попадет). Тут и в дальнейшем станем применять естественное кодирование, когда наборы значений двоичных переменных расписываются в порядке возрастания их номеров. С учетом кодирования перерисуем совмещенную таблицу переходов и выходов абстрактного автомата (таблица 23).
Таблица 23. Совмещенная таблица переходов и выходов
В таблицах кодировки выходные каналы Z1 и Z2 именуются физическими выходами автомата.
Пользуясь таблицами кодировки, разрешено на основе заданных переходов и выходов построить кодированные таблицы переходов и выходов. Кодированная таблица переходов определяет зависимость состояний Qi(t+1)элементарных автоматов в момент времени (t+1) от значения входного сигнала и внутренних состояний автоматов в предыдущий момент времени t.
Кодированная таблица переходов и выходов (совмещенная) имеет следующий вид (таблица 24):
Таблица 24.
Кодированная таблица переходов и выходов
Главная задача, решаемая в процессе структурного синтеза - построение таблицы функций побуждения элементарных автоматов, которая описывает значения сигналов на входах элементарных автоматов, нужные для обеспечения переходов автомата из 1-го состояния в иное. При построении данной таблицы используется матрица переходов подобранных элементарных автоматов, в нашем случае JK-триггера (таблица 25).
Таблица 25.
Матрица переходов JK-триггера
С помощью матрицы переходов заполняются столбцы таблицы функций возбуждения. В строках данной таблицы записываются значения J и K, обеспечивающие подходящий переход.
Так как функции возбуждения J(t) и K(t)определенны в тот же момент времени, что и их аргументы Q1(t), Q2(t) и О1(t), то данные функции считаются переключательными. В итоге мы получим систему переключательных функций Z1(t), Z2(t), J1(t), K1(t), J2(t) и K2(t) данных в виде таблиц их истинности.
Следующий шаг - синтез комбинационной доли конечных автоматов. На данном шаге по приобретенным переключательным функциям синтезируются комбинационные схемы. Обычно полученную систему ПФ минимизируют вместе. Но совместная минимизация всех ПФ представляет собой достаточно трудоемкую и долгую операцию, применимую, в общем случае, при применении машины. В итоге минимизации мы получим следующую схему конечного автомата (рисунок 10).
Рисунок 10. Схема конечного автомата
Функциональные схемы, получаемые в итоге структурного синтеза, в дальнейшем на шаге инженерной доработки подвергаются изменениям. Данные конфигурации связаны с тем, что прибавляются специальные цепи, нужные для работы разработанной схемы в составе остальных схем ЭВМ. К примеру, в схеме регистра сдвига информации прибавляется цепь «установка в 0». Остальные конфигурации связаны с особенностью физического представления информации в ЭВМ, с особенностями логических элементов и с техническими особенностями конечных автоматов.
1.6 Вероятностные автоматы
Детерминированные автоматы S мы задавали совокупностью из 5 объектов: S(А, Х, Y, , ), где А={а0,а1,а2,...,аM}- множество внутренних состояний автомата, Х={х1, х2,…, хF} - множество входных сигналов (входной алфавит), хi - буква входного алфавита, Y={y1, y2,…, yG} - множество выходных сигналов (выходной алфавит),
- функция переходов, обеспечивающая однозначный переход автомата в положение аs из состояния аm под действием входного сигнала хf, то есть аs= [аm, хf],
- функция выходов, характеризующая однозначное значение выходного сигнала yg в зависимости от состояния автомата аm и входного сигнала хf, т.е. yg =[аm , хf].
В работе Поспелова Д.А. «Вероятностные автоматы» рассмотрена наиболее общую модель автомата, а конкретно: зная состояние автомата аm и входной сигнал хf, мы не можем с вероятностью, равной 1 сказать, в каком состоянии окажется автомат в последующий момент времени, а также какой выходной сигнал он в этом случае вырабатывает. [2]
Законы распределения задаются в виде следующих таблиц (таблица 26, 27).
Таблица 26. Матрица переходов состояний
То есть в каждом случае имеем закон распределения, заданный в виде гистограмм.
Разумеется, так как автомат непременно перейдет в одно из состояний, то
|
(6) |
||
|
(7) |
где , .
Таблица 27.
Матрица появления выходных сигналов
Автоматы, в которых зная состояние автомата аm и входной сигнал хf, мы можем указать только вероятности перехода в новое состояние и вероятности появления выходных сигналов, т.е. законы распределения, именуются вероятностными автоматами (ВА).
По аналогии с детерминированными автоматами, Можно найти вероятностными автоматами Мили и Мура. Вероятностные автоматы, у которых вероятности появления выходных сигналов (закон распределения) находятся в зависимости только от состояний автомата, но не находятся в зависимости от входных сигналов, именуются ВА Мура. Если же вероятности появления выходных сигналов (закон распределения) находятся в зависимости как от состояний автомата, так и от входных сигналов, имеем автомат Мили.
Рассмотрим некие частные случаи вероятностных автоматов. Имеет возможность существовать, что выходные сигналы автомата ориентируются детерминировано, а переходы автомата - случайно. Эти автоматы именуются Y - детерминированными вероятностными автоматами. Ежели состояния определяются детерминировано, то владеем А - детерминированный вероятностный автомат.
Разумеется, разрешено рассмотреть общий случай, когда данные законы распределения находятся в зависимости от времени. Эти автоматы именуются ВА с переменной структурой. ВА с переменной структурой в любой фиксированный такт работы считается неким обычным ВА, однако в период между тактами ВА имеет возможность изменять свои матрицы переходных вероятностей или таблицы выходных вероятностей, либо и то и другое совместно.
Часто при построении ВА изменение вероятностей создают по некоторому закону, при этом закон находится в зависимости от истории функционирования автомата (т.е. находится в зависимости от входных сигналов, поданных на него и от выходных сигналов, т.е. реакции автомата). Эти ВА с переменной структуройименуются автоматами компенсирующего типа. Их исследованию и уделяется основное внимание.
В данном случае можно сказать, что ВА действует в некоторой среде, в которую он выдает выходные сигналы и из которой он приобретает входные (рисунок 11).
Рисунок 11. Схема вероятностного автомата
Входные сигналы условно можно поделить на поощрения («не штрафы») и наказания («штрафы»). При данном в зависимости от выходного сигнала на вход подается поощрение либо штраф. Если в зависимости от данных сигналов поменять вероятности перехода автомата из 1-го состояния в иное, то оказывается, что с течением времени автомат перестраивается таковым образом, будто он начинает с большой вероятностью получать сигналы поощрения, т.е. он в некотором смысле адаптируется к той среде, в которой он располагаться.
Неувязка организации целесообразного поведения автомата в случайной среде тесно связана со способом конфигурации вероятностей перехода автомата. Может быть, модифицирование возможностей перехода автомата по строкам и по столбцам.
Рассмотрим У-детерминированный вероятностный автомат. Пускай автомат в некий момент времени t располагаться в состоянии аm, выдал соответственный данному состоянию выходной сигнал yg и получил на вход сигнал поощрения. Тогда возможность рmm перехода из состоянии аm в состояние аm растут на некую величину, а все другие вероятности в строке уменьшаются на /М. Если же автомат получает сигнал штрафа, то возможность рmm перехода из состоянии аm в состояние аm убавляются на некую величину , а все другие вероятности в строке на растут на /М, чтобы сумма вероятностей осталась равной 1.
Возможен и иной принцип конфигурации вероятностей, при котором проистекает учет предыстории поведения автомата. Если автомат в момент времени t перешел из состояния аm в состояние ак и в момент времени t+1 получил сигнал «штраф», то вероятность рmк заменяется на рmк, где коэффициент более 0 и меньше 1, а все другие вероятности в строчке меняются на значение . Если же получил сигнал «нештраф», то вероятность рmк величину , а все другие убавляются на значение .
Можно поменять вероятности в матрице перехода не только по строкам, однако и по столбцам. К примеру, вероятен последующий алгоритм. Если в момент времени t под воздействием входного сигнала хf автомат перешел в положение аm и в момент времени t+1 получил сигнал «штраф», то самостоятельно от того, из какого состояния он перешел, все составляющие m-го столбца в матрице переходов заменяются на (рmm-) или рmm, а все другие вероятности меняются подобно тому, как это происходило при изменении возможностей по строчкам.
Основы организации подходящего поведения автомата в случайной среде тесно соединены со способом конфигурации возможностей перехода автомата. Может быть, модифицирование вероятностей перехода автомата по строчкам и по столбцам.
Подобные автоматы уже обретают использование при управлении в сложных системах и предоставляют более значительный результат там, где ранее действовали детерминированные автоматы.
Рассмотрим пример, который приводит Д.А. Поспелов - регулировка перемещения через автомобильный перекресток. Традиционно (мы с вами постоянно встречаемся именно с таким светофором) задают твёрдый режим переключения светофоров, при котором продолжительность включенных сигналов (красного и зеленого) - многократны. Но, как показывает практика работы таких светофоров, решение задачи получается неэффективным, так как предполагается, что потоки автомашин постоянные, стационарные.
Можно установить детекторы на перекрестке, которые бы подсчитывали количество автомашин, возникающее в данном направлении при красном свете светофора. Пускай на перекрестке стоит ВА компенсирующего типа, который имеет 2 состояния: подключен красный свет вдоль главного направления и подключен зеленый свет. Любому состоянию однозначно подходит выходной сигнал, т.е. автомат У-детерминированный. С датчиков поступают сигналы штрафа и нештрафа (рисунок 12).
Рисунок 12. Схема перекрестка
Матрица переходов выглядит следующим образом (таблица 28).
Таблица 28. Матрица переходов
Пускай в начале все эти вероятности равны 0,5 и на главном направлении накопилось П1 машин, а на другом - П2. На вход автомата поступает сигнал = П1 - П2. Пусть > 0, т.е. на главном направленности больше автомашин. Тогда если автомат в момент времени t располагался в состоянии зеленом, перешел в положение зеленый и получил сигнал нештраф, то возможность рзз (t+1) возрастает, а возможность рзк (t+1) миниатюризируется.
Тем самым возрастает возможность состояния зеленое вдоль главного направления, т.е. автомат подстраивается под ситуацию. Заметим, что если потоки одинаковы, то хорошей считается последующая матрица переходов (таблица 29).
Таблица 29. Матрица переходов
1.7 Применение вероятностных автоматов
Когда человек садится решать задачу. Хорошо, когда в его распоряжении имеется мощнейший компьютер с терабайтам оперативной памяти. Отлично, когда любая операция на данном компьютере не занимает и наносекунды. Вообще замечательно, если при этом имеется серьезный математический аппарат, который дозволяет решить задачу лучшим образом при всех входных данных.
А если нет? В жизни нередко приходится принимать решения «на авось» - неважно, виновата ли в данном недостающая емкость нашего мозга либо недостаток данных для четкого решения. А означает, и компьютеру иногда бывает рентабельно делать с долей риска. Именно на данный вариант эксперты придумали простую, но исключительно красивую модель - вероятностные автоматы.
Что это вероятностные автоматы? Что это детерминированные конечные автоматы, уже описывалось в дипломной работе. Предположим себе опытнейшего игрока на футбольном поле, расчерченном на крупные квадраты. Когда спортсмен ударяет по мячу, то наверное понимает, в какой квадрат он попадет - таким образом, координаты мяча находятся в зависимости лишь от нынешнего действия футболиста и того квадрата, в котором мяч был в истоке действия. Приблизительно так же действует детерминированный конечный автомат: аналог действия футболиста для него - текущий символ входной цепочки, аналог квадрата, с которого мяч начинает перемещение - текущее положение.
А теперь поменяем опытнейшего игрока на новенького, не так давно занявшегося футболом. В отличие от профи, его действия имеют все шансы заставить мяч передвигаться только в прогнозируемом спектре, однако никак не в заблаговременно загаданное пространство. Такая структура станет соответствовать еще 1 виду автоматов - вероятностным. В едином случае сходственные автоматы допускают переход из хоть какого состояния в любое иное, однако с различными возможностями (может быть, равными нулю).
Использование вероятностного автомата в задачах управления. Вероятностные автоматы нередко употребляются в моделировании как изящный и довольно действенный прием.
Говоря наиболее строго, вероятностный автомат разрешено рассматривать как детерминированный, на любом переходе которого генерируется случайное количество, в зависимости от которого будет подобрано последующее положение.
Рассмотрим в качестве образца автоматический регулировщик движения на трассе. Если из-за каждой машины на поперечной улице магистральное перемещение будет перекрываться, то в целом водители от такой регулирования только потеряют время (так как на трассе перемещение интенсивнее). Поэтому построим элементарный вероятностный автомат.
Пускай входная лента представляет собой протокол загруженности поперечной улицы. На входной ленте могут быть 2 символа: на поперечной улице никого нет (Пусто) и на поперечной улице имеется автотранспорт (Не пусто). Сам автомат имеет возможность находиться в 2-ух состояниях: движение по трассе открыто (на поперечной улице - перекрыто), и закрыто (открыто на поперечной улице). Обозначим эти состояния за Откр и Закр соответственно. Логично, что, если поперечная улица пуста, то автомат непременно переходит в положение Откр. Если трасса открыта, а на поперечной улице кто-то ожидает, то переходим в Закр с возможностью 30%, а в 70% случаев остаемся в Откр. Если трасса перекрыта, а автотранспорт на поперечной все еще имеется, то в половине случаев остаемся в Закр, а в половине - перейдем в Откр. (рисунок 13)
Рисунок 13. Схема автомата
Посчитайте, сколько времени нужно ожидать шоферу на поперечной улице для того, чтобы проехать перекресток с возможностью не меньше 80%, если сведения снимаются раз в 2 минуты. Естественно, в редких вариантах наш автомат имеет возможность создавать длинные пробки, однако в целом он действует удовлетворительно. Мы видим, что вероятностные автоматы - неплохой метод решения фактических задач, однако у них имеется серьезный недочет: нет никакой гарантии, что путь решения будет найден за количество шагов, наименьшее заранее заданного N. Поэтому нужно, чтоб шанс нахождения решения за приемлемое количество шагов был довольно велик - это следует помнить, назначая матрице переходов значения вероятностей.
Использование вероятностного автомата в задаче поиска. Задачка розыска ставится, в частности, практически в хоть какой RРG либо аркадной системе. К сожалению, достойным методом она позволяется далеко не всегда. Чаще только употребляются совсем простые алгоритмы, которые никак не справляются с мало-мальски трудными преградами (к примеру, если «нюхач» располагаться в комнате, а цель - в коридоре за стенкой, противоположной входу, «нюхач» непременно запутается). Очевидно, есть алгоритмы поиска с полной информацией о карте, однако для корректной работы они настоятельно просят огромных баз данных. Не считая того, эти алгоритмы поиска несправедливы по отношению к человеческому игроку.
Мы постараемся построить автоматный алгоритм поиска в ортогональном лабиринте. На 1-ый взгляд задачка видится неподъемной - так как подтверждено, что поиск в графе автоматно никак не допустим. Однако когда говорят «не разрешим автоматно», предполагают, будто невозможно выстроить такой детерминированный автомат, который бы сумел постановить задачу в общем случае. Мы же будем пользоваться вероятностными автоматами.
Допустим, что преследователь никак не владеет никакой информации о карте, но имеет возможность поставить, в какой-никакой приблизительно стороне располагаться мишень. Вообще говоря, преследователь, в том числе и не, понимает, располагаться ли перед ним стенка либо пустое пространство, покуда никак не попробует пройти в данном направленности. Проблема аналогична с той, что появляется перед человеком в полностью темном неизвестном подземелье, который идет на грохот, издаваемый целью, не зная пути и никак не имея способности оставить метки. Правда, человек располагаться в наиболее удачном расположении, нежели автомат - он имеет возможность отличить, к примеру, песчаный пол от каменного на ощупь либо ориентироваться по влажности и свежести воздуха в пещере. Но, даже и в данном случае человек, как правило, станет придерживаться одной стенки, чтоб вести поиск наиболее аккуратно. Мы будем управляться той же логикой.
Алгоритм хождения по стенке детерминирован и просто записывается в форме конечного автомата (рисунок 14).
Рисунок 14. Алгоритм автомата
Разберемся, что происходит в каждом состоянии.
Состояние Вправо. Производится поворот вправо и шаг. Если успешно, то переход в Вправо, иначе переход в Вперед.
Состояние Вперед. Производится поворот влево и шаг. Ели успешно, то переход в Вправо , иначе переход в Влево.
Состояние Влево. Производится поворот влево и шаг. Если успешно, то переход в Вправо, иначе переход в Назад.
Состояние Назад. Производится поворот влево и шаг. Переход в Вправо.
Если бы наш лабиринт никак не имел круговых путей и состоял из коридоров ширины, самое наибольшее, 2, то такой стратегии было бы достаточно. Однако мы разрешаем задачку в общем случае, поэтому поглядим, как люди справляются с повторяющимися путями. Человек, который долго идет по стенке в темноте, рано или поздно решит, что нужно поменять стратегию поиска, - тут стоит отметить фразу «рано или поздно»: это прямое распоряжение на то, что стоит применять вероятностные автоматы. Здравые суждения дают подсказку, что, повернув 4 раза на 90 градусов в 1 и ту же сторону, ищущий имеет возможность предположить зацикленность маршрута. Однако в спиральном лабиринте циклов нет, но там имеется та же картина поворотов. Так как наш автомат не может расценивать расстояния, он просто не сумеет распознать спираль и круг.
Поэтому, как и человек, автомат, повернув на 360 градусов, меняет стратегию поиска не всегда, а только с некой вероятностью.
Имеется еще один тип «развилки», где разрешено изменить стратегию. Она возникает на повороте в подходящем направлении. Предположим, если цель далековато на востоке к северу и, идя на восток, мы натолкнулись на стенку, то разумно пойти по правой руке и, повернув один раз на право, с некой вероятностью попробовать опять пойти напрямик к цели. В ортогональном лабиринте учет поворотов не препятствует «автоматности» алгоритма, так как достаточно распознавать их с точностью до 720 градусов. При этом, хотя количество состояний при поиске по стенке и возрастает в 8 раз, однако наш поиск делается еще наиболее осознанным.
Ключевой эпизод в построении нашего алгоритма - отбор вероятностей на «развилках». Если сделать вероятности замены стратегии очень большими, то автомат будет обнаруживать «нетерпеливость», идя вдоль неровной стены. Если сделать их очень маленькими - растет угроза долго кружить по 1 маршруту. Легче только выбирать применимые значения «на глазок», проведя для различных вероятностей огромное количество испытаний в нескольких лабиринтах и подобрав те характеристики, для которых время поиска оказывается в целом меньше. В нашем случае успешнее только оказалась возможность замены стратегии, равная 0,2.
Наконец, мы построили автомат поиска пути в лабиринте. Тесты такого автомата демонстрируют, что его выигрыш в количестве шагов по сопоставлению со стохастическим алгоритмом (передвигающимся за шаг случайным образом в любую из 4 сторон) сильно (нелинейно) растет с увеличением размеров лабиринта.
Как видно, вероятностные автоматы отлично подходят для создания моделей управления. Если задачка плохо решается точно либо наложены ограничения по используемой памяти, полностью возможно, это как раз тот вариант, когда надлежит обратиться к автоматному программированию. Но невозможно забывать, что у вероятностных автоматов имеется серьезный недочет - их непредвиденность. Поэтому лучше потратить час или 2 на отбор хороших возможностей на переходах, нежели позволять непослушному автомату на протяжении нескольких часов решать легкую задачку.
Особый «нрав» вероятностных автоматов стал среди математиков притчей в языцех: в других философских статьях даже говорится, что человек - это совсем непростой вероятностный автомат. Вряд ли к таким заявлениям стоит относиться серьезно, однако использование аналогии с человечьим поведением (как в нашем поиске) - действительно неплохой способ строить вероятностные автоматы.
2. СЛУЧАЙНЫЕ ВЕЛИЧИНЫ И ИХ РАСПРЕДЕЛЕНИЯ
2.1 Основные формулы комбинаторики
В предоставленном разделе мы займемся подсчетом количества «шансов». О количестве шансов говорят, как скоро возможно некоторое количество разных итогов какого-либо действия (извлечение игра в карты из колоды, подбрасывание кубика либо монетки, 2-ух кубиков и т.д.). Количество шансов - это количество таких вероятных итогов, либо, иначе говоря, количество методик сделать это действие.
Теорема о перемножении шансов. Пускай имеется, k групп частей, причем i-я категория охватывает ni частей, 1<=i<=k. Подберем из каждой категории по 1 составляющей. Тогда общее количество N методик, которыми разрешено произвести таковой отбор, приравнивается
|
ы(8) |
Примечание 1. В теореме 1 говорят, что даже если все составляющие в i-й группе неразличимы, избрать один из них разрешено ni методами.
Примечание 2. Итог выбора, описанного в теореме 1, предположим в виде комплекта (а1, а 2,…, а k) в котором аi - избранный из i-й категории элемент. Тогда общее количество разных комплектов (а1, а 2,…, а k) также приравнивается N.
Доказательство теоремы. Занумеруем составляющие i -ой категории количествами от 1 по ni. Элемент из 1 категории разрешено избрать n1 методами. Ежели мы избрали вещество j, 1<=i<= n1, то избрать вещество из 2-ой категории мы можем n2 методами. Получаем, что с первым составляющей j возможно составить n2 пар (j, l), где 1<=l<= n2 (рисунок 15)
Рисунок 15. Создание группы
Но столько же пар разрешено составить и с любым иным составляющей 1 категории. Тогда всего пар, в каких 1-ый элемент подобран из 1 категории, а 2-ой - из 2-ой, существует ровно
Иначе говоря, имеется способов избрать сообразно 1 составляющей из первых 2-ух групп. Возьмем 1 эту пару (j, l). Заметим, что элемент из третьей категории разрешено избрать n3 методами, то имеется возможно собрать ровно n3 троек (j, l, m), добавляя к предоставленной паре (j, l) любой из n3 частей третьей категории.
Но столько же троек разрешено собрать и с любой иной парой (j, l). Тогда всего троек, в каких 1-ый элемент подобран из 1 категории, 2-ой - из 2-ой, а 3-ий - из третьей, существует ровно .
Продолжая размышления, способом математической индукции заключаем верность утверждения теоремы.
Урны и шарики. Имеется урна, (то имеется ящичек), имеющая n занумерованных объектов, которые мы без ограничения общности станем полагать шариками. Мы избираем из данной урны k шариков. Нас интересует, сколькими методами разрешено избрать k шариков из n, либо насколько разных итогов (то имеется комплектов, состоящих из k шариков) выйдет.
На данный вопрос невозможно отдать однозначный ответ, пока мы никак не сориентируемся
- с тем, как организован выбор (скажем, можно ли шарики возвращать в урну), и
- с тем, что понимается под различными результатами выбора.
Рассмотрим следующие вероятные схемы выбора:
1) Отбор с возвращением: любой выбранный шарик возвращается в урну, то имеется каждый из k шариков выбирается из полной урны. В полученном комплекте, состоящем из k номеров шариков, имеют все шансы пересекаться одни и те же номера (подборка с повторениями).
2) Отбор без возвращения: подобранные шарики в урну не возвращаются, и в полученном комплекте не могут пересекаться одни и те же номера (подборка без повторений).
И в первом, и во втором случае итогом выбора является комплект из k номеров шариков. Удобно полагать, что шарики постоянно выбираются последовательно, по 1 (с возвращением либо без).
Условимся, какие итоги мы будем полагать разными.
Имеется ровно 2 возможности:
1) Отбор с учетом порядка: 2 комплекта номеров шариков считаются разными, если они различаются составом либо порядком номеров. Так, при выборе 3-х шариков из урны, содержащей 5 шариков, комплекты (1,2,5), (2,5,1) (4,4,5) различны, если делается отбор с учетом распорядка.
2) Отбор без учета порядка: 2 комплекта номеров шариков считаются разными, если они различаются составом. Комплекты, имеющие отличия только порядком следования номеров, числятся схожими. Так, в примере выше 1-ые 2 комплекта (1,2,5), (2,5,1) есть один и тот же итог выбора, а комплект (4,4,5) - иной итог выбора.
Подсчитаем ныне, сколько же может быть разных итогов при каждой из 4 схем (отбор с возвращением и в отсутствии, и в каждом из данных случаев предусматриваем ли мы распорядок либо нет).
Урновая схема: отбор в отсутствии возвращения, с учетом порядка
Теорема. Общее количество выборок в схеме выбора k частей из n без возвращения и с учетом распорядка определяется формулой и именуется числом размещений из n частей по k элементов.
|
(9) |
Доказательство. 1-ый шарик разрешено избрать n методами. При каждом из данных методик 2-ой шарик разрешено избрать n-1 методом, и т.д. Последний k-й шарик разрешено избрать (n-k+1) методом. По теореме 1, общее количество методик выбора равно
|
(10) |
что и требовалось доказать.
Следствие 1. Количество вероятных перестановок большого количества из n частей есть n!
Доказательство очевидно, если увидеть, что перестановка имеется не что другое, как итог выбора в отсутствии возвращения и с учетом порядка всех n частей из n. Так что общее количество перестановок равно
|
(11) |
Урновая схема: отбор в отсутствии возвращения и без учета порядка. Общее численность выборок в схеме выбора k частей из n в отсутствии возвращения и без учета порядка определяется формулой (12)
...Подобные документы
Понятие автомата как дискретного преобразователя информации, особенности его состояний. Синтез конечных автоматов, их задания и структурных анализ. Построение синтеза функций возбуждения элементарных автоматов. Комбинационный синтез конечных автоматов.
курсовая работа [336,4 K], добавлен 01.06.2014Минимизация абстрактного автомата Мили, моделирование его работы. Синтез схемы конечного автомата, микропрограммного автомата и счетчика числа микрокоманд. Разработка цифровой линии задержки. Построение граф-схем исходного и оптимизированного автоматов.
курсовая работа [823,8 K], добавлен 19.07.2012Составление треугольной таблицы. Нахождение списка максимальных классов совместимости, минимального замкнутого покрытия. Получение логических функций выходов автомата. Синтез конечного автомата и функциональной схемы. Принципиальная электрическая схема.
контрольная работа [215,8 K], добавлен 22.06.2012Теоретические и практические основы грамматик, теория конечных автоматов-распознавателей. Эквивалентные и недостижимые состояния конечных автоматов. Классификация грамматик и порождаемых ими языков. Разработка программного комплекса построения грамматик.
курсовая работа [654,2 K], добавлен 14.11.2010Разработка модели процессора, выполняющего набор машинных команд. Структурная схема процессора (операционного и управляющего автоматов), анализ принципа работы. Содержательный алгоритм микропрограммы, синтез управляющего автомата на основе жесткой логики.
курсовая работа [871,9 K], добавлен 16.09.2010Понятие и свойства конечного автомата, его назначение и сферы применения. порядок разработки специальной функции, реализующей конечный автомат. Способы описания данной функции, обоснование выбора одного из них. Программная реализация решения задачи.
курсовая работа [466,4 K], добавлен 20.01.2010Изучение методов построения конечного автомата, распознающего заданный язык, и принципы его программной реализации. Проектирование комбинационной и принципиальной схем распознающего конечного автомата с использованием библиотеки интегральных микросхем.
дипломная работа [1,8 M], добавлен 18.08.2013Принцип работы процессора (одномагистральная структура). Временные диаграммы, описывающие выполнение микроопераций для каждой команды. Структурная схема управляющего автомата на основе памяти с одним полем адреса. Описание процессора на языке Active VHDL.
курсовая работа [621,0 K], добавлен 24.09.2010Анализ использования цифровых автоматов в системах обработки информации и управления технологическими процессами. Знакомство с основными положениями электротехники. Элементы проектирование цифрового автомата, его функционирование и электрическая схема.
курсовая работа [941,6 K], добавлен 22.06.2012Построение праволинейной грамматики, автоматной грамматики по полученным результатам. Построение недетерминированного конечного автомата. Сведение недетерминированного конечного автомата к детерминированному. Описание программы и контрольного примера.
курсовая работа [674,9 K], добавлен 13.06.2012Последовательность выполнения задания и рекомендации по проектированию. Проектирование несложных дискретных устройств (цифрового автомата), структурная схема и алгоритм функционирования. Применение синхронного триггера и его отличия от асинхронного.
методичка [258,6 K], добавлен 28.04.2009Составление формальной грамматики, недетерминированный конечный автомат. Построение конечного автомата, программное моделирование работы конечного автомата. Граф детерминированного автомата, Синтаксическая диаграмма. Блок-схемы, примеры разбора строк.
курсовая работа [486,2 K], добавлен 19.11.2010Синтез автомата для преобразования двоично-десятичного кода. Кодировка алфавитов и состояний. Построение булевых функций, минимизация. Разметка вход-выходных слов для автомата Мили и автомата Мура. Реализация на элементах малой степени интеграции.
контрольная работа [141,5 K], добавлен 14.10.2012Построим содержательные графы выполнения трёх команд языка Ассемблера. Команда умножения двоичных чисел без знака mul. Команда преобразования типов cwde. Логическая команда xor. Синтез канонического автомата. Синтез М-автомата. Управляющие сигналы.
реферат [35,7 K], добавлен 18.11.2004Важный частный случай недетерминированного конечного автомата. Проверка нечетности числа единиц в произвольной цепочке, состоящей из нулей и единиц. Составление формальной грамматики, блок-схемы и программы, моделирующей работу конечного автомата.
курсовая работа [210,8 K], добавлен 05.12.2013Основные понятия структурных автоматов. Этапы канонического метода синтеза. Кодирование алфавитов автомата и выбор элементов его памяти. Построение уравнений булевых функций возбуждения и выходов. Методы устранения гонок в структурных автоматах.
курсовая работа [496,3 K], добавлен 27.01.2011Сведение недетерминированного конечного автомата к детерминированному. Построение минимального детерминированного автомата из праволинейной грамматики двумя различными способами: с помощью сетей Петри и с помощью таблиц. Описание контрольного примера.
курсовая работа [903,9 K], добавлен 14.07.2012В статье рассмотрено применение конечных автоматов для создания системы автоматов, связанных графами. Документооборот представляется в виде автомата, обрабатывающего автоматы, каждый из которых моделирует поведенческую единицу системы документооборота.
статья [80,8 K], добавлен 19.04.2006Разработка управляющего автомата, ориентированного на выполнение заданной микрооперации. Разработка алгоритма работы управляющего автомата. Листинг программы. Выбор оптимального варианта кодирования состояний автомата. Синтез функции возбуждения.
курсовая работа [506,9 K], добавлен 26.12.2012Понятие, последовательность построения и схемная реализация цифрового автомата. Описание форм представления функций алгебры логики. Принципы минимизации функций выходов и переходов автомата, их перевода в базис. Сведенья о программе Electronics Workbench.
курсовая работа [2,0 M], добавлен 27.10.2010
