Документ взят из кэша поисковой машины. Адрес оригинального документа : http://www.intsys.msu.ru/magazine/archive/v2(1-4)/grunskiy.pdf Дата изменения: Fri Nov 7 11:27:06 2008 Дата индексирования: Mon Oct 1 23:27:05 2012 Кодировка: Windows-1251

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

Проблема представления (идентификации) автоматов их фрагментами является важной как в теории автоматов (построение контрольных и распознающих экспериментов [1]), так и в технической диагностике дискретных устройств [2] и программных систем [3]. Теория представления автоматов фрагментами изложена в [4]. Одной из центральных задач этой теории является задача определения условий, при которых фрагмент представляет заданный автомат с заданной точностью относительно заданного класса автоматов. В [4] приведены критерии (необходимые и достаточные условия) представления для различного типа автоматов, различных конечных классов и различной точности. В настоящее время интенсивно начала развиваться теория экспериментов относительно бесконечных классов автоматов, заданных финитными средствами (формальной спецификацией [3] , недетерминированным автоматом [5] и т.п.). В данной работе исследуется структура представлений автомата относительно возможно бесконечного класса автоматов, в каждом из которых каждый вход-выходной сигнал из заранее заданного множества порождается не более чем одним состоянием [6]. Такие сигналы называются маркерами, а такие автоматы маркированными. Маркеры с точки зрения книги [4] являются идентификаторами состояний. Они присутствуют в реальных автоматах в виде оповещающих или служебных управляющих сигналов. Найдены критерии, при которых фрагмент является представлением автомата относительно класса маркированных автоматов (теоремы 24) и относительно дополнения до этого класса (теорема 1). В следствиях 249


к теоремам предложены условия существования контрольных экспериментов. В дальнейшем под автоматом понимается, если не оговорено противное, конечный детерминированный инициальный автомат Мили. Все автоматы имеют один и тот же входной X и выходной Y алфавиты. Если автомат частичен, то полагаем, что области определения его функции переходов и функции выходов совпадают. Пусть r мощность алфавита Y , r 1. Пусть A = (A, X, Y , , , a0 ) некоторый автомат, у которого A множество состояний мощности n; a0 начальное состояние; , функции переходов и выходов. Пусть p = x1 ...xk входное слово. Через (a, p) обозначим состояние, в которое переходит автомат из состояния a под действием этого слова, а через (a, p) соответствующее выходное слово длины k . Пусть (a, p) = q = y1 ...yk . Пара (p, q ) называется входвыходным словом, порожденным состоянием a. Она отождествляется со словом w = (x1 , y1 )...(xk , yk ) в алфавите U = X Ч Y . Равенство aw = b означает, что b = (a, p) и (a, p) = q . Множество всех вход-выходных слов, порожденных состоянием a обозначим a и A при a = a0 . Автомаa всех вход-выходных ту A поставим в соответствие множество A = слов, порожденных этим автоматом. Автомат A называется инициально связным, если для всех его состояний a найдется w A , для которого a0 w = a. В дальнейшем, если не оговорено противное, рассматриваются инициально связные автоматы. Состояние a и b называются эквивалентными, что обозначим (a, b) , если a = b . Через A/ обозначим автомат, полученный из A отождествлением всех эквивалентных состояний. Автомат A, для которого A = A/, называется приведенным. Через A(U ) обозначим класс всех всюду определенных приведенных автоматов. Неопределяемые понятия теории автоматов общеприняты и их можно найти, например, в [1,4]. При необходимости функции параметры и поведение автомата снабжаются нижним индексом его именем. Введем понятие представления автомата фрагментами. Пусть Q = (Q, X, Y , , , q0 ) некоторый автомат. Автомат Q назовем фрагментом автомата A, если существует гомоморфизм автомата Q в A, т.е. такое отображение : Q A, что (q0 ) = a0 и ((q , x)) = ((q ), x), (q , x) = ((q ), x) для всех q и x из области определения функции . Зафиксируем произвольно автомат-эталон A A(U ) и подкласс A A(U ). Автомат Q назовем представлением эталона относительно этого подкласса, если одновременно выполняются условия: 1. Q является 250
aA


