| Аннотація | В книге освещены вопросы алгебраической теории трансдьюсеров. Рассматриваются регулярные множества в полугруппах, изучаются алгоритмические проблемы, представлен метод жестких множеств. Рассматриваются гнездовые стековые автоматы, их связи с теорией формальных языков и комбинаторной теорией групп.
Рекомендовано для студентов, аспирантов и научных сотрудников.
Предисловие...3
Глава 5. Теория контекстных языков ... 5
5.1. Линейно ограниченные автоматы...5
5.2. О распознавании совершенных слов детерминированными линейно ограниченными автоматами...16
5.3. Индексные грамматики...19
5.4. Стековые автоматы... 24
5.5. Гнездовые стековые автоматы...30
Глава 6. Операции в классах языков... 39
6.1. Неформальная теория ... 39
6.2. Абстрактные семействаязыков... 46
Глава 7. Неразрешимость ... 65
7.1. Представления языков типа 0 ... 65
7.2. Специальные классы последовательностных преобразователей …70
7.2.1. Проблемы включения для отображений ...70
7.2.2. Недетерминированные системы защиты и конечны |