О некоторых свойствах траекторий автоматов в лабиринтах тема автореферата и диссертации по математике, 01.01.09 ВАК РФ

\uv

, v\j И

Л МОСКОВСКИЙ ГОСУДАРСТВЕННЫЙ УШШНРСзГГЕТ им. М.З.ЛОМОЫОСОВЛ

ГРУ НС КАЯ Зера Игорезна

I шштш. ШШЕЖ ШЕЗШЙ Й111МЙТ011 ЙШШШМ

<01.01.09 - математическая кибернетика)

Москвй - 1994

. Работа jsKnaaeus'Eb каЗегш кзтеквПкескоЁ KEScIHSTBKE с-ач^тьтеха шзаоягаедьног мамиегш! и • кзбзвзентЕкк псковского тогудатетьонного 5шшекЕ?ета им&зк 1».В.Лс«;оносоЕа.

Научна DTKOßuEBSöSb: гоктоп бЕзгко-мгггказ&ззскг: ватк.

• швшвосов.. вкалвшж iSK-pooezE В-Б.Кгаашог.

Свояшшге отзаат: жйирсф ткшгтаенах нате.

шзоФэсооо А.Б. Фтхжв. . .. кашка? вазяксьшгшгатач&асз. нгук. научий сотэшш-Е.А.АкЕсгеЗ'ШС.' •

Веадав «¡т&ннзаагя: Са&аговсг22 гоа-дарагБвкай знаавгеито?.

Sasvra еестостся " i5 " • ?995 г. в "//." часов на

зЕ^гдажа • Creas3jasKB3B^H-3n> • 'совета '21.053.00.33 в Вй02кж1«ш rcci'WKïsesK&i хвпдохяэде ша. й.5.Лс*ззосоза ао asseçy: 11Э39&.' ИоекБа» Воробьевы рови. МГУ.. факультет ШЯЕ. ауд.- .

.С- дассекацтей »оако ознакомься в асйистехо ¿¿етьила КЖ

КГ/. \ .. •. ... ;

'¿BTOWüréiií тзазоплан."*^7" 19S5 г.

ï'jGîuSl сеглзбтазь . ■ . еглл^шзззопгшоги соаега, rr-icccoap

I 0ЭД4Я ГСЛРАКТЕРЖЖта-РАБОТЫ.'. ■

Актуальность темы. Конечные автомату квдзагпя. -одтам ла глазных объектов математлтаскоа яйегнетаки. СлгсЗ '-з чентральннх проблем теории-'. автоматов. •• является ггсссеу*. взаимсдейстзая конечны! автскйтзв с рагдгапгя шьи ч частности, с деСирйнтгмн СМ. Основное знгмяаге пгт .«у-гек-гл зззимояействяя автомата с дзоярзштааги уделяетст зозаоявсстеа -автомата лет достагеняв- яекстсрсй ¿даяг ■■. лабщизте. 3 этом • направлении. зйапвя -из рсо'дть'гзгд?., нредегззлвнннх- в састемагаческсас- шше з обзеве • (21 ■ . Нзг^агс ззаамодэйотзня основана- на- хзучвили. еледзБ-П'згг.тс-гг.: автоматов в лабипантзх я. сспряено-- и ' -зкз трудностями,. определяемая! разнообразием -ЗКинисазрсзаакл автоматов и гэометрией лабиринтов- Поэтому; важной задачей з этом изучении является задача харахтещгзшга <нок&ста траекторий автомата в бэзевщ отандартящ классах лзбкрдаг.ш :т сравнение автоматов з- соответствии с. эти множествами.

Сравнение автоматов до поведении. то.- есть ас етсаеотву •. вход-выходках последовательностей,.. зорезсабмьх азтсматзмг. является: второй центральной' проблемой- теоршг" автоматов. 3 случае, когда в качестве среда,'выступает экслзпешнтзтор. зга Задача в основном решена Яурш-ГЗ}: Окончательные'- решектл этой з адачз птзэдатзЕленн з С4].. Существует" естеотвенное-ззашо-шознатазе соответствие «е«цу трэектогаямя автомата - з лаоиринте- я шожаствачя. зхзд-зыхедзнг- глоз," торозиаемкх автоматом шж ЕШС.ЯН5ЯИЯ зтой траектории. . '

В кастояшзЯ работе изучается задача «уносящаяся ж обеим -■вшеуказакнкм проблемам,. а именно, задача характоризации-траекторий петомэтз.при взалирдегстЕии с базовыми плоскими, лаОЕринташ (дзеты, квадраты, аряшутольншш и же эстеотаенное обсиаечге) дутем характ$ризащш ссотЕетсвущих. множеств " зход-зшшых слов, а также задача -сравнения автоматов .го даовзствам. таких слов»

