Перевод с английского А. Мучника. Под ред. и с предисловием А. Л. Семенова.
Книга содержит ряд замечательных результатов теории формальных языков. Она отличается методическими достоинствами, большим числом задач и примеров, постановкой новых проблем. Автор книги - профессор университета г.Турку (Финляндия), президент Европейской ассоциации вычислительных наук - успешно решил поставленные им две основные задачи: дать замкнутое введение в теорию для начинающих, изложить некоторые блестящие и порой сложные результаты, интересные для специалистов.
Оглавление
Предисловие редактора перевода............... 5
Предисловие................... .. 7
1. Повторения
1.1. Слова и языки................... 9
1.2. Проблема Туэ................... 11
1.3. Решение проблемы сильной бескубности......... 13
1.4. Решение проблемы бесквадратности........... 16
1.5. Перекрытие................... 18
1.6. DQL-системы и со-слова................ 20
Упражнения.................... . 21
2. Регулярность; характеризации
2.1. Представимость................ .. 24
2.2. Конечные детерминированные автоматы......... 29
2.3. Регулярные выражения............... 32
2.4. Теорема Клини................... 35
Упражнения.................... . 36
3. Регулярность; интересные проблемы
3.1. Звездная высота.................. 39
3.2. Свойство конечной степени.............. 46
Упражнения.................... . 58
4. Коды и множества совпадения
4.1. Основные свойства кодов............... 59
4.2. Максимальные коды................. 65
4.3. Коды с ограниченной задержкой............ 67
4.4. Множества совпадения и их регулярность......... 70
4.5. Элементарные морфизмы............... 74
4.6. Проблема соответствия Поста............. 76
Упражнения.................. ... 77
5. Разрешимость и неразрешимость
5.1. OL-системы................. 80
5.2. Проблемы эквивалентности для DOL-систем....... 83
5.3. Результаты о неразрешимости............. 90
Упражнения.................. ... 94
6. Представления посредством морфизмов
6.1. Локальные и регулярные языки............. 97
6.2. Морфический генератор для контекстно-свободных языков.. 99
6.3. Порождение морфнзмами рекурсивно перечислимых языков.. 109
Упражнения.................. ... 115
7. Семейства языков
7.1. Регулярные языки как грамматическое семейство...118
7.2. Плотная иерархия грамматических семейств......124
7.3. Раскраски и семейства графов.............128
Упражнения.................. ...134
Исторические и библиографические замечания......... 138
Литература.................. .... 140
Дополнительная литература,.............. 143
Послесловие. А. А. Мучник, А. Л. Семенов........... 145
Именной указатель.................... 153
Предметный указатель.................. 155
Дополнительно: ВНИМАНИЕ! В НАСТОЯЩЕЕ ВРЕМЯ ЗАКАЗЫ ОТ ПОКУПАТЕЛЕЙ ИЗ РФ и БЕЛАРУСИ НЕ ПРИНИМАЮ И НЕ ОТПРАВЛЯЮ В ЭТИ СТРАНЫ
Доставка ◆по всему миру ◆Укрпочтой или Новой почтой◆заказным отправлением ◆после полной предоплаты ◆по Украине Укрпочтой или Новой почтой - после оплаты
Способы оплаты ◆банковский перевод на карту Приватбанка (Украина)◆по международным системам д... [подробнее]
Дополнительно: При заказе от 3-х книг -- скидка от 3%.
При заказе от 6-ти книг -- скидка от 6%.
При заказе от 10-ти книг -- скидка от 10%.
Доставка "Почтой России" или "Яндексом": отправка со склада в течение 2х-3х дней!
Отправка другими транспортными компаниями в течение 4х дней.
Самовывоз в любой день.
Подробно опишу состояние книги; содержание -- до заказа (через кнопку "Спросить" *).
Фото -- до за... [подробнее]
)
отличное;
В продаже с 11.09.2024
)
хорошее;
В продаже с 03.09.2024
