Лекции. Тестирование ПО (all in one) (1186159), страница 18

Просмтор этого файла доступен только зарегистрированным пользователям. Но у нас супер быстрая регистрация: достаточно только электронной почты!

Текст из файла (страница 18)

Каждый переход — четверка (s1, i, o, s2)— имеет начальное состояние s1, конечное состояние s2, стимул i и реакцию o. Говорят, чтоон выходит из s1 и ведет в s2, помечен стимулом i и реакцией o. Этот переход изображаютстрелкой, ведущей из s1 и в s2 и помеченной i/o.Автомат работает следующим образом. В начале он считается находящимся в начальномсостоянии.

На вход он получает извне некоторую последовательность стимулов. Приполучении очередного стимула в некотором состоянии недетерминированным образомвыбирается один из переходов, помеченных принятым стимулом и выходящих из текущегосостояния. Очередным текущим состоянием автомата становится конечное состояниевыбранного перехода, и наружу выдается реакция, которой помечен выбранный переход.Выполнение автомата не определено, если в текущем состоянии нет переходов, помеченныхполучаемым стимулом.Таким образом, автомат реализует некоторое соответствие последовательностейсимволов из I и последовательностей символов из O, φ ⊆ I*×O*. Это соответствие, однако,описывается не прямо, а через возможные сценарии работы автомата.

Часто его называютповедением автомата и рассматривают автомат как способ реализации этого соответствия.a/y0b/xa/x1b/zb/ya/z2b/x3a/yНа рисунке выше изображен конечный автомат с множеством состояний {0,1,2,3},множеством стимулов {a,b}, множеством реакций {x,y,z} и множеством переходов{<0,a,x,1>, <0,b,x,2>, <1,a,y,0>, <1,b,z,2>, <2,a,z,0>, <2,b,x,3>, <3,a,y,3>, <3,b,y,1>}.Реализуемое им соответствие φ является отображением всех возможных конечныхпоследовательностей {a,b}* в конечные последовательности {x,y,z}*. Например, φ(aaaaaa) =xyxyxy, φ(abaabaaba) = xzzxzzxzz, φ(bbbbbb) = xxyzxy.Обобщением конечных автоматов являются необязательно конечные автоматы, в которыхмножества состояний, стимулов и реакций уже не всегда являются конечными.Другое обобщение — системы размеченных переходов или просто системы переходов(Labeled Transition Systems, LTS).

В обычных системах переходов не различают стимулы иреакции, называя их просто действиями. Ниже определяется система переходов состимулами и реакциями (Input Output Labeled Transition System, IOLTS) — такие системыболее естественно моделируют По с точки зрения тестирования, при котором всегда естьвоздействия на систему и есть выдаваемые ей реакции на эти воздействия.Конечная система переходов со стимулами и реакциями — набор (S, s0, I, O, τ, T), гдеS — конечное множество состояний системы;s0 — элемент S, называемый начальным состоянием;I — конечное множество входных символов, входов или стимулом, I называют входнымалфавитом системы;O — конечное множество выходных символов, выходов или реакций, O называютвыходным алфавитом системы; I и O не пересекаются;τ — некоторый символ, не являющийся элементом I и O, он называется пустым иливнутренним действием;T ⊆ S×(I∪O∪{τ})×S — множество переходов системы. Каждый переход — тройка (s1, a,s2) — выходит из s1, ведет в s2, и помечен действием a, которое может быть стимулом,реакцией или внутренним действием.

Этот переход изображают стрелкой, ведущей из s1 и вs2 и помеченной a. При этом, чтобы отличить стимулы от реакций, первые обычноизображают с вопросительным знаком, а вторые — с восклицательным: ?a, ?b, !x, !y.Для систем переходов тоже определено выполнение. Сначала система находится вначальном состоянии. На вход она получает извне некоторую последовательность стимулов.При получении очередного стимула в некотором состоянии недетерминированным образомвыбирается один из следующих вариантов.•Система может выполнить переход, помеченный принятым стимулом и выходящийиз текущего состояния. При этом принятый стимул выбирается из входнойпоследовательности, и очередным стимулом становится следующий за ним.•Система может выполнить переход, помеченный реакцией. При этом эта реакциявыдается вовне.•Система может выполнить переход, помеченный внутренним действием.

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

Нарисунке ниже показана конечная система переходов, реализующая то же поведение, что ипредставленный слева автомат.0b/xa/x10b/z!zb/ya/z2b/x3a/y6!ya/y8?a?b5!z!x?a!x4?b1711!y!y?b?a2?b9!x310?aВообще верно, что любое поведение конечного автомата может быть реализованоконечной системой переходов с теми же входным и выходным алфавитами, а обратное —неверно. Некоторые конечные системы переходов не имеют конечных автоматов с таким жеповедением.Так же, как и автоматы, системы переходов могут быть бесконечными — с бесконечныммножеством состояний или алфавитами.Другие обобщения автоматов связаны с введением дополнительных структур, например,выделением части информации о состоянии в отдельные переменные, а также введениемпараметров стимулов и реакций.

При этом получаются расширенные автоматы.Расширенный конечный автомат — набор (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).Поведение автомата можно определить не только для конечных, но и для бесконечныхвходных последовательностей.

Характеристики

Список файлов лекций