Асинхронные автоматы:
классификация и тестирование

 

И.Б.Бурдонов, А.С.Косачев, В.В.Кулямин

Институт Системного Программирования РАН

e-mail: {igor@, kos@, kuliamin@ispras.ru}

 

Рассматриваются конечные автоматы, отличающиеся от классического автомата Мили тем, что переход осуществляется либо по приему стимула (входного символа), либо по выдаче реакции (выходного символа), причем в каждом состоянии выбор одного из допустимых переходов недетерминирован. Такими автоматами являются автоматы с отложенной реакцией (АОР), в которых переход по стимулу выполняется всегда, когда этот стимул имеется на входе автомата, и автоматы ввода-вывода (IOSM - Input/Output State Machines), в которых переход по выдаче реакции допустим независимо от наличия стимула, а не принятый в этом состоянии стимул может быть принят позже, в другом состоянии. Обобщением этих классов автоматов является асинхронный автомат, в котором допускаются также переходы по отсутствию стимула. Предлагается классификация асинхронных автоматов, основанная на реализуемой автоматом словарной функции и эквивалентности автоматов с совпадающей словарной функцией. Показывается, что класс всех асинхронных автоматов эквивалентен своему подклассу автоматов с отложенными реакциями, а словарные функции автоматов ввода-вывода образуют собственное подмножество всех автоматных словарных функций. С автоматом связывается также множество сериализаций (смешанных последовательностей воспринимаемых стимулов и выдаваемых реакций), и исследуется его связь со словарной функцией. Статья завершается обзором основных проблем тестирования соответствия, когда асинхронные автоматы используются как спецификационная модель программных и аппаратных систем.

 

Асинхронные автоматы: классификация и тестирование. 1

1. Введение. 2

2. Словарная функция. 6

2.1. Асинхронный автомат. 6

2.2. Финальная допустимость стимулов. 8

2.3. Автоматы без смешанных состояний. 10

2.4. Три класса автоматов и словарных функций. 16

2.4.1. Автоматы с отложенными реакциями (АОР) √ императивные автоматы без e-переходов═ 16

2.4.2. Автоматы ввода-вывода (IOSM) √ факультативные автоматы без e-переходов. 18

2.4.3. Автоматы без смешанных состояний и e-переходов (A0) 19

2.5. Общая картина взаимосвязей классов асинхронных автоматов с точки зрения словарной функции═ 21

3. Сериализация. 23

3.1. Сериализации и маршруты. 23

3.2. Три класса автоматов и z-множеств. 27

3.2.1. Класс автоматов A2, в которых z-раскраска совпадает с z-множеством (каждое нетерминальное срабатывание есть переход) 27

3.2.2. Класс автоматов A3, в которых все допустимые маршруты (сериализации) вполне-допустимы.. 27

3.2.3. Класс автоматов A4 с детерминированным z-множеством.. 30

3.3. Автоматные множества сериализаций, распознающие и отвергающие автоматы. 32

3.4. Квази-конечные сужения словарной функции и z-множества. 34

3.5. Предикат на конечных сериализациях. 36

3.5.1. Предикат z-множества. 38

3.5.2. Предикат словарной функции. 38

4. Проблемы тестирования соответствия. 41

4.1. Модель и реализация. Адаптивный алгоритм тестирования. 41

4.2. Проблема избыточности реализации. 43

4.3. Проблема избыточности модели. 44

4.4. Проблема недетерминизма. 44

4.5. Проблема бесконечности модельного домена. 45

4.6. Итерация входных слов. 45

4.7. Проблема бесконечных входных слов. 46

4.8. Проблема пустых стимулов. 48

4.8.1. Перехват операции receive. 48

4.8.2. Серийное тестирование без пауз и стационарное тестирование. 48

4.8.2. Автоматы с однородным поведением.. 49

4.8.4.═ Автоматы с однородной допустимостью.. 50

4.9. Проблема выходных слов. 52

4.9.1. Тайм-аут на ожидание очередной реакции. 52

4.9.2. Время ожидания репрезентативного выходного слова. 54

4.9.3. Автоматы с конечными выходными словами для квази-конечных входных слов. 55

4.10. Проблема постсостояния. 56

4.11. Проблема имплицитной спецификации модели и обход графа состояний. 57

4.13. Проблема медиаторов и многоуровневые спецификации. 58

5. Заключение. 59

Литература: 60

 

 

1. Введение

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

 

Автоматы с отложенными реакциями похожи на хорошо известные в литературе [1-6] автоматы ввода-вывода (IOSM √ Input/Output State Machines), называемые также взаимодействующими конечными автоматами (CFSM - Communicating Finite State Machines). В обоих автоматах переход из одного состояния в другой происходит либо как прием входного символа (стимула) √ принимающий переход, либо как выдача выходного символа (реакции) √ посылающий переход, либо как пустой переход, не сопровождающийся ни приемом стимула, ни выдачей реакции. Стимул допустим в некотором состоянии, если в этом состоянии определен принимающий переход по этому стимулу, в противном случае стимул недопустим в данном состоянии. Поскольку мы не требуем допустимости каждого стимула в каждом состоянии, рассматриваемые автоматы являются частично-определенными.═ Состояние автомата принимающее, если в нем определены только принимающие переходы, посылающее, если в нем определены только посылающие или пустые переходы, смешанное, если в нем определены как принимающие, так и посылающие или пустые переходы, и терминальное, если в нем никаких переходов не определено. Принимающие и смешанные состояния будем называть рецептивными (в этих состояниях возможен прием стимула).

 

Стимулы могут поступать на автомат только в рецептивном состоянии, но они не обязаны поступать в каждом его рецептивном состоянии. Переходы, допустимые в данном состоянии, определяются в зависимости от наличия или отсутствия стимула на входе автомата и, в случае наличия стимула, от самого этого стимула. Если оказывается, что таких допустимых переходов несколько, то выбирается один из них недетерминированным образом. В обоих автоматах, если состояние посылающее или рецептивное, но стимул отсутствует, то допустимыми являются посылающие и пустые переходы, определенные в этом состоянии. Различие между АОР и IOSM имеет место при определении допустимых переходов в случае наличия стимула в смешанном состоянии. Для АОР допустимы только принимающие переходы по этому стимулу и недопустимы как принимающие переходы по другим стимулам, так и посылающие и пустые переходы. Для IOSM также допустимы принимающие переходы по этому стимулу и недопустимы переходы по другим стимулам, однако посылающие и пустые переходы остаются допустимыми. При этом, если выполняется посылающий или пустой переход, то стимул остается на входе автомата в ожидании либо 1) выборки допустимого принимающего перехода по этому стимулу в другом рецептивном состоянии, либо 2) перехода в принимающее состояние, в котором не определен переход по данному стимулу. В случае 1) стимул выбирается автоматом и далее на его вход может поступить следующий стимул, а в случае 2) поведение автомата считается не определенным и это рассматривается как, так называемая, ошибка неспецифицированного ввода. Заметим, что для АОР такая ошибка фиксируется сразу же, как только на вход автомата поступает недопустимый в текущем состоянии стимул. Разумеется, возможно также выполнение автомата, при котором стимул никогда не будет выбран: если автомат перешел в терминальное состояние или бесконечно выполняются посылающие и пустые переходы (для АОР √ в посылающих состояниях). В терминальном состоянии автомат останавливается: состояние не меняется и прекращается как прием стимулов, так и выдача реакций. Хотя в терминальном состоянии все стимулы формально недопустимы, тем не менее ошибка неспецифицированного ввода не фиксируется, поскольку считается, что работа автомата закончена.

 

Классический автомат Мили, который на каждый допустимый стимул выдает ровно одну реакцию и ничего не делает при отсутствии стимулов, может рассматриваться как частный случай═ АОР и IOSM. Для этого достаточно каждый его переход, сопровождающийся приемом стимула и выдачей реакции, представить как последовательность из двух переходов: принимающего перехода по этому стимулу и посылающего перехода по этой реакции, между которыми добавляется═ промежуточное посылающее состояние (исходные нетерминальные состояния становятся принимающими, а смешанных состояний нет).

 

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

 

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

 

Для классического автомата Мили такое определение словарной функции достаточно: все нетерминальные состояния рецептивны и подача на его вход допустимого входного слова длины n вызывает последовательность переходов через m£n рецептивных состояний, заканчивающуюся в m+1-ом терминальном или, если m=n, терминальном или рецептивном состоянии, и выдачу соответствующего выходного слова длины m. Однако, для АОР и IOSM, в которых посылающие и пустые переходы могут выполняться и при отсутствии стимулов,═ понятие словарной функции нуждается в уточнении. Для определения входного слова, кроме самой последовательности стимулов, нам следует рассматривать также ╚паузы╩ между соседними стимулами, которые естественно измерять в количестве рецептивных состояний, проходимых═ между приемом этих стимулов. Для моделирования прохода одного рецептивного состояния с отсутствием стимула на входе автомата удобно ввести понятие пустого стимула, расширив им алфавит стимулов. Если между двумя непустыми стимулами во входном слове располагается k пустых стимулов, то это означает, что автомат между приемами этих непустых стимулов пройдет k рецептивных состояний при отсутствии стимула на его входе. Пустой стимул считается допустимым в любом рецептивном состоянии.

 

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

 

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

 

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

 

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

 

Во-первых, от вида того автомата, из которого этот асинхронный автомат произошел √ АОР или IOSM, а именно, является ли прием непустого стимула в рецептивном состоянии обязательным или не обязательным. В первом случае асинхронный автомат будем называть императивным, а во втором √ факультативным.

 

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

 

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

 

Статья состоит из четырех частей. 2-ая (после Введения) часть посвящена определению и сравнительному изучению асинхронных автоматов базовых классов. При этом, в первую очередь, обращается внимание на реализуемые ими словарные функции. С помощью преобразований автоматов, сохраняющих их словарную функцию, все автоматы приводятся к одному классу автоматов без смешанных состояний. На этой основе проводится классификация автоматов, в частности показывается эквивалентность класса всех асинхронных автоматов подклассу АОР √ императивных автоматов без e-переходов, и, напротив, показывается, что класс IOSM √ факультативных автоматов без e-переходов √ не способен моделировать класс всех асинхронных автоматов.

 

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

 

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

