› › Методы теории автоматов. Теория автоматов

Методы теории автоматов. Теория автоматов

ТЕОРИЯ АВТОМАТОВ.

ВВОДНЫЕ ПОЛОЖЕНИЯ.

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

В этой теории достаточно четко выявляются ее направления, обусловленные:

    выбором изучаемых типов автоматов (конечные, бесконечные, детерминированные, вероятностные, автономные, комбинационные, без выхода)

    принятым уровнем абстракции (абстрактные и структурные автоматы)

    спецификой применяемых математических (алгебраическая теория автоматов)

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

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

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

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

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

a i  A , b j  B, q k  Q

Когда на вход подается сигнал a i , то в зависимости от него и текущего состояния q k  Q автомат переходит в следующее состояние q l  Q и выдает сигнал на выход b j  B. Это – один такт действия автомата q k a i  q l b j . Затем подается следующий сигнал, наступает следующий такт и т.д. Изменение сигнала на входе меняет состояние автомата и его выходной сигнал означает элементарное преобразование поступающей в виде сигналов информации.

    Бесконечный автомат – абстрактный автомат, хотя бы одно из определяющих множеств A, B, Q которого бесконечно.

    Ситохастический (вероятностный) автомат - абстрактный автомат, правила преобразования информации, которого R являются вероятностными.

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

    Структурный автомат - конечный автомат, внутреннее устройство которого известно.

    Формальная грамматика = - система правил построения P в заданном алфавите TH(T – терминальный алфавит, Н – нетерминальный алфавит, ТН=) конечных знаковых последовательностей, множество которых образует некоторый формальный язык () (JH, Н - аксиома).

    Формальный язык - язык, построенный по правилам некоторого логического исчисления (иначе – язык, синтаксис которого определен формальной грамматикой ).

    Слово – цепочка символов в некотором алфавите (принято цепочки в алфавите (TH) обозначать греческими буквами; так, например,  (TH)*).

    Предложение – слово в терминальном алфавите.

    Продукция (синтаксическое правило) – способ преобразования цепочки вида  (, ,  (TH)*) в цепочку вида  ((TH)*).

    Дерево вывода (разбора) – форма наглядного представления вывода предложения в заданной грамматике.

АВТОМАТЫ И ФОРМАЛЬНЫЕ ЯЗЫКИ.

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

Тип языка () по Хомскому

Тип формальной грамматики Хомского

Автоматная модель языка

Произвольная (алгоритмическая) грамматика типа 0 

Машина Тьюринга

Грамматика типа 1 (контекстная грамматика, Н.С. грамматика, грамматика непосредственно составляющих) В

Автомат с линейно-ограниченной памятью

Грамматика типа 2(контекстно-свободная грамматика, К.С. грамматика, бесконтекстная грамматика) В

Магазинный автомат

Грамматика типа 3(автоматная, регулярная, конечная)

ВаС, Ва

Конечный автомат

Классы языков по Хомскому являются иерархией, т.е. язык типа 3 является подклассом языка типа 2, т.е. ( 3) ( 2) ( 1)  ( 0). Следуя приведенной таблице, можно говорить, что

    регулярный язык (т.е. язык, порождаемый грамматикой типа 3) распознается конечным автоматом и в этом плане является самым простым в математическом плане

    бесконтекстный язык (т.е. язык ( 2)) распознается магазинным автоматом – бесконечным автоматом, внутренняя структура которого представляет собой стековую память

    контекстный язык ( 1) распознается автоматом с линейно-ограниченной памятью, т.е. автоматом, которому для распознавания последовательности длины nN необходима память объемом не более k*n, где k – число, независящее от входного слова

    произвольный формальный язык, т.е. ( 0), распознается машиной Тьюринга – математического понятия для формального уточнения интуитивного понятия «алгоритм»

Замечание : В синтаксическом правиле В являются контекстами (левый и правый), которые могут быть пустыми цепочками; ВН, а,, ,   (ТН).

ФОРМАЛЬНЫЕ ГРАММАТИКИ.

Формальные грамматики = как процедуры могут быть порождающими и распознающими. Порождающая грамматика по существу является частным случаем формальной системы FS / =<, D>-=. В этом случае A=TH, F(TH) * , JH, P= i  j  i , j  N ,  i ,  j (TH) * , т.е. правила вывода P позволяют получать слова в терминальном алфавите Т из единственной аксиомы J путем замещения нетерминальных символов цепочек в алфавите (TH).

Распознающая грамматика – алгоритм, распознающий по любой цепочке, является ли оно словом языка  T * .

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

    определения их принадлежности формальному языку ()

    порождений выходных цепочек символов

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

Пример 1 : Т=a, b, c, H=B, C, J=B, P=BaBС, BCc, Cb

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

В, аВС, аСсС, аbсС, аbсbТ *

Эта грамматика порождает язык b, bc, abcb.

Пример 2 : множество нечетных чисел в унарном представлении – это множество терминальных слов вида а, ааа, ааааа….., т.е. язык =хТ * : ха 2 n -1 , nN. Этот язык порождается автоматной грамматикой  3 =<a, J, J, Ja, JaB, BaJ>.

Пример 3 : Язык =хТ * : х=a n b n  n  N порождается К.С. грамматикой, т.е.  2 =<a, b, J, J, JaJb, Jab>.

Пример 4 : Язык булевых формул с переменными x, y, z порождается К.С. грамматикой  2 =<x, y, z, , , , (,), J, J, J(JJ), J(JJ), JJ, Jx, Jy, JZ>.

ДЕРЕВЬЯ ВЫВОДА ПРЕДЛОЖЕНИЙ.

На практике вывод слов языка () в виде последовательности цепочек часто оказывается громоздким. Кроме того, такой способ не позволяет получить в удобном виде информацию о синтаксических конструкциях. Наилучшим способом компактного представления вывода слов в таком случае является дерево вывода (дерево синтаксического анализа, дерево грамматического разбора). Говорят, что задано стандартное дерево вывода, если правилу r i:  1 A 2  1  2 (здесь  1 ,  2 – контекст,  1 ,  2 (TH) *), АН, (TH) *) поставлено в соответствие элементарное поддерево t(r i) с вершиной А и кроной  1  2.

Пример 1 : Пусть 1=<a, b, c, A, B, C, D, J, J, JAAB, ABDBB, aBBabB, Aa, Da, BC, Cc>.

Вывод J, AAB, aAB, aDBB, aaBB, aabB, aaaBC, aabc представим деревом:

ЗдесьJ – корень дерева, J A , A a - поддеревья.

Отправить свою хорошую работу в базу знаний просто. Используйте форму, расположенную ниже

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

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

Министерство образования РФ

Государственное образовательное учреждение

высшего профессионального образования

Сибирский Государственный аэрокосмический университет

имени академика М.Ф. Решетнева

Кафедра Системного анализа

Реферат по дисциплине "Теория систем" на тему:

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

Выполнил: Ларионов А.Ю.

Проверил: Иконников О.А.

Красноярск 2013 г.

Введение

1. Общие сведения о теории автоматов

1.1 Распознаватели

1.2 Классификация автоматов

1.2.1 Абстрактный автомат

1.2.2 Виды и подвиды автоматов

2. Цифровые автоматы. Общие сведения

2.1 Логические элементы

2.2 Теория конечных цифровых автоматов с памятью

2.3 Частичные автоматы

2.4 Т-триггер

2.5 D-триггер

2.6 RS-триггер

2.7 JK-триггер

2.8 Универсальный триггер

