Теория формальных грамматик
Автор(ы): | Гросс М., Лантен А.
29.04.2015
|
Год изд.: | 1971 |
Описание: | Книга М. Гросса и А. Лантена посвящена одной из наиболее важных областей математической лингвистики — теории формальных грамматик Хомского. В первой части вводятся необходимые понятия из алгебры, математической логики и теории алгоритмов. Во второй рассматриваются некоторые классы формальных языков; третья часть посвящена алгебраической трактовке языков и их свойств. Написанная на достаточно высоком уровне строгости, книга в то же время является сравнительно легкой для чтения. Она будет полезна широкому кругу читателей: математикам, желающим ознакомиться с математической лингвистикой, специалистам по программированию и вычислительной математике, лингвистам и всем специалистам, работающим в смежных областях. |
Оглавление: |
Обложка книги.
Предисловие редактора перевода [5]От авторов [7] Предисловие [9] ЧАСТЬ I. ПРЕДВАРИТЕЛЬНЫЕ СВЕДЕНИЯ ИЗ ЛОГИКИ И АЛГЕБРЫ. Глава I. Слова (цепочки). Полугруппы. Языки [18] § 1.1. Свободная полугруппа [18] § 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] ЧАСТЬ II. НЕКОТОРЫЕ ЗАМЕЧАТЕЛЬНЫЕ КЛАССЫ ЯЗЫКОВ. Глава 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. Класс языков, допускаемых (порождаемых) МП-автоматами [161] § 9.4. Приложения КС-языков [155] Глава X. Автоматные языки и конечные автоматы [169] § 10.1. А-грамматики [159] § 10.2. Конечные автоматы [162] § 10.3. Некоторые обобщения и видоизменения конечных автоматов [166] § 10.4. Свойства замкнутости Представление A-языков по Клини [168] § 10.5. A-языки и КС-языки [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. Преобразования [220] Глава 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] ПРИЛОЖЕНИЕ. ТРАНСФОРМАЦИОННЫЕ ГРАММАТИКИ. § 1. Формальные грамматики и естественные языки [272] § 2. КС-грамматики и трансформации [274] § 3. Расширение грамматики [275] § 4. Проблемы, связанные с трансформациями [281] Избранная библиография [287] |
Формат: | djvu |
Размер: | 3273688 байт |
Язык: | РУС |
Рейтинг: | 199 |
Открыть: | Ссылка (RU) |