markov_teorija_algorifmov (522344), страница 19
Текст из файла (страница 19)
Такое (I мы действительно умеем строить: достаточно положить У=-РЯ. Докажем обратную усиленную импликацию 1.3. Если сущесгпвует У такое, но<о Р— начало У, а У— конец !ч, то Р входит в !г. Фиксируем Р и 9. Нетрудно видеть, что импликация 1.3 означает то же, что и высказывание !.3.1. Каково бы ни было У, если Р— начало У, а У— конец !е, то Р входит в !е.
Для доказательства этого высказывания надо уметь для х любого У доказывать истинность материальной импликации 1.3.2, Если Р— начало К а (/ — конец !С, то Р входит в !г. Предположим, что истинна посылка импликации 1.3.2. Тогда существуют слова )г и Я такие, что (7 Х РЯ Я ХИI.
Отсюда 1~ о ДРЯ, и из слов Р и Я, разумеется, можно образовать пару )7аЯ. Таким образом, Р входит в !Е. Материальная импликация 1,3,2, таким образом, доказана и вместе с ней доказана теорема 1.3. Теоремы 1.2 и 1.3 могут быть переформулированы так: 1.4. Если Р входит в 1,1, то Р есть на ало некоторого конца !е. 1.5. Если Р ес2пь начало некоторого конца слова !Е, то Р входит в !е. Эти теоремы дают возможность следующим образом составить список всех слов, входящих в данное слово !е. Составляем список всех концов слова !1 !418.2.7!.
Для каждого элемента этого списка (т. е. для каждого конца слова Я) составляем список всех его начал !9 18.2.6!. Объединяем последние списки, что дает искомый список всех слов, входящих в !',!. В самом деле, всякое слово, входящее в !г, является элементом результирующего списка !1А! и всякий элемент результирующего списка входит в !Е (!.5!. Располагая списком всех слов, входящих в данное слово !г, мы сможем для всякого слова Р выяснить, входит ли оно в !г.
ВХОЖДЕНИЯ 97 й й»1 ИГЛ. и СЕМИОТИКА (з) Р'н ТР,РЗ(7 [Рд ~г [ТРд [Рд [5(/д х[Р [ткд[зи ЛХ тйд[5(lд [таад: Л [5(7д Х Л тк мл 5(7ХЛ )г о Л З.йл Р аг гг что н требовалось доказать, (4) (5) (6) (7) (8) (9) (10) (11) [(2) (1)] [(З), 4 19.1,3] [4 18, 10.1Ц, [9 17.5.2,(4)], Н5), 6 17.6.3], [(5), 3 17,6.3], [(6), 9 19.1.6], [(7), ~ 19.1.6], [(8), ~ 17.6.3], [(9), 6 17.6.3], [( 1), ( 10), ( 1 1)], Для этого нам достаточно сравнить Р с каждым элементом списка 19 11.7.21.
Если сравнение даст положительный результат для некоторого элемента списка, то Р входит в «е. Если же для всякого элемента сравнение даст отрицательный результат, то Р не входит в «г. В силу этого имеем 1.6. Двуместный вербальный предикат «Р входит в Я» разрешим. Ввиду этого импликацин 1.4 и 1.5 можно рассматривать как материальные. Так как они взаимно обратны, их можно объединить, что дает 1.7. Слово Р тогда и только тогда входит в слово «г, когда Р есть начало некоторого конца ге'. Аналогично доказывается 1.8. Слово Р тогда и только тогда входит в слово ге, когда Р есть конец некоторого начала 1е. 2. Легко доказываются следующие два высказывания: 2.1.
Всякое начало и всякий конец слова Р входят в Р. В частности, во всякое слово входит оно сил«о и пустое слово. 2.2. Если Р входит в (г, а гг входит в гх, то Р входит в гг. Докажем высказывание 2.3. Если Р входит в «Е, а гЕ входит в Р, то Рм.Я. Пусть Р входит в «7, а Я входит в Р. Тогда существуют пары )гаЗ и Та(7 такие, что (1) ЯдКРЗ и (2) Р я ТС1(7. Имеем 3. Будем называть вхождениями (точнее, Ж-вхождениями в алфавите А) слова вида РЖРЖЗ, где гг, Р и З вЂ” слова в алфавите А, а Ж вЂ” буква, не принадлежащая А.
3.1. Если вхождения Р, ЖРЖЗ и ТЖУЖ'р' совпадают, та г«я.т, Р дьем и 59Ьу. Это легко доказывается с помощью 9 22.1.2. Теорема 3.1 утверждает, что всякое вхождение представляется в виде г«Ж Р ЖЗ единственным образом. Слово )7 называется левым крылом вхождения Р.ЖРЖЗ, слово Р— основой этого вхождения, слово 5 — правым крылом этого вхождения. В силу 3.1 и определения вхождения имеем-, 3.2.
Вхождения Х и 1 тогда и только тогда совпадают, когда совладают их левые крылья, совпадают их основы и совладают их правые крылья. Вхождения с основой Р мы будем называть вхождениями СЛОВа Р; ВХОждЕНИя РЖРЖЗ таКИЕ, Чта КРЗ дь(Е, МЫ будем называть вхождениями в слово ~; вхождения слова Р, являющиеся вхождениями в слово «е, будем называть вхождениями слова Р в слово (е. Имеем очевидно 3.3. Трехместный предикат «Х есть вхождение Р в 1Е» разрешим. Имеет место материальная импликация 3.4. Если Р входит в 1Е, то существует вхождение Х слова Р в слово 1е. В самом деле, тогда существует пара А1аЗ такая, что ЯХКРЗ, и, полагая Х.==РЖРЖЗ, мы видим, что Х есть вхождение Р в (~.
Обратная импликация «если существует вхождение Р в 1е, то Р входит в 14» может быть рассматриваема как усиленная (3.31. Эта усиленная импликацня утверждает то же, что и высказывание общности: «каково бы ни было Х, если Х вЂ” вхождение слова Р в слово «Е, то Р входит в 1Е». Последнее, очевидно, верно. Таким образом, имеем 3.5. Если существует вхождение слова Р в слово «е, то Р входит в «7. Ввиду 3.4, 3.5, а также правила п1ойпз ропепз для материальной импликации 19 13.4,11 и для усиленной импликации 4 А. А.
Марков, Н. М. Нагорный 98 семнотикА [гл. и 14 14.2.1), мы м ожем использовать имеющийся мегод распознавания истинности предиката «Р входит в для построения метода распознавания истинности предиката «существует вхождение Р в ф. Таким образом, имеем З.В. Двуместный предикат «существует вхождение Р в «С» разрешим. Зто дает возможность рассматривать импликацию 3.5 как материальную. Объединяя ее с материальной импликацией 3.4, получаем 3.7. Слово Р тогда и только тогда входит в слово гг, когда суи!ествует вхождение Р в гг. Легко доказывается высказывание 3.8. Е .. Если 7>> есть левое крыло некоторого вхождения слова Р в слово гг, то с«Р есть начало гт.
Зто высказывание мы понимаем как равнозначное следующей усиленной импликацни: 3.9. Если существует Х такое, что Х есть вхождение слова Р в слово Я и )А> есть левое крыло Х, то ВР есть на- В качестве таковой 3.9 без труда доказывается. Также легко доказывается 3.10. Если КР есть начало гг, то )7 есть левое крыло некоторого вхождения слова Р в слово гг. )9 18.2.8) и как с Зту импликацию мы можем понимать и как мате риальную и как усиленную. Она верна при обоих пониманиях )9 14.3). Объединяя материальные импликации 3.8 и 3.10, чаем и ., полу- 3.11. Слово Рт Рт тогда и только тогда являепгся левым крылом некоторого вхождения слова Р в слово Я, когда КР является началом слова Аналогично получаем 3.12. Сл ово В тогда и только тогда является правьсм крылом некоторого вхождения слова Р в слово гг, когда РВ цом а является кон- 4.
В . Вхождение с пустым левым крылом мы будем называть начальным вхождением. Вхождение с пуст пустым правым крылом мы называем концевым вхождением. $23! 99 Вхождения Следующие высказывания легко доказываются: 4.1. Начальное вхождение слова Р в слово гг существуесп тогда и только тогда, когда Р есть начало гг; концевое вхождение слова Р в слово >ч сущеспгвует тогда и только тогда, когда Р есть конец гг. В случае суи!ествования начального вхождения слова Р в слово г1 такое вхождение Р в.гг единственно и имеет вид ЖРЖ(Р ф. В случае существования концевого вхождения слова Р в слово г.'г такое вхождение Р в г,'г единственно и имеет вид (Р- гг) ЖРЖ.
4.2. ЖЖ Р есть начальное вхождение >густого слова в Р; РЖЖ есть концевое вхождение пустого слова в Р. 5. Нас теперь будут интересовать различные вхождения слова Р в слово гг, где Р и 9 фиксированы. Для краткости мы в данном пункте будем называть их просто «вхожденггями», не упоминая Р и г~. 5.1. Вхождения Х и У' тогда и только тогда совпадают, когда совпадшот их левые (правые1 крылья $17.5.2, 3.2, 9 17.5.1).
Будем говорить, что вхождение Х предшествует вхождению г', если левое крыло Х есть собственное начало левого крыла !'. 5.2. Для вхождений Х и Г имеет место одно из трех: Х предшествует 1', )' предимствует Х, Хя У )318.4.5, 9 18.4.1). 5.3. Вхождение не предигествует самому себе )9 18,4,17!. 5.4.
Если вхождение Х предшесспвует вхождению 1', а !' предшествует вхождению 2, то Х предшествует 2 )9 18.4.18). Докажем высказывание 5.5. Три возможности, указанные для вхождений Х и 'г' в теореме 5.2, исключают дру друга. Иначе говоря, незвал«ажно, чтобьс Х предсиествовало !л и 1' предшествовало Х; невозможно, чтобы Х предисествоволо У и совпадало с )'; невозможно, чтобы У предшествовало Х и совпадало с Х.
Действительно, второй и третий случаи сразу отпадают согласно 5.3. Если бы имел место первый случай, то вхождение Х предшествовало бы самому себе )5.4), что невозможно в силу 5.3. Докажем высказывание В.В. Если вхождение Х предшествует вхождению У, пго правое крыло У есть собственный конец правого крыла Х. 4« Р01 вхождения а а»1 1гл. н СЕМИОТИКА 100 Пусть В, Ю, Т и У означают соответственно левое крыло"Х, правое крыло Х, левое крыло У и правое крыло У. Имеем (1) ВРВх Я, (2) ТРУ я.
се. У 3= 6УВ, и мы имели бы (8) [(5),(6), 6 17.5.1], откуда УАСЛ [(8), 3 19.2.3] вопреки (4). Таким образом, В не есть конец У, и потому в силу того, что В и У суть концы одного и того же слова [(6)], У есть собствен- ный конец В [318.4.9], что и требовалось доказать. Аналогично доказывается 5.7. ..
Если правоекрыло вхождения У есть собственный конец правого крыла вхождения Х, то Х предшествует У. В силу 5.6 и 5.7 имеем 5.8. Вхождение Х тогда и только тогда предшествует вхождению У, когда правое крыло вхождения У есть собствен- ный конец правого крыла вхождения Х. Б удем называть глубиной вхождения Х длину левого крыла вхождения Х. 5.9. Если вхождение Х предшествует вхождению У, то глу- бина Х меньше глубины У [$19.1.7]. 5.16.
Если глубина вхождения Х меньше глубины вхожде- ния У, то Х предшествует У [5.2, 5.9, 3 18.8.7 918.8.8, $ 18.8.12]. ю [5.2, 5,9]. 5.! 1. Если глубины вхождений Х и У совпадают то ХльУ У Так как Х предшествует У, В есть собственное начало Т и существует слово 1' такое, что (3) Т3:РУ, (4) у-ел, так как Т ~Ы [(3)]. Имеем (5) ВРВ~ВУ У [(1) (3)], (6) РЮ х УРУ [(5), ~ 17.5.2].
![](https://s.studizba.com/z.php?f=/templates/si/i/noavatar.png&w=100&h=100&t=1"){kind=avatar}
