← Все учебники

Решение задач по теории автоматов, языков и сложности

[550/47%]

Д. Ду, К. Ко

Глава

1 · Регулярные языки[46/52%]

§1.1 · Строки и языки[18/56%]

§1.2 · Регулярные языки и регулярные выражения[20/60%]

§1.3 · Графовые представления регулярных выражений[8/25%]

Глава

2 · Конечные автоматы[102/59%]

§2.1 · Детерминированные конечные автоматы[8/63%]

§2.2 · Примеры детерминированных конечных автоматов[13/77%]

§2.3 · Недетерминированные конечные автоматы[10/60%]

§2.4 · Преобразование НКА в ДКА[8/63%]

§2.5 · Конечные автоматы и регулярные выражения[7/43%]

§2.6 · Свойства замкнутости регулярных языков[22/50%]

§2.7 · Минимальные детерминированные конечные автоматы[14/64%]

§2.8 · Леммы о накачке[20/55%]

Глава

3 · Контекстно-свободные языки[95/52%]

§3.1 · Контекстно-свободные грамматики[18/50%]

§3.2 · Дополнительные примеры контекстно-свободных грамматик[14/64%]

§3.3 · Разбор и неоднозначность[13/38%]

§3.4 · Автоматы с магазинной памятью[11/64%]

§3.5 · Автоматы с магазинной памятью и контекстно-свободные грамматики[13/46%]

§3.6 · Леммы о накачке для контекстно-свободных языков[26/50%]

Глава

4 · Машины Тьюринга[89/37%]

§4.1 · Одноленточные машины Тьюринга[7/14%]

§4.2 · Примеры машин Тьюринга[17/41%]

§4.3 · Многоленточные машины Тьюринга[9/22%]

§4.4 · Тезис Чёрча—Тьюринга[1/0%]

§4.5 · Неограниченные грамматики[9/44%]

§4.6 · Примитивно рекурсивные функции[17/59%]

§4.7 · Функции сопряжения и гёделевская нумерация[18/33%]

§4.8 · Частично рекурсивные функции[11/27%]

Глава

5 · Теория вычислимости[90/36%]

§5.1 · Универсальные машины Тьюринга[6/50%]

§5.2 · Рекурсивно перечислимые и рекурсивные множества[15/33%]

§5.3 · Диагонализация[15/33%]

§5.4 · Сводимость[24/33%]

§5.5 · Теорема о рекурсии[18/28%]

§5.6 · Неразрешимые проблемы[12/50%]

Глава

6 · Вычислительная сложность[57/32%]

§6.1 · Асимптотический темп роста[12/33%]

§6.2 · Временная и ёмкостная сложность[13/38%]

§6.3 · Теоремы об иерархии[12/33%]

§6.4 · Недетерминированные машины Тьюринга[12/25%]

§6.5 · Контекстно-зависимые языки[8/25%]

Глава

7 · NP-полнота[71/58%]

§7.1 · NP[23/65%]

§7.2 · Полиномиальная сводимость[13/62%]

§7.3 · Теорема Кука[12/42%]

§7.4 · Дополнительные NP-полные задачи[12/58%]

§7.5 · NP-полные задачи оптимизации[11/55%]