═

2. Словарная функция

2.1. Асинхронный автомат

Асинхронным автоматом будем называть шестерку m=(V,v₀,X,e,Y,T), где:

╥        V - множество состояний;

╥        v₀ÎV √ начальное состояние;

╥        X - входной алфавит стимулов;

╥        eÏX - пустой стимул, X`=XÈ{e} √ расширенный алфавит стимулов;

╥        Y √выходной алфавит реакций;═ будем считать, что алфавиты стимулов и реакций не пересекаются X`ÇY= Æ;

╥        T = R`ÈSÈI - множество переходов, где:

o       R` Í V´X`´V - принимающие переходы,

o       S Í V´Y´V - посылающие переходы,

o       I Í V´V - пустые переходы.

 

Принимающие переходы можно разделить на два вида: R=R`ÇV´X´V √ принимающие переходы по непустым стимулам или x-переходы, и E=R`ÇV´{e}´V √ принимающие переходы по пустым стимулам или e-переходы.

 

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

 

Стимул x допустим в состоянии v, если имеется хотя бы один принимающий переход (v,x,v`).

 

Автомат конечен, если конечны множества состояний V и переходов T. По умолчанию, мы будем рассматривать только конечные автоматы.

 

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

╥        M=MiÈMf √ класс всех асинхронных автоматов,

╥        Mi=Mi0ÈMi1ÈMi2ÈMi3 √ императивные автоматы,

╥        Mf=Mf0ÈMf1ÈMf2ÈMf3 √факультативные автоматы,

╥        Mi0 (Mf0) √ императивные (факультативные) автоматы без e-переходов (E=Æ),

╥        Mi1 (Mf1) √ императивные (факультативные) автоматы с e-переходами и приоритетом посылающих и пустых переходов над e-переходами,

╥        Mi2 (Mf2) √ императивные (факультативные) автоматы с e-переходами и приоритетом e-переходов над посылающими и пустыми переходами,

╥        Mi3 (Mf3) √ императивные (факультативные) автоматы с e-переходами и равноприоритетностью посылающих и пустых переходов и e-переходов.

 

Будем считать, что с автоматом связаны две очереди: входная очередь, в которой располагается бесконечное входное слово в алфавите X`, и выходная очередь, в которую помещаются выдаваемые автоматом реакции, формируя выходное слово в алфавите Y. Срабатывание (однократное выполнение) автомата в состоянии v заключается в определении допустимых переходов, определенных в этом состоянии и, если такие есть, недетерминированном выборе одного из них и выполнении его. Если выбирается пустой переход (v,v`), автомат переходит в состояние v`, входная и выходная очереди не изменяются. Если выбирается принимающий переход (v,x,v`), то x √ головной стимул входной очереди и он удаляется из нее, автомат переходит в состояние v`, выходная очередь не изменяется. Если выбирается посылающий переход (v,y,v`), автомат переходит в состояние v`, а в конец выходной очереди помещается реакция y; если v √ смешанное состояние и головной стимул входной очереди пустой, то он удаляется из входной очереди, в противном случае входная очередь не изменяется. В срабатывание автомата входит также его действия в случае отсутствия допустимых переходов.

 

Множество допустимых переходов, а также действия автомата при отсутствии допустимых переходов, зависят в общем случае от состояния v, головного стимула x входной очереди и класса автомата:

╥        В терминальном состоянии v допустимых переходов нет. Автомат останавливается: состояние, входная и выходная очереди не изменяются.

╥        В посылающем состоянии v допустимые переходы - это все посылающие (v,y,v`) и пустые (v,v`) переходы.

╥        В принимающем состоянии v допустимые переходы √ это все принимающие переходы (v,x,v`). Если таких переходов нет, то выполнение автомата зависит от того, пустой или непустой головной стимул: если x¹e непустой (недопустимый) стимул, то поведение автомата не определено, это квалифицируется как ошибка неспецифицированного ввода; если же x=e пустой стимул, то автомат остается в состоянии v, а пустой стимул удаляется из входной очереди, выходная очередь не изменяется.

╥        В смешанном состоянии v:

o       Если x=e пустой стимул, то допустимые переходы:

╖         для автоматов Mi0,Mi1,Mf0,Mf1 - посылающие (v,y,v`) и пустые (v,v`) переходы;

╖         для автоматов Mf2,Mi2 - e-переходы (v,e,v`), а если их нет, то посылающие (v,y,v`) и пустые (v,v`) переходы;

╖         для автоматов Mf3,Mi3 - e-переходы (v,e,v`), если они есть, плюс посылающие (v,y,v`) и пустые (v,v`) переходы.

o       Если x¹e непустой допустимый стимул, то допустимые переходы:

╖         для императивных автоматов Mi - x-переходы (v,x,v`);

╖         для факультативных автоматов Mf - x-переходы (v,x,v`) плюс посылающие (v,y,v`) и пустые (v,v`) переходы.

o       Если x¹e непустой недопустимый стимул, то допустимые переходы:

╖         отсутствуют для императивных автоматов Mi - поведение автомата не определено, это квалифицируется как ошибка неспецифицированного ввода;

╖         для факультативных автоматов Mf - посылающие (v,y,v`) и пустые (v,v`) переходы.

 

Заметим, что класс автомата влияет на его срабатывание только в смешанных состояниях.

 

Выполнением автомата по бесконечному входному слову w будем называть последовательность однократных срабатываний, начинающуюся в начальном состоянии v₀, когда во входной очереди находится слово w. Подпоследовательность посылающих переходов определяет выходное слово u, появляющееся в выходной очереди при данном выполнении. Выполнение допустимо, если оно бесконечное или заканчивается в терминальном состоянии, и недопустимо, если оно заканчивается по ошибке неспецифицированного ввода. Поскольку автомат, вообще говоря, недетерминированный, одному входному слову может соответствовать множество возможных выполнений автомата. Входное слово допустимо, если все его возможные выполнения допустимы. Соответственно, выполнение по допустимому входному слову будем называть вполне-допустимым. Заметим, что вполне-допустимое выполнение допустимо, но обратное, вообще говоря, не верно. Словарная функция автомата W ставит в соответствие каждому допустимому входному слову w множество выходных слов u для всех возможных выполнений. Заметим, что входное слово не обязательно будет полностью выбрано из входной очереди при том или ином выполнении.

 

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

2.2. Финальная допустимость стимулов

Для факультативного автомата, в отличии от императивного, допустимость или недопустимость стимула x в смешанном состоянии v еще ничего не говорит о допустимости или недопустимости в этом состоянии входного слова w, начинающегося со стимула x, в частности, учитывая, что пустые стимулы допустимы во всех нерецептивных состояниях, слова xe^w. Введем понятие финальной допустимости стимула в факультативном автомате: непустой стимул финально допустим в рецептивном состоянии v, если он допустим в любом принимающем состоянии v`, в которое можно попасть из состояния v по цепочке посылающих и пустых переходов (цепочка будет нулевой длины, если v принимающее состояние). Возможные сочетания допустимости и финальной допустимости стимулов приведены на рис.2.2.1.

 

Рис.2.2.1

 

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

 

Обозначим через M`fÌMf, M`f1ÌMf1, M`f2ÌMf2, M`f3ÌMf3 подклассы факультативных автоматов, в которых допустимость и финальная допустимость стимулов совпадают.

 

Теорема о финальной допустимости стимулов: Каждый базовый класс факультативных автоматов моделируется своим подклассом автоматов, в которых совпадают допустимость и финальная допустимость стимулов, и, следовательно, эквивалентен ему: W[M`f]=W[Mf], W[M`f1]=W[Mf1], W[M`f2]=W[Mf2], W[M`f3]=W[Mf3].

 

Док-во: Определим следующую процедуру преобразования факультативного автомата (рис.2.2.2):

╥        Добавим дополнительные состояния вида (v,x), где vÎV √ основное состояние, а xÎX - непустой стимул.

╥        Для каждого основного смешанного состояния v удалим все определенные в нем принимающие переходы (v,x,v`) по допустимым, но финально недопустимым стимулам x.

╥        Для каждого основного смешанного состояния v и недопустимого, но финально допустимого в нем стимула x, добавим принимающий переход, ведущий в дополнительное состояние (v,x,(v,x)).

╥        Если в основном рецептивном состоянии v стимул x финально допустим, то для каждого принимающего перехода (v,x,v`) добавим пустой переход из соответствующего дополнительного состояния ((v,x),v`).

╥        Для каждого посылающего (v,y,v`) и пустого (v,v`) перехода добавим, соответственно, посылающий ((v,x),y,(v`,x)) или пустой ((v,x),(v`,x)) переход из дополнительных состояний.

Рис.2.2.2

 

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

 

Случай 1. Если автомат не имеет e-переходов (класс Mf0), то финальная недопустимость стимула x в состоянии v означает существование выполнения, начинающегося в v, содержащего только посылающие и пустые переходы и заканчивающегося в принимающем состоянии v`, в которой стимул x недопустим. Поскольку в v` не определены e-переходы, сначала будут удалены из очереди все пустые стимулы, а потом выбран непустой стимул и, если это x, то фиксируется ошибка неспецифицированного ввода. Следовательно из финальной недопустимости стимула x в смешанном состоянии v следует финальная недопустимость в нем любого слова eⁿx. Тем самым, если в состоянии v недопустимы все непустые стимулы, то в этом состоянии допустимо единственное бесконечное слово e^w (которое всегда допустимо). Поскольку для ew=e^w, очевидно, w=e^w, имеем ew=w и, следовательно, словарная функция не меняется.

 

Случай 2. Если автомат может иметь e-переходы (классы Mf1, Mf2, Mf3), то, вообще говоря, из финальной недопустимости стимула x в состоянии v не следует финальная недопустимость в нем слова ex, то есть, финальная недопустимость стимула x в конце v` какого-нибудь e-перехода (v,e,v`). Простое удаление принимающих переходов, определенных в v, может изменить словарную функцию. Пример на рис.2.2.3.

 