Заключение

Список использованных источников

Введение

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

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

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

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

1. Общие сведения о теории автоматов

Теория автоматов подразделяется на абстрактную и структурную теорию.

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

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

1.1 Распознаватели

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

Язык L праволинейный тогда и только тогда, когда он определяется односторонним детерминированным конечным автоматом;

Язык L контекстно свободный тогда и только тогда, когда он определяется односторонним недетерминированным автоматом с магазинной памятью;

Язык L контекстно зависимый тогда и только тогда, когда он определяется двухсторонним недетерминированным автоматом с магазинной памятью;

Язык L рекурсивно перечислимый тогда и только тогда, когда он определяется машиной Тьюринга (этот вид математических объектов рассматривается в курсе "Математическая логика и теория алгоритмов").

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

Рисунок 1 - Распознаватель

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

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

Незаполненные ячейки (по окончании входной строки) заполняются специальным символом, обозначающим конец строки. Обычно совпадает с символом пустой строки языка е (см. рис. 1);

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

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

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

1.2 Классификация автоматов

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

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

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

1.2.1 Абстрактный автомат

Абстрактный автомат - математический объект, представляющий собой совокупность элементов: A=(S,X,Y,д,л), где S - конечное множество состояний автомата; X,Y - конечные входной и выходной алфавиты соответственно, из которых формируются строки, считываемые и выдаваемые автоматом; д:SxY->S - переходное отношение (переходная функция); л - выходная функция.

Абстрактный автомат имеет следующую функциональную схему, в соответствии с рисунком 2.

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

Где si - новое состояние автомата; xi - текущий входной символ; yi - текущий выходной символ.

Порядок работы абстрактного автомата следующий:

При поступлении очередного символа на вход автомата переходная функция у на основании поступившего символа xi и текущего состояния si определяет новое состояние автомата Si+1;

Выходная функция на основе текущего состояния автомата si и текущего входного символа xi определяет текущий выходной символ.

Объемом памяти абстрактного автомата называют количестве его внутренних состояний.

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

Понятие абстрактного автомата является наиболее общим. И фактически большинство видов автоматов являются частным случаем абстрактного автомата. В целом иерархия автоматов может быть представлена в соответствии с рисунком 3.

Рисунок 3 - Иерархия автоматов

1.2.2 Виды и подвиды автоматов

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

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

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

Частным случаем недетерминированного автомата является вероятностный автомат. Если функция переходов и/или функция выходов являются случайными, то автомат называют вероятностным. Иными словами, вероятностным автоматом называется система, описываемая конечными наборами входных сигналов Х={x1, x2,..., xn}, состояний S={s1, s2,..., sn}, выходных сигналов Y={y1, y2,..., yn}. Также задан набор условных вероятностей того, что вероятностный автомат, находясь в состоянии aj и получив входной сигнал x, перейдет в состояние ai, и выдаст сигнал y.

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

По наличию дополнительно памяти выделяют автоматы с магазинной памятью. В отличии от абстрактных автоматов, объём памяти, которых определяется количеством состояний, в таких автоматах имеется дополнительный элемент, называемый стеком. Стек реализует модель памяти LIFO (Last In - First Out) и служит для хранения промежуточных результатов работы.

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

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

2. Цифровые автоматы. Общие сведения

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

Все схемы ЭВМ можно разделить на два больших класса:

Класс логических или комбинационных схем (КС).

Класс конечных автоматов.

В логических (комбинационных) схемах значение выходных сигналов в момент времени t однозначно определяется значениями входных сигналов в момент времени t1 t.

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

Технические вопросы синтеза комбинационных схем решаются с помощью аппарата математической логики. При этом используется самая простая часть математической логики, а именно, алгебра логики или Булева алгебра. Основным понятием в алгебре логики, на котором основывается её приложение к синтезу КС, является понятие Булевой или переключательной функции (ПФ).

2.1 Логические элементы

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

В эту систему элементов входят как элементы универсального базиса: И-НЕ, ИЛИ-НЕ, так и комбинации операций булевого базиса: И-ИЛИ-НЕ.

2.2 Теория конечных цифровых автоматов с памятью

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

y (t ) = f (x (t ) ) .

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

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

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

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

Например: в алфавите X = (x1, x2), состоящем из двух букв, словами будут: x1, x2, x1x1, x1x2, x2x1,x2x2, x1x1x1 и т.д.

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

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

Автомат функционирует в дискретные моменты времени, интервал, между которыми Т называется тактом. При этом в каждый дискретный момент времени на вход автомата поступает одна буква входного алфавита, автомат переходит из одного состояния в другое и выдается одна буква выходного алфавита. В зависимости от того, как задается длительность такта Т, различают автоматы синхронного действия (T=const) и асинхронного действия (Tconst). Мы будем рассматривать, в основном, синхронные автоматы, функционирующие в дискретные моменты времени, которые можно обозначить целыми неотрицательными натуральными числами, t=0,1,2,3,…., имеющими смысл номера такта.

Для задания конечного автомата S необходимо задавать совокупность из пяти объектов: S(A, X, Y,), где A = {a0,a1,a2,...,an}- множество внутренних состояний автомата, X = {x1, x2,…, xm} - множество входных сигналов (входной алфавит), xi - буква входного алфавита, Y = {y1, y2,…, yk} - множество выходных сигналов (выходной алфавит),

Функция переходов, определяющая состояние автомата a(t+1), в котором автомат будет находится в момент времени (t+1), в зависимости от состояния автомата a(t) и входного сигнала x(t) в момент времени t, то есть a(t+1) = ,

Функция выходов, определяющая значение выходного сигнала y(t) в зависимости от состояния автомата a(t) и входного сигнала x(t) в момент времени t, т.е. y(t) = .

Автомат работает следующим образом: в каждый момент времени t он находится в определенном состоянии a(t) из множества А возможных состояний. Причем в начальный момент времени t = 0 он всегда находится в состоянии a(t = 0) = a0. В момент времени t автомат воспринимает входной сигнал x(t), выдает выходной сигналу y(t) = и переходит в следующее состояние a(t+1)=. Другими словами абстрактный автомат каждой паре символов a(t) и x(t) ставит в однозначное соответствие пару символов a(t+1) и y(t). Такие автоматы называют детерминированными. На преобразование информации в детерминированных автоматах наложены условия.

Условия преобразования информации в детерминированных автоматах:

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

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

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

Применяемые на практике автоматы принято разделять на два класса - это автоматы Мили и автоматы Мура, названные так по имени американских ученых, которые впервые начали их изучать. Функционирование автоматов строго подчиняется определённым законам (законы функционирования автоматов). Законы функционирования автоматов описываются системами уравнений:

Автомат Мили:

a(t + 1) =

y(t) =

Автомат Мура:

a(t + 1) =

Отличительной особенностью автоматов Мили является то, что их выходные сигналы зависят как от состояния автомата, так и от значения входного сигнала. В автоматах Мура выходные сигналы y (t ) в каждый дискретный момент времени t однозначно определяются состоянием автомата в тот же момент времени и не зависят от значения входного сигнала.

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

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

Строки этих таблиц соответствуют входным сигналам x (t ), а столбцы - состояниям. На пересечении столбца ai и строки x j в таблице переходов ставится состояние a s = [ a i, x j], в которые автомат перейдет из состояния a i под воздействием сигнала x j; а в таблице выходов - соответствующий этому переходу выходной сигнал y g = [ a i,x j]. Иногда автомат Мили задают совмещенной таблицей переходов и выходов, она в некоторых случаях более удобна.

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

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

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

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