Цель работы. Охарактеризовать структуру . множества вход-выходных последовательностей, порекдаэмых автоматом , при взаимодействии с каждым из слэдупиг классов плселях лабяпинтоз-без дар: классом- о всех лен?, ашринн - одна. и. произвольной конечной.дляен,классом о11 всех лент фиксированной шгяян 1г..

г произвольной., конечной длины, классом :< всех конечных квадратов, классом т есзх конечных прямоугольников» классам- г ' лабиринтов,, представляшаг собой:.яомпозишт.'специального вида лабиринтов из классов о.с11,*,?- (Эти классы являются базовыми и ггоззеляззт ашроксииировать произвольные лабиринта. отражая ж некоторые основные свойства.) Изучить свойства отношения эквивалентности и предаорядкз автоматов (по ' множествам этих последовательностей), -определить ■ условия , конструктивной проз ерш наличия, этих отношений.

Методы исследований. В- .работе используются метода теории графов, автоматов, формальных языков и алгоритмов... Научная новизна. 8 работе- решена задача характеризаши. вышеуказанного■ множества взссд-?ыходнкх слов, а именно: - получен конструктивный "гслтеша (необходимое и достаточное условий) пороадаемости вход-выходного слова при взаимодействии автомата с лабиринтом из рассматриваема классов:

- показано, что множество ¡^ всех вход-выходных слов, порождаемых конечным автоматом- и- при . взаимодействии со • всевожожшш - лаОщжЕтакк ез класса - где .2 сройэгает С,с* является кснтекстно-о&шсшгда ■ языком; тем сш показано дриншпиальное . отличие поведения автомата.. при взаимодействии . с экспериментатором • (когда оно •■■является регулярным языком) от • поведения при взаимодействии с лаоютятши из £ {когде оно'является яонтекегш-зазлкшм);

гтпк некоторых ограничениях.-наложенных на автомат, получено конструктивное описание ■.-мяокества. л^ з виде специальных формул.

В • работе изучается три отношения эквивалентности' на «нсжестае конечных автоматов, вгашодействукшх с -классом лаСирвнтов г. Автоматв ал» названы е»-?кЕК2алейтншга.- если (аюкгства их траектория в кагдок лайиркнте г.з класса £ равны. . я к ® названы ££-эквивалентными, если множества их траектошй в каждом лабиринте из класса £ равна с'точностью до налокгаш. траекторий. айв названы с^-екшзвалеЕтшми, -если множества их ,-траекторий в лабиринтах совпадают с точностью до наложимых :траекторий. ".Подучены- «идущие результаты. Дяя - каждого зга введенных вжэ класса. £ -

- автоматы а к £-являются ...е^-эквквалеатЕыми -тогда" и .только -тогда, когда пои взаимодействии с классом £ они порождаю? одно п ток? множество вхол-ааходЕшг слов;

класс всех прлЕэдешшх вв-эквивалентаых автоматов всегда 'бесконечен:.найдены достаточные условия, при которых классы

и о»-эккздален?ках автоматов .Сесгаыечнц, конечна. состоят та-одасго автжата; .; ' '-' '

.- ло;:?нано, ч?о'_прк -вексторыг ограничениях .не 'автоматы зпэоблзка.. - е„— • с^-вквивалегавостк . алгоритмически -.

-.разрешим?; - предлоген апторгж ■•.. проверки . . .х»-,-. ■ с„-зг^йвалентностк-автоматов, который .для :классов о, . .0* прикеЕзв.!.к-любой ларе-автоизтоБ.

- • Последний результат.представляет интерес и с точки зрения " теория формальны?. -языкэе, поскольку .онксывает частный , случай кетекстно-аависвкых языков, для которшс.в отличие от общего -• случая, т^олема.их-тевенса'вз-.алгоритмическа разрешала, '■Теоретическая и практическая цешгасть.- -Работа. - -носит ■тооретичеекйй, характер,• однако-•..полученные в ней .результаты могут даешь -прикладное значение -в силу ■ .тесной связи задач . вваимодейстшя. автоматов, с лабиринта®'с-.задачами • автоматного -анализа изображений:,-Графов,- сормальньх - языков и- друпп; ягскретних-систек'[21,- - -' \ '

¿ггробаьшя. ; Результата - -ииссергааве • докладывались -'.«а-кеЕддаародной конференции по-ктчдаетуальнш-.системам (Кс-сква, ' -1990,1993), -сна гкоздкнши""ГДкскрэтная . математика'ЧМоскБа, 1990,1993), - -на мекдунгродпой конференции но теоретической •лйернз'нзю (Саратов,- "1993), на--.шда-езнинаре "Дискретные "мэдели ь-теори; .улраЕлашн систем (199<}. семинарах во теории • ав-г окатов зек руководством академика 1ТК И? Ь.Б-Кудашэва. РШшгкааш.-По теш диссертации -авторок-опубликовано -6 -работ, - сшсок шторахяриводитея * конца .азхерэфзрата. Структура в поъек диссортавд;. -.Диссертация - состоит '-из ведения, .дву£ глав и ..сшска; - литератущ "1? . -наименовапй, солевая 2 деянка. ОЗвяё обми" ДЕСсерт&заг 190 страниц.

п OBSCP- сошяьш жст&т;

• диссертация состой? зз введения и'двух глаз.-;-- -■ Зо введеляя дана общая ззрактергстнЕа. "г * ясазгЕг.Х! зсло5>ае результаты работы.

Первая глава посв'ядева' хзрактеризчшш' . •«пд*;?* i зхОд-?ыходнах слов, тотяздаэмьа автоматом при ssaarasttrnn;; с лзбирпнтагя. Таклз слова нэавянн гоотокадамя >. -v-..-взаимодействуя;. 3. 1 . введены. оскош/е пснлгг.. ,1';; ласнинтом понимаем ззоск?! • аашдЕй .-абвсент- Г2.\ •:. . .uocratf связны?- неоряентпрсвааннй граф.без петель д .зт"-реСеть- L=<:f, ,Г..>, янозэсгзо закон 7, которого .с-да зодчзоаестасм целочисленной' решетки г2, а- ачссв г.

соединяют все пары вошин аз 7 , расстоякхэ -мезсду когссь1::.; . разно здзшце. - ЛЭДшянга. которые можно гсалесжь зэраллаяыш • переносом, считается хоЕГТзузнтякма 2 различаются.

3 заботе введена следующие.. класса ла&грнктсз: гязге -всех конечных лабирщггов в гиде лент - варнак зетз ? нрсиавольног дшеы. кдгсс гг" псзх "саечных лент ¡ватаг» а « сссязвольЕоа длимы, . класс ■ X' ■ всех кааечянх ззазсажк лабиринтов, кгасс ? згех конечных дзйгрЕтев з >нсс. акэ«о}год1яшгав с ¡гооягзожгхма.дгангет стосон. Пусть i. ч д, шна z згркна лабгсякта I ас одного из ?тпх классов.

мнедаетэе л?С!1:интоэ аз классов о,с\у.,р опграшзз ксяткгшзга. Чйоечвта аоследозателънсст! ."зСиТ^тпз

I- . I . . где- !>,=<*.• ,г, > ' назовгм

1 i я» . ¡ L-^

к-лослелонательнастья, если выполнены следующие условия:

1) (2.У)€7,- оаваосильпа"íkxsl. -!, Qsysi*. -i;

! "1 . "I

2) для лябсго IM ix.y)«?^ равносильно •<f i,:) ils if 1. )-t. • a Osysh -1. •

