URSS.ru - Издательская группа URSS. Научная и учебная литература
Об издательстве Интернет-магазин Контакты Оптовикам и библиотекам Вакансии Пишите нам
КНИГИ НА РУССКОМ ЯЗЫКЕ


 
Вернуться в: Каталог  
Обложка Саломаа А. Жемчужины теории формальных языков: Пер. с англ.
Id: 2369
 
599 руб.

Жемчужины теории формальных языков: Пер. с англ.

1986. 160 с. Мягкая обложка. Букинист. Состояние: 4+. Есть погашенная библиотечная печать.

 Аннотация

Книга содержит ряд замечательных результатов теории формальных языков. Она отличается методическими достоинствами, большим числом задач и примеров, постановкой новых проблем. Автор книги - профессор Университета г. Турку (Финляндия), президент Европейской ассоциации вычислительных наук -- успешно решил поставленные им две основные задачи: дать замкнутое введение в теорию для начинающих, изложить некоторые блестящие и порой сложные результаты, интересные для специалистов.

Для специалистов по вычислительным наукам, для студентов и аспирантов университетов как введение в предмет.


 Оглавление

Предисловие редактора перевода............... 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

 
© URSS 2016.

Информация о Продавце