При графическом способе задание автомата осуществляется с помощью графа. Этот способ основан на использовании ориентированных связных графов. Вершины графов соответствуют состояниям автомата, а дуги - переходам между ними. Две вершины графа a i и a s соединяются дугой, направленной от a i к a s, если в автомате имеется переход из a i в a s, то есть a s = (a i, x j). В автомате Мили дуга отмечается входным сигналом x j, вызвавшим переход, и выходным сигналом y g, который возникает при переходе. Внутри кружочка, обозначающего вершину графа, записывается состояние.

Граф для автомата Мили:

Граф для автомата Мура

2.3 Частичные автоматы

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

Пример таблицы переходов и выходов частичного автомата Мили

Из таблицы переходов видно, что Т-триггер обладает полной системой переходов и выходов, поскольку для каждой пары состояний (0-0, 0-1, 1-0,

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

Матрица переходов:

Матрица переходов определяет значения сигналов на входах элементарного автомата, обеспечивающие каждый их четырех возможных переходов. Здесь Q(t) и Q(t+1) - состояния автомата в моменты времени t и t+1 соответственно. Поскольку Т-триггер имеет один вход, а число возможных переходов равно четырем, то матрица переходов имеет четыре строки.

Для записи закона функционирования Т-триггера в аналитическом виде составим диаграмму Вейча по матрице перехода:

Из диаграммы имеем:

=> (T(t) + Q(t)) mod 2

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

Поясняющая работу комбинационная схема и обозначение синхронного

Т-триггера представлены на рисунке:

2.5 D-триггер

D-триггером (триггером задержки) называют элементарный автомат Мура с двумя устойчивыми состояниями и одним входом D таким, что Q(t+1) = D(t). Название D-триггера происходит от английского слова "delay" - задержка. Из определения следует, что состояние триггера в момент времени t+1 повторяет значение входного сигнала D(t) в момент времени t (отсюда и название триггера задержки).

Матрица переходов для D-триггера:

Обозначения асинхронного и синхронного D-триггеров:

В синхронном D-триггере при С=0 триггер свое состояние не меняет, а при С=1 работает так же, как и асинхронный, то есть

Q(t+1)=D(t)*C(t) v Q(t)*

Асинхронный D-триггер практического значения не имеет.

Граф D-триггера

2.6 RS-триггер

RS-триггером называют автомат Мура с двумя устойчивыми состояниями, имеющий два входа R и S такие, что при S=1 и R=0 триггер принимает состояния 1, а при R=1 и S=0 состояние 0. В соответствие с состоянием, принимаемым триггером, вход S называет единичным входом, а вход R нулевым.

Матрица переходов RS-триггера:

Комбинация сигналов R=1 и S=1 является запрещенной и поэтому переход в триггере при таких значениях входных сигналов не определен. Переход триггера из 0 в 0 возможен при двух комбинациях входных сигналов: R=0, S=0 и R=1, S=0. Поэтому в первой строке матрицы переходов RS триггера в столбце R поставлена переменная b1, которая может принимать два значения 0 v 1. Аналогично, переход из состояния 1 в 1 также возможен при двух комбинациях входных сигналов: R=0, S=0 и R=0, S=1. Поскольку при таком переходе значения сигнала на входе S безразлично, то в нижней строке матрицы переходов в столбце S записана переменная b2. По матрице переходов можно построить граф RS-триггера.

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

Запишем закон функционирования RS-триггера в аналитическом виде, для чего составим по матрице переходов диаграмму Вейча:

2.7 JK-триггер

JK-триггером называют автомат Мура с двумя устойчивыми состояниями и двумя входами J и K, который при условии J * K = 1 осуществляет инверсию предыдущего состояния (т.е. при J*K=1, Q(t+1) = Q(t)), а в остальных случаях функционируют в соответствии с таблицей истинности RS триггера, при этом вход J эквивалентен входу S, а вход K - входу R. Этот триггер уже не имеет запрещенной комбинации входных сигналов и его таблица истинности, то есть зависимость Q(t+1) = f имеет вид:

Таблица истинности JK-триггера:

По этой таблице можно построить диаграмму Вейча для Q(t+1), которую можно использовать для минимизации, и матрицу переходов:

Матрица переходов JK-триггера:

В интегральной схемотехнике применяются только тактируемые (синхронные) JK триггера, которые при C=0 сохраняют свое состояние, а при C=1 работают как асинхронные JK триггера.

2.8 Универсальный триггер

Триггер JK относится к разряду универсальных триггеров, поскольку на его основе путем несложной внешней коммутации можно построить RS-, D- и T- триггера. RS-триггер получается из триггера JK простым наложением ограничения на комбинацию входных сигналов J=K=1, так как эта комбинация является запрещенной для RS триггера.

Счетный триггер на основе JK триггера получается путем объединения входов J и K.

Триггер задержки (D-триггер) строится путем подключения к входу K инвертора, на который подается тот же сигнал, что и на вход J. В этом случае вход J выполняет функцию входа D, а все устройство в целом реализует таблицу переходов D-триггера .

Заключение

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

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

Список использованных источников

1. Дискретная математика. Учебное пособие. Саяпин А.В., Сливина Т.А. Редакционно-издательский отдел СибГАУ. Красноярск 2010 163с.

2. Лекции по теории цифровых автоматов [Электронный ресурс]. Лекции [Сайт]. URL: http://www.twirpx.com/file/455856/

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

...

Подобные документы

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

    курсовая работа , добавлен 18.10.2015

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

    учебное пособие , добавлен 07.06.2009

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

    контрольная работа , добавлен 04.02.2012

    Теория игр – раздел математики, предметом которого является изучение математических моделей принятия оптимальных решений в условиях конфликта. Итеративный метод Брауна-Робинсона. Монотонный итеративный алгоритм решения матричных игр.

    дипломная работа , добавлен 08.08.2007

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

    реферат , добавлен 13.06.2011

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

    презентация , добавлен 22.10.2013

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

    учебное пособие , добавлен 11.02.2014

    реферат , добавлен 13.01.2011

    Изучение конкретного раздела дискретной математики. Решение 5-ти задач по изученной теме с методическим описанием. Методика составления и реализация в виде программы алгоритма по изученной теме. Порядок разработки программного интерфейса и руководства.

    курсовая работа , добавлен 27.04.2011

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

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

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

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

Терминология

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

  • Слово - строка символов, создаваемая через конкатенацию (соединение).
  • Алфавит - конечный набор различных символов (множество символов)
  • Язык - множество слов, формируемых символами данного алфавита. Может быть конечным или бесконечным.
Автомат Автомат - последовательность (кортеж) из пяти элементов , где: Слово Автомат читает конечную строку символов a 1 ,a 2 ,…., a n , где a i ∈ Σ, и называется словом .Набор всех слов записывается как Σ*. Принимаемое слово Слово w ∈ Σ* принимается автоматом, если q n ∈ F.

Говорят, что язык L читается (принимается) автоматом M, если он состоит из слов w на базе алфавита таких, что если эти слова вводятся в M, по окончанию обработки он приходит в одно из принимающих состояний F:

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

Применение

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

Другое важнейшее применение теории автоматов - математически строгое нахождение разрешимости и сложности задач.

Типовые задачи

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

См. также

Литература

  • Джон Хопкрофт, Раджив Мотвани, Джеффри Ульман Введение в теорию автоматов, языков и вычислений = Introduction to Automata Theory, Languages, and Computation. - М .: Вильямс, 2002. - С. 528. - ISBN 0-201-44124-1
  • Касьянов В. Н. Лекции по теории формальных языков, автоматов и сложности вычислений. - Новосибирск: НГУ, 1995. - C. 112.

Ссылки


Wikimedia Foundation . 2010 .

Смотреть что такое "Теория автоматов" в других словарях:

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

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

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

    Сущ., кол во синонимов: 1 тавт (1) Словарь синонимов ASIS. В.Н. Тришин. 2013 … Словарь синонимов

    теория автоматов - automatų teorija statusas T sritis automatika atitikmenys: angl. automata theory vok. Automatentheorie, f rus. теория автоматов, f pranc. théorie des automates, f … Automatikos terminų žodynas

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

    Теория машин и механизмов (ТММ) это научная дисциплина об общих методах исследования, построения, кинематики и динамики механизмов и машин и о научных основах их проектирования. Содержание 1 История развития дисциплины 2 Основные понятия … Википедия

    ТЕОРИЯ - (1) система научных идей и принципов, обобщающих практический опыт, отражающих объективные природные закономерности и положения, которые образуют (см.) или раздел какой либо науки, а также совокупность правил в области какого либо знания млн.… … Большая политехническая энциклопедия

    Теория алгоритмов Экономико-математический словарь

    Теория алгоритмов - раздел математики, изучающий общие свойства алгоритмов. Проблема построения алгоритма с теми или иными свойствами называется алгоритмической проблемой, ее неразрешимость означает отсутствие соответствующего алгоритма; если… … Экономико-математический словарь

Книги

  • Теория автоматов. Учебник для бакалавриата и магистратуры , Кудрявцев В.Б.. Учебник содержит обширный материал по теории автоматов. В нем вводится понятие автомата, даны теории…

Федеральное агентство по образованию

Государственное образовательное учреждение высшего профессионального образования

«МОСКОВСКИЙ ГОСУДАРСТВЕННЫЙ УНИВЕРСИТЕТ

ПРИБОРОСТРОЕНИЯ И ИНФОРМАТИКИ»

Кафедра ИТ-4 «Персональные компьютеры и сети»

«УТВЕРЖДАЮ»

Заведующий кафедрой ИТ-4

Михайлов Б.М.

«___»__________________2007г.

ЛЕКЦИИ

По дисциплине 1425 «Теория автоматов»

Для студентов 2 курса факультета ИТ

Специальности 230101

«Вычислительные машины, комплексы, системы и сети»

Обсуждены на заседании кафедры

«___»________________2007г.

Протокол № _____

Москва 2007

^ Общие положения

Цели и задачи дисциплины

Целью дисциплины является изложение принципов организации программных и аппаратных средств, в рамках персональных ЭВМ с использованием теории автоматов, овладение навыками разработки программного обеспечения и аппаратных средств ЭВМ.

^ Требования к уровню освоения содержания дисциплины

Знания, приобретенные в результате освоения дисциплины:


  • Принципы и основные понятия теории автоматов;

  • Применение теории автоматов для построения трансляторов алгоритмических языков;

  • Применение теории автоматов при разработке устройств и дискретной аппаратуры в рамках персональных ЭВМ;
Умения и навыки, приобретенные в результате освоения дисциплины:

  • Применение теории автоматов для решения прикладных задач;

  • Проектирование дискретных устройств;

  • Проектирование трансляторов;

Основная литература

1. Савельев А.Я. Основы информатики: учебник для вузов.-М.:Издательство МГТУ им. Н.Баумана,2001.-328с.

2. Карпов Ю.Г.Теория автоматов:СПб.:Питер,2003.-224 с.:ил.

3. Зайцев Е.И. Теория автоматов: Учебное пособие.-М.:МГАПИ,2002.-59с.

Дополнительная литература

1. Хопкрофт Д., Мотвани Р., Введение в теорию автоматов, языков и вычислений: пер с англ.-М.:Издат. Дом Вильямс,2002.-528с.

Лекция №1.

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

Продолжительность: 2 часа (90) минут

1.1. Ключевые (основные) вопросы (моменты)

Место дисциплины «Теория автоматов» в ряду дисциплин, читаемых на кафедре

Объекты Теории автоматов

Задачи Теории автоматов

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

^ ТЕОРИЯ АВТОМАТОВ.

1.2.1. Основные положения теории автоматов. До 20 минут

Автомат (от греческого   - самодействующий) - управляющая система , являющаяся конечным автоматом или некоторой его модификацией, полученной путем изменения его компонент или функционирования. Основное понятие - конечный автомат - возникло в середине 20 века в связи с попытками описать на математическом языке функционирование нервных систем, универсальных вычислительных машин и других реальных автоматов. Характерной особенностью такого описания является дискретность соответствующих математических моделей и конечность областей значений их параметров, что приводит к понятию конечного автомата.

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

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

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

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

^ 1.2.2. Проблемы и задачи, решаемые теорией автоматов. До 30 минут

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

В этой теории достаточно четко выявляются ее направления, обусловленные:


  1. выбором изучаемых типов автоматов (конечные, бесконечные, детерминированные, вероятностные, автономные, комбинационные, без выхода)

  2. принятым уровнем абстракции (абстрактные и структурные автоматы)

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

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

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

Поиск материалов:

Количество Ваших материалов: 0.

Добавьте 1 материал

Свидетельство
о создании электронного портфолио

Добавьте 5 материала

Секретный
подарок

Добавьте 10 материалов

Грамота за
информатизацию образования

Добавьте 12 материалов

Рецензия
на любой материал бесплатно

Добавьте 15 материалов

Видеоуроки
по быстрому созданию эффектных презентаций

Добавьте 17 материалов

На протяжении последних десятилетий велись и ведутся интенсивные работы по созданию
и использованию различных систем и устройств для переработки дискретной
информации. Преобразователи дискретной информации широко используются в качестве
различного рода технических автоматов, вычислительных устройств и их функциональных
блоков, устройств управления роботами, управляющих объектами по заданному
алгоритму. Широкий класс таких преобразователей объединяется под общим названием
­автоматы. Эти устройства имеют конечное число входов, воспринимающих информацию,
и конечное число выходов для выдачи переработанной информации. Зависимость между
входами и выходами задается предписанным алгоритмом переработки информации.
Информация на входе и выходе представляется символами, физическими носителями
которых являются квантованные по времени сигналы.
Если «К» символов одновременно следующих по параллельным входным либо выходным
каналам, рассматривать как один символ из соответствующего алфавита, следующего по
единому "склеенному" каналу, то такой автомат можно представить как устройство с
одним входом и одним выходом (рис. 1).
Рис.1 – Общая функциональная модель преобразователя дискретной информации
Известны два подхода к определению термина автомат. При первом его истолковывают
как устройство, которое без непосредственного участия человека выполняет функции
приема, преобразования и передачи энергии, информации и т.п. в соответствии с
заложенной в него программой, при втором ­ как математическую модель реальных
преобразователей дискретной информации. Функционирование его состоит в том, что
последовательность z1,z2,... символов конечного или в общем случае бесконечного
алфавита Z, поступающая на вход, вызывает на его выходе определенную
последовательность w1,w2,... символов того же или другого алфавита. Таким образом,
самой общей математической моделью преобразователя дискретной информации является
последовательностная функция, отображающая множество Z всех последовательностей
символов алфавита Z в другое множество W* последовательностей символов алфавита W.
Такая интерпретация позволяет схематично представить преобразователь как устройство,
реализующее отображение одного множества на другое (рис. 2а).

Рис.2а – Формальная модель преобразователя
Данное отображение называется алфавитным отображением или алфавитным
оператором.
Теория автоматов ­ это раздел теории управляющих систем, изучающий математические
модели преобразователей дискретной информации, называемые автоматами. С
определенной точки зрения такими преобразователями являются как реальные устройства
(вычислительные машины, живые организмы), так и абстрактные системы
(например, формальная система – это совокупность абстрактных объектов, не связанных
с внешним миром, в котором представлены правила оперирования множеством символов в
строго синтаксической трактовке без учета смыслового содержания, т.е.
семантики; аксиоматические теории, описывающие определенную совокупность явлений
в их причинно­следственной связи друг с другом).
Наиболее тесно теория автоматов связана с теорией алгоритмов. Это объясняется тем,
что автомат преобразует дискретную информацию по шагам в дискретные моменты
времени и формирует результирующую информацию по шагам заданного алгоритма. Эти
преобразования возможны с помощью технических и/или программных средств. Автомат
можно представить как некоторое устройство (чёрный ящик), на которое подаются
входные сигналы и снимаются выходные и которое может иметь некоторые внутренние
состояния. При анализе автоматов изучают их поведение при различных возмущающих
воздействиях и минимизируют число состояний автомата для работы по заданному
алгоритму. Такой автомат называют абстрактным, т.к. абстрагируются от реальных
физических входных и выходных сигналов, рассматривая их просто как буквы некоторого
алфавита и в связи с идеализированным дискретным временем. При синтезе автоматов
(процесс соединения или объединения) формируют систему из элементарных автоматов,
эквивалентную заданному абстрактному автомату. Такой автомат
называется структурным. Особое место в теории автоматов занимает понятие конечного
автомата.
Результат преобразования вход => выход (рис.2а) зачастую зависит не только от входа в
данный момент времени, но и от того, что было раньше на входе, от входной истории, т.е.
от предыстории преобразования. Число возможных входных историй бесконечно (счетно),
даже если различных элементов входной информации у автомата конечное число (как в

конечном функциональном преобразователе). Чтобы эти предыстории как­то запоминать и
отличать друг от друга преобразователь должен иметь память. Для этого в устройство
(рис. 1.1,6) вводится алфавит состояний Q = {qx,q2,...qm).
Понятие состояния q при этом играет очень важную роль. В своих состояниях автомат
запоминает свое концентрированное прошлое. На один и тот же входной сигнал
преобразователь может реагировать по­разному в зависимости от того, в каком состоянии
он находится в данный момент.
Конечный автомат (рис.2б) - математическая абстракция, позволяющая описывать пути
изменения состояния объекта в зависимости от его текущего состояния и входных данных,
при условии, что общее возможное количество состояний Q и множество входных сигналов
Z конечны. Конечный автомат является частным случаем абстрактного автомата.
Рис.2б – Конечный автомат
Конечный автомат является одним из важнейших видов управляющих систем.
Главным достоинством конечных автоматов является то, что в них естественным
образом описываются системы, управляемые внешними событиями.
Теория автоматов занимается изучением процессов, протекающих в автоматах различного
рода, и общих закономерностей, которым они подчинены, широко применяя для этого
алгебраический аппарат, математическую логику, комбинаторный анализ и теорию
вероятностей.
Конструируя надежные, хорошо работающие автоматы, приходится решать необычайно
сложные задачи. Например, надо определять устойчивость систем, чтобы уменьшить
различные отклонения в работе автоматических машин. Надо изучать и чувствительность
автоматов, так как в процессе работы свойства систем регулирования не остаются
постоянными.
Теория автоматов находит применение как в математике, так и в решении практических
задач. Например, средствами теории автоматов доказывается разрешимость некоторых
формальных исчислений. Применение методов и понятий теории автоматов к изучению
формальных и естественных языков привело к возникновению математической
лингвистики (математическая лингвистика ­ математическая дисциплина, предметом
которой является разработка формального аппарата для описания строения естественных
и некоторых искусственных языков.) Понятие автомата может служить модельным

объектом в самых разнообразных задачах, благодаря чему возможно применение теории
автоматов в различных научных и прикладных исследованиях.
Актуальность теории автоматов
Существует множество объектов управления, связанных с большой
ответственностью: ядерные и химические реакторы, комплексы промышленного,
оборонного, космического назначения, горное дело. Успех в работе с ними прямо
зависит от четкости и слаженности действий, от умения принимать выверенные решения и
грамотно анализировать ситуацию, от возможности однозначной интерпретации
информации. Различная природа физических процессов, протекающих в объектах, сложный
характер взаимодействия между ними и управляющими системами обуславливает
трудности разработки, алгоритмизации и программирования задач управления. Возникают
трудности, связанные с необходимостью достижения наглядности и структурированности.
Для решения этих задач используется развитый математический аппарат теории автоматов.
Описание логики поведения (при каких условиях необходимо выполнить те или иные
действия) при автоматном подходе структурировано. Это свойство делает автоматное
описание сложного поведения наглядным и ясным. Корректность работы при
использовании автоматов закладывается еще на этапе проектирования, благодаря
графическому представлению, т.е.
 наглядно представляется поведение управляющих автоматов (графически, таблично)
и композиций из них;
 отображаются желаемые состояния;
 отражается динамика и условия переходов автомата из состояния в состояние;
 можно легко увидеть возможные ошибки в проектировании, такие как отсутствие
некоторого перехода, недоступность состояния и т.д.
Все это приводит к четкому пониманию работы устройства. Процессы управления,
проектирования могут быть представлены в виде элементов с предсказуемым поведением.
Пример: один из крупнейших мировых производителей авиационной, космической и
военной техники – американская корпорация «Боинг» занимается системами стабилизации
самолетов с использованием чистой теории автоматов. Большая часть теории автоматов
была успешно использована в системных программах и текстовых фильтрах в ОС UNIX.
Это позволяет множеству людей работать на высоком уровне и разрабатывать очень
эффективные программы.

Области применения ТА поражают своим размахом и не ограничиваются узкой
направленностью и специализацией. Рассмотрим некоторые из них.
Программирование
Возникает вопрос, почему же конечно­автоматная модель теории автоматов особенно
актуальна сейчас, когда существует огромное количество, как языков
программирования, так и сред для разработки ПО? Имеют место две проблемы:
 непредсказуемое поведение кода программы, разработанной исключительно
средствами RAD (Rapid Application Development – средства быстрой разработки
приложений);
 «угасание» «культуры программирования».
Примеры RAD: Borland Delphi и C++ , обеспечивающие ускоренную разработку
приложений за счет использования объектно­ориентированного и визуального
программирования. Они позволяют не только программировать в привычном смысле слова,
но и фактически рисовать программы (как интерфейс, так и реализацию), используя
визуальные компоненты VCL.
Любой визуальный объект VCL характеризуется рядом свойств, методов и событий.
Казалось бы, простой манипуляцией перечисленными атрибутами возможно заставлять
разрабатываемую программу делать то, что требует от нее программист­разработчик. Но
это далеко не так.
Давно стало ясно, что VCL имеет тенденцию скрывать точную реализацию определенных
объектов, тем самым не давая посторонним менять умалчиваемое поведение кода. Как
показывает практика, поведение кода программы, созданной с помощью средств RAD, не
всегда предсказуемо даже для очень опытного программиста, не говоря уже о начинающем.
Программа, несмотря на «очевидность» авторского кода, всегда стремится пойти своим
путем, попадая в такие замысловатые обработчики событий, о существовании которых
можно даже и не догадываться.
В современном мире объемы и сложность разрабатываемых приложений возрастают с
каждым днем, поэтому такой подход резко увеличивает время тестирования и отладки ПО.
Управлять поведением кода дает возможность механизм теории автоматов еще
сорокалетней давности.
Стили программирования различаются по базовым понятиям, в качестве которых
используются такие понятия как «событие», «подпрограмма», «функция», «класс»

(«объект») и т. д. Стиль программирования, основанный на явном выделении состояний
и применении автоматов для описания поведения программ, назван «автоматное
программирование», а соответствующий стиль проектирования программ -
«автоматное проектирование». Автоматное программирование можно рассматривать не
только как самостоятельный стиль программирования, но и как дополнение к другим
стилям, например, к объектно­ориентированному, т.к. речь идет не только и не столько об
использовании конечных автоматов в программировании, сколько о методе создания
программ в целом, поведение которых описывается автоматами. Т.е. как отдельный
компонент, так и программа в целом может быть реализована как автомат.
В автоматном программировании существует два направления: SWITH­технология и
КА (конечно­автоматная) технология. Switch­технология - технология разработки систем
логического управления на базе конечных автоматов, охватывающая процесс
проектирования, реализации, отладки, верификации (проверки), документирования и
сопровождения.
Кодирование/программирование автоматов в рамках КА­технологии основано на
следующих принципах:
 введено понятие динамичного объекта, который может быть наделен алгоритмом
поведения во времени;
 алгоритм поведения объекта задается моделью конечного автомата;
 язык описания автомата основан на базе табличной формы представления автоматов;
 логика поведения объекта (таблица переходов автомата) отделена от методов
автоматного объекта (предикатов и действий), связанных с реализацией его
поведения во времени;
 любые динамичные объекты могут выполняться параллельно.
Рассмотрим эти технологии подробнее:
1) SWITH­технология. Основные положения: предлагается сделать понятие «состояние»
первичным, а алгоритмы представлять в виде графов переходов (диаграмм состояний), т.е.
представлять программу как систему взаимодействующих конечных автоматов,
описываемых графами переходов. Состояния кодируются для того, чтобы их различать.
Графы в наглядной для человека форме отражают переходы между состояниями, а также
«привязку» выходных воздействий и других автоматов к состояниям и/или переходам.
Внутри программы автоматы могут взаимодействовать:

 по вложенности (один автомат вложен в одно или несколько состояний другого
автомата)
 по вызываемости (один автомат вызывается с определенным событием из выходного
воздействия, формируемого при переходе другого автомата)
 обмену сообщениями (один автомат получает сообщения от другого)
 по номерам состояний (один автомат проверяет, в каком состоянии находится
другой автомат).
Ни число автоматов, вложенных в состояние, ни глубина вложенности не ограничены.
Основной критерий оптимальности реализации управляющих автоматов – возможность
преобразования графа переходов в программный код. <><><>Известно большое число
инструментальных средств для генерации программ, реализующих графы переходов:
 Visio2Switch ­ инструментальное средство Visio2Switch позволяет по графу