. ?-« T-i^j • 4

Яолсдам h «sLiih. 1 >, где Uusm-t. лаблпет L-<7,,r >

u ^ L L. i-

u, ц + !

зазовем композицией к-аамедова$ольноои1 лабиринтов -

ëCJSI '

. . 7=1 r UV U...U7 И - ■ Г=Г, иг и. ..иг U.

i s _ __ S La

w<;i,-i,0).(i ,а)>,...,<(1 -i.ií -!},и ,ь,-1)>)и...и i 1 il il..

1К<(1 -Г.СЗМ1 ,Q)>, —«<£1 -1,й -tí. (1- S ,-î)-'/.

• m-*i. a—I ¡a— 1 л— i

Пусть C£,.....a } - конечно» мнсеэстзо классов

лабтоштсз, где 2. «ío.í^, :<,?)., Бхдем . говорить, .-.что класс.

г<2,является ксшозишей классов если

любой лы5щя®г ' L. кз г(* •) является кшсэшией

к-доследова-тэльносгл- ' лабиринтов Ь, '' кз

L sij....»^^.- Классом jy^,-...,^) назовем композиции

• КЛ2ССОЗ а , удовлегвосявдп свойству: для. тзсэх isäc-i-

i it.

jssüo r лиоо . до не оба одновременно. совпадает-с о. . в дальнвйаеи всюду, где не сговорено противное,, ад .классом £ лабгршнсз пенима«* ошш яз. "классов о, о", х, .

Пусть х=<7 ,г > - г-йгсоторый лаошзаи из класса г. Каждой •варэ целых'чисел (i,7) m•• .тасьзаем отметку а(х.у),- равную.' вела л о ,в грот.аном случае. Кзхетй вершине v-<x,y)