Рис.2.2.3

 

Поэтому для таких автоматов, кроме удаления принимающих переходов (v,x,v₁) из состояния v, мы дополнительно преобразуем хотя бы один пустой (v,v₂) или посылающий (v,y,v₃) переход из v, в два смежных перехода, первый из которых - e-переход (v,e,v₂`), ведущий в дополнительное состояние v<sub>2</sub>`, а второй пустой (v₂`,v`) переход, или, соответственно, e-переход (v,e,v₃`) и посылающий (v<sub>3</sub>`,y,v`) переход. Состояние v остается рецептивным, а движение по паре новых смежных переходов эквивалентно (по изменению состояния и содержимого очередей) движению по одному старому переходу. Поэтому и в этом случае словарная функция не меняется. См. Рис.2.2.4.

 

Рис.2.2.4

 

Теорема о финальной допустимости стимулов доказана.

 

В дальнейшем мы вместо базовых классов Mf, Mf1, Mf2, Mf3 будем рассматривать эквивалентные им подклассы M`f, M`f1, M`f2, M`f3, которые также будем называть базовыми классами факультативных автоматов там, где это не приведет к недоразумениям.

2.3. Автоматы без смешанных состояний

Обозначим через A класс автоматов без смешанных состояний с e-переходами. Отсутствие смешанных состояний и возможное наличие e-переходов делает автомат этого класса одновременно элементом любого из базовых классов с разрешенными e-переходами, которые отличаются друг от друга поведением только в смешанных состояниях, то есть, A = Mi3ÇMi2ÇMi1ÇM`f3ÇM`f2ÇM`f1. Тем самым, класс A моделируется каждым из базовых классов: W[A]ÍW[Mi3], W[A]ÍW[Mi2], W[A]ÍW[Mi1], W[A]ÍW[M`f3], W[A]ÍW[M`f2], W[A]ÍW[M`f1].

 

Теорема об автомате без смешанных состояний: Класс M всех асинхронных автоматов моделируется своим подклассом A автоматов без смешанных состояний и, следовательно, эквивалентен ему.

 

Из этой теоремы следует эквивалентность W[A]=W[Mi3]=W[Mi2]=W[Mi1]=W[M`f3]=W[M`f2]=W[M`f1] и вложенности W[Mi0]ÍW[A] и W[Mf0]ÍW[A].

 

Док-во: Для доказательства достаточно рассмотреть возможные срабатывания автоматов разных классов в смешанных состояниях. Можно выделить 11 случаев, изображенных на таб.2.3.1. Здесь переход, помеченный ⌠x■, означает принимающий переход по непустому стимулу x; переход, помеченный ⌠e■, означает e-переход; переход, помеченный ⌠y■, означает переход посылающий реакцию y или пустой переход. Записи x:(...) и e:(...) означают здесь допустимость перехода (...) когда головной стимул входной очереди равен, соответственно, непустому стимулу x или пустому стимулу e.

Таб.2.3.1

 

1. Смешанное состояние без e-переходов.

1.1. Императивный автомат (рис.2.3.1).

Рис.2.3.1

Для каждого состояния v типа 1 добавляется дополнительное состояние (v,e). Посылающий (v,y,v`<sub>y</sub>) или пустой (v,v`_y) переход из v заменяется на e-переход, ведущую в дополнительное состояние (e,v,(v,e)) и, соответственно, посылающий ((v,e),y,v_y) или пустой ((v,e),v_y) переход из этого дополнительного состояния.

 

1.2. Факультативный автомат (рис.2.3.2).

Рис.2.3.2

Аналогично случаю 1.1, для каждого состояния v типа 1 добавляется дополнительное состояние (v,e); посылающий (v,y,v`<sub>y</sub>) или пустой (v,v`_y) переход из v заменяется на e-переход в дополнительное состояние (e,v,(v,e)) и, соответственно, посылающий ((v,e),y,v_y) или пустой ((v,e),v_y) переход из этого дополнительного состояния. Затем в моделирующий автомат добавляются дополнительные состояния вида (v,x) для состояний vÎV и непустых стимулов xÎX. Для каждого основного смешанного состояния vÎV рассматриваемого типа и допустимого в нем непустого стимула x добавляется принимающий переход (v,x,(v,x)). В каждом дополнительном состоянии (v,x) определяются посылающие ((v,x),y,(v`,x)) и пустые ((v,x),(v`,x)) переходы тогда и только тогда, когда в моделируемом автомате есть переходы, соответственно, (v,y,v`) и (v,v`). В каждом дополнительном состоянии (v,x) определяется пустой переход ((v,x),v`) тогда и только тогда, когда в моделируемом автомате есть переход (v,x,v`).

 

 

 

 

 

 

 

 

 

 

2. Смешанное состояние, в котором все принимающие переходы - e-переходы.

2.1. Равный приоритет e-переходов и посылающих и пустых переходов (рис.2.3.3).

Рис.2.3.3

Аналогично случаю 1.1, для каждого состояния v типа 2 добавляется дополнительное состояние (v,e); посылающий (v,y,v`<sub>y</sub>) или пустой (v,v`_y) переход из v заменяется на e-переход в дополнительное состояние (e,v,(v,e)) и, соответственно, посылающий ((v,e),y,v_y) или пустой ((v,e),v_y) переход из этого дополнительного состояния.

 

2.2. Приоритет e-переходов (рис.2.3.4).

Рис.2.3.4

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

 

2.3. Приоритет посылающих и пустых переходов (рис.2.3.5).

Рис.2.3.5

Приоритет посылающих и пустых переходов приводит к тому, что в состоянии типа 2 вообще никогда не будут выполняться e-переходы. Однако, если такие переходы просто удалить, то состояние перестанет быть рецептивным. Поэтому, как и в случае 1.1, для каждого состояния v типа 2 добавляется дополнительное состояние (v,e); посылающий (v,y,v`<sub>y</sub>) или пустой (v,v`_y) переход из v заменяется на e-переход в дополнительное состояние (e,v,(v,e)) и, соответственно, посылающий ((v,e),y,v_y) или пустой ((v,e),v_y) переход из этого дополнительного состояния.

 

3. Смешанное состояние общего вида.

3.1. Императивный автомат.

3.1.1. Равный приоритет e-переходов и посылающих и пустых переходов (рис.2.3.6).

Рис.2.3.6

Аналогично случаю 2.1, для каждого состояния v типа 3 добавляется дополнительное состояние (v,e); посылающий (v,y,v`<sub>y</sub>) или пустой (v,v`_y) переход из v заменяется на e-переход в дополнительное состояние (e,v,(v,e)) и, соответственно, посылающий ((v,e),y,v_y) или пустой ((v,e),v_y) переход из этого дополнительного состояния.

 

3.1.2. Приоритет e-переходов (рис.2.3.7).

Рис.2.3.7

Аналогично случаю 2.2, приоритет e-переходов приводит к тому, что в состоянии типа 3 вообще никогда не будут выполняться посылающие и пустые переходы, ═поэтому их можно удалить.

 

3.1.3. Приоритет посылающих и пустых переходов (рис.2.3.8).

Рис.2.3.8

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

 

3.2. Факультативный автомат.

3.2.1. Равный приоритет e-переходов и посылающих и пустых переходов (рис.2.3.9).

Рис.2.3.9

Аналогично случаю 1.2, для каждого состояния v типа 3 добавляется дополнительное состояние (v,e); посылающий (v,y,v`<sub>y</sub>) или пустой (v,v`_y) переход из v заменяется на e-переход в дополнительное состояние (e,v,(v,e)) и, соответственно, посылающий ((v,e),y,v_y) или пустой ((v,e),v_y) переход из этого дополнительного состояния. Затем в моделирующий автомат добавляются дополнительные состояния вида (v,x) для состояний vÎV и непустых стимулов xÎX. Для каждого основного состояния v типа 3 и допустимого в нем непустого стимула x добавляется принимающий переход (v,x,(v,x)). В каждом дополнительном состоянии (v,x) определяются посылающие ((v,x),y,(v`,x)) и пустые ((v,x),(v`,x)) переходы тогда и только тогда, когда в моделируемом автомате есть переходы, соответственно, (v,y,v`) и (v,v`), кроме того, определяется пустой переход ((v,x),v`) тогда и только тогда, когда в моделируемом автомате есть переход (v,x,v`).

 

3.2.2. Приоритет e-переходов (рис.2.3.10).

Рис.2.3.10

Приоритет e-переходов приводит к тому, что в состоянии типа 3 при пустом головном стимуле не будут выполняться посылающие и пустые переходы; эти переходы могут выполняться только при непустом и допустимом головном стимуле. Поэтому делаем аналогично случаю 3.2.1, но только посылающий или пустой переход из основного состояния типа 3 не заменяем на e-переход в дополнительное состояние, и, соответственно, посылающий или пустой переход из этого дополнительного состояния, а просто удаляем. В моделирующий автомат добавляются дополнительные состояния вида (v,x) для состояний vÎV и непустых стимулов xÎX. Для каждого основного состояния v типа 3 и допустимого в нем непустого стимула x добавляется принимающий переход (v,x,(v,x)). В каждом дополнительном состоянии (v,x) определяются посылающие ((v,x),y,(v`,x)) и пустые ((v,x),(v`,x)) переходы тогда и только тогда, когда в моделируемом автомате есть переходы, соответственно, (v,y,v`) и (v,v`), кроме того, определяется пустой переход ((v,x),v`) тогда и только тогда, когда в моделируемом автомате есть переход (v,x,v`). Посылающие и пустые переходы из основных состояний типа 3 удаляются.

 

 

 

3.2.3. Приоритет посылающих и пустых переходов (рис.2.3.11).

Рис.2.3.11

Приоритет посылающих и пустых переходов приводит к тому, что в состоянии типа 3 при пустом головном стимуле не будут выполняться e-переходы; тем более они не будут выполняться при непустом головном стимуле. Поэтому делаем аналогично случаю 3.2.1, но только e-переходы из основных состояний типа 3 удаляем. В моделирующий автомат добавляются дополнительные состояний вида (v,x) для состояний vÎV и непустых стимулов xÎX. Для каждого основного состояния v типа 3 и допустимого в нем непустого стимула x добавляется принимающий переход (v,x,(v,x)). В каждом дополнительном состоянии (v,x) определяются посылающие ((v,x),y,(v`,x)) и пустые ((v,x),(v`,x)) переходы тогда и только тогда, когда в моделируемом автомате есть переходы, соответственно, (v,y,v`) и (v,v`), кроме того, определяется пустой переход ((v,x),v`) тогда и только тогда, когда в моделируемом автомате есть переход (v,x,v`). e-переходы из основных состояний типа 3, удаляются.

 

Теорема об автомате без смешанных состояний доказана.

2.4. Три класса автоматов и словарных функций

В этом разделе мы рассмотрим три класса автоматов: 1) класс Mi0=АОР императивных автоматов без e-переходов (автоматы с отложенными реакциями), 2) класс Mf0=IOSM факультативных автоматов без e-переходов (автоматы ввода-вывода), 3) пересечение этих классов - класс A0 автоматов без смешанных состояний и e-переходов. Мы покажем, что класс АОР моделирует класс A и, тем самым, эквивалентен классу всех асинхронных автоматов W[АОР]=W[M], класс IOSM этим свойством не обладает, то есть, W[IOSM]ÌW[M], а класс A0 не моделирует класс IOSM, W[A0]ÌW[IOSM], и, тем более, класс АОР, то есть, является самым узким классом в смысле словарной функции.═

