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

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

• О книге
• Предисловие редактора перевода
• Предисловие
• 1. Повторения
  • 1.1. Слова и языки
  • 1.2. Проблема Туэ
  • 1.3. Решение проблемы сильной бескубности
  • 1.4. Решение проблемы бесквадратности
  • 1.5. Перекрытие
  • 1.6. DOL-системы и ω-слова
  • Упражнения
• 2. Регулярность; характеризации
  • 2.1. Представимость
  • 2.2. Конечные детерминированные автоматы
  • 2.3. Регулярные выражения
  • 2.4. Теорема Клини
  • Упражнения
• 3. Регулярность; интересные проблемы
  • 3.1. Звездная высота
  • 3.2. Свойство конечной степени
  • Упражнения
• 4. Коды и множества совпадения
  • 4.1. Основные свойства кодов
  • 4.2. Максимальные коды
  • 4.3. Коды с ограниченной задержкой
  • 4.4. Множества совпадения и их регулярность
  • 4.5. Элементарные морфизмы
  • 4.6. Проблема соответствия Поста
  • Упражнения
• 5. Разрешимость и неразрешимость
  • 5.1. OL-системы
  • 5.2. Проблемы эквивалентности для DOL-систем
  • 5.3. Результаты о неразрешимости
  • Упражнения
• 6. Представления посредством морфизмов
  • 6.1. Локальные и регулярные языки
  • 6.2. Морфический генератор для контекстно-свободных языков
  • 6.3. Порождение морфизмами рекурсивно перечислимых языков
  • Упражнения
• 7. Семейства языков
  • 7.1. Регулярные языки как грамматическое семейство
  • 7.2. Плотная иерархия грамматических семейств
  • 7.3. Раскраски и семейства графов
  • Упражнения
• Исторические и библиографические замечания
• Литература
• Дополнительная литература
• Послесловие. А. А. Мучник, А. Л. Семенов
  • Литература

Источник:
Саломаа А. 'Жемчужины теории формальных языков' \\Перевод с английского А.А. Мучника под редакцией А.Л. Семенова - Москва: Мир, 1986 - с.159