лабиринта L сопоставим naöoc- с(т>=(а где

е-.....с сСОИ> К ^=«{1-1,7-. 5), ' »3=о(1+1..Ч1!,

с,=а(Г- а^а'.Х.У), С.=<У(24-1 ,7). . -0^=0(2-1,7-1),

а »¡»6..у-1), й Еаоэр характеризует п0л02?кив

воршена т г- дебпринте: т вазывбит левой (правой) ' граничной

Тгврягаой ПРИ я гО (в =0). АЕаЛСГНЧВО ;ОГрбДеЛлВТСЯ ь-орхвяя и ■ никняя грзагжве верила. Если' V кышется граашгай зершкой •какого-то ышеукгзанкого типа, то £(т) ¿взывается символом грхазик этого типа. Классу £ сопоставим шоке-сггво г„ наборов £ (Vвсех верпзн всех .шсвсгртов из этого класса. Пусть

£ ~

где ,...л )

Под - автоматом пона/ьем кшечявй, векду . спредрДсКный . шшзгльЕий астомг? 143 ' я- ,\в,ссУ, у которого 0 -

МЙГ^СТВО состояний, А-?, - ВХОДНОЙ Б='С1,1 .-> ,■} -

ввходзой ая$?ЕК». к ?:0хД-+£ - ^иг-сап яергходсв и

кпсст-зг- соооъегстк'стно, чп - начаиаое состойпие. Оункшн р, у еать.'твезшя! образа.' т&йзжзийя до словарных Дуккцпй 1, V. . Кцсягстаз Т *-{*;'¡*И а ,Ъ »..Ла .Ъ ), ь ...а ек,

Д 11 г г í г

а^)} кзгегек поэдкккм автсаата а.

пусть ъсв. поло&км

Г 1-, НТК Ь=->, „ пр;: Ь-1,

Л'(Ъ>н-1, при -1, при ъ-з,,

• I 0, в ярэгваяш 'Случае; I 0, ь щоги&ом случае.

Еуо»ь I.- - кекотореа леовда» - из класса Под

взя^пес.лебсгй'ск пртомгто я с л'зЗ^рто^ом I поктш&еч Аескенечнуй -

ЖС.%Д0Г-8?2ДЬ2ССТЬ .

. (чс,та-;,21,Ь1-)...(о!_г?а-1),г1,Ь1).Л ' (1)

Га^ нжльное пкагжв оргокгтв ■ в лаСнршгте,

а'" (Ъ,) ,у(3-1 )'->Лг{Ъ)).

IvZfcW -TOSOpEft. что автомат с дсшзгма£.,аля - -лайЕКЗ!® X, о era для лютого--взаимодействия (1)-всь верииш у.(1) гтого , 2паиь:од83ст£ия щагаадяекаг Vi- Пусть ttíA.P) - это класс всех' автоматов дсщгетша для всех' лабиштов • из зоех: введению; •

клйнсое. в •лальне'йша! рассматриваем только автокаиг .из этого

' - -- '.. . ■

Траекторией . автомата " s в лабиринте I. назовем г.сслсдс-1>2тельноот-ь . V

WO),sworn—(vW,5Cy<t))).- ". . (2) •

в'аяученкую удаленна ro4t). состояний автомата и его вкходешх символов. ¡¿ва&ество ecsi траекторий автомата 2 в -лабиринте 1 обозначим TSgj. - -".

.C.weo w»í&4,'b .¿Ь ) из (АхВ)* ...назовем лротоколш

sms г. "Е/дзи •. гозареть, что прогсясол '»• яздяется

ís,I-)-teüJEr3yeK®v--6üSK найдется такая траектория (2)-автомата

-sst.ь лабщанте L, что длл всех I, islsr, -е =E(vra(i-1)) .в' •

