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

       

Управляющие автоматы


Первым шагом в формализации понятия тестового сценария является определение управляющих автоматов.

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

Управляющим автоматом будем называть пятерку ( V, X, Y, E, Q ), где

  • S - множество состояний,
  • X - множество стимулов,
  • Y - множество реакций,
  • E
    V x X x Y x V - множество переходов,
  • Q
    V - множество заключительных состояний.

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

Стимул s

X называется допустимым в состоянии u
V абстрактного автомата A = ( V, X, Y, E ) (или управляющего автомата ( V, X, Y, E, Q ) ), если существует переход ( v, x, y, v' )
E, такой что v = u и x = s.

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

Управляющие автоматы предназначены для управления другими системами. Входные символы автомата (или стимулы) рассматриваются как действия над управляемой системой, а выходные символы (или реакции) - как ответная реакция управляемой системы. Часто, в качестве управляемой системы выступает абстрактный автомат, множества стимулов и реакций которого совпадают с соответствующими множествами управляющего автомата.

Управляющий автомат начинает свою работу в некотором начальном состоянии. Он выбирает один из допустимых в данном состоянии стимулов и подает его управляемой системе. Затем управляющий автомат получает ответную реакцию и переходит в состояние, которое приписано переходу с данными пресостоянием, стимулом и реакцией. Если таких состояний несколько, то новое состояние выбирается недетерминированным образом. Если новое состояние является заключительным, то работа управляющего автомата завершается. В противном случае, все вышеописанные действия повторяются в новом состоянии.

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

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

Функционированием управляющего автомата ( V, X, Y, E, Q ) с начальным состоянием v0

V называется конечный или бесконечный путь { ei = ( vi, xi, yi, v'i ) }, удовлетворяющий следующим условиям:


  • если начальное состояние является заключительным (v0
    Q), то путь является пустой последовательностью,
  • если начальное состояние не является заключительным (v0
    Q), то пресостояние первого перехода v1 совпадает с начальным состоянием v0, (v1 = v0),
  • если путь является конечным и его длина больше нуля, то постсостояние последнего перехода является заключительным (vn
    Q),
  • если заключительное состояние присутствует в пути, то путь является конечным и это состояние есть постсостояние последнего перехода.


Управляющие автоматы будут использоваться далее для определения понятия тестового сценария.


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