Теория формальных грамматик, Гросс М., Лантен А, 1971

Теория формальных грамматик, Гросс М., Лантен А, 1971.

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



ОГЛАВЛЕНИЕ
Предисловие редактора перевода.
От авторов.
Предисловие.
ЧАСТЬ I ПРЕДВАРИТЕЛЬНЫЕ СВЕДЕНИЯ ИЗ ЛОГИКИ И АЛГЕБРЫ
Глава I. Слова (цепочки). Полугруппы. Языки.
§ 1.1. Свободная полугруппа.
§ 1.2. Операции над словами.
§ 1.3. Языки.
§ 1.4. Упражнения.
Глава //. Общие сведения о формальных системах.
§ 2.1. Описание исчисления высказываний на интуитивном уровне
§ 2.2. Понятие формальной системы.
§ 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. Проблемы, связанные с трансформациями.
Избранная библиография.



Бесплатно скачать электронную книгу в удобном формате, смотреть и читать:
Скачать книгу Теория формальных грамматик, Гросс М., Лантен А, 1971 - fileskachat.com, быстрое и бесплатное скачивание.

Скачать djvu
Ниже можно купить эту книгу, если она есть в продаже, и похожие книги по лучшей цене со скидкой с доставкой по всей России.Купить книги


Скачать - djvu - Яндекс.Диск.




Теги: Гросс :: Лантен :: грамматика :: 1971