t-___ts =v(ct",a ...s. j. При этой ечктаек, что протокол т, ш его „1 г "О .1 • г

траектория соответствуй? J3>?r гтугу.

- - Бротсжал' к назовем' (вДИзшззуаззд, если найдете?: такой -лабнркт 1 из z, что í' яеляьтсй протокол «

• s.iscar.v £-рззл!зуэкак, бодЕ.ва2дагсд такие 2 г. i .из что - он яьаюгеа (а,Г>-реал4-1гуе:*шХ. ..Обозначим.. через . .л^ • и' -аЯс соотнс-тствезно. шокзетва .всех .-{£,!)- г (а^Ьре&яаз/ешх moi'osanos.. " • • - ;' ' ....

Б работе лоьагазо, чтедля лвсого- автомата -а .2а2дз?ся • - т-кой ípuTOKQS V ил $в,ч?о к не являем? (а.гьреЕлхзуемнм, " ти- я jxpoC-3PseT-0,v£ih. к: rjjt ...г ;. ' ' - -

ai м

Лycii }.... («; , ь ■) -кеко?0£«£

S - P I . t С r -

протокол. -Протоколы

х £ * -6 1 с е- г

,рг нИО.о'.О.О.о', С,0,а'",С,Ь'')...(0>й1Л>С,с!',0,С1.^,0,ьуЬ где для воех ' . 1

1 [-.в ггоотиввом случае; ГЬ, .при .

в протиыкж случае; • -. . .

назовем соответственно 2- и у- проекцией протокола *г.

Протокол «г казсвэм: -- одномерным. если 1=ТТТ .

двумер^м,. если для всех 1<К1.... .г) хотя Он одно кз чисел «1.1«' не равно О,

. - смее^неш, едеротиеном случае.

Очевидно, что одномерные в- екекжгше -еоотксо-ш не .является о"-, Х-. ?- реализуешь, а дгуяергае и сксиа.аае срэтоколы ве являктдя о-рсализуемле.

В. §2 для' каздого ес . введенных классов гайгдатов а в»1!д:-нв вздоходимое к достаточное .услоьия ^-реализуемости ' произвольного протокола -'л терганах - вякзследуиииг его характеристических, свойств. -Пусть «=(а1.Ь])...(а)_,Ьг) ' в -а,-!«*)протокол к назовем сюзтакючески правильным, -еслв выпоязенц- следуйте условия: 1) для всех 1=Т7? • ■ .

если 3^=0, 'то Ъ - "если а}=0, то Ь вели то'Ъ *->; '

' • ' если о1-0. то Ъ Л; -2) № ьоех - ■• . . '. ' * . '

-еслг ?>,,->. и '■ /

CZJX 0 , и Wl'W.^U p-

есж-Vl , то i'U ^ pa ^

ÜOÄ J> в. , то a'*1^1..

• 1&Я0» p etcm вашграфе- Щ-едлоши. гакщуре гкзжза протекала,

в тязультате которой пшгакай w преобразуется е.- некоторый.

чаот-глй, . в- оСвви 'случае, .'.агтака? -Куре S со - входным .

злЗ»вггзк В г шздшаг-А-идв -.окагьаавгся, его w не является ■ _

г-реагдауешг. Автокат sj назовем сезржзй щхжжояв к.

йзггакеиекЕ ВГЙШЛШЙ- протокол, ьмеюсй свертку, вызове!,'

нелротрйсвечнвш.:. Назло согтслшй свзрткь s оЗозпачик |s I..

•lEDEliÄ 1. *5uöET когто 'слэджке утвггизекий: : ■ "

1. OjiHOiicpa;«-;ро?'окол** с-ъегжэуек iq-zvj тогда, - когдг- он еспютзогйчпз F.является слойси ь aüjoTTö S^xB.

протокол w ,7- рэнжгуем кете тох-да, когда ов и обо

N ?Jb ЩОвКЗЫ: ЯСЩ'СТННС^ЧПЗК 2-Y, ллляетсл ' С.'ОБС:,; Е 2Лф2Е1:ТЗ HyiiB.

S. . £.'.УУ'.ЗТЬТПЙ ПРС1.л?.0Л Vi TJ'SiC тргда. когда .

?jfc-0ST!SB.aäHP вйьаднеци ейэдшяг тс^са:' -

ь) ^(•ij.hxS)*; ..." . .

С) с в o?«i его хгро&щйк.ьил^л'йорё^гБ«; ' . .'

в) еслЕ .?,' содержав екм&ш щктетсжжзуг Г^;-.иазалышг то-число cociOEiiiTi-свертке его адртййЛ! ной срсчетя. 7 рэыю й:

Г. - Ь- ' -

/ ^ ..- - ■ ■ "

т) еели-« годемкт • символ' oeoii гс-изсйгхпког гаяетв, ■ т;

¡5. ¡£Ь-1;

д) зс.тз т. -да -содотзкгг. -ошалев гошаоюзлита ггггет. 15 !<&-1.

рг-

У - ' '

4~ Яв/явгжз протокол 7 х-ре&явзуем тсшо -тогда,' "ксглз 1 о^э. его ггрс9!-'1йк н?:хс?тзоречзвы, з часла соезс»*233

22эрт0к прсбкх^'й этого ерстсчсла удоз.п-э'гзо-яют

ч} ге.Гу1 я содзют отзолы зсзх чзтязэх 13 N13 1:

. >г ч' СГ ч

* • у - -

з) . если * содэгазгг строях протавашожак в«глкзл:>ннх

3 ежлвол только ОЕНРЗ горпж'-^&ясг ГРУЗОК, ."о

5) - веля т содерют сдавал» претавешлойщ; гэртиягхнзг гпозщ а' не ссдаряя символов горагентгльнех ланд. -о

X у

г; если я сододак? семюш й^зЕйгс-йялах горхсскггы^чг.: границ и сяязсл только одной вергакадьнея "•с