2.4.1. Автоматы с отложенными реакциями (АОР) √ императивные автоматы без e-переходов

Сначала мы рассмотрим специальный подкласс A1ÌA автоматов без смешанных состояний и без таких принимающих состояний, в которых определены только e-переходы (такие состояния будем называть e-состояниями), то есть, в каждом принимающем состоянии определен хотя бы один принимающий переход по непустому допустимому стимулу.

 

Теорема о e-состояниях: Класс A моделируется своим подклассом A1 и, тем самым, они эквивалентны W[A]=W[A1].

 

Док-во: Для доказательства достаточно рассмотреть моделирование поведения автомата класса A в e-состоянии (рис.2.4.1), поскольку в остальных состояниях автоматы классов A и A1 ведут себя одинаково.

Рис.2.4.1

Для каждого e-состояния v добавляем два дополнительных состояния v₁ и v₂, и в состоянии v определяем два пустых перехода в v₁ и v₂. В состоянии v₁ определяем принимающий переход по любому непустому стимулу x, а в состоянии v₂ - множество принимающих переходов по всем остальным непустым стимулам. Очевидно, что в состоянии v все непустые стимулы финально недопустимы. После этого каждый e-переход (v,e,v_e) заменяем на два e-перехода из состояний v₁ и v₂, соответственно, (v₁,e,v_e) и (v₂,e,v_e).

 

В этом доказательстве мы неявно использовали тот факт, что алфавит стимулов состоит хотя бы из двух непустых стимулов, то есть, x₁ÎX и X\{x₁}¹Æ. Если это не так, то мы всегда можем добавить в алфавит стимулов еще два непустых стимула, один из которых будем использовать только для принимающих переходов из v₁, а другой вместе с остальными стимулами из X - для принимающих переходов из v₂. Понятно, что эти дополнительные стимулы не будут входить в допустимые входные слова, поэтому словарная функция не изменится.

 

Теорема о e-состояниях доказана.

 

Теорема об автомате с отложенными реакциями: Класс M всех асинхронных автоматов моделируется своим подклассом автоматов с отложенными реакциями АОР=Mi0 (императивные автоматы без e-переходов) и, следовательно, эквивалентен ему.

 

Док-во: Класс Mi0, как подкласс класса M всех асинхронных автоматов, им моделируется. Поскольку класс M всех асинхронных автоматов эквивалентен классу A, а класс A эквивалентен своему подклассу A1, нам достаточно показать, что класс A1 моделируется классом Mi0. Для моделирования автомата класса A1 автоматом класса Mi0 достаточно рассмотреть поведение автомата в принимающих состояниях, в которых определены прием как пустого стимула, так и непустых допустимых стимулов, поскольку в автоматах класса A1 нет смешанных состояний и нет e-состояний, а в принимающих состояниях без e-переходов также как═ в терминальных и посылающих состояниях все автоматы ведут себя одинаково. Моделирование поведения в таком состоянии тривиально: e-переходы заменяем пустыми переходами (рис.2.4.2).

Рис.2.4.2

Теорема об автомате с отложенными реакциями доказана.

 

Итак, мы показали, что W[Mi0]=W[A]=W[A1] и, тем самым, доказана эквивалентность всех базовых классов, кроме Mf0: W[M]=W[A]=W[A1]=W[Mi0]=W[Mi3]=W[Mi2]=W[Mi1]=W[M`f3]=W[M`f2]=W[M`f1].

2.4.2. Автоматы ввода-вывода (IOSM) √ факультативные автоматы без e-переходов

Теорема об автомате ввода-вывода (IOSM): Класс M всех асинхронных автоматов не моделируется своим подклассом автоматов ввода-вывода IOSM=Mf0 (факультативные автоматы без e-переходов).

 

Док-во: Поскольку класс Mf0 моделируется своим подклассом M`f0, а класс M всех асинхронных автоматов моделируется подклассом A, нам достаточно показать, что существует автомат aÏA, который не моделируется классом M`f0, то есть, W[a]ÏW[M`f0].

 

Напомним, что автомат класса M`f0 - это факультативный автомат без e-переходов, в котором совпадают допустимость и финальная допустимость стимулов. Такие автоматы обладают следующими двумя свойствами, которыми некоторые асинхронные автоматы класса A не обладают.

 

Свойство 1: Если словарная функция автомата класса M`f0 определена на входном слове uexw, где u - конечное слово, e - пустой стимул, x - некоторый стимул (быть может, пустой), w - бесконечное слово, то она должна быть определена также на входном слове uxe^w.

 

Действительно, поскольку входные слова uexw и uxe^w имеют общий начальный отрезок u, и слово uexw допустимо, ошибка неспецифицированного ввода может проявиться для слова uxe^w только после выборки слова u из входной очереди при приеме стимула x в принимающем состоянии v (последующие стимулы пустые и, тем самым, всегда допустимые). Значит стимул x недопустим в состоянии v. Но тогда для слова uexw автомат после выборки слова u также может оказаться в принимающем состоянии v и примет пустой стимул e. Поскольку v √ принимающее состояние и e-переходов нет, выборка пустого стимула не меняет состояние и автомат в том же состоянии v выберет недопустимый стимул x, то есть, будет зафиксирована ошибка неспецифицированного ввода и окажется, что слово uexw недопустимо. Мы пришли к противоречию и, значит, входное слово uxe^w должно быть допустимо.

 

Заметим, что требование наличия после непустого стимула x в слове uxe^w только пустых стимулов существенно, поскольку может оказаться, что для любого допустимого входного слова вида uexw любое входное слово вида uxw`, допустимо только тогда, когда w`=e^w. Пример приведен на рис. 2.4.3. При X = {x,x`} единственное допустимое слово вида xw` - это слово xe^w, а для всех допустимых входных слов вида uexw, u - должно быть пусто.

Рис.2.4.3

Теперь нам достаточно привести пример автомата класса A, словарная функция которого не обладала бы этим первым свойством (рис. 2.4.4). Словарная функция автомата определена на и только на словах вида ew, начинающихся с пустого стимула, и отображает каждое такое входное слово в пустое выходное слово. Для любого непустого стимула x эта функция определена на любом слове вида exw, но не определена на слове xe^w.

Рис.2.4.4

 

Свойство 2: Если словарная функция W автомата класса M`f0 определена на слове w, то она определена также на любом слове w`, полученное из w добавлением в произвольные места произвольного числа пустых стимулов, и W(w`)ÍW(w).

 

Действительно, если по конечному слову u автомат может попасть в принимающее состояние v, то, поскольку в принимающем состоянии не определены e-переходы, автомат в состоянии v не сможет различить остатки входных слов, находящиеся во входной очереди в этот момент времени, отличающиеся только количеством пустых стимулов в начале. Все эти пустые стимулы будут "глотаться" принимающим состоянием. Поэтому любое возможное продолжение выполнения автомата для допустимого слова uw дает ту же последовательность переходов (а значит, и реакций), что и для слова uew, и наоборот. Если по конечному слову u автомат может попасть в смешанное состояние v, то, поскольку в смешанном состоянии автомат может сработать по посылающему или пустому переходу независимо от головного стимула, пустой головной стимул в этом случае выбирается из очереди, а непустой остается, любое продолжение выполнения автомата для бесконечного слова uew дает такую последовательность переходов (а значит, и реакций), которая возможна также для продолжения выполнения в случае слова uw, хотя обратное, вообще говоря, неверно. Тем самым оказывается, что любое выполнение для слова uew дает последовательность переходов (а значит, и реакций), которая возможна также для слова uw, то есть, W(uew)ÍW(uw). Отсюда непосредственно следует свойство 2.

 

Теперь нам достаточно привести пример автомата класса A, словарная функция которого не обладала бы этим вторым свойством (рис.2.4.5). Здесь для═ X={x,x`} слово xx`e^w допустимо, а слово xex`e^w недопустимо.

Рис.2.4.5

 

Теорема об автомате ввода-вывода (IOSM) доказана.

 

Рассмотренные нами два свойства словарной функции автоматов ввода-вывода (IOSM)═ являются необходимыми. Можно сформулировать следующую нерешенную задачу: найти свойства словарной функции, необходимые и достаточные для того, чтобы она была словарной функцией автомата ввода-вывода (IOSM).

2.4.3. Автоматы без смешанных состояний и e-переходов (A0)

Специальный интерес представляет класс A0 автоматов без смешанных состояний и e-переходов, вложенный, очевидно, во все остальные рассматривавшиеся выше классы автоматов.

 

Теорема об автомате без смешанных состояний и e-переходов: Класс M`f0 не моделируется классом A0.

 

Док-во: Автоматы класса A0 обладают тремя особыми свойствами, которыми не обладают некоторые автоматы надкласса M`f0.

═

Свойство 1: Если словарная функция W автомата класса A0 определена на слове w, то она определена также на любом слове w`, полученном из w вставкой или удалением конечного числа пустых стимулов, и принимает на нем то же значение W(w`)=W(w).

 

