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

Автор(ы):Гросс М., Лантен А.
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 байт
Язык:РУС
Рейтинг: 215 Рейтинг
Открыть: