Содержание к диссертации
Введение
Глава 1 16
1. Основные понятия и результаты 16
2. Доказательство вспомогательных утверждений 27
3. Доказательство основных утверждений 38
4. Заключение главы 1 42
Глава 2 49
1. Основные понятия и результаты 49
2. Доказательство вспомогательных утверждений 54
3. Доказательство основных утверждений 91
4. Заключение главы 2 98
Глава 3 100
1. Основные понятия и результаты 100
2. Доказательство вспомогательных утверждений 103
3. Доказательство основных утверждений 115
4. Заключение главы 3 119
Глава 4 121
1. Основные понятия и результаты 121
2. Доказательство вспомогательных утверждений 122
3. Доказательство основных утверждений 128
4. Заключение главы 4 130
Глава 5 132
1. Основные понятия и результаты 132
2. Доказательство вспомогательных утверждений 133
3. Доказательство основных утверждений 140
4. Заключение главы 5 143
Глава 6 146
1. Основные понятия и результаты 146
2. Доказательство вспомогательных утверждений 154
3. Доказательство основных утверждений 191
4. Заключение главы 6 199
Заключение 201
Краткий список обозначений 203
Библиография 2
- Доказательство основных утверждений
- Доказательство вспомогательных утверждений
- Доказательство основных утверждений
- Доказательство основных утверждений
Введение к работе
Актуальность темы исследования. Теория кодирования по праву занимает важное место среди разделов дискретной математики. Можно считать, что современная теория кодирования началась с работы Клода Э. Шеннона - американского математика, первым решившего проблему избыточности передачи информации по каналу связи. В ней Шеннон, ссылаясь на своего коллегу, Белла Ричарда Хэмминга, предложил линейный код, исправляющий одну ошибку. Справедливости ради следует упомянуть, что такой же код был независимо получен другим математиком из Швейцарии - Марселем Дж. Голеем. Но исторически так сложилось, что эти коды в дальнейшем стали называть кодами Хемминга. После этого в 1949 году Леоном Г. Крафтом для класса префиксных кодов было получено знаменитое неравенство Крафта-Макмиллана. Своим именем оно также обязано американскому ученому и политику Броквею Мак-Миллану, который в 1956 году доказал выполнение этого неравенства для разделимых кодов. Затем американский ученый Дэвид Хаффман, будучи аспирантом создает первый код оптимального сжатия, широко известный теперь как код Хаффмана. В 1954 году американцы Ирвинг С. Рид и Дэвид Е. Мюллер придумывают блочные коды Рида-Маллера. Далее французский математик Алексис Хоквингем и независимо от него чуть позже американцы Радж Чандра Боуз и Двайджендра Камар Рей-Чоудхури изобретают коды Боуза-Чоудхури-Хоквингема (сокращенно БЧХ-коды). В том же 1960 году уже упоминавшийся Ирвинг С. Рид и еще одного американец Густав Соломон представляют общественности коды Рида-Соломона. Затем результаты в области теории кодирования идут
1см. C. E. Shannon. A Mathematical Theory of Communication, Bell System Technical Journal, № 27, pp. 379-423,
1948, см. также перевод К. Э. Шеннон. Математическая теория связи. В сб. "Работы по теории информации и
кибернетики". Издательство иностранной литературы, 1963.
2см. Marcel J. E. Golay, Notes on Digital Coding, Proc. IRE 37: 657, 1949.
3см. L. G. Kraft. A device for quantizing, grouping, and coding amplitude modulated pulses, Cambridge, MA: MS Thesis,
Electrical Engineering Department, Massachusetts Institute of Technology, 1949.
4см. B. McMillan. Two inequalities implied by unique decipherability, IEEE Trans. Information Theory 2 (4), pp. 115-116,
1956.
5см. D.A. Huffman. A Method for the Construction of Minimum-Redundancy Codes, Proceedings of the I.R.E., pp
1098-1102, 1952.
6см. D. E. Muller. Application of boolean algebra to switching circuit design and to error detection, IRE Transactions on
Electronic Computers, 3:6-12, 1954 и Irving S. Reed. A class of multiple-error-correcting codes and the decoding scheme,
Transactions of the IRE Professional Group on Information Theory, 4:38-49, 1954.
7см. A. Hocquenghem. Codes correcteurs d’erreurs, Chiffres (in French) (Paris) 2, pp 147-156, 1959.
8см. R. C. Bose; D. K. Ray-Chaudhuri. On A Class of Error Correcting Binary Group Codes, Information and Control
3 (1), pp 68-79, 1960.
9см. Irving S. Reed; Gustave Solomon, Polynomial Codes over Certain Finite Fields, Journal of the Society for Industrial
and Applied Mathematics (SIAM) 8 (2), pp 300-304, 1960.
по нарастающей. К наиболее важным из них, пожалуй, стоит отнести создание LDPC-кодов (Роберт Галлагер, 1963), возникновение алгоритма Витерби по декодированию сверточных кодов (Эндрю Витерби, 1967), создание арифметического кодирования (Йорма Риссанен, 1976), появление алгоритмов сжатия LZ-77 и LZ-78 (Якоб Зив, Авраам Лемпел, 1977-1978), появление турбо-кодов (Клод Берроу , Алэйн Главиукс и П.Ситимашимой, 1993), преобразование Барроуза-Уилера (Майкл Бар-роуз, Дэвид Уилер, 1994), изобретение полярных кодов (Эрдал Арикан, 2009).
Параллельно с теорией кодирования развивалась и теория формальных грамматик. Самым важным результатом этой теории, без сомнения, является создание в 1956 году иерархии Холмского, названной так в честь американского философа и лингвиста - Аврама Ноама Хомского. Согласно этой иерархии все формальные грамматики можно разделить на 4 типа:
рекурсивно-перечислимые грамматики;
контекстно-зависимые грамматики;
контекстно-свободные грамматики;
регулярные грамматики.
Для каждой из этих грамматик известно, какими моделями можно их распознавать. Так, рекурсивно-перечислимые грамматики распознаются машинами Тьюринга, контекстно-зависимые грамматики - линейными ограниченными автоматами, контекстно-свободные грамматики - автоматами с магазинной памятью, и, наконец, регулярные грамматики
10см. Robert G. Gallager, Low Density Parity Check Codes, Monograph, M.I.T. Press, 1963.
11см. A. Viterbi. Error bounds for convolutional codes and an asymptotically optimum decoding algorithm. IEEE
Transactions on Information Theory 13 (2): 260-269, 1967.
12см. Jorma Rissanen. Generalized Kraft Inequality and Arithmetic Coding, IBM Journal of Research and Development
20 (3), pp 198-203, 1976.
13см. Jacob Ziv, Abraham Lempel. A Universal Algorithm for Sequential Data Compression, IEEE Transactions on
Information Theory, 23(3), pp. 337-343, 1977.
14см. Jacob Ziv, Abraham Lempel. Compression of Individual Sequences Via Variable-Rate Coding, IEEE Transactions
on Information Theory, 24(5), pp. 530-536, 1978.
15см. C. Berrou, A. Glavieux, P. Thitimayshima. Near Shannon Limit Error - Correcting Coding and Decoding: Turbo-Codes, Ecole Nationale Superieure des Telecommunications de Bretagne, France, 1993.
16см. Michael Burrows; David J. Wheeler.A block sorting lossless data compression algorithm, Technical Report 124,
Digital Equipment Corporation, 1994.
17см. E. Arikan. Channel Polarization: A Method for Constructing Capacity-Achieving Codes for Symmetric Binary-Input Memoryless Channels, IEEE Transactions on Information Theory, vol.55, №7, pp. 3051-3073, 2009.
18см. N. Chomsky. Three Models for the Description of Language, IRE Transactions on Information Theory IT-2, 113-24,
1956.
- абстрактными конечными автоматами.
Диссертация посвящена одному из основных типов кодирования - алфавитному кодированию. Основоположником этого направления в России можно считать русского математика из Нижнего Новгорода Александра Александровича Маркова. Обязательно следует упомянуть здесь его работу "Основания общей теории кодов", которая, несомненно, внесла большой вклад в развитие теории кодирования в России. В 1984 году Ал. А. Марков успешно защищает в Московском государственном университете докторскую диссертацию по теме "Вопросы взаимной однозначности и сложности в алфавитном кодировании". Там ставится и успешно решается вопрос об алгоритмической разрешимости проблемы однозначности алфавитного декодирования для класса регулярных языков из классификации Хомского. В дальнейшем, для краткости, мы будем обозначать эту проблему как проблему ОАД. Для случая, когда регулярный язык совпадает с множеством всех слов входного алфавита, этот результат широко известен и называется Теоремой Маркова. Также известно, что в классе контекстно-свободных грамматик проблема ОАД при ряде дополнительных незначительных ограничений алгоритмически неразрешима. Тем не менее, оставался открытым вопрос о практической реализации решения проблемы ОАД в классе регулярных языков. В связи с этим автором диссертации была разработана специальная автоматно-алгебраическая техника, дающая альтернативное доказательство алгоритмической разрешимости проблемы ОАД и обеспечивающая необходимые оценки сложности алгоритма в терминах абстрактных конечных автоматов. Для этого сначала был введен и исследован подкласс регулярных языков - класс тонких языков T(A). Этот класс можно рассматривать, как класс языков в алфавите A, которые
регулярны;
имеют не более чем линейную функцию роста.
Было дано описание структуры таких языков, предложен способ их канонического представления и приведены оценки на его сложность. Все эти результаты позволили получить хорошие оценки на сложность алгоритма, доставляющего решение проблемы ОАД в классе T(A). После
19доказательства этих утверждений можно найти, например, в John E. Hopcroft; Jeffrey D. Ullman. Introduction to
Automata Theory, Languages, and Computation (1st ed.), Addison-Wesley, 1979.
20см. Ал. А. Марков. Основания общей теории кодов. Проблемы кибернетики, 1976, №31, с. 77-108.
21см. Ал. А. Марков. Введение в теорию кодирования. М: Наука, 1982.
22см. С. В. Яблонский. Введение в дискретную математику. М.: Наука, 1986.
23см. Л. П. Жильцова. Современные проблемы теории кодирования. Учебное пособие, Нижний Новгород, 2007.
этого исследование было перенесено на гораздо более широкий класс регулярных языков - класс RP(A). Под этим классом мы здесь понимаем класс языков в алфавите A, которые
регулярны;
имеют полиномиальную функцию роста.
Также автором был предложен алгоритм решения проблемы ОАД для этого класса, работающий достаточно быстро для того, чтобы его можно было реализовать на практике. Прежде чем переходить к описанию такой реализации в диссертации нужно было еще решить пару проблем - проблему сравнения полезности произвольной пары функций алфавитного кодирования (или, сокращенно, проблему ВКД1) и проблему сравнения полезности произвольной пары регулярных языков (или, сокращенно, проблему ВКД2). Удалось доказать, что первая проблема всегда алгоритмически разрешима. Для второй проблемы алгоритмическая разрешимость показана для случая, когда мощность входного алфавита равна двум. Чтобы полученные результаты не выглядели оторванными от реальности, их практическое применение демонстрируется на примере разработанной автором модели передачи информации на большие расстояния по оптическому волокну, в которой применяется алфавитное кодирование в классах T(A) и RP(A). Исследован вопрос о надежности такой системы. Автор работы особо подчеркивает, что эта модель не претендует на внедрение в стандарты шифрования и ее основной задачей является иллюстрация одного из способов применения полученных теоретических результатов в реальной жизни. В рамках этого вопроса в конце каждой главы дается описание применения полученных теоретических результатов на практике.
Цели и задачи работы. Основной целью работы является разработка нового автоматно-алгебраического подхода к решению проблемы ОАД, доставляющего полиномиальные верхние оценки на сложность решения проблемы в классах T(A) и RP(A). Так же необходимо разработать модель, демонстрирующую практическую ценность применения этого подхода. Поэтапное достижение основной цели ставит перед автором следующие задачи.
Разработать общий автоматно-алгебраический подход к решению
проблемы однозначности алфавитного кодирования регулярных
языков.
Привести для языков из класса тонких языков полное неизбыточное описание в терминах конечных объединений прогрессивных множеств.
Привести для языков из класса регулярных языков с полиномиальной функцией роста полное неизбыточное описание в терминах конечных объединений множеств правильного линейного вида.
Применить разработанный подход решения проблемы однозначности алфавитного декодирования к классам тонких языков и регулярных языков с полиномиальной функцией роста и, используя информацию об их структуре, улучшить его, получив соответствующие оценки на сложность решающего алгоритма.
Найти алгоритмическое решение проблемы сравнения полезности произвольной пары функций алфавитного кодирования в общих алфавитах.
Найти алгоритмическое решение проблемы сравнения полезности произвольной пары регулярных языков в общем алфавите.
Показать, что процедура алфавитного декодирования в классах тонких языков и регулярных языков с полиномиальной функцией роста имеет простую сложность.
Научная новизна. Результаты являются новыми, получены автором самостоятельно. Основные результаты:
Предложен новый автоматно-алгебраический подход к решению проблемы однозначности алфавитного кодирования регулярных языков.
Приведена классификация внутренней структуры тонких множеств в терминах конечных объединений прогрессивных множеств.
Приведена классификация внутренней структуры регулярных языков с полиномиальной функцией роста в терминах конечных объединений множеств правильного линейного вида.
Показана полиномиальность верхних оценок на сложность решения проблемы однозначности алфавитного кодирования регулярных языков новым автоматно-алгебраическим подходом.
Показано, что проблема сравнения полезности произвольной пары функций алфавитного кодирования в общих алфавитах алгоритмически разрешима.
Показано, что проблема сравнения полезности произвольной пары регулярных языков в общем алфавите алгоритмически разрешима в случае, когда мощность этого алфавита равна двум.
Предложена модель, демонстрирующая практическую значимость полученных результатов.
Исследован вопрос о сложности процедуры алфавитного декодирования в классах тонких языков и регулярных языков с полиномиальной функцией роста.
Теоретическая и практическая значимость. Работа имеет теоретический характер и может быть интерпретирована как продолжение исследований Ал. А. Маркова в области алфавитного кодирования. С помощью результатов работы можно эффективно проверять свойство однозначности алфавитного кодирования в языках из классов тонких языков и регулярных языков с полиномиальной функцией роста. Также эти результаты могут быть применены в области исследований по сжатию информации. Разработана модель, демонстрирующая практическую ценность полученных теорем и при передаче информации по оптическому каналу связи с целью сокрытия внутренней логики соответствующего кодирования.
Методология и методы исследования. В работе применены методы дискретной математики, теории чисел и теории автоматов.
Положения, выносимые на защиту:
1. Получение верхних полиномиальных оценок на сложность реше
ния проблемы однозначности алфавитного кодирования в классах тон
ких языков и регулярных языков с полиномиальной функцией роста.
-
Построение полной неизбыточной классификации внутренней структуры элементов из класса тонких языков в терминах конечных объединений прогрессивных множеств.
-
Построение полной неизбыточной классификации внутренней структуры элементов из класса регулярных языков с полиномиальной функцией роста в терминах конечных объединений множеств правильного линейного вида.
Степень достоверности и апробация результатов. Результаты прошли апробацию на международных и всероссийских научных конференциях, а также на авторитетных научных семинарах.
Конференции.
Международная конференция студентов, аспирантов и молодых ученых "Ломоносовские чтения" (7-15 апреля 2011 года, 2-9 апреля 2012 года, 15-26 апреля 2013 года, 14-23 апреля 2014 года, 18-27 апреля 2016 года, Москва, МГУ).
XI Международный семинар "Дискретная математика и ее приложения", посвященный 80-летию со дня рождения О.Б. Лупа-нова (18-23 июня 2012, Москва, МГУ).
Семинары.
Семинар "Теория автоматов" под руководством академика, профессора, д.ф.-м.н. В. Б. Кудрявцева, механико-математический факультет МГУ им. М.В. Ломоносова (2008 - 2016 г.г.).
Семинар "Кибернетика и информатика" под руководством академика, профессора, д.ф.-м.н. В. Б. Кудрявцева, механико-математический факультет МГУ им. М. В. Ломоносова (2008 - 2016 г.г.).
Семинар "Вопросы сложности алгоритмов поиска" под руководством академика АТН РФ, профессора, д.ф.-м.н. Э. Э. Гасанова, механико-математический факультет МГУ им. М. В. Ломоносова (2013 - 2016 г.г.).
Семинар "Дискретный анализ" под руководством член-корр. АТН РФ, профессора, д.ф.-м.н. С. В. Алешина, механико-математический факультет МГУ им. М. В. Ломоносова (2013 - 2016 г.г.).
Семинар "Теория графов и синтез БИС" под руководством доцента, к.ф.-м.н. А. А. Часовских, механико-математический факультет МГУ им. М. В. Ломоносова (2013 - 2016 г.г.).
Публикации. Материалы диссертации опубликованы в 5 печатных работах, из них 5 статей в списке ВАК.
Структура и объем диссертации. Диссертация состоит из введения, раздела благодарностей, 6 глав, заключения, краткого списка обозначений и библиографии. Общий объем диссертации - 213 страниц, из них 200 страниц текста. Библиография включает в себя 40 наименований на 5 страницах.
Доказательство основных утверждений
Также возникают автоматы W llW 2 Є K(B,E2,rh), W3 є К {В,E2lттг), для которых X( rv і ) — / (J-( vv )) X( KF о ) — / (J-( IT9 )) X( \/\/ о ) — / (J.( Ккя Отметим, что автоматы Vi и VFi совпадают, так как получены из автомата Vq применением леммы 3 о разрезе по одинаковому слову 7- Кроме того, q - начальное состояние у V\. Пусть І7І п и (/?i, ф\ - функция переходов и функция выходов автомата V\ соответственно. Рассмотрим множество {(/?i(g, [/(7)) I 0 I п}. Его мощность не превосходит мощности множества всех состояний автомата Vi, которая равна п. Поэтому из принципа Дирихле заключаем, что найдутся О l\ I2 п, /і, Ь Є No такие, что (#, [ (7)) = ( 5 [/2(7))-Рассмотрим слово У = [/1(7) ]7І- (7)- Тогда = ipi( pi(q, [/2(7))?]7І-/2(7)) = ФІІЯІ [z2(т) ]ІтІ— 2( )) = і( 7) = 1-Последнее равенство верно, так как 7 Є l(Vi). Поэтому Є 1(Vi) и у афі Є l(Vi) І( ) 1( з) С Р, 7 2/ 2 Є 1(И і) І(И ) 1(И з) Q Р-При этом 7 1 А 7 7 аФъ так как аі 7 &2- Кроме того, Т I О/ /jfi Г)л J 7" I О/ /jfrj /Г/О ) ведь /(7 1 А) — /(7а2/У- Наконец, І7І = і + І7І — h І7І Исходя из всего вышеизложенного изначально можем теперь считать, что І7І ft. Пусть /(Д) = 1/1, /(ft) — 2 1 Так как / ( "У ) / ( (Хл ) Z i — / (/ ) / (tXi ) / (кЭл ) — / ( "УСЬл Оі ) — — т ( о/ /jf г) Па ) — г I о/ J I [ CLo ) Т \ LJO ) — / ( / ) / ( CL о ) Z 9 Z l то Применяя лемму 2 о склейке для автоматов V , W Є К {В, 2, т) и слов /(ft), /(/%) по их общей части i/i, получаем существование такого слова i/J в алфавите В, для которого выполнено i J Є l(V ), 1/2 1 Є 1(1Уз), \v[\ ттг . Так как l(V ) = /(1(Уз)), 1(И з) = f(l(W )), то существуют такие, что При этом 7 22/ 2 Є 1( і) 1( г) 1( з) Q Р-Кроме того, т І у/7,1 /у-і ) — / ( / ) / ( (7,1 ) А — Т І О/ J 7" І /То ) ІУоІУі — — т І О/ ] т І /7,о ) / ( Г)п ) — / ( /(7/9 Оо Наконец, 7 l/?i 7 7а2/ 2 5 так как а\ о 2- Исходя из всего вышеизложенного изначально можем теперь считать, что \v\\ т2. Далее, так как f{a\) = /(аг) 2? то 2І — /(al) — /(а2) If — 1 Значит І7 іАІ = І7І + Іаі + ІАІ + 1 + /(А) = п +1 + г і n + 1 + т , l7a2ft — І7І + Іа2І + \h\ n + 1 + /(/52) = n + 1 + I 2 11 n + 1 + m + If — 1 = n + m + If. Получили требуемую оценку. Для случая, когда 7 = Л рассуждения проходят аналогично с той лишь разницей, что в них нет автоматов Vi, W\, V{, W[. И итоговая оценка станет равна т2 + If. Утверждение леммы доказано. 3. Доказательство основных утверждений Теорема 1.1 Пусть А, В - некоторые конечные непустые алфавиты, / Є F(A1B)1 Р С А . Пусть, кроме того, для некоторых фиксированных m, к Є N имеем: 1) существует V Є К (А, Е к), для которого 1(V) = Р; 2) для каждого V\ Є [V] существует W\ Є К (В,Е2,т), для которого \{W\) = f(l(Vij). Тогда P Є /(/) если и только если Р (к + т2 + If) Є /(/). Доказательство. Нетрудно видеть, что утверждение теоремы 1.1 непосредственно вытекает из леммы 5. Теорема доказана. Замечание. Из леммы 4 следует, что в качестве числа т из формулировки теоремы 1 всегда можно взять число 2k(Lf \A\+l). Ясно, что это очень грубая оценка. Для класса тонких языков и для класса регулярных языков с полиномиальной функцией роста ее можно значительно понизить. Об этом можно прочитать в главах 4 и 5.
Теорема 1.2 Пусть А, В - некоторые конечные непустые алфавиты, f Є F(A1B)1 Р С А . Пусть, кроме того, Р представимо в виде конечного объединения множеств Pi таких, что для некоторых фиксированных m, к Є N при всех г имеем: 1) существует Vi Є К (А, E2,h), для которого l(V ) = Р 2) для каждого V Є [V ] существует W Є К (В,Е2,т), для которого l(W) = /(1(V)). Тогда Р Є /(/) если и только если Р (к2 + т2 + If) Є /(/). Доказательство. Ясно, что из условия Р Є /(/), очевидно следует Р (к2 + т2 + lf) Є /(/). Допустим теперь, что Р ф 1(f)- Тогда существуют скі,а2 Є Р такие, что аі ft2 и /( i) — /( 2)- Так как Р распадается в конечное объединение Р то для некоторых г, s Є N имеем а\ Є Рг и а 2 Є Ps. При этом г и s могут совпадать. Далее рассуждение почти полностью повторяет идею доказатель 40 ства теоремы 1 c использованием леммы 5 о минимизации. Единственным отличием является то, что оценка на длину общего для а\ и OL2 префикса 7 теперь равна не /с, а к2. Это связано с тем, что верхний (по QLI) и нижний (по а ) автоматы для этого префикса теперь могут быть разными. Теорема 1.2 доказана. Замечание. Эта теорема будет использована в главе 4 для решения проблемы ОАД2 - проблемы ОАД для класса тонких языков. Теорема 1.3 Пусть А, В - некоторые конечные непустые алфавиты, / Є F(A1B)1 Р С А . Пусть, кроме того, Р представимо в виде конечного объединения множеств Pi таких, что для некоторых фиксированных га, к Є N при всех г имеем: 1) существует Vi Є К (А, E2,k), для которого l(V ) = Р 2) для каждого V Є [V ] существует конечное множество автоматов UІ Є К (В, 2, га), 1 г s, sGN таких, что (J 1(Ю = f(l(Vj). г=1 Тогда Р Є /(/) если и только если Р (к2 + га2 + If) Є /(/).
Доказательство вспомогательных утверждений
Другими словами, в Р должно быть s несовпадающих слов одинаковой длины, но не должно быть s+1 несовпадающих слов одинаковой длины. При s = 1 мы получаем определение класса 1-тонких множеств, приведенное выше.
Для каждого s G N обозначаем через %S{A) множество всех s-тонких множеств в алфавите А. Через %{А) обозначаем множество оо %(А) := I \%S(A). г=\ Называем это множество классом тонких множеств, а его элементы - тонкими множествами. Пусть Р С А . Через Тп{Р) обозначаем мощность множества Р {п) : Тп{Р) := -Р (ГІ). Через Тр обозначаем функцию Тр : N — No, где Тр{п) := Тп{Р) для всех п Є N. Называем Тр функцией роста для Р. Говорим, что Р имеет константную функцию роста и пишем Тр є Const, если функция Тр ограничена сверху каким-нибудь полиномом нулевой степени (то есть, константой). Говорим, что Р имеет линейную функцию роста и пишем Тр Є Lm, если функция Тр ограничена сверху каким-нибудь полиномом первой степени и при этом не ограничена сверху никаким полиномом нулевой степени (то есть, константой).
Пусть a, b Є N. Если а делится нацело на 6, то пишем Ъ\а. Через Zab обозначаем множество: Za,b = {п Є N п а, Ь\п}. Проблемой проверки однозначности алфавитного декодирования в классе тонких языков в алфавите А (или сокращенно - проблемой ОАД2) называем проверку свойства Р Є /(/) для произвольных / є F(A, В) и Р є (А). Теорема 2.1 Имеют место следующие утверждения: а) любое конечное объединение спектрально независимых в сово 54 купности общепрогрессивных множеств является 1-тонким множеством; б) любое 1-тонкое множество представимо в виде конечного объединения спектрально независимых в совокупности общепрогрессивных множеств. Теорема 2.2 Имеют место следующие утверждения: а) любое конечное объединение попарно непересекающихся прогрес сивных множеств является тонким множеством; б) любое тонкое множество представимо в виде конечного объ единения попарно непересекающихся прогрессивных множеств. 2. Доказательство вспомогательных утверждений Лемма 1. Пусть А - некоторый конечный алфавит и Р - регулярное множество в алфавите А. Тогда оно представимо регулярным выражением вида к V CVi,l №,l) г,2 Cti,s(i)-1 РРг,в(г)-і) (г), где к, s(l),..., s(k) - некоторые натуральные числа, адд,..., &k,s(k) - некоторые слова в алфавите А, ЧРід? 4Pfc,s(fc)-i - некоторые регулярные выражения в алфавите А. Доказательство. Будем доказывать утверждение индукцией по минимальной длине I вывода Р из 0 и букв алфавита А с помощью операций U, , . База индукции (I = 0). Если Р = 0, то Р представимо регулярным выражением Л. Здесь к = 1, s(l) = 1, скід = Л. Если же Р = {а}, где а Є А, то Р представимо регулярным выражением а. Здесь к = 1, s(l) = 1, Переход индукции (1,... ,1 = I + 1). Разбираем случаи в зависимости от того, какая из операций U, , применена последней. Случай 1. Минимальная длина вывода Р равна I и Р = Р . Тогда минимальная длина вывода Pi меньше I и по предположению индукции Рі представимо регулярным выражением к Pl = \J al}i (фг,і) Яг,2 i,s{i)-l №,s(i)-l) «г,8(г)-г=1 Значит Р представимо регулярным выражением рРі) . Осталось взять к = 1, s(l) = 2, адд = ад;2 = А, Рід = Рь Случай 2. Минимальная длина вывода Р равна Z и Р = Pi U Р2. Тогда минимальная длина вывода Pi и Р меньше I и по предположению индукции Pi и Р представимы регулярными выражениями к
Доказательство основных утверждений
Если бы слово f3n было префиксом сверхслова а, то оно было бы равно а). Но из леммы 2 главы 2 тогда бы следовало, что слова а и р соизмеримы. Полученное противоречие завершает доказательство леммы 5. Лемма 6. Пусть А - конечный алфавит и Р - множество линейного вида в алфавите А. Тогда оно представимо в виде конечного объединения множеств Pi правильного линейного вида в алфавите А. Доказательство. Из определения множеств линейного вида следует, что множество Р представимо регулярным выражением ли 107 нейного вида Р = а\ (А) OL2 . . . OLs (/У &s+l (1) для некоторых s Є No и #1,..., as+i Є А , Д,..., /3S Є А \ {Л}. Можно сразу считать, что первые буквы (если они есть) слов / ,с +і различны при всех 1 і s. В самом деле, если это не так, то где-нибудь в выражении можно применить операцию перекидывания:
Ясно, во-первых, что такое преобразование можно применить к выражению последовательно лишь конечное количество раз, так как через итерации можно перекидывать только буквы из слов щ и делается это всегда справа налево. Во-вторых, что более интересно, окончательный результат }У таких преобразований не зависит от того, в каком именно порядке перекидываются буквы через итерации. Будем при этом говорить, что }У получен применением процедуры перекидывания к выражению (1). Пусть: Р := а[ (Р[) Q-2 oi s (fig) c/s+i Допустим, что хотя бы одно из слов а2,... , OL S равно Л. Пусть это, например, а 2. Тогда в р рядом находятся две итерации - (/3[) и 108 Наряду с процедурой перекидывания нам потребуется еще одна процедура, которую мы будем называть процедурой расщепления. Эта процедура применяется к выражению вида (а) (/?) (2) и устроена следующим образом. Если слова а и /3 соизмеримы, то применяется лемма 4 и выражение (2) заменяется на дизъюнкцию выражений вида S . В каждом из этих выражений ровно одна итерация. При этом под итерацией может быть и пустой символ Л; называем такие итерации пустыми. Если же слова а и /3 не соизмеримы, то (2) заменяется на выражение (а) (Л) V (а) /3 (Л) V (а) /3 (Л) V ... V V(a) /? а (Л) V (а) /? а (/3) . После этого к выражению (а) /та (/З) применяется процедура перекидывания. Из доказательства леммы 5 следует, что результат этого преобразования будет иметь правильный линейный вид. Каждый из дизъюнктов нового выражения содержит ровно две итерации; при этом либо одна из них пустая, либо дизъюнкт имеет правильный линейный вид. Описание процедуры расщепления закончено. При этом важно помнить, что результат ее применения представляет то же множество, что и (2).
Теперь мы можем применить к }У процедуру расщепления для (/3J) (/ЗУ . Новое выражение распадается на дизъюнкты, в каждом из которых или есть пустая итерация, или к самой левой из итераций неприменима операция перекидывания. Удаляем из дизъюнктов все итерации пустого символа и применяем к результатам процедуру перекидывания. Таким образом, выражение }У заменено нами на дизъюнкцию выражений, в каждом из которых или стало меньше итераций, или появилось больше итераций с неприменимой к ним операцией перекидывания. Для каждого из новых дизъюнктов проверяем, есть ли в них соседние пары итераций. Если такие есть, то к самой левой из пар опять применяем операцию расщепления. Рано или поздно в получаемых выражениях или кончатся итерации, или к ним нельзя будет нигде применить операцию перекидывания. В любом случае выражения будут иметь правильный линейный вид. Утверждение леммы 6 доказано.
Доказательство основных утверждений
Лемма 1. Пусть А - конечный алфавит и Р Є WRP (A) для некоторого п Є N. Тогда существует V Є К (А, , + 2) такой, что 1(V) = Р. Доказательство. Эта лемма является обобщением леммы 2 из предыдущей главы. Все обозначения для диаграмм автоматов взяты оттуда. Так как Р Є WRP (A), то Р представимо выражением правильного линейного вида сложности не выше п : Р = \а\ (ft) «2 (ft) ois (ft) c +i 134 Построим диаграмму Мура для V. Возможно 4 случая. Случай 1. \ Л, s+\ Л. Тогда соответствующая диаграмма имеет вид /о Л /о Л s /О Л i/0 __ 2/0 _ з/0 ... s/0 _ s+i/l Случай 2. і = Л, s+i 7 Л. Тогда диаграмма имеет вид /о /о s /о Л Л Л 2/ _ __ з/0 ... s/0 __ s+l/1 Случай 3. i 7 Л, s+i = Л. Тогда диаграмма имеет вид /0 Л /о Л s-i/o А s/1 Л i/0 __ 2/0 _ з/0 ... s_i/0 _ ./ Случай 4. i = s+i = Л. Тогда диаграмма имеет вид /о Л /о Л s-i/o / \ s/1 Л 2/ __ __ з/0 ... s_i/0 .ч/ Во всех этих диаграммах есть еще одно дополнительное состоя 135 ние, выполняющее роль "тупика". В него отправляются все недостающие стрелки и на выходе у этих стрелок символ 0. В каждой из этих диаграмм не более чем (s + 2) + (Z(CKI) — 1) + (I(Pi) — 1) + ... + (l(Ps) — 1) + (l(as+i) — 1) + 1 = = l(ai) + I (Pi) + ... + l(Ps) + l(as+i) + (s + 2) — (2s + 1) + 1 l(a\) + I (Pi) + ... + l(Ps) + l(as+i) + 2 n + 2 состояний. Утверждение леммы 1 доказано. Лемма 2. Пусть А - конечный алфавит, Р Є WRP (A) для некоторого п Є N и V - автомат из леммы 1 для множества Р. Тогда для всех V\ Є [V] выполнено одно из двух условий: 1) l(V\) = 0; 2) l(Vi) Є WRP A). Доказательство. Эта лемма является обобщением леммы 3 из предыдущей главы. Так как Р Є WRP (A), то Р представимо выражением правильного линейного вида сложности не выше п : Р = \а\ (Р\У OL2 (Р2Т . . . QLS (Ps) as+l\ (1) Разберем, для примера, случай, когда а\ Л и as+\ Л. Остальные случаи разбираются аналогично. Если в качестве начального состояния автомата V\ берется "тупиковое" состояние автомата V, то l(V\) = 0. Опять же, если это состояние, находящееся на конце 136 у слова as+i, то l(Vi) = 0. Пусть теперь это какое-то другое состояние. Возможны три принципиально разных случая. Случай 1. Это состояние находится внутри или по краям одного из слов с , где і s. Тогда 1( і) — W (ft) (ft) &s+i\ (2) для некоторого постфикса (возможно, пустого) а слова с . Так как выражение из (1) имеет правильный линейный вид, то и множество (2) имеет правильный линейный вид. Кроме того, L{a (ft) ... (ft) ois+i) L(0L\ (ft) OL2 (ft) OLs (ft) Cl +l) П. Значит l(Vi) Є WRP (A). Случай 2. Это состояние находится внутри какой-то из петель ft, где г s. Тогда 1( 1) — ft (ft) (ft) s+l\ (3) для некоторого постфикса ft слова ft. Так как выражение из (1) имеет правильный линейный вид, то и множество (3) имеет правильный линейный вид. Кроме того, L(ft (ft) ... (ft) as+i) 2L(a\ (ft) 0L2 (ft) OLS (ft) as+i) 2n. 137 Значит l(Vi) Є WRP2ln(A). Случай 3. Это состояние находится внутри as+\. Тогда l(Vi) = І7І (4) для некоторого постфикса слова as+\. Очевидно, что множество (4) имеет правильный линейный вид и - (тО — L{a\ (ft) 0L2 (ft) ... OLS (ft) cwi) n Значит l(Vi) Є WRP (A). Все случаи разобраны. Утверждение леммы 2 доказано. Лемма 3. Пусть А - конечный алфавит и Р Є RPn(A) для некоторого п Є N. Тогда Р Є WiPn2(A). Доказательство. Доказательство леммы основано на процедуре, описанной в лемме 6 главы 3. Рекомендуется предварительно вспомнить используемую там технику. Очевидно, что достаточно доказать утверждение лишь для случая, когда Р Є RP (A). Пусть Р представимо регулярным выражением линейного вида Р = а\ (ft) OL2 . . . OLs (ft) C s+li (1) где s Є No, скі,..., as+i Є A , ft,... ,ft Є A \ {Л}. Рассмотрим более подробно процедуру преобразования этого выражения в конечную дизъюнкцию выражений правильного линейного вида, 138 которая описана в лемме 6 главы 3. При выполнении процедуры "перекидывания" сложность рассматриваемых линейных выражений остается неизменной. А процедур "расщепления" всего будет проведено не более s — 1 - по числу соседних пар итераций. Для каждой из этих процедур возможны два случая. Случай 1. Под расщепляемыми итерациями находятся соизмеримые слова. Без ограничения общности, рассмотрим случай, когда это /3 и /?2- Для некоторых v Є A , a, b Є N имеем j3\ = і/а, /% = zA Получаем выражение