фрагментом эталона; 2. если Q является фрагментом автомата B A, то A = B . Из определения вытекает, что эталон A является представлением самого себя относительно любого подкласса A и поэтому представления всегда существуют. Рассмотрим условия, при которых автомат Q является представлением A относительно подкласса A. Если в A нет автоматов, отличных от A, т.е. если A пуст или состоит из одного A, то любой фрагмент эталона является представлением. Поэтому в дальнейшем полагаем, что в A существует автомат B = A. Тогда r 2, поскольку при r = 1 класс A(U ) состоит из одного автомата. Пусть B некоторый автомат и b некоторое его состояние. Автомат C , образованный всеми состояниями c = bw, w B , называется подавтоматом, порожденным состоянием b. Класс A назовем замкнутым, если для всех B A(U ) как только некоторый его подавтомат входит в A, то и B A. Легко видеть, что для r 2 непустой замкнутый класс бесконечен. Теорема 1. Автомат Q является представлением эталона A A(U ) относительно замкнутого подкласса A тогда и только тогда, когда Q/ = A. Д о к а з а т е л ь с т в о. Если Q/ = A, то очевидно Q фрагмент эталона. Пусть Q фрагмент некоторого B A. В силу приведенности автомата B Q/ тоже его фрагмент. В силу инициальной связности A = B и, тем самым, Q представление. Пусть теперь Q/ = A и Q представление эталона относительно A. Тогда Q фрагмент эталона и, следовательно, частичный автомат. Пусть C A. Доопределим автомат Q с помощью C , полагая (q , x) = c0 для всех пар (q , x), не входящих в область определения функции . Функцию выходов доопределяем произвольно. Получим всюду определенный автомат D. Пусть H A и H = C . Точно также доопределяем автомат Q с помощью H и получаем автомат G. Так как H = C , то C (c0 , p) = H (h0 , p) для некоторого входного слова p. Пусть (q , x) неопределено в Q и (q0 , p ) = b. Очевидно D (d0 , p xp) = G (g0 , p xp). Поэтому D/ = G/. Автомат Q является фрагментом автоматов D/ и G/ и оба эти автомата входят в A. Следовательно, Q не представление, что противоречит предположению. Теорема 1 доказана. Контрольным экспериментом для эталона A относительно A называется конечное подмножество W A , для которого W B , где B A, влечет A = B . Любому конечному множеству W A очевидным образом взаимно однозначно соответствует автомат Q, граф которого является деревом, Q = W . Ясно, что если W контрольный эксперимент, то Q представление. Поэтому, контрольный эксперимент считаем 251


частным видом представлений. Из сказанного и теоремы 1 вытекает Следствие 1. Не существует контрольных экспериментов для любого A A(U ) относительно любого замкнутого A A(U ). Поскольку A(U ) замкнут, то для него выполняются теорема 1 и следствие 1. Рассмотрим классы автоматов, введенные в [6]. Зафиксируем множество M U . Через A(U, M ) обозначим класс всех тех автоматов из A(U ), для которых каждое вход-выходное слово u M порождается не более чем одним состоянием. Элементы u M называем маркерами. Состояние a автомата A A(U, M ), порождающее некоторый маркер, назовем отмеченным (маркированным). Пусть A(U, M ) = A(U ) - A(U, M ). Автомат принадлежит дополнению A(U, M ), если в нем существуют два неэквивалентных состояния, порождающие один и тот же маркер. Поэтому непустое дополнение является замкнутым классом и теорема 1 дает критерий, при котором фрагмент Q является представлением для A A(U ) и A = A(U, M ). Следствие 1 показывает, что в этом случае контрольные эксперименты не существуют. Рассмотрим случай, когда A = A(U, M ). Для всех M класс A не пуст и при пустом M совпадает с A(U ). В [6] найдены критерии бесконечности, конечности и одноэлементности класса A. Пусть A A(U, M ). Пусть Q некоторый, возможно частичный, автомат. Через [Q] обозначим автомат, полученный из Q, отождествлением всех состояний, порождающих один и тот же маркер и дальнейшей детерминизацией: если q u = q1 и q u = q2 для некоторого u, то отождествляем состояния q1 и q2 . При этом может быть два случая. Если Q фрагмент некоторого автомата C A(U, M ), то [Q] детерминированный автомат и фрагмент автомата C . В противном случае, B = [Q] недетерминированный, т.е. для некоторого его состояния b и входа x найдутся такие состояния b1 , b2 и выходы y1 , y2 , y1 = y2 , что b(x, y1 ) = b1 = b(x, y2 ) = b2 . Автомат [Q] назовем замыканием Q по маркерам. Через M x обозначим подмножество всех тех маркеров u, для которых u = (x, y ), y Y , а через rx мощность этого подмножества. Рассмотрим случай A A(U, M ). Рассмотрим некоторый фрагмент Q эталона. Состояния q и h этого фрагмента называются совместимыми, если для любого входного слова p как только Q (q , p) и Q (h, p) определены, то они равны. Пусть отношение совместимости состояний фрагмента. Известно, что гомоморфизм фрагмента Q в автомат из A(U ) порождает на состояниях фрагмента конгруентность по правилу: (q , h) , если (q ) = (h), и наоборот всякая конгруентность на состояниях фрагмента порождает гомоморфизм его в некоторый автомат из A(U ). Пусть rank число 252