переходов, построенному с помощью редактора Microsoft Visio, автоматически
реализовать его в виде изоморфной программы на языке С. Конвертор Visio2Switch
используется в настоящее время при создании программного обеспечения ряда
ответственных систем реального времени.
 MetaAuto ­ инструментальное средство MetaAuto позволяет по графу переходов,
построенному с помощью того же редактора, автоматически реализовать его в виде
изоморфной программы на любом языке программирования, для которого
предварительно построен шаблон (C, C# , Turbo Assembler и т.д.).
 UniMod ­ инструментальное средство UniMod предназначено для поддержки
автоматного программирования и построения и реализации не только автоматов, но и
программ в целом.
Практика показала, что для многих классов программ только 20–30% программного
кода строится вручную.
На основе SWITCH­технологии уже разработаны приложения для: устройства продажи
газированной воды, банкомата (см. пример 1), светофора, системы управления
пассажирским лифтом, система управления автомобильной сигнализации (см. пример 2),
автоматизированной системы оплаты мобильного телефона, устройства обмены валюты,
устройства для продажи проездных билетов и т.д.
2) КА­технология позволяет реализовать идею параллелизма. Технологии разработки
программ “сверху вниз”, “снизу вверх”, структурный подход таких возможностей или не

имеют, или они ограничены. Даже в технологии объектно­ориентированного
программирования (ООП) вопросы параллельной работы объектов вынесены за ее рамки.
Использование других технологий, базирующихся на известных параллельных моделях,
сопряжено с трудностями, связанными если не с ограничениями области их применения, то
с проблемами последующей реализации на программном и/или аппаратном уровнях.
Параллельные модели ­ одно из основных и перспективных направлений в области развития
программирования и аппаратных средств. Идея параллелизма весьма привлекательна. Но
для ее использования необходимо, во­первых, решить проблему описания, т.е. выбора
формальной параллельной модели, и, во­вторых, проблему реализации модели. КА­
технология использует модель со средствами представления и описания параллелизма,
которые по своим возможностям не уступают другим параллельным моделям, а ее
реализация во многом проще. Кроме того, применяя стандартные приемы, несложно
перейти от параллельного конечно­автоматного представления к последовательному
описанию.
Примеры применения КА­технологии: бухгалтерские программы типа расчета
заработной платы или учета квартирной платы, проект системы управления
технологическим процессом выращивания кристаллов с множеством динамически
порождаемых параллельно функционирующих объектов реализующих процессы съема
данных с датчиков, выдачу управляющих воздействий на объект, автоматные алгоритмы
работы драйверов с разнообразной аппаратурой, процессы отображения и расчета.
3) Основное отличие рассматриваемых технологий заключается в реализации логики
автоматных программ. В SWITCH­технологии она реализуется переводом автоматного
описания в программный код языка программирования, в КА­технологии реализуется
прямое исполнение автоматов путем интерпретации его исходного табличного
представления. Это более короткий и наглядный путь реализации автоматов, хотя и более
медленный, если рассматривать уровень отдельного компонентного автомата сети
автоматов.
Вывод: Автоматное программирование используется в настоящее время при
проектировании программного обеспечения систем автоматизации ответственных объектов
управления (автомат управления криогенно­вакуумной установкой, дизель­генератором).
Конечный автомат работает по принципу «шаг в сторону – недопустимо». Реализовать
непредусмотренные действия конечный автомат не даст ни пользователю (исходный
вариант кода), ни самой программе (модифицированный вариант кода).

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