|3 ЫЗ 1 — '

-■V; "V . • . - . .

5) ЗОЛ! ,.т ССД9С2Я? -.силзолн протзвсполсзея ■ РОР5СОН7К&К.-Я

гга.-шд я седест? символов вйдахальяых - гешьК. ' !5 ' ¡<|з !-1; . ' '

я) з ооталъньЕ гу-арх.этя часла нэ оаздеят дгог от .друга.

В ост"ЗБ2бЛся части дтаагр-афэ-. лсследуяхся услязн с-за.Езугмости ск-гйэлйза: протоколов з кщоаи-7 (2 ..... ;. Л-"к огого !гс?йк»?на олэ27хзая процедура зяэлйзэ сшгь-гнаг

гготс;:.:.-сБ. Хе-с-гаЗ ясскшг '•' . заляпаете» дз егдо- т двумерное чаотс. ксторк? ззг?м нумеругг-оя спе1нальнун ссг'^с.!,

Все 'часто с: одинаковыми номерами, преобразуйся, з • ¡¡шг яазнваемке ксапоЕзнтнзв -врстоЕОлк-' .9 ,...Д ' исходного

г-р. ■

прогокслз. •"'••'

ТЗОРЕУД 2. Для- любого ■ класса ■■■ 7 (&,...„»;)

О I к

. смеакзеЗ протокол- я 7 -реализуем тсчяо тогда,

когда * непр-этазорэчяв, разбиваем на г,, 2а$с. - компонентных

протоколов 9 : , к нслдэтся 7эксй. ношв х,

,-р зг-р - -

что протокол 1 ¿:~ревлзэуем Я г, -реализуем...., й

-От- .¿г ' * -р*1 ^ ♦ 1

г^-резлизуом.

Следствие 2.1.' Одкомершй ш двуйерикй протока« я то-,...,г}-реализуем-.точно тогда... когда, найдется такой , номес X, что * является г -реалазуаиам.

Теоремы. 1 и. 2 дазг кеямруъ-гизкае критерии ■ ремизуемсыти протоколов в изучаемых классах, лабиринтов. .

. Параграф 3" яосвянен шгедэдешш места множества л^ в . гзр»стай иерасхии йораалша языков .153. В начале этого-дграграфа достроена автомата, у которых это гшсаество является -регулярном, . контекстно-свободна* и нерегулярным, контекстно-зависимым и не коЕтекстнс-свободншл. Поскольку доведение. Уа регулярно, то ■ эти примеры показывают-ориацшиальние отличие. функционирования свободного автомата ст функционггровашш автомате пре" взаимодействии с лабиринтом.

ТЕОРЕМА 3. Для лжбкх автомата а л класса лабиринтов, .г.. .множество л^ является яонтехстно-зависшым.

. Доказательство теоре.'« кшструктевно н состоят а посгроешя до автомату а я массу 2 .тинейно-огракнченного автомата-акцептора 151, -уздставляющего множество а^.

Следствие-3.1.. Для лаб-зго класса лзСшзетсв а существует

такой автомат а, что. для .лвооги бесконечного пош-исса к . классе z мкояветво /^..является контекстно-зависимам, , во не контвкстно-сзооодньаг.

Легко, показать, что для -.люСйи агтоматэ 3 .и конечного подкласса ж -лзбирннтов множество ' л^. - является регулярным. Следствие 3.-1 показывает, Что даке для простейших лабиринтов . -лент и бесконечного Mzo ситуация принципиально отлична:' множество Адд-ддя некоторых а не только не регулярно, но и . не контекстно-свободно; ''"■-.

Параграф 4 посвящен-построению' конструктивного - описания , ■ множества ' специальной фотаулоа. -Зта ; задача .решается на основе свойства периодичности. траекторий и протоколов автоката '

s, полученных в §1.

•Траектория '(!)- автомата s .в- зас-штте Х- названа периодической..-если найдутся такие ..целыг> веограибтельшй. число íc и Т, что • для всех- i;>to выполнено Va<t+T)=V2(t). Наименьшее из чисел .t , Г, для. которая выполнено .это равенство, названы соответственно предпериодом t и - периодом ,

Т траектории-(1 У. : ** -

ЛЕША Í.I.-Любая траектория любого конечного-автомата--а в лгоом конечном 'лабиринте является периодической. .

Jenco привести тикер бесконечного лабиринта и , конечного -автомата а, траектория которого в этсяй. лабиринте не является периодической. ...

Из леммы 1.1 непосредственно ннт-екае'т, -что ■ мвонество И " всех аостоколов, ' соответствующих траектории - '.(2},'..однозначно 'определяется протоколов w ив-ТГ, длина которого равна сумме длин лредпериода и периода траектории (2)- 'Такое протокол назван . характеристическим протоколом, ссответстйувдэд' траектории (2)'..

Следовательно, -ккогсестзо ¿^ всех ч2»й)-реалкз5емнх -лротозссшое сжоаначно определяется множеством f^ всех {й,£)-реализуешх хйргкт&шсткчеожх -'протоколор. '