классов эквивалентности конгруентности . Теорема 2. Пусть n < r или rx < r для всех x. Автомат Q является представлением эталона A A(U, M ) относительно A(U, M ) тогда и только тогда, когда [Q]/ = A. Д о к а з а т е л ь с т в о. Если последнее равенство выполняется, то Q фрагмент эталона. Если Q фрагмент некоторого автомата B A, то A фрагмент этого автомата и A = B . Поэтому Q представление. Пусть B = [Q], B / = A и Q представление эталона относительно A. Тогда B фрагмент эталона и частичный автомат. Доопределим его полагая B (b, x) = b для всех (b, x), не входящих в область определения. Пусть n < r. Тогда для каждого фиксированного x и любого b, для которого B (b, x) не определено, можно выбрать свой особый yb Y и положить B (b, x) = yb так, чтобы (x, yb ) порождалось только этим состоянием. Полученный всюду определенный автомат обозначим C . Рассмотрим автомат D = C /. Если D = A, то, учитывая, что B фрагмент D, получаем, что B , а,значит, и Q не представление. Если D = A, то зафиксируем пару (b, x), для которой B (b, x) не определено. По построению состояние b в автомате C не имеет эквивалентных. Тогда в автомате D дугу (d, (x, yb ), h) заменяем дугой (d, (x, y ), h), где (x, y ) A . В силу n < r такая пара (x, y ) существует. Полученный автомат обозначим H . По построению B фрагмент автомата H/. Этот автомат отличен от A, входит в A и, следовательно, B не может быть представлением. Поэтому и Q не представление. Пусть теперь rx < r для всех x и n = r 2. Покажем, что в автомате B существуют такие состояния b1 , b2 и входной символ x , что B (b1 , x ) = B (b2 , x ). Если эти состояния и вход x не существуют, то что все состояния автомата B являются совместимыми, является конгруенцией и B / имеет одно состояние. Если B / частичен, то доопределяем его полагая b(x, y ) = b, где b единственное его состояние, (x, y ) M и (b, x) не входит в область определения функций этого автомата. Получаем, что доопределенный в случае необходимости автомат B / отличен от A, входит в A(U, M ) и, поэтому, B не может быть представлением. Поэтому вышеуказанные состояния в B существуют. Доопределим автомат B двумя способами. Сначала, если B (b, x) не определено, то полагаем b(x, y ) = b1 , где (x, y ) M . В силу неравенства rx < r такая пара существует. Полученный автомат обозначим C . Затем, если B (b, x) не определено, то полагаем b(x, y ) = b2 , где (x, y ) M . Полученный автомат обозначим D. Если B (b0 , p) = b и B (b, x) не определено, то по построению C (b0 , pxx ) = D (b0 , pxx ). Поэтому C = D, C / и D/ входят в A(U, M ) и B фрагмент этих автоматов. Поэтому B не представление. Теорема 2 доказана. 253


