Формальные грамматики и языки - Гладкий А.В.
Формальные грамматики и языки
Автор: Гладкий А.В.Издательство: Москва
Год издания: 1973
Страницы: 368
Читать: 1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 30 31 32 33 34 35 36 37 38 39 40 41 42 43 44 45 46 47 48 49 50 51 52 53 54 55 56 57 58 59 60 61 62 63 64 65 66 67 68 69 70 71 72 73 74 75 76 77 78 79 80 81 82 83 84 85 86 87 88 89 90 91 92 93 94 95 96 97 98 99 100 101 102 103 104 105 106 107 108 109 110 111 112 113 114 115 116 117 118 119 120 121 122 123 124 125 126 127 128 129 130 131 132 133 134 135 136
Скачать:
А. В. ГЛАДКИЙ
ФОРМАЛЬНЫЕ ГРАММАТИКИ И ЯЗЫКИ
ИЗДАТЕЛЬСТВО «НАУКА» ГЛАВНАЯ РЕДАКЦИЯ ФИЗИКО-МАТЕМАТИЧЕСКОЙ ЛИТЕРАТУРЫ
618 Г 62
УДК 519-95
Формальные грамматики и языки. Г л а д к и й А. В.
Книга посвящена теории формальных грамматик и языков, являющейся важнейшей составной частью так называемой математической лингвистики. Эта теория вызвана к жизни потребностями лингвистики, но нашла свою почву в чистой математике и стала полноправной отраслью математической логики, тесно связанной с теорией алгоритмов и теорией автоматов.
В книге рассматривается ряд важных проблем теории формальных грамматик — таких, как взаимоотношения между различными классами грамматик и классами задаваемых ими языков, связь между грамматиками и автоматами, оценки сложности вывода в грамматиках, алгоритмические проблемы для грамматик.
Книга представляет большой интерес для специалистов как в области математической лингвистики, так и в смежных областях, например в теории алгоритмов и автоматов.
Страниц 368. Иллюстраций 17.
Алексей Всеволодович Гладкий ФОРМАЛЬНЫЕ ГРАММАТИКИ И ЯЗЫКИ М., 1973 г., 368 стр. с илл.
Редактор В. В. Донченко Техн. редактор Е. Н. Земская Корректор Я. Б. Румянцева
Сдано в набор 10/VII 1972 г. Подписано к печати 8/II 1973 г. Бумага 84ХЮ8/К. тип. №2. Фнз. печ. л. 11,5. Условн. печ. л. 19,32. Уч.-изд. л. 20,20,
Тираж 7000 экз. Т-00756. Цена книги 1 р. 51 к. Заказ № 273
Издательство «Наука»
Главная редакция физико-математической литературы 117071, Москва, В-71, Ленинский проспект, 15
Ордена Трудового Красного Знамени Ленинградская типографифя № 2 имени Евгении Соколовой «Союзполнграфпрома» прн Государственном комитете Совета Министров СССР по делам издательств, полиграфии и книжной торговли г. Ленинград, Л-52, Измайловский проспект, 29
0223-1714 : -
942 ( 02)-73
ОГЛАВЛЕНИЕ
Предисловие’ ................................................
Введение ' : : : :...........................................
Глава 1. Основные понятия....................................
§ 1.0. Некоторые предварительные пояснения...............
§ 1:1. Цепочки и языки...................................
§ 1:2. Грамматики .......................................
§ 1:3. Примеры грамматик .................
§ 1.4. Машины Тьюринга ..................................
Упражнения ? • ....................................
Глава 2. Сигнализирующие функции.............................
§ 2.1. Сигнализирующие функции грамматик.................
§ 2.'2. Сигнализирующие функции машин Тьюринга .... § 2.3. Ускорение и сжатие выводов. Связь между сигнализирующими грамматик и машин................................
§ 2.4. Существование сколь угодно сложных рекурсивных
языков.............................................
Упражнения ..............................................
Глава 3. Грамматики составляющих.............................
§ 3.1. Деревья выводов...................................
§ 3.2. Неукорачивающие грамматики и машины Тьюринга
без растяжений :...................................
§ 3.3. Сложность вывода в неукорачивающих грамматиках и
НС-грамматиках ....................................
§ 3.4. Оценка временной сложности некоторых НС-языков . § 3:5. НС-грамматйки с Ьдйосторонним контекстом .... Упражнения ..............................................
Глава 4. Бесконтекстные грамматики и машины с магазинной
памятью............................................
§ 4.1. Некоторые вспомогательные утверждения.............
§ 4.2. 'Распознавание пустоты и конечности Б-языка. Проекции ‘ ................................
§ 4.3. Необходимые условия бесконтекстности..............
§ 4.4. Неоднозначность ..................................
§ 4.5. Машины с магазинной памятью.......................
Упражнения . . . . ......................................
5
9
17
17
19
25
33
39
50
55
55
62
64
71
75
79
79
84
89
93
105
И»:
115
115
121
126
134
137
152-
4
ОГЛАВЛЕНИЕ
Глава 5. Некоторые специальные классы бесконтекстных языков ...........................................................157
§ 5.1. Автоматные и обобщенные автоматные языки. Конечные автоматы...............................................157
§ 5.2. Операции над ОА-языками. Регулярные языки . . . 162 § 5.3. Линейные, металинейные и итерационно-линейные
языки ..............................................168
§ 5.4. Грамматики с ограниченной активной емкостью выводов. ОАЕВ-языки............................................174
Упражнения ................................................179
Глава 6. Дополнительные сведения о бесконтекстных грамматиках. Другие способы задания бесконтекстных языков ...........................................................185
§ 6.1. Категориальные грамматики...........................185
§ 6.2. Нормальная форма Б-грамматики.......................196
§ 6.3. Доминациониые грамматики............................200
§ 6.4. Системы уравнений в языках. Формальные степенные
ряды ...............................................207
