URSS.ru - Издательская группа URSS. Научная и учебная литература
Об издательстве Интернет-магазин Контакты Оптовикам и библиотекам Вакансии Пишите нам
КНИГИ НА РУССКОМ ЯЗЫКЕ


 
Вернуться в: Каталог  
Обложка Гросс М., Лантен А. Теория формальных грамматик. Пер. с франц.
Id: 88878
 
1199 руб.

Теория формальных грамматик. Пер. с франц.

1971. 294 с. Твердый переплет. Букинист. Состояние: 4+. .

 Аннотация

Книга М. Гросса и А. Лантена посвящена одной из наиболее важных областей математической лингвистики --- теории формальных грамматик Хомского. В первой части вводятся необходимые понятия из алгебры, математической логики и теории алгоритмов. Во второй рассматриваются некоторые классы формальных языков; третья часть посвящена алгебраической трактовке языков и их свойств.

Написанная на достаточно высоком уровне строгости, книга в то же время является сравнительно легкой для чтения. Она будет полезна широкому кругу читателей: математикам, желающим ознакомиться с математической лингвистикой, специалистам по программированию и вычислительной математике, лингвистам и всем специалистам, работающим в смежных областях.


 ОГЛАВЛЕНИЕ

Предисловие редактора перевода................ 5

От авторов......................... 7

Предисловие......................... 9

ЧАСТЬ I. предварительные сведения из логики и алгебры

Глава I. Слова (цепочки). Полугруппы. Языки........... 13

§ 1.1. Свободная полугруппа................ 13

§ 1.2. Операции над словами................ 18

§ 1.3. Языки...................... 23

§ 1.4. Упражнения.................... 26

Глава II. Общие сведения о формальных системах.......... 30

§ 2.1. Описание исчисления высказываний на интуитивном уровне.. 30

§ 2.2. Понятие формальной системы............. 37

§ 2.3. Формализованный вариант исчисления высказываний.... 42

§ 2.4. Определение формальной системы........... 46

Глава III. Комбинаторные системы................ 49

§ 3.1. Определение комбинаторных систем........... 49

§ 3.2. Нормальные системы................ 57

§ 3.3 Упражнения.................... 61

§ 3.4. Независимость от алфавита.............. 61

Глава IV. Алгоритмы. Машины Тьюринга............. 64

§ 4.1. Алгоритмы.................... 64

§ 4.2. Машины Тьюринга................. 68

§ 4.3. «Численные» машины Тьюринга............ 76

§ 4.4. Упражнения.................... 79

Глава V.' Вычислимость и разрешимость.............. 81

§ 5.1. Исчисление функций................. 81

§ 5.2. Операции над функциями............... 83

§ 5.3. Метод Гёделя................... 86

§ 5.4. Рекурсивные и рекурсивно перечислимые множества.... 89

§ 5.5. Замечания и дополнения............... 93

Глава VI. Комбинаторные системы и машины Тьюринга: неразрешимые проблемы...................... 99

§ 6.1. Комбинаторные системы и машины Тьюринга....... 99

§ 6.2. Неразрешимые проблемы............... 105

часть VI. некоторые замечательные классы языков

Глава VII. Контекстно-свободные языки (языки Хомского): общая характеристика и основные свойства..............112

§ 7.1. Грамматика и описание синтаксических структур......112

§ 7.2. Определения. Распознаваемые свойства.........116

§ 7.3. Свойства замкнутости................123

§ 7.4. Специальные классы КС-языков............126

§ 7.5. Упражнения....................129

Глава VIII. Нераспознаваемые свойства КС-грамматик........130

§ 8.1. Проблемы, связанные с пересечением..........130

§ 8.2. Проблемы, связанные с неоднозначностью........133

§ 8.3. Существенная неоднозначность минимальных линейных языков 139

Глава IX. Автоматы с магазинной памятью.............143

§ 9.1. Автоматы, допускающие языки.............143

§ 9.2. Автоматы, порождающие языки............149

§ 9.3. Класс языков, допускаемых (порождаемых) МП-автоматами. 151

§ 9.4. Приложения КС-языков...............155

Глава X. Автоматные языки и конечные автоматы..........159

§ 10.1. А-грамматики...................159

§ 10.2. Конечные автоматы................162

§ 10.3. Некоторые обобщения и видоизменения конечных автоматов. 166

§ 10.4. Свойства замкнутости. Представление А-языков по Клини.. 168

§ 10.5. А-языки и КС-языки................171

§ 10.6. Односторонние конечные преобразователи........172

Глава XI. Задание языков с помощью систем уравнений........175

§ 11.1. Функции, аргументами и значениями которых являются языки 175

§ 11.2. Языки и формальные степенные ряды.........189

Глава XII. Грамматики непосредственно составляющих. Автоматы с линейно

ограниченной памятью................194

§ 12.1. Грамматики непосредственно составляющих (НС-грамматики) 194

§ 12.2. Линейно ограниченные автоматы...........196

§ 12.3. Классификация автоматов..............199

§ 12.4. Упражнения...................201

часть iii. алгебраический подход

Глава XIII. Гомоморфизмы полугрупп..............202

§ 13.1. Произвольные полугруппы..............202

§ 13.2. Конгруэнция и эквивалентности, сопоставляемые языку... 207

§ 13.3. Понятия, связанные с кодами.............212

Глава XIV. Дополнительные сведения об автоматных языках......214

§ 14.1. Стандартные А-языки................ 214

§ 14.2. Свойства стандартных А-языков............217

§ 14.3. Алгебраическое описание А-языков...........218

§ 14.4. Преобразования..................226

Глава XV. Дополнительные сведения о КС-языках........... 232

§ 15.1. Языки Дика................... 232

§ 15.2. Стандартные КС-языки...............240

§ 15.3. Совпадение класса КС-языков с классом языков, допускаемых

автоматами с магазинной памятью...........244

§ 15.4. Упражнения...................245

Глава XVI. Алгебраические языки................247

§ 16.1. Дополнительные сведения о формальных степенных рядах.. 247

§ 16.2. Алгебраические ряды................257

§ 16.3. Приложения к языкам...............259

§ 16.4. Упражнения...................264

§ 16.5. Применение «языковых» уравнений в комбинаторной геометрии 264

ПРИЛОЖЕНИЕ. трансформационные грамматики

§ I. Формальные грамматики и естественные языки....... 272

§ 2. КС-грамматики и трансформации............274

§ 3. Расширение грамматики...............276

§ 4, Проблемы, связанные с трансформациями.........281

Избранная библиография....................287

 
© URSS 2016.

Информация о Продавце