Спецификация и тестирование систем с асинхронным интерфейсом

       

Взаимодействующие автоматы


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

Взаимодействующим автоматом будем называть шестерку ( S, s0, X, Y, E, Q ), где

  • S - множество состояний,
  • s0
    S - начальное состояние,
  • X - множество стимулов,
  • Y - множество реакций,
  • E
    S x ( X
    Y
    {τ} ) x S - множество переходов, которые мы будем называть

    • посылающими, если второй элемент перехода является стимулом,
    • принимающими, если второй элемент перехода является реакцией,
    • внутренним, если второй элемент перехода является τ;

  • Q
    S - множество заключительных состояний.

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

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

Заметим, что множества стимулов и реакций могут пересекаться (X

Y ≠ Ø), и поэтому в определении множества переходов используется операция дизъюнктивного объединения. Для обозначения того факта, что сообщение является стимулом мы будем использовать символ !, помещаемый следом за элементом множества X (например, x!), а для обозначения принадлежности сообщения к множеству реакций будет использоваться символ ?: (например, y?).

Конечная последовательность переходов ( e1, e2, …, en ) взаимодействующего автомата A = ( S, s0, X, Y, E, Q ) называется путем, если для каждого i = 1, …, n-1 постсостояние перехода ei совпадает с пресостоянием перехода ei+1. При этом мы будем говорить, что путь ведет из пресостояния перехода e1 в постсостояние перехода en.

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

Путь ( e1, e2, …, en ) взаимодействующего автомата A = ( S, s0, X, Y, E, Q ) называется функционированием, если пресостоянием перехода e1 является начальное состояние s0, а постсостояние перехода en принадлежит множеству конечных состояний Q.


Предположим, что взаимодействующий автомат A = ( S, s0, X, Y, E, Q ) входит в состав распределенного взаимодействующего автоматов DA. Переходы автомата A ( s1, m, s2 )
E будем называть внутренними для DA, если сообщение m сокрыто в одной из систем взаимодействующих автоматов, входящей в состав DA. В противном случае, переходы будем называть внешними для DA.

Функционированием распределенного взаимодействующего автомата DA называется тройка ( E,
, μ ), где


  • E - набор функционирований { ( ei,1, ei,2, …, ei,n(i) ) } всех взаимодействующих автоматов, входящих в DA;
  • - частичный порядок на множестве всех переходов { ei,j }i, j=1,…,n(i) набора E;
  • μ : { ei,j }
    { ei,j } - отображение на этом же множестве переходов;


при условии, что E,
и μ удовлетворяют следующим ограничениям:


  • областью определения μ является множество всех принимающих переходов ei,j = ( s1, m?, s2 ) автомата A, сообщение m которых сокрыто в некоторой системе взаимодействующих автоматов SA, входящей в состав DA;
  • для каждого такого перехода ei,j = ( s1, m?, s2 ) значением μ(ei,j) является посылающий переход ei',j' = ( s'1, m!, s'2 ) автомата A', входящего в состав той же системы взаимодействующих автоматов SA, но не совпадающего с A (A ≠ A');
  • частичный порядок
    сохраняет порядок переходов, относящихся к функционированию одного взаимодействующего автомата, то есть

    ei,j, ei',j'
    { ei,j } (i = i')
    (j < j')
    ei,j
    ei',j';
  • переходы, связанные отношением μ, являются неразличимыми относительно частичного порядка
    , то есть

    ei,j, ei',j'
    &#x007B; ei,j &#x007D; ei',j' = μ(ei,j)


    e
    &#x007B; ei,j &#x007D; ( (e
    ei,j)
    (e
    ei',j') )
    ( (ei,j
    e)
    (e i',j'
    e) ).


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

Содержание раздела