Это непосредственно следует из того, что каждое рецептивное состояние является принимающим состоянием без e-переходов, поэтому такое состояние "глотает" все пустые стимулы. Примером автомата класса M`f0, не моделируемого классом A0 из-за нарушения свойства 1, может служить автомат на рис.2.4.3. Для X = {x,x`} входное слово exx`e<sup>w</sup> допустимо, а входное слово xx`e^w недопустимо. Заметим, что здесь мы использовали только часть свойства 1 класса A0 - выделенную курсивом. Если использовать это свойство полностью, то можно привести более простой пример автомата класса M`f0, не моделируемого классом A0 (рис.2.4.6). Для этого автомата допустимы как входное слово xw, так и входное слово exw, где w - произвольное бесконечное слово. Однако, для слова exw определено одно выходное слово - (y), а для слова xw - два выходных слова: пустое () и (y).

Рис.2.4.6

 

Для того, чтобы определить второе свойство автоматов класса A0, введем следующие обозначения:

╥        c£c`, где c и c` - два слова (конечных или бесконечных) в одном алфавите, означает, чтоили c конечно и является начальным отрезком c`, или они совпадают.

╥        C£C`, где C и C` - два множества слов (конечных или бесконечных) в одном алфавите, означает, что "cÎC $c`ÎC` c£c` и "c`ÎC` $cÎC c£c`. Будем писать C<C`, если C£C` и С¹С`; очевидно, что в случае строгого неравенства C содержит хотя бы одно конечное слово.

 

Свойство 2: Если словарная функция W автомата класса A0 определена на слове ue^w, где u - конечное слово, то для любого допустимого слова uw имеет место W(ue^w)£W(uw).

 

Действительно, после выборки автоматом из входной очереди входного слова u автомат либо через конечное число посылающих и пустых переходов попадает в 1) принимающее или 2) терминальное состояние v и в выходной очереди оказывается конечное слово c, либо 3) выполняет бесконечную последовательность посылающих и пустых переходов. В случаях 2 и 3, очевидно, прекращается выборка стимулов из входной очереди и поэтому получившееся выходное слово принадлежит как W(ue^w), так и W(uw). В случае 1 автомат остается в принимающем состоянии v и более ничего не помещает в выходную очередь, то есть, выходным словом останется конечное слово c. В то же время для любого допустимого продолжения слова u, то есть, для слова uw автомат выполняет принимающий переход по первому непустому стимулу в слове w, то есть, выходное слово будет некоторым, быть может, пустым, продолжением c`³c.

 

Примером автомата класса M`f0, не моделируемого классом A0 из-за нарушения свойства 2, может служить тот же автомат на рис.2.4.6. Для этого автомата при xÎX допустимы как входное слово xw, где w - произвольное бесконечное слово, так и входное слово e^w. При этом W(e^w)={(y)}, а W(xw)={(),(y)}, и, очевидно, W(xw)<W(e^w).

 

Свойство 3: Если словарная функция W автомата класса A0 определена на слове ue^w, где u - конечное слово, и существует недопустимое слово uw, где w - бесконечное слово, содержащее непустые стимулы, то в множестве выходных слов W(ue^w) имеется хотя бы одно конечное слово.

 

Действительно, если существует недопустимое слово uw, то, значит, после выборки из входной очереди слова u, автомат может за конечное число посылающих и пустых переходов перейти в принимающее состояние v, в котором первый непустой стимул слова w недопустим. В этот момент в выходной очереди окажется конечное выходное слово c. Очевидно, что для входного слова ue^w дальше будут выбираться только пустые стимулы и автомат класса A0 будет оставаться в состоянии v, не изменяя выходную очередь. Это значит, что при таком выполнении для входного слова ue^w будет получено конечное выходное слово c, то есть, cÎW(ue^w).

 

Заметим, что если для некоторого допустимого слова uw имеет место W(ue^w)<W(uw), то из определения отношения "<" следует, что W(ue^w) содержит хотя бы одно конечное слово. Поэтому необходимым и достаточным условием отсутствия в W(ue^w)═ конечных слов является отсутствие недопустимых слов вида uw и для всех допустимых слов вида uw равенство (с учетом свойства 2) W(ue^w)=W(uw).

 

Пример автомата класса M`f0, не моделируемого классом A0 из-за нарушения свойства 3, приведен на рис.2.4.7. В этом автомате для X={x,x`} W(e^w)={y^w} и в тоже время существует недопустимое слово xx`w, где w - любое бесконечное слово.

 

Рис.2.4.7

 

Теорема об автомате без смешанных состояний и e-переходов доказана.

 

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

2.5. Общая картина взаимосвязей классов асинхронных автоматов с точки зрения словарной функции

Если рассматривать автоматы, в которых e-переходы определены только в принимающих состояниях (не определены в смешанных состояниях), то, очевидно, мы получим следующие классы автоматов Bi=Mi1ÇMi2=Mi1ÇMi3=Mi2ÇMi3, Bf=Mf1ÇMf2=Mf1ÇMf3=Mf2ÇMf3,

B`f=M`f1ÇM`f2=M`f1ÇM`f3=M`f2ÇM`f3.

 

Теперь определим разбиение класса всех асинхронных автоматов на непересекающиеся области (таб.2.5.1)

 

 

 

Таб.2.5.1

 

Теперь можно представить классы автоматов как объединения областей (таб.2.5.2).

Таб.2.5.2

 

 

 

 

В разделах 2.2-2.4 было показано следующее:

╥         Каждый базовый класс факультативных автоматов Mfn (n=0,1,2,3) моделируется своим подклассом M`fn, в котором допустимость и финальная допустимость стимулов совпадают, и, следовательно эквивалентен ему.

╥         Класс A моделирует базовые классы Min и M`fn, где n=0,1,2,3. Учитывая вложенность классов, получаем эквивалентность класса A и классов Min и M`fn, где n=1,2,3.

╥         Класс A моделируется своим подклассом A1 и, тем самым, ему эквивалентен.

╥         Эквивалентность класса A1 и класса Mi0.

╥         Немоделируемость класса A классом M`f0.

╥         Немоделируемость класса M`f0 классом A0.

Тем самым, учитывая вложенность классов, имеем три группы классов M0, M1, M таких, что W(M0)ÌW(M1)ÌW(M0), и все классы одной группы эквивалентны:

╥         W(M0) = W(A0)

╥         W(M1) = W(M`f0) = W(Mf0)

╥         W(M) = W(A1) = W(A) = W(Mi0) = W(Bi) = W(Mi1) = W(Mi2) = W(Mi3) = W(B`f) = W(M`f1) = W(M`f2) = W(M`f3) = W(Bf) = W(Mf1) = W(Mf2) = W(Mf3)

На рис.2.5.1 изображены эти три группы классов; стрелки показывают частичный порядок по отношению вложенности.

 

 

Рис.2.5.1

 

3. Сериализация

3.1. Сериализации и маршруты.

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

 

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

 

Сериализацией будем называть слово (конечное или бесконечное)═ в объединенном алфавите стимулов (включая пустой) и реакций Z=X`ÈY. Через xz и yz обозначим, соответственно, x-подслово и y-подслово z, то есть, подпоследовательность z, состоящую из, соответственно стимулов и реакций. Мы будем также говорить, что z является сериализацией пары (zx,zy). Для множества сериализаций S обозначим xS={xz|zÎS} и yS={yz|zÎS}. На множестве всех сериализаций (как и вообще на множестве слов в любом алфавите) имеется естественный частичный порядок: z£z` означает, что сериализация z является начальным отрезком (тогда она конечна) или совпадает с сериализацией z`.

 

Сериализация z, соответствующая выполнению автомата любого класса, строится в процессе выполнения следующим образом. Реакция y помещается в z одновременно с выдачей этой реакции в выходную очередь, то есть, когда автомат совершает посылающий переход (v,y,v`). Стимул x`ÎX` помещается в z тогда, когда автомат впервые его ╚распознает╩, то есть, ╚читает╩ в рецептивном состоянии v для того, чтобы определить свое дальнейшее поведение в зависимости от этого стимула. Если дальнейшее поведение заключается в совершении принимающего перехода (v,x`,v`), то стимул удаляется из очереди и мы присоединим его к z: z^(x`). Однако, дальнейшее поведение не обязательно включает принимающий переход (v,x`,v`) по стимулу и/или удаление стимула из входной очереди. Для пустого стимула x`=e автоматы некоторых классов═ в смешанном состоянии v могут совершить посылающий (v,y,v`) или пустой (v,v`) переход (если в этом состоянии нет e-переходов или они имеют равный или меньший приоритет, чем посылающие и пустые переходы) и, тем самым, в z помещается два символа z^(ey) или один символ z^(e). Для принимающего состояния v без e-переходов при срабатывании автомата по пустому головному стимулу никакого перехода не совершается, состояние не меняется, а пустой стимул удаляется из входной очереди: z^(e). Факультативный автомат, кроме этого, при непустом головном стимуле x`¹e в смешанном состоянии v может, не удаляя стимула из входной очереди, совершить посылающий (v,y,v`) или пустой (v,v`) переход. Хотя стимул x` не удаляется из очереди, он, тем не менее, читается и определяет набор допустимых переходов; поэтому z изменяется соответственно: z^(x,y) или z^(x). Дальнейшее поведение автомата определено ╚прочитанным╩ стимулом x` до тех пор, пока этот стимул не будет удален из очереди при совершении принимающего перехода по x`; таким образом, при всех дальнейших срабатываниях автомата, включая этот принимающий переход, автомат не читает головной стимул и никаких стимулов в z не помещается. Если до этого принимающего перехода совершаются посылающие переходы, то только соответствующие реакции помещаются в z.

 

Такое определение сериализации выполнения может показаться странным, особенно для факультативных автоматов. Например, для непустого головного стимула x═ в смешанном состоянии v последовательность переходов (v,y,v₁),(v₁,x,v₂) помещает в сериализацию не (y,x), как можно было бы ожидать, а (x,y). На самом деле, это вполне объяснимо, поскольку стимул x прочитывается первый раз в состоянии v, а не в последующем состоянии v₁, и поскольку прочитанный, но не удаленный из очереди, стимул x уже не может быть изменен и, тем самым, повторное чтение его в состоянии v₁ излишне. Фактически, такой стимул как бы запоминается автоматом, что и происходит явно в тех преобразованиях, которые мы использовали в разделах 2.2-2.4 для моделирования поведения факультативного автомата в смешанных состояниях.

 

Если для входного слова w некоторое выполнение порождает сериализацию z, то, очевидно, yz √ выходное слово при этом выполнении, а xz£w, причем x-подслово конечно xz<w в одном из трех случаев: 1) выполнение заканчивается в терминальном состоянии; 2) начиная с некоторого момента, автомат проходит только через нерецептивные (посылающие) состояния; 3) выполнение заканчивается по ошибке неспецифицированного ввода. При этом само слово z конечно в случаях 1) и 3), а в случае 2) может быть как бесконечным, так и конечным √ если автомат с некоторого момента совершает только пустые переходы в нерецептивных состояниях. Заметим, что последовательность прочитанных автоматом из входной очереди стимулов совпадает с xz, причем все эти стимулы, кроме, быть, может, последнего стимула xz (для конечного xz), удалены из входной очереди, после чего произошел один из указанных трех случаев. Для допустимого входного слова w имеются только первые два случая.

 