Рассмотрим случай, когда условие теоремы 2 не выполняется, т.е. n r и rx = r для некоторого x. Тогда у любого автомата из A(U, M ) имеется не более чем r состояний, этот класс конечен и n = r. Пусть 1 = Q U . Q Теорема 3. Пусть r = n и rx = r для некоторого x. Автомат Q является представлением эталона A относительно A(U, M ) тогда и только тогда, когда одновременно выполняются условия: 1. Q фрагмент эталона, 2. 1 = 1 , Q A 3. на состояниях фрагмента [Q] существует конгруентность с rank = n. Д о к а з а т е л ь с т в о. Пусть для фрагмента Q выполняются условия 13. Пусть Q фрагмент некоторого автомата B A(U, M ). Так как rx = r для некоторого x, то nB r. Условие 2 влечет равенство nB = n0 . Поскольку B A(U, M ), то [Q] тоже фрагмент B . Из условия 3 вытекает, что A = B . Следовательно, Q представление. Пусть Q представление эталона относительно A(U, M ). Покажем, что выполняются условия 13. Поскольку Q представление, то 1 выполняется. Пусть 2 не выполняется. В силу условия 1 1 A и существует Q u A - Q . Пусть au = b. По предположению n = r 2. Преобразуем эталон полагая au = d, где d = b. В силу леммы 3.2.14 из [4] получаем автомат B не равный эталону, B / A(U, M ), B / = A и, значит, Q не представление. Следовательно, условие 2 выполняется. Пусть теперь не выполняется условие 3 и, кроме конгруентности , порожденной гомоморфизмом фрагмента Q в эталон, существует другая конгруентность , причем rank = rank = n. Так как = n, то [Q]/ = A = B = [Q]/ . Если B всюду определен, то B / входит в A(U, M ), отличен от A и, следовательно, Q не представление. Пусть автомат B частичен. По условию 2 и определению B 1 A 1 B . Поскольку n = r = rx для некоторого x, то nB = n. Пусть B (b, x) не определено для некоторого x. В силу последнего включения, эталон может порождать не более n - 1 пар вида (x, y ), где y Y . Следовательно, существует (x, y ) U - 1 . Полагаем b(x, y ) = b. Таким способом автоA мат B можно преобразовать во всюду определенный автомат C . Фрагмент [Q] инициально связен, поэтому инициально связны автоматы B и C . В автомате Q каждый маркер из M порождается не более чем одним состоянием. Так как nB = r, то автомат B преобразовать в C можно таким образом, что в C каждый маркер порождается не более чем одним состоянием. По построению A = C . Следовательно, автомат C /, отличен от эталона, входит в A(U, M ). Поэтому Q не представление, что противоречит предположению. Отсюда вытекает, что 3 выполняется. 254


Теорема доказана. Теоремы 2 и 3 вместе дают критерий, при котором фрагмент Q является представлением эталона A A(U, M ) относительно A(U, M ). Следствие 2.[6] Контрольный эксперимент для A A(U, M ) относительно A(U, M ) существует тогда и только тогда, когда в каждом цикле графа эталона имеется отмеченное состояние. Д о к а з а т е л ь с т в о. Пусть в каждом цикле эталона имеется отмеченное состояние. Рассмотрим множество W всех слов из A длины 2n и соответствующий ему древовидный автомат Q с Q = W . В Q каждое состояние q либо является висячим, либо Q (q , x) определено для всех x. Пусть q висячее и q0 w = q . Тогда найдутся такие слова w1 , w2 , что w = w1 , w2 , состояние a = a0 w1 эталона отмечено, слово w2 не пусто и его длина не превосходит n. Кроме того a0 w3 = a для некоторого слова w3 длины не большей n - 1. Состояние q0 w3 и q0 w1 порождают один и тот же маркер, Q (q0 w3 , p) определено для всех входных слов p длины n + 1. Поэтому в Q состояние q0 w3 и q отождествляются и состояние, соответствующее состоянию q висячим не является. Поэтому автомат [Q] всюду определен и [Q]/ = A. В силу теорем 2 и 3 фрагмент Q является представлением. Пусть теперь в эталоне имеется цикл, не содержащий отмеченных состояний, т.е. a0 w1 = a и aw2 = a, для некоторых w1 и непустого w2 , а для всех начальных отрезков w слова w2 состояние aw не отмечено. Следовательно, для всех x rx < r, т.е. выполняется условие теоремы 2. Зафиксируем произвольно натуральное k 1 и пусть l = d1 + k d2 , где di длина слова wi для i = 1, 2 . Рассмотрим множество Wk всех слов из A длины l и соответствующий ему фрагмент Q. Из сказанного k выше следует, что в замыкании B = [Q] состояние b = b0 w1 w2 является висячим. Поэтому автомат [Q]/ имеет висячее состояние и не равен эталону. Тогда, в силу теоремы 2, фрагмент Q не является представлением. Следовательно, для всех k 1 множество Wk контрольным экспериментом не является. Поэтому контрольных экспериментов не существует. Следствие доказано. Рассмотрим случай, когда A A(U, M ) и A = A(U, M ). Теорема 4. Фрагмент Q является представлением эталона относительно A тогда и только тогда, когда Q фрагмент эталона и выполняется хоть одно из условий: 1. [Q] является недетерминированным автоматом; 2. rx = r и замыкание недоопределено по x для некоторого x и для всех конгруенций на состояниях замыкания rank > r. Д о к а з а т е л ь с т в о. Пусть Q фрагмент эталона и выполняется условие 1. Из определения замыкания по маркерам следует, 255


