лекции, страница 15

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

При этом получаются расширенные автоматы.Расширенный конечный автомат — набор (S, V, P, s0, P0, I, nI, X, O, nO, Y, T), гдеS — конечное множество управляющий состояний автомата;V — множество, возможно бесконечное, значений внутренних данных автомата;P — отображение конечного набора [1..n] индексов в V, P:[1..n] → V; значение P наиндексе I называется значением i-й переменной автомата, которое также обозначается pi.s0 — элемент S, называемый начальным состоянием;P0 — отображение [1..n] индексов в V, называемое начальными значениями переменных;I — конечное множество, элементы которого называются операциями или стимулами,само I называют входным алфавитом автомата;nI — отображение I в неотрицательные числа, определяет число параметров для каждогостимула;X — множество, возможно бесконечное, значений параметров стимулов;O — конечное множество, элементы которого называются реакциями, само O называютвыходным алфавитом автомата;nO — отображение O в неотрицательные числа, определяет число параметров или данныхкаждой реакции;Y — множество, возможно бесконечное, значений данных реакций;T — множество переходов автомата; каждый переход t включает начальное управляющеесостояние s1, стимул i, охранное условие или условие перехода gt (guard condition) —предикат на множестве Vn×XnI, реакцию o, отображение параметров реакции Vn×XnI вмножество YnO, определяющее правила вычисления данных реакции по текущим значениямпеременных и параметрам стимула, конечное управляющее состояние s2, и действие at —некоторое отображение Vn×XnI в множество Vn, определяющее новые значения переменных.Выполнение расширенного автомата отличается от выполнения обычного тем, чтопомимо текущего состояния имеются текущие значения переменных, при приходе стимула снабором аргументов охранное условие определяет, может ли быть выполнен данный переходпри текущем наборе значений переменных и заданных значениях параметров стимула.Выполняемый переход выбирается недетерминировано из всех, помеченных даннымстимулом, начинающихся в данном управляющем состоянии и имеющих выполненноеохранное условие.

При выполнении некоторого перехода новое управляющее состояниеавтомата равно конечному управляющему состоянию перехода, новые значения переменныхопределяются при помощи его действия — новое pi = at(p1,…, pn, x1,…, xnI), значенияпараметров реакции — по соответствующему отображению в переходе.int x — переменнаяa[x >= 0] / x++01b[x == 1] / x--a[x > 0] / x++b[x > 1] / x--Другое обобщение конечных автоматов — взаимодействующие автоматы.Система взаимодействующих автоматов определяется как конечное множествоавтоматов, некоторые из которых связаны направленными каналами передачи данных — укаждого канала есть автомат-приемник и автомат-передатчик.

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

Это полезно для возможности определитьпереход по одному и тому же стимулу из целого множества состояний в одно.Иерархический автомат может быть преобразован в конечный при помощи процедурыуплощения — состояниями конечного автомата объявляются цепочки состоянийиерархического, в которых каждое следующее состояние является под-состояниемпредыдущего, а у последнего состояния нет под-состояний.Иерархические расширенные автоматы с дополнительной возможностью определенияпараллельных под-состояний — это диаграммы переходов (Statecharts) в рамках UML.Помимо переменных, в автомат можно добавить таймеры — это специальныепеременные, которые автономно изменяют свое значение в соответствии с ходом времени.Расширенные автоматы с таймерами называются временными (Timed Automata).Поведение автомата можно определить не только для конечных, но и для бесконечныхвходных последовательностей.

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

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

в курсах по базам данных).•Абстрактные типы данных (пример приведен в Лекции 3 — там описан абстрактныйтип индексированного списка)•Разнообразные алгебры процессов.•Машины с абстрактным состоянием (Abstract State Machines, ASM, см. ниже).Основные виды логических моделей такие.•Исчисления высказываний и предикатов, первого и высших порядков.•λ-исчисление первого и высших порядков.•Временные логики, использующие операторы «раньше», «позже», «когда-нибудь вбудущем» и пр.•µ-исчисление, являющееся расширением временных логик.•Логики явного времени, где вместо соотношений между порядком событий типа«позже»-«раньше»-«между» явно указывается время или временные интервалы,когда они имели место.Промежуточные моделиПромежуточные модели либо определяются как исполнимые, но могут быть легкоинтерпретированы как логико-алгебраические или наоборот, либо сочетают в себе чертыобоих основных классов моделей.Например, алгебры процессов представляют собой алгебраические исчисления, в которыхпроцессы представлены термами, строящимися по определенным правилам.

В то же времяестественная интерпретация алгебр процессов дается системами размеченных переходов, ичасто между системами переходов и представляемыми ими процессами не делаетсяразличий.Пример второго рода — машины с абстрактным состоянием (ASM). В качествесостояний такой машины рассматриваются различные универсальные алгебры с одной и тойже сигнатурой (называемой сигнатурой машины), включающей константы true, false, undef.Переходы составляются из конечного набора элементарных действий нескольких типов.•Смена значения операции из сигнатуры символа на некотором наборе аргументовf(a1, …, an) := <выражение, составленное из операций сигнатуры>•Условное выполнение определенных действийif(<условие>) <действия>•Параллельное выполнение некоторых действий для всех объектов, обладающихнекоторым свойствомforall x : P(x) do <действия, зависящие от x>Приведем простой пример описания стека с помощью ASM.•Сигнатура.o size : int — размер стека;o elements(int) : object — содержимое стека;o top : object — элемент в вершине стека;o input : {pop, push}×object — выполняемая операция.•Начальное состояние.size = 0; ∀i elements(i) = undef; top = undef;•Описание.if(π1(input) = push){ size := size + 1; elements(size+1) := π2(input); top := π2(input); }if(π1(input) = pop){ size := size - 1; elements(size) := undef; top := elements(size-1); }Еще один вид промежуточных моделей, использующий элементы исполнимых моделей илогических — программные контракты (software contracts).Программный контракт описывает некоторый компонент с определенным интерфейсом.Интерфейс представляет собой конечное множество операций.

Каждая операция имеет имя инабор параметров определенных типов.Программный контракт компонента состоит из следующих элементов.•Описание структуры данных внутреннего состояния компонента.Это описание включает определение элементов данных и их типов, а такжеинварианты.Каждый инвариант — это предикат, зависящий от описанных элементов данных.Если такой предикат выполнен, данные состояния компонента корректны. Иначе —нарушены их ограничения целостности и пользоваться таким компонентом нельзя.•Описание структур данных всех используемых типов.Для каждого типа также определяются элементы данных, их типы и инвариантыданного типа.Описание контракта для каждой операции.o Предусловие.Предусловие определяет ситуации, в которых операцию можно вызывать.Оно представляет собой предикат, зависящий от внутреннего состояниякомпонента и аргументов операции.o Постусловие.Постусловие описывает требования к корректным результатам работыоперации.

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