Сериализацию z будем называть допустимой (в автомате), если она соответствует некоторому допустимому выполнению, и вполне-допустимой, если она соответствует вполне-допустимому выполнению, то есть, выполнению для допустимого входного слова. Через Z^all обозначим множество допустимых сериализаций, Z(w) -═ множество сериализаций для допустимого входного слова w, а через Z √ подмножество Z^all═ вполне-допустимых сериализаций, которое, для краткости, мы будем называть также z-множеством автомата. Если нужно указать автомат m, будем писать═ Z[m]. Для класса автоматов N будем писать Z[N] ={Z[m] |mÎN}. Заметим, что во множестве всех сериализаций выполнения автомата все допустимые сериализации максимальны (не имеют продолжения, так как бесконечны или заканчиваются в терминальных состояниях), а недопустимые сериализации немаксимальны (заканчиваются в рецептивных состояниях, то есть, могут быть продолжены для другого входного слова). Соответственно, множество Z^all является множеством максимальных сериализаций (антицепью - все допустимые сериализации несравнимы друг с другом).

 

На самом деле, Z может быть определено через Z^all непосредственно. Будем говорить, что входное слово w допустимо во множестве максимальных сериализаций S, если любой начальный отрезок z[1..n] любой сериализации zÎS, x-подслово которого является начальным отрезком w, x(z[1..n])<w, всегда может быть продолжен в S сериализацией z`ÎS, z[1..n]=z`[1..n], такой, что ее x-подслово xz`£w. Сериализацию zÎS будем называть вполне-допустимой в S, если ее x-подслово является начальным отрезком или совпадает с допустимым входным словом. Вполне-допустимым (дуальным) замыканиемS назовем подмножество C<S> всех сериализаций вполне-допустимых в S; замкнутым по вполне-допустимости назовем такое множество S, что C<S>=S. Поскольку вместе с каждой вполне-допустимой сериализацией zÎS вполне-допустима также любая сериализация z`ÎS, x-подслово которой совпадает═ с x-подсловом z, xz`=xz, или является его начальным отрезком xz`£xz, нетрудно показать, что C<C<S>>=C<S>. Будем называть x-подслово сериализации z вполне-допустимого замыкания C<S> максимальным, если оно конечно, но в C<S> не существует сериализации z` с большим x-подсловом xz`>xz. Тогда, очевидно, множество входных слов допустимых в S, которое мы будем обозначать w(S), совпадает с множеством всех бесконечных x-подслов и всех бесконечных продолжений максимальных конечных x-подслов сериализаций вполне-допустимого замыкания C<S>.

 

Для S= Z допустимость входного слова в Z как раз и означает, что при любом выполнении не возникнет ситуации, когда в рецептивном состоянии читается очередной стимул входного слова и для этого стимула не определено поведение автомата. Таким образом, z-множество Z является замыканием по вполне-допустимости множества допустимых сериализаций Z =С(Z^all).

 

Z-множество Z однозначно определяет автоматную словарную функцию W. Словарную функцию для z-множества Z будем обозначать W(Z:

╥        Dom(W(Z))=w(Z)=w(Z^all) √ множество входных слов допустимых в Z (Z^all).

╥        "wÎDom(W(Z)) W(Z)(w)={yz|zÎZ xz£w} √ множество y-подслов сериализаций z-множества, x-подслова которых совпадают с входным словом или являются его начальными отрезками.

 

Будем говорить, что класс автоматов N строго моделируется классом автоматов N`, если Z[N]ÍZ[N`], то есть, для каждого автомата mÎN существует автомат m`ÎN`, имеющий то же z-множество Z[m]=Z[m`]. Если классы автоматов N и N` взаимно строго моделируют друг друга, то есть, множества их z-множеств совпадают Z[N]=Z[N`], то будем говорить, что эти классы автоматов строго эквивалентны. Преобразования разделов 2.2-2.4 сохраняют z-множество, что легко проверяется для каждого преобразования; поэтому═ все доказанные выше эквивалентности классов являются также строгими эквивалентностями.

 

Конечную или бесконечную последовательность смежных переходов (следующий переход начинается в том состоянии, в котором заканчивается предыдущий переход) будем называть маршрутом. (Автомату соответствует граф его состояний, в котором вершины √ это состояния, а дуги, раскрашенные стимулами, реакциями или нераскрашенные - это, соответственно,═ принимающие, посылающие или пустые переходы; последовательности смежных переходов соответствует последовательность смежных дуг, то есть, маршрут в графе.) Маршруту P соответствует последовательность стимулов и реакций его непустых переходов, то есть, сериализация, которую будем называть z-раскраской маршрута и обозначать zP; x-подслово xzP будем называть x-раскраской маршрута, а═ y-подслово yzP - y-раскраской маршрута. Выполнению автомата для данного входного слова w соответствует маршрут, начинающийся в начальном состоянии, который мы будем называть маршрутом выполнения; множество таких маршрутов будем обозначать P(w). Маршрут допустимого выполнения будем называть допустимым маршрутом √ это любой маршрут, начинающийся в начальном состоянии и непродолжаемый, то есть, либо бесконечный, либо заканчивающийся в терминальном состоянии; множество вполне-допустимых маршрутов обозначим P^all. Маршрут вполне-допустимого выполнения будем называть вполне-допустимым маршрутом; множество вполне-допустимых маршрутов обозначим P (если нужно указать автомат m, будем писать P[m]).═ Множество их z-раскрасок zP={zP|PÎP} будем называть z-раскраской автомата.

 

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

1)      срабатывание в терминальном состоянии (автомат останавливается);

2)      срабатывание в принимающем состоянии при отсутствии e-переходов и пустом головном стимуле (пустой стимул помещается в сериализацию);

3)      срабатывание с фиксацией ошибки неспецифицированного ввода, когда непустой головной стимул недопустим в текущем состоянии: рецептивном √ для императивных автоматов, и принимающем √ для факультативных автоматов.

 

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

 

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

3.2. Три класса автоматов и z-множеств

3.2.1. Класс автоматов A2, в которых z-раскраска совпадает с z-множеством (каждое нетерминальное срабатывание есть переход)

Рассмотрим подкласс A2ÌA автоматов без смешанных состояний, в которых нет срабатываний типа 2. Это означает, что в таком автомате в каждом принимающем состоянии определен хотя бы один e-переход и тогда каждое нетерминальное срабатывание для допустимого выполнения сопровождается переходом. Поэтому каждый допустимый маршрут как последовательность переходов═ взаимно-однозначно соответствует последовательности нетерминальных срабатываний автомата, z-раскраска маршрута zP совпадает с сериализацией выполнения, а z-раскраска автомата совпадает с его z-множеством Z=zP. При этом для допустимого входного слова wÎDom(W) и маршрута выполнения PÎP(w) имеет место xzP£w и yzPÎW(w).

 

Теорема о срабатываниях и переходах: Класс автоматов A строго моделируется своим подклассом A2.

 

Док-во: От срабатываний типа 2 легко избавиться, если в каждом принимающем состоянии v, в котором не определены e-переходы, добавить e-переход (v,e,v), не изменяющий состояния (петлю). Очевидно, что такие преобразования не изменяют z-множество, а получившийся автомат относится к классу A2.

 

Теорема о срабатываниях и переходах доказана.

 

Следствие: поскольку Z(A)=Z(M), A2ÌA и Z(A)ÍZ(A2), очевидно,═ Z(A2) =Z(M).

3.2.2. Класс автоматов A3, в которых все допустимые маршруты (сериализации) вполне-допустимы

В автомате класса A2, вообще говоря, не все допустимые маршруты являются вполне-допустимыми маршрутами. Рассмотрим подкласс A3ÌA2 автоматов, в которых все допустимые маршруты вполне-допустимы.

 

Теорема о вполне-допустимых маршрутах: Класс автоматов A2 строго моделируется своим подклассом A3.

 

Док-во:═ Пусть задан автомат m=(V,v₀,X,e,Y,T) класса A2; мы построим автомат m`, имеющий то же z-множество и принадлежащий классу A3.

 

Для каждого непустого подмножества состояний HÍV построим y-подавтомат yH, переходы которого - это все переходы, принадлежащие маршрутам в m, начинающимся в состояниях из H и содержащим только посылающие и пустые переходы, а состояния - это состояния инцидентные═ таким переходам (являющиеся их началами и концами). Множество H будем называть множеством входных состоянийy-подавтомата yH. Через tH обозначим множество состояний y-подавтомата, являющихся принимающими в m; это множество состояний y-подавтомата будем называть его множеством выходных состояний. Полученные y-подавтоматы, как подавтоматы одного автомата, имеют общие состояния и переходы. Нам нужно "расклеить" их, превратив в y-автоматы с непересекающимися множествами состояний и переходов. Поэтому для каждого y-подавтомата yH определим соответствующий y-автомат (yH,H), получающийся переименованием состояний: каждое состояние v из y-подавтомата yH в y-автомате (yH,H) обозначим как (v,H).

 

Автомат m` строится как объединение всех y-автоматов автомата m, в которое добавлены дополнительные принимающие переходы следующим способом (рис.3.2.1):

1)      Для каждого y-подавтомата yH и каждого стимула x (пустого или непустого), допустимого в автомате m в каждом выходном состоянии y-подавтомата, определяется множество R(H,x) принимающих переходов, начинающихся в этих выходных состояниях.

2)      Для множества H` концов переходов из R(H,x) рассматривается y-подавтомат yH`.

3)      Для каждого перехода (v,x,v`)ÎR(H,x) в автомате m` добавим переход ((v,H),x,(v`,H`)) из выходного состояния (v,H) y-автомата (yH,H) во входное состояние (v`,H`) y-автомата (yH`,H`).

4)      Начальным состоянием автомата m` объявим состояние (v₀,{v₀}) y-автомата (y{v₀},{v₀}) (соответствующий y-подавтомат порождается одним начальным состоянием {v₀} автомата m).

5)      После этого оставляем в автомате m` только те состояния, которые достижимы из начального состояния (v₀,{v₀}), и только те переходы, которые определены в достижимых состояниях.

 

Рис.3.2.1

 

По построению видно, что автомат m` обладает всеми нужными свойствами.

 