обучению. Использование автоматов при создании искусственных нейронных сетей
позволяет исключить появление непредусмотренных состояний в работе.
Нейронные технологии особенно интенсивно применяются в экспертных системах
прогнозирования месторождений и финансовом деле при оценке инвестиций.
Пример: В жидкостных ракетных двигателях (ЖРД), представляющих собой сложную
техническую систему, состоящую из множества агрегатов, взаимодействующих между
собой, необходима быстрая реакция контролирующей системы на процессы, происходящие
в одном из самых ответственных и напряженных агрегатов – турбонасосном агрегате
(ТНА). При использовании нейронных сетей и автоматов появляется возможность
раннего диагностирования аварийных ситуаций, что позволяет снизить последствия аварии
и предотвратить разрушение двигателя при проведении огневых испытаний (см. пример 3).
При функционировании ТНА представляется в виде конечного автомата. Состояния, в
которых он может находиться: Ожидание, Запуск, Основной режим, Останов, Аварийное
состояние (разделяется на ряд состояний, классифицирующих характер отказа).
Значение предельного отклонения подбирается с таким расчетом, чтобы быть
минимальным и в то же время допускать небольшие вариации. В случае отказа (выход
любой из четырех сетей равен единице) активируются нейронные сети, обученные на
характерных для ТНА отказах, по показаниям которых можно определить, что послужило
причиной отказа (выход сети равен единице). Если этого сделать не удается (несколько
выходов сетей равны единице), то считается что отказ комбинированный – одновременно
произошло несколько отказов, а в случае неопределенности (все выходы сетей равны
нулю), автомат переходит в состояние Новый отказ.
Разработанная методика позволяет обнаруживать отказы турбонасосного агрегата. Т.к.
данное устройство является очень сложным, то после наступления аварийной ситуации
проблематично определить вид поломки, в каком состоянии работы на данный момент
находится агрегат и как его снова перевести в рабочее состояние. Нейронная сеть
позволяет либо предупредить аварию, либо фиксирует время, когда произошел отказ и
определяет вид отказа. Применение SWITCH­технологии при разработке управляющего
ПО позволяет получить полный протокол работы диагностирующего автомата – в любой
момент времени его работы можно узнать в каком состоянии автомат находится, и в какое
состояние его можно перевести.
Создание прикладного ПО для мобильных устройств и микроконтроллеров