Для яакдото классик удалось Евделить конечное множество ■ оношНа ласирштов дз этого класса. "В .разработана. -техника . .анализа - ' пс-вторявдихся -частей '(квазиперисдов} . характеристически протоколов, соответствующих .траекториям ■■ EEfQf.53TS.5i в опорных .'лабЕризтгх. -с пающыо -этой т6хниш . построено такое кнокество протсколоь- Б^, что люоо£ протокол кз r^ предстаъш. кошсатенашей протока/юр пз. д^. На KHosecTEe.Ifgj, введено-некоторое отношение .следования j и. на-ето основе построен -специальный орграф G^., Б • выделено:

множество , -?- ...драииьнкг. - мзрярутоз. - - -Показано. что .

■Е_»с -и V-W* -к'. „V-v'. -iSmm-i. 39, 1.27, . 1.37), где * - /

i . . ■ ' - -операция гтерации e ani'eope яаыкое. . . . -

:.. кадому • тгравильнску ■ мащзугу -в сопоставлена

• система \шзгйЕНГгИйвнвиФ:2(*л?")- '• ••

КайдеЕО -конструктиваое^достаточное условие, -налокенное ва ¿рьф Gjy.i.npa-TtosopoK ' • . .

* У

и и к,1.—--'*? . (3)

ia— -»Í . . w "х ... к . "-к

- .-i . - . Я . -5 -в .....

- '-натуральное - .рдаз-е.. системыt(í> )..

Ьцдзленк 15еорше. -4} ■ аекоторш класса --js лаокрлвтев, для которых sto условие выполнено .для всех s-. . . ' -

. -Ш-РШк 5. " Пусть-■sí____.¿^еСсЛ.оХ. • тогда - для -soex

«cío,с".ffgCJTj,^ — ,'Л )> у '-всех, автоматов ■ 2 - -шокество 1 -J^, выряжается формулой . . - . - . ■

Пслучезкой '.•предегйьйеаш (3) - мнокоства позволяет

решить проблемы равенства.и включения, -для-; некоторых • чэстюх еядоя: «штексчво-ззшяавсс" языке»,- - э ••о<етссггг,' . pesare проблему " окзЕвалилЕссти ; автоматов, ■ ' зэаияодейстзу^цкх •- с. лзбирлнтсм, рассматриваемую-з-глава 2. ' ",'-"""■

Глава 2. шсвяиена оравши® автоматов.. взавмодействутайх с дрсиз вольем классом ла&гряптсз- "..'■.

. пусть. ТЯ^и^и объединение ■оёретсд до

всем автоматам'аз множества АШ,В).- - _

.. За MHCsteciBS' • • '55 ' введена •. следпше - отнпс?йн? лявязалентвост. Даеятдда-- . -