Теорема о допустимых маршрутах доказана.

 

Замечание: На рис. 3.2.1 не показаны e-петли, определенные в каждом принимающем состоянии. С учетом этих петель выделяются еще два y-автомата: (y{2,3},{2,3}) и (y{0,2,3},{0,2,3}), в которых вход совпадает с выходом, во все их состояния ведут e-переходы из всех копий принимающих состояний 0,2,3 во всех y-автоматах и во всех состояниях этих y-графов определены принимающие переходы по стимулу x во входное состояние y-графа (y{0},{0}). В этом автомате существует недопустимый бесконечный маршрут 0¾x╝1,(1¾y₂╝3,3¾x₁╝1)^w (этот маршрут является маршрутом выполнения только для одного слова x(x₁)^w, однако это слово недопустимо, поскольку для него имеется другой маршрут выполнения 0¾x╝1,1¾y₁╝2, заканчивающийся по ошибке неспецифицированного ввода: в состоянии 2 стимул x₁ недопустим).

 

Следствие: поскольку Z(A2)=Z(A)=Z(M), A3ÌA2 и Z(A2)ÍZ(A3), очевидно,═ Z(A3)=Z(M).

═

Выше мы уже говорили, что поскольку автомат с некоторого момента может прекратить выборку стимулов из входной очереди, x-подслово сериализации может не совпадать со входным словом, а являться его начальным отрезком. Теперь мы можем показать, что неравенство xz<w для сериализации z выполнения по некоторому допустимому входному слову w и конечность x-раскраски маршрута PÎP(w), xzP<w носят принципиальный характер. Если выполнение заканчивается в терминальном состоянии v (сериализация и маршрут конечны), то этот случай легко обойти, преобразовав автомат с сохранением словарной функции (правда, без сохранения сериализаций): для этого достаточно сделать состояние v принимающим, определив в нем переходы-петли (v,x`v) для всех стимулов x`ÎX`. Однако, другой случай, когда выполнение бесконечно, но с какого-то момента проходит только через нерецептивные состояния (маршрут бесконечен), обойти не удается. Мы покажем, что для некоторых словарных функций любой реализующий их конечный автомат выбирает из входной очереди лишь конечное число стимулов для некоторых допустимых входных слов.

 

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

 

Док-во: Примером может служить словарная функция автомата класса A3, изображенного на рис. 3.2.2: e^w╝(), e*x(e*x)ⁿe^w╝{y^w,y*y₁ⁿ}, (e*x)^w╝{y^w,y*y₁^w}, где n=0.. - число зависимых повторений - все вхождения n в показателе степени указывают на одно и то же число повторений n, "*" - как обычно, независимое число повторений ноль или более раз.

Рис.3.2.2

 

Допустим, существует автомат, реализующий эту словарную функцию, в котором все вполне-допустимые сериализации имеют бесконечные x-подслова. Тогда, очевидно, существует такой же автомат класса A3, и в нем все допустимые маршруты имеют бесконечные x-подслова. Заметим, что, согласно словарной функции, входное слово x^w может быть отображено в выходное слово y^w. Отсюда следует, что в автомате есть бесконечный допустимый маршрут P такой, что xzP=x^w и yzP=y^w. Тогда существует циклический маршрут C, все переходы которого - это принимающие переходы по стимулу x или посылающие переходы с реакцией y, причем число и тех и других в маршруте C больше нуля. Также должен существовать конечный маршрут N, начинающийся в начальном состоянии и заканчивающийся в начальном состоянии цикла C. В автомате класса A3 в принимающих состояниях определены e-переходы. Пусть такой e-переход определен в состоянии, в котором определен принимающий переход C[i], и пусть E - произвольный маршрут, начинающийся этом состоянии, содержащий только посылающие, пустые и e-переходы (не содержащий x-переходов) и бесконечный или заканчивающийся в терминальном состоянии. Рассмотрим допустимый маршрут P1=N^C^C[1..i-1]^E. В нем, очевидно, конечное ненулевое число принимающих переходов по стимулу x. Тогда, в соответствии со словарной функцией, в нем должно быть конечное число посылающих переходов по реакции y₁; пусть это число равно n. Тогда рассмотрим допустимый маршрут Pn=N^Cⁿ⁺²^C[1..i-1]^E. В нем, очевидно, конечное число N³n+2 принимающих переходов по стимулу x. Очевидно, N-1>n. Тогда, в соответствии со словарной функцией, в нем должно быть N-1 посылающих переходов по реакции y₁, но, поскольку C не содержит y₁-переходов, маршрут Pn должен содержать столько же y₁-переходов, сколько их содержит маршрут P1, то есть, n, чего не может быть, поскольку N-1>n . Мы пришли к противоречию и, тем самым, утверждение доказано.

 

Теорема о конечном x-подслове сериализации доказана.

3.2.3. Класс автоматов A4 с детерминированным z-множеством

Распространим понятие регулярности [7-9] на множества не только конечных, но и бесконечных слов. Пусть задан некоторый алфавит символов A.═ Порождающим графом будем называть граф G с выделенными начальными и конечными вершинами, некоторые дуги которого раскрашены символами из A. Маршрут в графе G имеет раскраску как последовательность раскрасок его раскрашенных дуг (нераскрашенные √ пустые √ дуги пропускаются). Порождающий маршрут √ маршрут, начинающийся в начальной вершине и бесконечный или заканчивающийся в конечной вершине. Будем говорить, что граф G порождает множество раскрасок всех порождающих маршрутов графа. Множество слов H в алфавите A будем называть регулярным, если оно порождается некоторым конечным порождающим графом.

 

Порождающий граф G будем называть детерминированным, если из каждой его вершины выходит не более одной дуги, раскрашенной данным символом из алфавита A. Конечный детерминированный порождающий граф будем называть нормальным, если он имеет одну начальную вершину, не имеет пустых дуг и все вершины достижимы из начальной вершины. Очевидно, в нормальном порождающем графе все порождающие маршруты имеют разные раскраски, то есть, каждое слово из порождаемого множества порождается ровно одним маршрутом. Аналогично случаю регулярных множеств конечных слов, можно сформулировать следующую теорему:

 

Теорема о нормальном порождающем графе: Каждое регулярное множество слов порождается нормальным порождающим графом.

 

Док-во: Пусть задан произвольный конечный порождающий граф G; мы построим нормальный порождающий граф G`, порождающий то же множество слов. Прием его построения похож на соответствующий прием для порождающих графов регулярных множество конечных слов [7,9].

 

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

 

Этап 2. Далее вершинами графа G` объявим все непустые подмножества вершин графа G. Для каждого подмножества вершин U и каждого символ a рассмотрим конечный маршрут, начинающийся в некоторой вершине из U, все дуги которого нераскрашены, кроме одной, раскрашенной символом a. Если такие маршруты есть и H √ множество их концов, то проведем дугу (U,x,H) из U в H раскрашенную символом a. Начальной вершиной графа G` объявим множество всех начальных вершин графа G. Конечными вершинами графа G` объявим все множества, содержащие хотя бы одну конечную вершину графа G. После этого удалим из G` все его вершины, недостижимые из начальной, и все инцидентные им дуги. Полученный граф является нормальным по построению (рис. 3.2.3).

 

Рис.3.2.3

Поскольку дуге (U,a,H) графа G` взаимно-однозначно соответствует непустое множество всех конечных маршрутов графа G, начинающихся в вершинах из U и имеющих раскраску (a), то и любому маршруту P` графа G`, начинающемуся в вершине U взаимно-однозначно соответствует непустое множество всех маршрутов графа G, начинающихся в вершинах из U и имеющих такую же раскраску, что и P`. Поскольку начальная вершина G` есть множество начальных вершин G, а конечная вершина G` содержит конечную вершину графа G (включая добавленные на этапе 1), порождающему маршруту графа G`, очевидно, взаимно-однозначно соответствует непустое множество всех порождающих маршрутов графа G, имеющих ту же раскраску.

 

Теорема о нормальном порождающем графе доказана.

 

В автомате класса A3 все допустимые маршруты вполне-допустимы. Поэтому, если в графе состояний такого автомата конечными вершинами объявить терминальные вершины, то такой граф является порождающим графом в объединенном алфавите стимулов (включая пустой стимул) и реакций X`ÈY, а порождаемое им регулярное множество является z-множеством автомата. Однако, в общем случае, этот порождающий граф недетерминирован, то есть, может существовать несколько разных допустимых маршрутов, имеющих одну и ту же z-раскраску. Заметим, что детерминированность графа состояний как порождающего графа вовсе не означает детерминированности автомата: все принимающие переходы, определенные в данном состоянии, отличаются стимулами и поэтому при данном головном стимуле возможен только один принимающий переход; однако, хотя все посылающие переходы, определенные в данном состоянии, отличаются реакциями, допустим любой из них и выбор посылающего перехода, то есть, посылаемой реакции, по-прежнему недетерминирован. Классом A4ÌA3 назовем подкласс, в котором все допустимые маршруты имеют уникальные z-раскраски, то есть, граф состояний которого является детерминированным порождающим графом. Будем говорить, что такие автоматы - это автоматы с детерминированным z-множеством. Более строго, следовало бы говорить о мульти-множестве сериализаций (маршрутов) √ множестве с повторяющимися элементами, где каждая сериализация (раскраска маршрута) повторяется столько раз, скольким выполнениям (маршрутам) она соответствует; детерминированное мультимножество √ это обычное множество, где каждый элемент повторяется один раз.

 

Теорема о детерминированном z-множестве: Каждый автомат класса A3 строго моделируется некоторым автоматом класса A4.

 

Док-во: Пусть задан автомат m класса A3, мы построим автомат m`, имеющий ту же z-раскраску и принадлежащий классу A4.

 

Этап 1. Граф состояний автомата m можно рассматривать как порождающий граф, конечными вершинами которого являются терминальные состояния. Заметим, что порождающие маршруты совпадают в этом случае с допустимыми маршрутами. Для этого графа построим нормальный порождающий граф.

 

Этап 2. В полученном графе могут появиться конечные вершины, не являющиеся терминальными. Чтобы избавиться от них, из каждой такой вершины v проведем пустую дугу в какую-нибудь терминальную вершину (если таких нет, добавим новую терминальную вершину) и объявим вершину v не конечной. Очевидно, порождаемое множество от этого не изменится, а граф останется детерминированным порождающим графом (хотя уже и не нормальным).

 

Этап 3. В полученном графе могут быть смешанные вершины. Чтобы избавиться от них, для каждой смешанной вершины v добавим новую вершину v₁ и пустую дугу (v, v₁), а каждую принимающую дугу, ведущую из v, (v,x,v`), где xÎX`, заменим на принимающую дугу из v₁ - (v₁,x,v`). Вершина v будет теперь посылающей, а вершина v₁ - принимающей (рис.3.2.4). Раскраски маршрутов, очевидно, не изменились (добавленные пустые дуги не участвуют в раскраске маршрута) и граф остался детерминированным порождающим графом.