При построении серверных приложений, отвечающих на запросы, большую роль играет
«отсутствие состояния» - нет нужды сохранять состояния между двумя
последовательными запросами.
При построении удачного интерактивного приложения управляемого событиями, многое
зависит от того, продумана ли модель управления состояниями.
Конечный автомат - весьма удобная концепция, которую целесообразно использовать для
структурирования приложений.
Поскольку мобильные приложения должны использовать пространство экрана и системные
ресурсы эффективно, конечные автоматы оказываются особенно полезными при
разработке ПО для таких приложений.
Программа представляет собой совокупность конечных автоматов, взаимодействующих
друг с другом и с «внешним миром». Диаграмма переходов КА описывает переходы между
экранными формами, дуги переходов из состояния в состояние описывают действия
пользователя. С каждой из конструируемых форм должен связываться конечный автомат,
управляющий визуальным поведением формы. Если в самой форме содержится несколько
страниц, например, диалоговые окна с вкладками, то предусматривается для каждой из
подстраниц собственный конечный автомат.
Конечные автоматы значительно расширяют возможности управления выполнением
фоновых задач. Их использование делает возможным предоставление фоновыми потоками
информации о состоянии выполнения, а также обращение других потоков с запросами к
фоновому потоку на выполнение определенных действий, например, с запросом на
прекращение выполнения фоновой работы. При этом в наглядной графической форме
могут быть выражены как связи между автоматами, так и их внутренняя
структура. Главное преимущество: возможность повторного использования кода, быстрая
модификация, наглядность, что важно в случае приложений для мобильных устройств,
требующих экономного расходования экранного пространства, памяти, вычислительной
мощности и других ресурсов.
Построение моделей документооборота на основе конечно­автоматной модели теории
автоматов
В современном обществе идет процесс интенсификации вычислительных и
информационных технологий во всех отраслях деятельности.
Документооборот - движение документов в организации с момента их создания или
получения до завершения исполнения: отправки и/или направления в дело. Внедрение