tsi=(71(0),g(7I(0)))...;71(t)^(v>(:jiu..'". -х

tr2'(73{c;,éí72(0)>)--.(^ft),5c72(t)5)... яззеззк рзвизя, йсля для всэх' tao у'Ш»*3'« _ ij.-j-r1ff»='5{7s(t;;.

3yoTi.vít)=(x1fT),y1(t)?,7ft;^fx2',t;,y;rrt}) jwí всод saö.

п

Траектс сиг- ir1 и tr2 • назовем капежмши ( обозначений сг1"" тг!, fem найдутся таете, целив числа а, я а,, что для веек гх» E£ira,iHSHo.x1ít}=i"<t)+41¿ yi(t;=y2(i;)!-á2 ,

•Автомата а я в названы. э^зкЕиваданиЕМи,- если для- .ве-к лайташтов I из .г ?лножества 'П^' и /Г?.^ равна-

3 §5 исследуется «»»-.эквивалентность автоматов.. Доказано, .что-для-любого класса лабиаинтоз- ¿ автоматы а л.® нерездает. з лайгринтах яз. этого хласса -разные щожества .траёкторай точно тогда, когда множества, л^ ¡г л^ равны (Лемма 2.2)..

Щяданвк алгоритм срсзерка. - э ^-зкЕивалеятнооти. • asp, автоматов а и s, зря условия,, что для множеств • iL^ а А,;., ауавсгвуа'Тм^эдстаЕлеше а виде (3}. ('Теорема 6i.-,

r20P3tt Т. £ля -sadoro автомата.-а существует бесконечное '-\ирло'приведенных ^„-зяЕивалентных e?jy зетсмзтоб.

Доказательство тзср&чы состоит-б описании .способа построения, та произвольному автомату, я приведениях «^-эквивалентных ему

• автоматов. : . . '. .

В ' §5 -введены следувдае отношения предаорядка. Будем-

• говорить, что. автомата я • д 8 находятся з отнесении V., ■ (обозцзченкэ (я.в)е.и'г), если £ Щ&ь» "де через

ТН^'з обозначено Фактор-множество . жозества - тн^ до отношению ЭЕвиваяентнсстк Будем говорить.., что автоматы а и 8 находятся в отношении ¡¡г. (обозначение- (з,в)«ц,,),.. если для всех, I из 2 выполнено ТРч^д = В1^ . - ,

Отношения. и '- их индущгруот следующие отношения эквивалентности..

Автомата я. л в назовем <т,,-зЕШзал9НтннгЕГ точно тогда,, когда- (з,8)еУэ л. (8,я)еУ„.. Автоматы а ж в.- назовем 2„-зкЕЯвалвЕтнкмд точно тогда...когда (а,в)б(г„ и (В,а)еда. Показано, . что- отношения . в»,о^,£г-йквяваяэЕтнссти. попарна-различна. Через обозначено множеетзо автоматов,.

(^-эквивалентных и. не е^-экзивалентных. автомату %г Через обсзначэно множество автоматов, ¿„-эквивалентных и.не .

»^-экЕшалэатныг автомату а.

В «6 найдено, при каких.соотношениях мезду ыновестзавд-Лд^' з А^.. автоматы я а в находятся в отношениях ¡/-¿л

Предлозшн алгоритм, щэовеакя находятся ли автоматы а а 8 в отношениях ¡>„ я ц2 (я тем самым, злгсштм проверил . иг л Е^-экБшалеятнсстд) при условии, что .ыя шозсеста Мщ» а Щ&г . .существует представление (3). Найдены достаточные условия (теоремы 10, 11), при которых множества - сг£(з>/в я £2(а)/й

£

■ч.

бесконечна, конечна, состоя? из одного ал&магта.

Автор вярззает глубокую благодарность Бзлс-ршг. Боризочичу Кудэтзцеву за' постановку задаче и постоянное - шмзвав к работа.

список шиБОБАйей жЕРл^ы: *;"..'• " 1- Шеннон к. Сообщение о/кавяне, рощггаеЗ''лабЕрйэтндо'задачу.г •• В кн. К.ЕГеккон. Работы но теор;с! анзго'рващи-и тЗгрнеицж.-М. : ИЛ, 1963. . ' ' ' Л .

2. Кудрявцев 3.В.. ЗДумюя Щ., Кдлиоараа- Г. O-..доаедении автоматов в -лабиринтах. //Дискретная математика.1.-1992-?.4, вып.З.- а-3-28--. "- . '-."'" -

3. Мур Э.Ф. Умозрительные зксггеав(днты с поатедозательностакш . ■маяинама. - В кн. : Азтсмзтн.- M. :М. - 1956-с. 179-2 !0.

¿. Кудрявцев В.Б., Алене® С.5., Подссшая ¿.с.' Введение в теорию конечных автоматов. - М. : Наука, 1S35. - 32Сс-..

5. Гросс М., Лантен А." Гесрия Формальных грамматик. -1А. : Мир, ¡97 ! .-287с. ■ /.

Ш'ОШКМЩ' АВТОРА^ Ш. ТЭЛЕ ДИССЕРТАЦИЙ Грунская В.Л.; 00 ' эквиваязагном поведении ч автоматов' в •геометрических ' 'средах.. //ЛогЕно-алгвбртаческле вояструяши; 'йзя-во. Тверского ун-тэ.1992 г.-С.41-48. 2. Грунская В.И. О динамическом взаимодействии автоматов.// Математическая.кибернетика и ее приложения-к- биологии, йзд-ьо Московского ун-та.1987. -С.в-19.

■ 4. Грунская B.Ii. Сравнение автоматов, ззашюдэ2ству:-оких ' с геомоУиявска®; сдедз.«и. // Штсдн и системы tszbittsokoI диагностики, Саратов. йзд-зо- Саратовского ун-та. 1993.. -с. 55-56.

.5- Грунская Б".И. Сравнение автоматов в геометрических . ср?двх. //Труда всесоюзной конференции по дискретной математике. Î393- г. - .

6. Грунская В.И. Сравнение автоматов в .лабиринтах. //Труда всесоюзной конференции по диеярегней-математике.. 1930 г.

7. Грунская В.Ü. О контекстной зависимости множества протоколов. автоматов в .' -геометрических' ■ средах. //Труды межвтЕарадкой конференция по'ангащеятуалдам системам. '594 г.