═

Рис.3.2.4

 

Этот граф будем считать графом состояний автомата m`. По построению он относится к классу A2 (нет смешанных состояний и в каждом принимающем состоянии определен e-переход, поскольку так было в m). По построению, множествам всех одинаково раскрашенных допустимых маршрутов в m взаимно-однозначно соответствуют так же раскрашенные допустимые маршруты в m`, то есть,═ Z^all[m`]= Z<sup>all</sup>[m]. Поскольку m относится к классу A3, в нем все допустимые маршруты вполне-допустимы Z[m]=C<Z<sup>all</sup>[m]>=Z<sup>all</sup>[m], поэтому Z[m`]=C<Z^all[m`]>=С<Z<sup>all</sup>[m]>=Z<sup>all</sup>[m`] и Z[m`]=Z[m], то есть, автомат m` тоже относится к классу A3 и имеет то же z-множество, что m. Из детерминизма порождающего графа следует детерминированность z-множества в m`, то есть, m` относится к классу A4.

═

Теорема о детерминированном z-множестве доказана.

3.3. Автоматные множества сериализаций, распознающие и отвергающие автоматы.

Множество S сериализаций будем называть автоматным, если оно является z-множеством некоторого автомата. Выше уже показано, что автоматное множество регулярно, и для того, чтобы регулярное множество было автоматным, нужно, чтобы оно было замкнуто по вполне-допустимости C<S> = S и любой начальный отрезок сериализации, продолжаемый в ней стимулом, мог быть также продолжен═ пустым стимулом (допустимость пустых стимулов во всех рецептивных состояниях). Таким образом, мы имеем следующую теорему.

 

Теорема об автоматности множества сериализаций: Необходимым и достаточным условием автоматности множества S сериализаций является выполнение следующих трех требований:

╥        Регулярность: Множество S регулярно.

╥        Допустимость x-подслов: Все x-подслова сериализаций из S допустимы в S, что эквивалентно замкнутости S по вполне-допустимости C<S> = S.

╥        Допустимость пустого стимула: Для любой сериализации zÎS═ любой ее начальный отрезок u<z, непосредственно предшествующий стимулу z[nu+1]ÎX`, где nu √ длина u, может быть продолжен пустым стимулом, то есть, существует z`ÎS такая, что ue<z`.

 

С точки зрения тестирования, представляет интерес вопрос: существует ли автомат, который, имея во входной очереди сериализацию, определяет, может или не может она принадлежать z-множеству заданного автомата. Поскольку речь идет не только о конечных, но и о бесконечных словах, мы в общем случае не можем говорить о распознающих автоматах, то есть, автоматах, которые определяли бы принадлежность слова множеству за конечное число шагов, то есть, по его начальному отрезку конечной длины. Например, автомат на рис.3.3.2 имеет сериализацию xy^wÎZ, каждый начальный отрезок которой xyⁿ является начальным отрезком сериализации xyⁿy₁^wÏZ. Заметим, что для множеств конечных слов распознаваемость совпадает с регулярностью: по нормальному порождающему графу легко построить граф состояний распознающего автомата, а по графу состояний распознающего автомата √ порождающий граф.

 

Рис.3.3.2

 

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

 

Будем говорить, что автомат m является отвергающим автоматом для множества слов S в алфавите A, если

╥        алфавит стимулов автомата m - это алфавит A;

╥        алфавит реакций состоит из одной реакции "не принадлежит";

╥        для каждого слова zÎS автомат m выдает единственное пустое выходное слово,

╥        для каждого слова zÏS автомат m выдает единственное выходное слово, состоящее из одной реакции "не принадлежит".

 

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

 

Теорема об отвергающем автомате: Множество слов регулярно тогда и только тогда, когда для него существует нормальный отвергающий автомат.

 

Док-во: По нормальному порождающему графу регулярного множества слов H в алфавите A можно построить граф состояний нормального отвергающего автомата для H:

╥        алфавитом стимулов объявляется алфавит A;

╥        алфавитом реакций объявляется множество из одной реакции "не принадлежит";

╥        начальным состоянием объявляется состояние автомата, соответствующее начальной вершине порождающего графа;

╥        добавляются два состояния t и t` и посылающий переход из t в t` с реакцией "не принадлежит";

╥        если из какой-то вершины v порождающего графа не выходит дуга, помеченная некоторым символом a из A, в соответствующем состоянии v автомата определим принимающий переход по стимулу a в состояние t, то есть, переход (v,a,t).

 

Наоборот, если задан нормальный отвергающий автомат для множества слов H в алфавите A, то по его графу состояний можно построить нормальный порождающий граф для множества H. В графе состояний автомата выполним следующие преобразования:

╥        удаляются вершины, являющиеся началами посылающих дуг с реакцией "не принадлежит", и все инцидентные им дуги;

╥        если при этом образуются новые терминальные вершины, то эти вершины удаляются═ вместе с инцидентными им дугами (старые терминальные вершины остаются) - это повторяется до тех пор, пока остаются новые терминальные вершины;

╥        удаляются все вершины, не достижимые из начальной вершины, и все дуги им инцидентные.

 

Теорема об отвергающем автомате доказана.

 

Для словарной функции W═ можно говорить об отвергающем автомате, который имеет две входные очереди, в которые помещаются входное слово w и выходное слово u, и одну выходную очередь, в которую автомат должен поместить вердикт "не принадлежит", если wÏDom(W) или uÏW(w), а в противном случае - ничего. Если для словарной функции существует такой отвергающий автомат, будем называть ее регулярной. Можно сформулировать следующие нерешенные задачи:

1.      Всякая ли автоматная словарная функция (быть может, с некоторыми дополнительными условиями) регулярна?

2.      Всякая ли регулярная словарная функция (быть может, с некоторыми дополнительными условиями) автоматна?

3.4. Квази-конечные сужения словарной функции и z-множества

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

 

Квази-конечным сужением словарной функции W будем называть функцию W|_F, определенную только на квази-конечных входных словах:

╥        Dom(W|_F) = (X`^*^{e^w})ÇDom(W)

╥        "wÎDom(W|_F) W|_F(w)=W(w)

 

Соответственно, квази-конечным сужением множества сериализацийS (в частности, z-множества автомата Z) будем называть его подмножество S|_F, содержащее только такие сериализации, x-подслова которых конечны или квази-конечны. Для произвольного множества слов U через U[] будем обозначать множество начальных отрезков конечной длины слов из U; это множество будем называть конечным сужением множестваU.

 

Прежде всего, зададимся вопросом: однозначно ли определяется словарная функция автомата по ее квази-конечному сужению?

 

Ответ на этот вопрос отрицательный. Пример приведен на рис.3.4.1.═ Для двух автоматов 1 и 2 значение словарной функции на всех допустимых квази-конечных словах одно и то же √ реакция y. Однако, полные словарные функции (на всех бесконечных словах)═ автоматов 1 и 2 различаются: при непрерывной (без пустых стимулов) подаче на автомат стимула x, автомат 1 ничего не выдает (пустое выходное слово), а автомат 2 по-прежнему выдает реакцию y.