что если [Q] недетерминировано, то в Q существуют состояния q1 , q2 , порождающие один и тот же маркер, и входное слово p, для которого Q (q1 , p) = Q (q2 , p). Следовательно, эти состояния несовместимы и для любого гомоморфизма фрагмента Q в автомат B A(U ) состояния (q1 ), (q2 ) порождают один и тот же маркер и не эквивалентны. Поэтому B A(U, M ) и Q представление. Пусть выполняется условие 2. Предположим, что Q не представление, т.е. Q фрагмент некоторого автомата B A(U, M ), отличного от эталона. Тогда существует гомоморфизм этого фрагмента в B . По условию 2 для некоторого входа x rx = r и [Q] недоопределен по x. Тогда nB = r и для соответствующей гомоморфизму конгруенции rank = r, что противоречит условию 2. Из противоречия следует, что Q представление. Пусть теперь Q представление. Ясно, что Q фрагмент эталона. Покажем, что выполняется хоть одно из условий 1, 2. Предположим противное, что оба этих условия не выполняются. Тогда замыкание B = [Q] является детерминированным автоматом. Если B всюду определен, то B / A(U, M ) и Q не представление. Пусть B частичен и B (b, x) не определено. Если rx < r, то существует (x, y ) M . Полагаем b(x, y ) = b. Таким образом доопределим B и получаем всюду определенный автомат C , для которого C / A(U, M ). Тогда Q не представление. Если же существует конгруентность , для которой rank R, то автомат C = B / имеет не более r состояний. Поэтому, если C недоопределен по x, то для каждого его состояния c можно выбрать свою особую пару (x, y ) и положить c(x, y ) = c. Получим всюду определенный автомат D, для которого D/ A(U, M ) и B фрагмент D/. Поэтому Q не представление, что противоречит предположению. Теорема 4 доказана. Теоремы 42 дают критерий, при котором фрагмент является представлением эталона A A(U ) относительно A(U, M ). Из теоремы 4 следует, что для A A(U, M ) относительно A(U, M ) контрольный эксперимент всегда существует. Действительно, так как A A (U, M ), то в нем существуют состояния a1 , a2 , порождающие один и тот же маркер u и (a1 , p) = q1 = q2 = (a2 , p). Пусть a1 = a0 w1 и a2 = a0 w2 . Тогда легко видеть, что 4 слова {w1 u, w1 (p, q1 ), w2 u, w2 (p, q2 )} являются контрольным экспериментом.

Список литературы
[1] В.Б. Кудрявцев, С.В. Алешин, А.С. Подколзин. Введение в теорию автоматов М.: Наука 1985. 320 с 256


[2] Основы технической диагностики /Под ред. П.П. Пархоменко М.: Энергия 1976. 464 с [3] Протоколы информационно-вычислительных сетей: Справочник /Под ред. И.А. Мизина, А.П. Кулешова М.: Радио и связь 1990. 504 с [4] И.С. Грунский, В.А. Козловский, Г.Г. Пономаренко. Представления конечных автоматов фрагментами поведения Киев:Наукова думка 1990.232c [5] Б.Д. Лукьянов. О различающих и контрольных экспериментах с недетерминированными автоматами //Кибернетика и системный анализ. (1995) с.6976 [6] Грунский И.С., Максименко И.И. Об экспериментах с автоматами при отсутуствии верхней оценки числа состояний //Доповiдi НАН Украни. (1996) с.3135

257