электронного документооборота является актуальной задачей современного общества, т.к.
он позволяет сделать процесс движения документов управляемым и контролируемым, что
обеспечивает более качественные услуги управления. Предприятия и организации для
решения этой задачи тратят значительные средства и время. В тоже время, каждая
разработка системы документооборота является уникальной и возможность повторного
использования полученного опыта в полном объеме практически отсутствует. Правильная
организация данного процесса определяет качество и стабильность работы любого
предприятия.
Использование автоматной модели в разработке спецификаций документооборота и
программного продукта позволяет создавать системы более адекватные требованиям
пользователей и обеспечивает возможность достижения совместимости приложений.
Теория автоматов позволяет реализовать логику ветвления движения документов между
участниками процессов документооборота. Автомат позволяет установить реакцию
элементов системы документооборота на изменения в системе.
В качестве моделируемого объекта рассматривается так называемый композитный
документооборот, то есть такой документооборот, в котором участвуют, как электронные,
так и бумажные представления документов. Композитный документооборот
представляется тройкой: Дт = {У, Д, Ф}, где
 Дт – формальная модель документооборота;
 У – множество участников;
 Д – множество действий;
 Ф – множество состояний документов.
Множество состояний документов S получается путем анализа жизненного цикла
документа. Это множество всех состояний, которые могут быть приняты документом в
пределах моделируемого документооборота, где каждое значение уникально: {S}={Ф}.
Под начальным состоянием подразумевают первоначальное состояние, в которое поступает
документ после инициализации процесса. При представлении документооборота в виде
совокупности процессов, начальное состояние представляет первый шаг, после которого
можно говорить о том, что документ существует и процесс активизирован. Таким образом,
начальные состояния – это объекты, элементы множества Ф, которые имеют одну или
несколько исходящих связей и ни одной входящей.

Документооборот состоит из совокупности процессов, каждый из которых обрабатывает
один или несколько документов. Жизненный цикл процесса документооборота
определяется движением документов от начальных состояний к завершающим состояниям.
В рассматриваемой модели завершающие состояния автомата определяются, как состояния
документа, после возникновения которых работа автомата останавливается, то есть
процесс документооборота перестает существовать. Таким образом, завершающие
состояния можно определить как объекты множества Ф, которые имеют одну или
несколько входящих связей и ни одной исходящей.
В документообороте документ принимает следующее состояние в зависимости от
результата действия, которое над ним произвели. Функцию перехода автоматной
модели документооборота можно определить как i­й элемент множества действий {Д}
документооборота, после выполнения которого, происходит смена состояния на
состояние. {F}={Д}
Алфавит автомата – это множество символов, наборы которого поступают или могут
поступить автомату. В качестве алфавита автомата следует рассматривать список
участников.
Можно однозначно определить автомат, который будет адекватно реализовывать модель
документооборота. Модель, построенная на детерминированных автоматах, позволяют
строить модели, которые легче воспринимаются визуально. Для них проще построить
программную реализацию. В то же время, при создании моделей процессов, имеющих
сложную ветвящуюся структуру, автоматная модель на детерминированных автоматах
получается большой и громоздкой.
Недетерминированные автоматы позволяют задавать сложные процессы, используя
меньшее количество описательного материала. Однако, для наглядного восприятия они
намного сложнее.
Вывод: при небольших слаборазветвленных процессах лучше использовать
детерминированные автоматы, в то время, как недетерминированные более удобны при
задании процессов с большим количеством шагов и ветвлений.
После разработки теоретической базы реализуется программное обеспечение,
применяющее на практике автоматную и графовую модели документооборота. Каждый из
участников имеет возможность получать доступ к конкретным видам документов и
выполнять над ними строго определенные действия.

