Центральный Дом Знаний - Гладкий А.В. Формальные грамматики и языки

Информационный центр "Центральный Дом Знаний"

Заказать учебную работу! Жми!



ЖМИ: ТУТ ТЫСЯЧИ КУРСОВЫХ РАБОТ ДЛЯ ТЕБЯ

      cendomzn@yandex.ru  

Наш опрос

Я учусь (закончил(-а) в
Всего ответов: 2590



Гладкий А.В. Формальные грамматики и языки

Гладкий А.В. 
М.: Наука, 1973. - 368 с. 

 Книга посвящена теории формальных грамматик и языков, являющейся важнейшей составной частью так называемой математической лингвистики. Эта теория вызвана к жизни потребностями лингвистики, но нашла свою почву в чистой математике и стала полноправной отраслью математической логики, тесно связанной с теорией алгоритмов и теорией автоматов. В книге рассматривается ряд важных проблем теории формальных грамматик — таких, как взаимоотношения между различными классами грамматик и классами задаваемых ими языков, связь между грамматиками и автоматами, оценки сложности вывода в рамматиках, алгоритмические проблемы для грамматик. Книга представляет большой интерес для специалистов как в области математической лингвистики, так и в смежных областях, например в теории алгоритмов и автоматов.


ОГЛАВЛЕНИЕ:
Предисловие'   .'................... 5
Введение ................. 9
Глава 1. Основные понятия............. 17
§ 1.0. Некоторые предварительные пояснения...... 17
§ 1:1. Цепочки и языки.............. 19
§ 1:2. Грамматики ................ 25
§ 1:3. Примеры грамматик ........ 33
§ 1.4. Машины Тьюринга.............. 39.
Упражнения      ■   •   •............... ^0
Глава 2. Сигнализирующие функции.......... 55
§ 2.1. Сигнализирующие функции грамматик...... 55
§ 2.'2. Сигнализирующие функции машин Тьюринга  .... 62 § 2.3. Ускорение и сжатие выводов. Связь между сигнализирующими грамматик и машин......... 64
§ 2.4. Существование сколь угодно  сложных рекурсивных
языков.................. 71
Упражнения .................. 75
Глава 3. Грамматики составляющих.......... 79
§ 3.1. Деревья выводов.............. 79
§ 3.2. Неукорачивающие грамматики и машины Тьюринга
без растяжения  :.............. 84
§ 3.3. Сложность вывода в неукорачивающих грамматиках и
НС-грамматиках .............. 89
§ 3.4. Оценка временной сложности некоторых НС-языков  . 93
§ 3.5. НС-грамматйки с односторонним контекстом .... JQ5
Упражнения................... 1М-
Глава 4. Бесконтекстные грамматики и машины с магазинной
памятью................. 115
§ 4.1. Некоторые вспомогательные утверждения..... 115
§ 4.2. Распознавание пустоты и конечности Б-языка. Проекции • : : :...... 121
§ 4.3. Необходимые условия бесконтекстности...... 126
§ 4.4. Неоднозначность.............. 134-
§ 4.5. Машины с магазинной памятью......... 137>
Упражнения     .   .  .  .   ;............. IS*
Глава 5. Некоторые специальные классы бесконтекстных языков ...................157
§ 5.1. Автоматные и обобщенные автоматные языки. Конечные  автоматы...............157
§ 5.2. Операции над OA-языками. Регулярные языки . . . 162 § 5.3. Линейные,   металинейные   и итерационно-линейные
языки ..................168
§ 5.4. Грамматики с ограниченной активной емкостью выводов. ОАЕВ-языки..............174
Упражнения ..................179
Глава 6. Дополнительные сведения о бесконтекстных грамматиках. Другие способы задания бесконтекстных языков ...................185
§ 6.1. Категориальные грамматики..........185
§ 6.2. Нормальная форма Б-грамматики........196
§ 6.3. Доминационные грамматики..........200
§ 6.4. Системы уравнений в языках. Формальные степенные
ряды ..................207
§ 6.5. Каноническое представление Б-языка......213
Упражнения ..................218
Глава 7. Сложность вывода .в бесконтекстных грамматиках   . 221
§ 7.1. Глубина и разброс..............221
§ 7.2. Активная емкость..............228
§ 7.'3. Степень гнездования и степень самовставления . . 242 Упражнения ..................249
Глава 8. Неразрешимые алгоритмические проблемы   .... 252
§ 8.1. Предварительные замечания.......... 252
§ 8.2. Инвариантные свойства произвольных грамматик  .   . 256
§ 8.3. Инвариантные свойства НС-грамматик......260
§ 8.4. Некоторые проблемы, связанные с Б-грамматиками . 268 Упражнения ..................279
Приложение I. Системы составляющих и деревья синтаксического   подчинения.........282
§ Ш. 1. Системы составляющих...........282
§ П1.2. Деревья подчинения............294
§ Ш. 3. Связь между системами составляющих и деревьями
подчинения................304
Упражнения .............310
Приложение П. Замещаемость...........314
§ ПИЛ. Свободные полугруппы...........315
§ ПИ. 2. Замещаемость и взаимозамещаемость. Конфигурации ..... ...........318
§ ПИ. 3. Окрестности, классы и типы.........324
Упражнения ..................340
Библиографические замечания.............343
Литература................. , 349
Предметный "указатель   .  ,............!  ! 357
Указатель обозначений................367
Loading

Календарь

«  Ноябрь 2017  »
ПнВтСрЧтПтСбВс
  12345
6789101112
13141516171819
20212223242526
27282930

Архив записей

Друзья сайта

  • Заказать курсовую работу!
  • Выполнение любых чертежей
  • Новый фриланс 24