Скачать Советский учебник

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

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

Авторство: Гросс М., Лантен А

Формат: DjVu, Размер файла: 3.12 MB

СОДЕРЖАНИЕ

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

От авторов.

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

ЧАСТЬ I ПРЕДВАРИТЕЛЬНЫЕ СВЕДЕНИЯ ИЗ ЛОГИКИ И АЛГЕБРЫ

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

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

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

§ 1.3. Языки.

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

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

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

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

{spoiler=ОТКРЫТЬ:  оглавление полностью...}

 

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

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

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

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

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

§ 33 Упражнения.

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

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

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

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

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

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

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

§ 5 1 Исчисление функций.

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

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

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

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

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

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

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

ЧАСТЬ И. НЕКОТОРЫЕ ЗАМЕЧАТЕЛЬНЫЕ КЛАССЫ ЯЗЫКОВ

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

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

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

§ 7 3. Свойства замкнутости.

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

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

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

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

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

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

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

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

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

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

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

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

§ 10 1. А-грамматики.

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

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

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

§ 10 5. А-языки и КС-языки.

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

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

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

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

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

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

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

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

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

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

ЧАСТЬ 111. АЛГЕБРАИЧЕСКИЙ ПОДХОД

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

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

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

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

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

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

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

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

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

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

§ 15 1. Языки Дика.

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

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

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

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

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

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

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

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

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

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

ПРИЛОЖЕНИЕ. ТРАНСФОРМАЦИОННЫЕ ГРАММАТИКИ

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

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

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

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

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

{/spoilers}

Скачать бесплатный учебник  СССР - Теория формальных грамматик (Гросс, Лантен) 1971 года

Скачать...DjVu

 

{spoiler=ОТКРЫТЬ: - отрывок из учебника...}

 «Универсальный» метод решения проблемы эквивалентности, который прежде всего приходит в голову, состоит в следующем: взяв произвольную пару слов S и Г, последовательно образовать все слова, смежные с S, потом все слова, смежные с каждым из слов, полученных на первом шаге, и т. д., т. е., короче говоря, перечислить все слова, эквивалентные слову S, применяя сначала одно, потом два, потом три преобразования и т. д., пока мы не дойдем до Т. Однако сколько бы преобразований ни было выполнено, тот факт, что Т не найдено, еще ничего не означает: оно может быть получено после очередных преобразований. Таким образом, наш наивный «универсальный» метод не гарантирует нахождения решения.

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

{/spoilers}