Реализация систем композитного документооборота позволяет сделать делопроизводство
более прозрачным и прогнозированным, уменьшает личностное влияние исполняющего
персонала на конечный результат.
Рассмотренная отрасль в настоящее время быстро развивается. Проводятся дальнейшие
исследования в данном направлении, особенно это касается применения КС­грамматик и
создания программного обеспечения, реализующих описанную автоматную модель
композитного документооборота в полном объеме.
Поиск цепочек в тексте
Согласно данным официальной статистики, около 85 % пользователей Интернет постоянно
обращаются к поисковым системам
(Google, Yandex, Rambler, Yahoo!, Апорт, Поиск@Mail.ru и др.) с целью найти
необходимую им информацию о товарах или услугах.
Положения теории автоматов прекрасно подходят для описания таких реальных
задач, возникающих в приложениях, как поиск в сети Internet и извлечение
информации из текста. Многие современные поисковые системы Интернета используют
специальную программу – поисковый робот, который является автоматом.
В век Internet и электронных библиотек с непрерывным доступом обычной является
следующая проблема. Задано некоторое множество слов, и требуется найти все
докумен¬ты, в которых содержится одно (или все) из них. Популярным примером такого
процесса служит работа поисковой машины, которая использует специальную технологию
поиска, называемую обращенными индексами (inverted indexes). Для каждого слова,
встречающегося в Internet (а их около 100,000,000), хранится список адресов всех мест, где
оно встречается. Машины с очень большим объемом оперативной памяти обеспечивают
постоянный доступ к наиболее востребованным из этих списков, позволяя многим людям
одновременно осуществлять поиск документов.
В методе обращенных индексов конечные автоматы не используются, но этот метод
требует значительных затрат времени для копирования содержимого сети и переписывания
индексов. Существует множество смежных приложений, в которых применить технику
обращенных индексов нельзя, зато можно с успехом использовать методы на основе
автоматов. Те приложения, для которых подходит технология поиска на основе автоматов,
имеют следующие отличительные особенности:
1. Содержимое хранилища текста, в котором производится поиск, быстро
меняется.

Вот два примера:
o каждый день аналитики ищут статьи со свежими новостями по
соответствующим темам. К примеру, финансовый аналитик может искать
статьи с определенными аббревиатурами ценных бумаг или названиями
компаний;
o "робот­закупщик" по требованию клиента отслеживает текущие цены по
определенным наименованиям товаров. Он извлекает из сети страницы,
содержащие каталоги, а затем просматривает эти страницы в поисках
информации о ценах по конкретному наименованию.
2. Документы, поиск которых осуществляется, не могут быть каталогизированы.
Например, очень непросто отыскать в сети все страницы, содержащие информацию обо
всех книгах, которые продает компания Amazon.com, поскольку эти страницы
генерируются как бы "на ходу" в ответ на запрос. Однако мы можем отправить запрос на
книги по определенной теме, скажем, "конечные автоматы", а затем искать в той части
текста, которая содержится на появившихся страницах, определенное слово, например
слово "прекрасно".
Моделирование работы банкомата
Банкомат ­ это автоматизированное устройство, позоляющее удаленно осуществлять
операции, связанные с аутентификацией пользователя (держателя счета в банке),
просмотром текущего состояния счета, снятием денег со счета и осуществлением
различных платежей. В данном примере рассматривается работа банкомата, включая не
только клиентскую часть, но и серверную часть, обрабатывающую запросы, а также
подсистему авторизации.
Основная задача при реализации таких систем ­ гарантия высокого уровня надежности
клиентов­пользователей банка и информационной системы банка.

Несмотря на отсутствие связи между автоматами, AServer вложен в AClient. При
нахождении автомата AClient в состояниях «Авторизация», «Запрос баланса» и
«Запрос денег» программно управление передается автомату AServer , который
отправляет запрос на сервер, получает ответ и возвращает управление автомату

AClient. Сам сервер спроектирован традиционным путем и реализован как
консольное приложение.
Интерфейс программы:
Пример показывает, что инструментальное средство UniMod позволяет упростить процесс
создания программы, по сравнению с традиционным подходом. При этом большая часть
времени разработчика уходит на проектирование системы. Ввиду того, что основная часть
кода генерируется автоматически, повышается надежность программы.
Система управления автомобильной сигнализациейфары, сирена и светодиод – как объекты управления. Использование сложного состояния
«2. Включена» (содержит 3 состояния) обеспечивает возможность выключения
сигнализации в каком бы состоянии не находился автомат.
Генераторы событий системы
Генератор событий p1. Этот объект описывает события, производимые пультом
управления сигнализацией. События:
 e11 – нажатие кнопки «1»;
 e12 – нажатие кнопки «2»;
 e13 – нажатие кнопки «3».
Генератор событий p2. Этот объект соответствует датчику удара. Он может выдавать два
события:
 e21 – фиксирование слабого удара;
 e22 – фиксирование сильного удара.
Генератор событий p3. Этот объект запускает один из трех таймеров. Когда отсчет
завершается, он генерирует соответствующее событие. Таймер запускается по запросу
объекта управления «o2» с указанием номера и требуемого времени.
 e31 – таймер «1» завершил отсчет (таймер для отсчета времени в состоянии «3.
Тревога» автомата А1);

 e32 – таймер «2» завершил отсчет (таймер для отсчета времени в состоянии «2.
Состояние опасности» автомата А1);
 e33 – таймер «3» завершил отсчет (таймер для управления выключением звука).
Объекты управления системы
Объект управления o1. Этот объект описывает действия, совершаемые фарами
автомобиля.
 z1 – мигнуть один раз;
 z2 – мигнуть два раза;
 z3 – мигнуть три раза;

 z5 – прервать любые действия.
Объект управления o2. Этот объект используется для запуска таймера «p3».
 z1 – запустить таймер «1» на 15 с;
 z2 – запустить таймер «2» на 5 с;
 z3 – запустить таймер «3» на 3 с;
z4 – остановить все таймеры.
Объект управления o3. Данный объект управления отражает работу сирены. Его
выходные воздействия практически совпадают с выходными воздействиями фар.
 x1 – логическая переменная, показывающая включен звук (то есть может подавать
сигналы) или нет;
 z1 – генерация звука, соответствующего постановке автомобиля на сигнализацию;
 z2 – генерация звука, соответствующего снятию автомобиля с сигнализации;
 z3 – генерация звука, соответствующего реакции на слабый удар;
 z4 – начать подавать тревожный сигнал;
 z5 – прервать звук;
 z6 – включить звук (разрешить подавать сигналы);

 z7 – выключить звук (запретить подавать сигналы).
Объект управления o4. Этот объект управления описывает работу светодиода,
расположенного в машине. Он показывает текущее состояние сигнализации.
 z1 – начать мигание;
 z2 – завершить мигание.
Объект управления o5. Данный объект управления используется для вывода



Популярное в рубрике:
Сонник туши свиней. Разделывать свинью. Малый Велесов сонник
Сонник туши свиней. Разделывать свинью. Малый Велесов сонник
читать
Традиционные блюда в стране
Традиционные блюда в стране
читать
Грушевый компот рецепт. Компот из груш на зиму. Как быстро приготовить компот из груши на зиму
Грушевый компот рецепт. Компот из груш на зиму. Как быстро...
читать
Арктур — самая яркая звезда в Северном полушарии (видео) В каком созвездии звезда арктур
Арктур — самая яркая звезда в Северном полушарии (видео) В каком...
читать

Последние Статьи
Как выглядит большая медведица созвездие на фото
читать
Женале - инструкция по применению...
читать
Как гормональный контрацептив джес влияет на...
читать
В какие часы и по каким дням введен запрет на...
читать
Льготы почетным работникам общего образования...
читать
Дрожжевое пышное тесто для пиццы рецепт с фото...
читать
Кисель из семян льна для похудения
читать
Омлет с цветной капустой в духовке
читать
Top