ТАФЯ — чек-лист самопроверки
Используйте после прохождения обзора и статей Теория алгоритмов — формальные основы–Магазинные автоматы, Мили и Мура. Цель — проверить понимание, а не вызубрить определения: отвечайте своими словами, затем сверяйтесь с подсказками ниже и с указанными статьями.
- Закройте подсказки и ответьте на вопрос в 2–4 предложениях или нарисуйте схему.
- Если застряли — откройте только "Куда смотреть", без "Суть ответа".
- После ответа сверьтесь с "Суть ответа" и при необходимости перечитайте раздел статьи.
- Вопросы 31–35 — связка с реальной разработкой; их удобно обсуждать в паре "теория + код".
Блок 1. Алгоритмы и вычислимость
1. Чем задача отличается от экземпляра?
Куда смотреть: Теория алгоритмов — формальные основы, раздел "Общее понятие алгоритма", таблица задача / экземпляр.
Суть ответа: задача — семейство "вход → ответ" для всех допустимых входов одного типа; экземпляр — один конкретный вход (один файл, один массив). Алгоритм описывает задачу целиком.
2. Назовите пять свойств алгоритма в формулировке теории.
Куда смотреть: Теория алгоритмов — формальные основы, "Основные требования" и сводная таблица.
Суть ответа: дискретность, определённость (детерминированность в постановке), конечность (завершаемость на допустимых входах), массовость, результативность; часто отдельно упоминают конструктивность и (на другом уровне) эффективность.
3. Что такое алфавитный оператор и как он связан с распознавателем?
Куда смотреть: Теория алгоритмов — формальные основы, "Понятие алфавитного оператора".
Суть ответа: правило Σ* → Σ* (или в {да, нет}), преобразующее строку. Распознаватель языка — оператор, который по слову отвечает, входит ли оно в язык L.
4. Перечислите четыре формальные модели вычисления и сформулируйте тезис Чёрча–Тьюринга.
Куда смотреть: Теория алгоритмов — формальные основы, таблица моделей; Машина Тьюринга.
Суть ответа: машина Тьюринга, λ-исчисление, частично-рекурсивные функции, нормальные алгоритмы Маркова (достаточно трёх + одна). Тезис: всё интуитивно эффективно вычислимое реализуемо на МТ (и эквивалентных моделях).
5. Чем примитивная рекурсия отличается от рекурсии в Python?
Куда смотреть: Рекурсивные и вычислимые функции, callout "Не путать"; схема примитивной рекурсии.
Суть ответа: в Python — способ написать код; примитивная рекурсия — строгая схема из базовых функций, дающая только тотальные функции с гарантированным завершением. Обычный рекурсивный def без ограничений может не уложиться в примитивный класс (хотя может быть вычислимым).
6. Почему функция Аккермана вычислима, но не примитивно рекурсивна?
Куда смотреть: Рекурсивные и вычислимые функции, раздел про Аккерман.
Суть ответа: для каждой пары (m,n) результат конечен — есть алгоритм (МТ / μ-рекурсия). Рост слишком быстрый, чтобы выразить конечным числом применений только примитивных схем от S и проекций.
7. Чем разрешимый язык отличается от рекурсивно перечислимого?
Куда смотреть: Рекурсивные и вычислимые функции, таблица "Языки и множества".
Суть ответа: разрешимый — и "да", и "нет" решаются алгоритмом с остановкой. RE — есть полуалгоритм: для слов из языка ответ "да" за конечное время; для слов вне языка процедура может не остановиться.
8. Сформулируйте проблему остановки и идею доказательства.
Куда смотреть: Машина Тьюринга, "Проблема остановки", диаграмма с D.
Суть ответа: нет программы, которая для любой пары (код P, вход x) всегда за конечное время решает, остановится ли P на x. Доказательство — предположить такую H, построить D, ведущую себя противоположно H на входе ⟨D⟩ — противоречие.
9. Что делает универсальная машина Тьюринга?
Куда смотреть: Машина Тьюринга, "Универсальная машина".
Суть ответа: одна фиксированная МТ U, которая на ленте получает код программы ⟨P⟩ и вход x и симулирует шаги P на x — аналог интерпретатора / VM.
10. Назовите одну разрешимую и одну неразрешимую задачу про программы.
Куда смотреть: Машина Тьюринга, таблицы; Конечные автоматы и регулярные языки для разрешимых на подклассе.
Суть ответа (примеры): разрешимая — "принимает ли ДКА слово w"; "эквивалентны ли два минимальных ДКА". Неразрешимая в общем виде — остановка, эквивалентность двух произвольных программ, тотальность семантики (дух теоремы Райса в Рекурсивные и вычислимые функции).
Блок 2. Грамматики и разбор
11. Запишите кортеж G = (N, Σ, P, S) и поясните компоненты.
Куда смотреть: Формальные грамматики и разбор, "Основные понятия".
Суть ответа: N — нетерминалы, Σ — терминалы, P — правила, S — стартовый символ. Язык — все строки только из терминалов, выводимые из S.
12. Чем сентенциальная форма отличается от предложения?
Куда смотреть: Формальные грамматики и разбор, "Сентенциальные формы".
Суть ответа: сентенциальная форма — промежуточная строка (терминалы + нетерминалы); предложение — сентенциальная форма без нетерминалов (готовое "слово" языка).
13. Чем дерево вывода отличается от AST?
Куда смотреть: Формальные грамматики и разбор, таблица после "Дерево вывода".
Суть ответа: дерево вывода отражает все применения правил грамматики; AST — сжатое дерево для семантики и оптимизаций, без синтаксического шума.
14. Перечислите типы 0–3 по Хомскому и автоматы.
Куда смотреть: Формальные грамматики и разбор, Формальные языки и автоматы.
Суть ответа: 3 — регулярная / КА; 2 — КС / МП-автомат; 1 — контекстно-зависимая / ЛОА; 0 — без ограничений / МТ. Вложение 3 ⊂ 2 ⊂ 1 ⊂ 0.
15. Чем левый вывод связан с LL, правый — с LR?
Куда смотреть: Формальные грамматики и разбор, "Левый и правый вывод".
Суть ответа: LL строит левосторонний вывод (сверху вниз); LR сворачивает к корню, соответствует правостороннему выводу (снизу вверх).
16. Пример неоднозначной грамматики.
Куда смотреть: Формальные грамматики и разбор, "висячий else", приоритет + и *.
Суть ответа: вложенные if без else / if … else — два дерева; или a + b * c без приоритета в грамматике — два дерева с разной группировкой.
17. Зачем устраняют левую рекурсию перед LL(1)?
Куда смотреть: Формальные грамматики и разбор, "Преобразования КС-грамматик".
Суть ответа: LL-разбор "разворачивает" нетерминал слева; правило A → Aα заставляет снова выбирать A без продвижения по входу — бесконечная рекурсия в парсере. Замена на A → βA', A' → αA' | ε устраняет это.
18. Для чего FIRST и FOLLOW?
Куда смотреть: Формальные грамматики и разбор, "LL(1)".
Суть ответа: FIRST — с каких терминалов может начаться вывод из символа/строки; FOLLOW — что может идти после нетерминала. Вместе заполняют таблицу LL(1): по текущему нетерминалу и lookahead выбирают правило.
19. Почему { aⁿbⁿ } не регулярный, но обычно КС?
Куда смотреть: Конечные автоматы и регулярные языки, лемма о накачке; Магазинные автоматы, Мили и Мура, стек.
Суть ответа: нужен счётчик a перед b — КА с конечной памятью не помнит произвольное n. МП-автомат кладёт a на стек и снимает на b — язык КС.
20. Почему { aⁿbⁿcⁿ } не контекстно-свободный?
Куда смотреть: Формальные грамматики и разбор, лемма о накачке для КС.
Суть ответа: накачка для КС позволяет "раздувать" два сегмента v и y синхронно; для трёх блоков aⁿbⁿcⁿ при накачке нарушается равенство трёх счётчиков — язык требует тип 1 (или сильнее), не чистый КС.
Блок 3. Автоматы
21. Кортеж ДКА и условие принятия слова.
Куда смотреть: Конечные автоматы и регулярные языки.
Суть ответа: A = (Q, Σ, δ, q₀, F); слово w принято, если δ̂(q₀, w) ∈ F.
22. Почему НКА не сильнее ДКА по языкам?
Куда смотреть: Конечные автоматы и регулярные языки, детерминизация подмножеств.
Суть ответа: каждый НКА можно преобразовать в эквивалентный ДКА (состояния ДКА — подмножества состояний НКА); класс языков тот же.
23. Построение НКА из regex (Thompson).
Куда смотреть: Конечные автоматы и регулярные языки, таблица Thompson.
Суть ответа: рекурсивно собирают мини-автоматы для ∅, ε, символа, объединения, конкатенации, звезды с ε-переходами; в конце — один НКА для всего выражения.
24. Что делает детерминизация подмножеств?
Куда смотреть: Конечные автоматы и регулярные языки.
Суть ответа: строит ДКА, чьи состояния — множества состояний НКА (после ε-замыкания); переход по символу a — объединение δ(q,a) по всем q из множества, снова замыкание.
25. Лемма о накачке и aⁿbⁿ.
Куда смотреть: Конечные автоматы и регулярные языки.
Суть ответа: в ДКА после p символов повторяется состояние на префиксе из a; накачка только y из a даёт слово с лишними a и тем же числом b — не в языке aⁿbⁿ.
26. Минимальный ДКА и Майхилл–Нероде.
Куда смотреть: Конечные автоматы и регулярные языки.
Суть ответа: минимальный ДКА — наименьшее число состояний для языка; Нероде: язык регулярен ⟺ отношение "строки z ведут себя одинаково" имеет конечное число классов.
27. Где в компиляторе КА, где МП-автомат?
Куда смотреть: Конечные автоматы и регулярные языки, Магазинные автоматы, Мили и Мура, диаграмма пайплайна.
Суть ответа: лексер — ДКА/regex; синтаксический парсер — МП-автомат (стек) + грамматика.
28. Компоненты МП-автомата и роль стека.
Куда смотреть: Магазинные автоматы, Мили и Мура.
Суть ответа: Q, Σ, Γ, δ, q₀, Z₀, F; стек хранит вложенность (нетерминалы, маркеры скобок), LIFO.
29. Мили и Мура.
Куда смотреть: Магазинные автоматы, Мили и Мура, таблица.
Суть ответа: Мили — выход на переходе (ребре); Мура — выход привязан к состоянию. Классы эквивалентны с ростом числа состояний при преобразовании.
30. Диагностическая последовательность.
Куда смотреть: Магазинные автоматы, Мили и Мура, Конечные автоматы и регулярные языки минимизация.
Суть ответа: входная цепочка, на которой два состояния (или два автомата) ведут себя по-разному — их можно различить; если такой цепочки нет, состояния сливают при минимизации.
Практические вопросы
31. Почему regex не заменяет парсер JSON?
Суть ответа: JSON с вложенными объектами и массивами — КС (нужен стек), regex — регулярный уровень Конечные автоматы и регулярные языки. Плюс семантика (числа, escape) — отдельные правила.
32. Почему статический анализ "всех багов" невозможен?
Суть ответа: полная проверка произвольной семантики упирается в неразрешимость остановки и теорему Райса; инструменты ограничивают класс программ или свойств.
33. ReDoS и тип автомата.
Суть ответа: наивный backtracking regex может перебирать экспоненциально много путей; детерминированный ДКА после компиляции даёт линейное время по длине входа Конечные автоматы и регулярные языки.
34. Когда "сессия как 5 кружков" ломается?
Суть ответа: вложенные подсценарии (оплата внутри заказа, 3DS) требуют стека состояний Магазинные автоматы, Мили и Мура, а не одного плоского КА Конечные автоматы и регулярные языки.
35. Уровень Хомского для сбалансированных скобок?
Суть ответа: тип 2 (КС), МП-автомат Магазинные автоматы, Мили и Мура; регулярного типа 3 Конечные автоматы и регулярные языки недостаточно.
Типичные путаницы (самопроверка)
| Путают | На самом деле |
|---|---|
| "Рекурсия в Python" = "примитивная рекурсия" | разные уровни: код vs формальная схема Рекурсивные и вычислимые функции |
| "Недетерминированный" = "случайный" | в НКА "существует путь"; в коде — random Конечные автоматы и регулярные языки |
| "МТ = реальный ПК" | МТ с бесконечной лентой; ПК с лимитом RAM Машина Тьюринга |
| "AST = дерево вывода" | AST сжатое Формальные грамматики и разбор |
| "PEG = КС" | упорядоченный выбор / — другая семантика Формальные грамматики и разбор |
Оценка готовности
| Результат | Что делать дальше |
|---|---|
| ≥ 28 уверенных ответов | можно углублять компилятор и алгоритмы |
| 15–27 | перечитайте слабые блоки по таблице "куда смотреть" |
| меньше 15 | пройдите цепочку Теория алгоритмов — формальные основы→Магазинные автоматы, Мили и Мура по одной статье в день с упражнениями |
Назад к обзору ТАФЯ.