1626435695-d1df5d2e6d953ce7ad4b4ccb5f4f4e30 (844296), страница 11
Текст из файла (страница 11)
„ń— конечные алфавиты, Ес П П Еу — О для с~у. По- 1 6 юудиагукыьвоб (над Х»... ...,Е„) называется тройка Ф Ф (~=(Го "~). 1'.." 1 д» где Го = (К», Ее,'Фд)— 0 размечеипый ориектироваикый граф без свободных дуг, ЛΠ— выделенная Ряс. 3.3. двухлевточаый автомат А»л выходкая вершина из Уо, иэ которой ие выходит ии одной дуги, а у»ос Ь'е -» ( у Е» — функ- » 1 ция разметки дуг графа Гс„обладающая следующим свойством: если из иекоторой вершвпы и Е- "Уо выходит хотя бы одиа дуга, помеченная символом о ек Е„то для всех а' с= Хс имеется дуга графа Го, выходящая из и и помеченная символом а'. Мы будем говорить, что вершина й является д-кавввдкиквдь вершины в, если имеется дуга, выходящая из вершины и, котораи ведет к вершине о' и помечена символом а Е- "Х,.
Коротко этот факт будет записываться как и- и' в (3. Когда будет ясно, о ка- кой полудиагрэмме идет речь, мы будем опускать индексы у Г, Л, р, У, Е, Ф. Полуднаграмма 9 называется конечной, если У~— конечное множество. Вершина и Е= г'о называется свободной, если опа не является выходной и не имеет наследников.
Отображение 1: г'о -~- $'о называется иорфиаддом Д в Д' (обозначение ~: д,д — (У), если 1(Ле) = Ло. и из дд — г' в Д сле- ду 1 (г) / (о') в 0'. 'дождествеяное отобрании~ Мд Га уа, а также композиция морфиэмов 11'. Уе -д- ГО, определяема» соотношением Щ') (и) = /'(г(и)), являются, очевидно, морфиз- мами. Морфием 1д ч Д' называется иввмор~йианвэд, если сущест- вует морфизм у': Д' — Ч такой, что 1у' = до и у'1 = ц.
Полу- диаграммы Д и (,д' иволдорфны (обозначение ч Ч'), если судцест- вует иэоморф эм У: (') Ч'. Если дан морфием 1: Д вЂ” ~7, то через 1ш Щ будем обозначать полудиаграмму, определяемую следующим образом: а) г'д Идд = И (гйг й- =Ю. б) Лд и =У(Ло), , в в) дд~ - ид в 1вд Щ ж Эид, ид ~ Ус а такие, что гд- дд в ~? и В дальнейшем мы будем соединять несколько соотношений в в' О таких, как гд-+ г„ид сз и ддд — гд в (3, следующим образом: о" в 0 Полудиаграмма Р называется диагра,ммвй, если она обладает следующим свойством детерминированности: из следует, что ид = иг. Вершина и диаграммы Р иаэивается гамкну- гиой, если иэ в Р, где а б Хд, а'б Ер дФЯ, е' следует существование такай вершины ие ~ Уо, что пд в Р.
с Диаграмма называется гамкнукий, если замкнуты все ее вершины. Схемой Берда называется пара (Р, о), где и — вершина диаграммы Р, называемая входной еерюиной схемы, а Р— такая диаграмма, что для всякой вершины и, отличной от выходной, найдется целое д (1 ~( д а,', п) такое, что о имеет д-наследников в никаких других. Заметим, что ?лдвграмма схемы Бердв является замкнутой и не содержит свободных вершин.
д' каждым путем до в полудиаграмме (? свяжем набор слов (ид,..., и„), определяемых следующвм образом: и, — зто слово, которое получается из последовательности пометок дуг пути до выбором символов, принадлежащих Х„и выписыванием их подряд. Если последовательность пометок дуг пути щ не содержит символов из Е„то ид — пустое слово над алфавитом Х„которое мы обозначим е,. Для произвольной полудиаграмми Д и вершины обЕ е'о через тя(и) обозначим множество всех наборов слов, свяванвых с путями в (? от вершины о к вершине Ло.
Две схемы Берда (Р, и) и (Р', о') называются гкеиеавдеюинмми, если то(и) = = тв (о'). Пусть Хд = (ад, ад), Хд = (Ьд, Ьд)в а Рв Р' и С вЂ” диаграммы над Хд и Хд, првведенные на рис. 3.3. Понятно, что схемы Берда (Р, и) и (Р', од) эквивалентны, а С вЂ” замкнутая диаграмма. Вершины этих трех диаграмм помечены для того, чтобы поквввть морфиэмы ив Гв в гс и из Уо в Ус. Т е о р е м а 3.3. Дла каждого я- деювочного аедкомадяа А = =(2, (?, Б, де, ~, 1) суи~ескдеуав жаков схема Берда З)д (А), тлю Ад ° Ад +Ф З)д (А ) З)д (А ).
Д о к а з а т е л ь с т в о состоит в построении схемы ЗЫА) = =(Р, ие) по автомату А. Если Х =(а,..., ар), мы возьмем и различных копий множества Х Ц (Щ, обозначая их Хд = (од~ ~,... ..., агн?, фез), д ~ д а, н. Пусть дд — семейство множеств, которое определяется следуэпцим обравом: Рас. з.з. прамерм диаграмм Р, Р' н с аад е( = (а(, ас), е = (ьг, бс) а) 1у)((~((4,п) ш( =($,...,я)~~ (1), ш»(:'БУ, б) если ш (1:— У и ш ча и. то и ~ (ш)п (а)) ~ У; в) других множеств в У нет. .8 яачестве множества вершин диаграммы Р возьмем ги = = (1) (» (и ~ и) (== У) (» (и ), ли = ии. Дуги диаграммы Р проводятся следующим образом: в()» а) (у — 1. д' вР,если (да(-г д') (.:х уи»уб-"()) для некоторых (), »у' Е Д, а, (:— ' Е, у ~ (1,..., я); а(Л б) д — и в Р, если ((у4р'-» д') (=:-У, ()»==()у и р'е="У( для некоторых д, д С- "((), у (== (1,..., я);.
е(й в) р и в Р, если (рчр (у')(:=у, д~(уу и д'Юу) для некоторых р д'(= О, у ~ ((, ..., я); .()» „()) г) и — и ни " и„~()) вР для всех шЕУ,тчаО, для всех 1 = $,..., р и для у = ш)п (л)); а1 (и «(1) д) и — и и и — 1.и в Р для всех 1 = 1,..., р. Как нетрудно видвть, все наборы слов в ти (и ), и = »ус, имеют вид ( (3) $1) 4р(1) (А) у(ю ~(а)) где а(„..., а)„ЕЕ Е, пркчем (а(',»... а(г~ тг~ )., а); ~... а)1~ хи~"~) (== ти ( с) тогда и толъко тогда, когда (аи...
а~„,..., аъ... ау„) ~ Ма. Отсюда следует, что Ма полностью о~ределяет множест~о тэ (пг) и наоборот. Таким образом, проблема эквивалентности и ленточных автоматов сводится к проблеме и-~)енточньгх схем Берда. ( ) 4 (!и Йс" ~д ~ иси... „: 2.2. Свойства замкнутых диаграмм. Схемы Верда (Р, г) в (Р', э'), приведенные в качестве примера на рис. З.З, обладают тем свойством, что существуют замкнутая диаграмма С и морфизмы у. "Р- С, у'с Р' «С, у(э) =-у'(й). Здесь будет показано, что это свойство является необходимым и достаточным для эквивалентности двух схем Верде. Определвм универсальную замкнутую диаграмму следующем образом: У = (Уо, Еп.
Фи), где Уц — множество всех подмножеств множества ((и„.. „ ..., и„) ~ Ус ($ ~~ ~ ~.. и) ис е— : ЕУ). Множество О имеет сьнаследвиков, если 0 не содержит наборов с пустой с'-й компонентой. в Если зто условие вьшолнено, то для всех а е= Х, Π— ((и,... ..., и„) 1 (и1,..., и, м ои„иД,..., и„) ~ 0) в У. Выходной вершиной диаграммы П является одноэлементное множество ((з„..., е„)). Т е о р е м а 3.4. У вЂ” гамлиуэиш диаграмма. Д о к а з а т е л ъ с т в о.
Очевидно, что (У вЂ” диаграмма. Пу О~У„, прд с, е ~в, в П, в, где аг 0= Хи аз Е хм $ чь у. Тогда (и„..., и„) в= О, -> (и„... ° ° ° оьии °, и„) Е О -т иу ~ зу, поскольку у вершины О имеются у-наследники. Итак, Ог имеет у-наследников, а Оз— ~-наследников. Пусть Ог — Оз и Оз — О, в П. Тогда (ит,..., и„) Е:— с= Ог и (и,..., о им..., и„) (=:.О <-ь (и,..., а ии..., озим ..., и„) с= 0 ьь (ит,..., аги,„..., и„) ~ Оь +=> (им..., и ) ~=' — Ом Такам образом, Оз = О„т. е. П замкнута.
Д Определим двииу эабвра савв (и,..., и„) как сумму длин слов иэ..., и„. Если э — вершнна полудиаграммы ф а й ~ О, то через тэ (э) обозначим подмножество множества тэ(э), состоящее *)ю" нз всех наборов длины й. Через ю обозначим пустое множество наборов слов. Лемма ЗЛ. Пусгпь С вЂ” замкнутая диаграмма. Два всех й «О иг г — й в С свсдусш чс+ ~ (и) — тес (о') в П. 47 Д о к а з а т е л ь с т в о проводится икдукцвей по й. Псе и а кажем сначала, что из э — э' в С, следует 4~ (о) — т~м (о') в б'. Предположим, а е= Х,. Если тс (о) ие имеет Г-наследников в У, то и) Зу (у Ф ю) (е„..., ег и о', ег+„..., е„) я топ (и), а' а это означает, что и — Лс в С.
В силу замкнутости вершины и отсюда следует, что Лс имеет 1-наследников, а это противоречие. Стало быль, т3~ (и) имеет Г-наследников. Пус1ь 4~ (и) — 0 в П. Тогда ((е,,...,е„)), если(е„...,е; „а,е;+и....с„) ЕБто (и), н) ю в противном случае. Но (е„..., е, „а, е,+„..., е„) ~ те (и) еэ и- Лс в С<=э Р) ж э' = Лс.
Поэтому 0 = к~~ее~ (э). Предположим теперь, что доказываемое утверждение верно для некоторого й ~ 0 и и- о' в С„Докажем т~4~~ (и) — т~~е+и (э') в П, Пусть о е= Хэ Возьмем произвольный набор (и1,..., и„) ~= тР+~~ (и) и рассмотрим любой из путей из и к Лс, который порождает этот набор. Здесь имеется две возможности. 1. Путь начинается у-шагом. у чь 1, т. е.
существуют ог ~ ЕБ Ус, о' Е Хг и щ" ~ Хг такие, что и- и в С, иг — — о'и) и (им..., иг, и), и>,.„..., и„) Е тс (иг). В силу замкнутом+и стн С вершина и, должна иметь ~-наследников. Тогда по индуктивному предположению т~с+ ~ (иг) имеет 1-паследников в откуда н~ чь е,. 2.
Путь начинается г-шагом. Это сразу дает и~ чь с,. Итак, с~~+и (и) имеет ю-наследников. Предположим, что с~~+и (и) - 0 е П. Тогда (им..., и ) ~== тс"+и (э') г (ид, ..., ои„..., ц„) ~= тЯ"и (и) -> (иг, ..., и„) ~с! О, т. е. т~"+и (э') с: О. Пусть теперь (иг, ..., и ) е= О, тогда (ит,..., ои;,..., и„) Е= ~= 4*"и (и), т. е. существует путь от э к Лс, порождающий набор (нг,..., оно..., и„).
Снова рассмотрим два возможных случая. 1. Путь начинается у-шагом, у чь 1', т. е. существуют э ~== Ес, Ф Ф ю и Я Хг и и) Е Хг такие, что и - и в С, иг — — о и) и (ит,... ..., ои„..., иь „и ) ~ т~"+п(иг). В силу замкнутости С существует вершина и Е= Ус такая, что Индунтивное предположение дает 4""'(ог)-~-4Ю(о,)' в У, откуда (ии..., иг ю и), и~~„..., и„) ~"=- тс (ог). Следовательно но, (и,..., иг, а и"., ин„..., и„) Е=тсс (о), т. е. (и,... ..., и„) ~ 4"" (о'). е 2.
Путь начинается ю-шагом о- о. Отсюда немедленно следует (и„..., )ятс и (о'). Итак, в кюкдом случае (иг,..., и„) е= тф+» (о'), что дает 8 с:тс""'(о'), т. е. 8 = тс и (и'). Д Если дана полудивграмма Ч, то с каждой вершиной о ~ Уо связано множество наборов то (о) ЕБ Ус. Таким образом, то задает отображение из Го в Ус. Т е о р е м в 3.5.
![](https://s.studizba.com/z.php?f=/templates/si/i/noavatar.png&w=100&h=100&t=1"){kind=avatar}
