Бесплатная библиотека - 1 338 003 изданий в библиотеке

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

Книга Теория формальных грамматик, Гросс М., Лантен А, 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. Проблемы, связанные с трансформациями.
Избранная библиография.

Рейтинг: 4.8 баллов / 2537 оценок
Формат: Книга
Уже скачали: 12754 раз

Похожие Книги

Нам показалось, что Книги ниже Вас заинтересуют не меньше. Эти издания Вы так же можете скачивать и читать совершенно бесплатно на сайте!

Вы не зарегистрированы!

Если вы хотите скачивать книги, журналы и аудиокниги бесплатно, без рекламы и без смс, оставлять комментарии и отзывы, учавствовать в различных интересных мероприятиях, получать скидки в книжных магазинах и многое другое, то Вам необходимо зарегистрироваться в нашей Электронной Библиотеке.

Войти Регистрация

Отзывы читателей

Ой!

К сожалению, в нашей Бесплатной Библиотеке пока нет отзывов о Книге Теория формальных грамматик, Гросс М., Лантен А, 1971. Помогите нам и другим читателям окунуться в сюжет Книги и узнать Ваше мнение. Оставьте свой отзыв или обзор сейчас, это займет у Вас всего-лишь несколько минут.