Формальные языки и автоматы

НЕ ОБЯЗАТЕЛЬНОДЛЯ НОВИЧКОВ

Архитектору Инженеру

Формальные языки — множества строк над конечным алфавитом. Автоматы и грамматики — два способа задать язык: распознать вход или породить строки. Теория лежит в основе компиляторов, regex, протоколов и границ анализа кода.

См. также: регулярные выражения в разделе алгоритмов.

Иерархия Хомского (кратко)

Тип	Грамматика	Автомат	Пример языка
3	регулярная	конечный автомат	суффикс ab, чётное число a
2	контекстно-свободная	магазинный	скобки, выражения с приоритетом
1	контекстно-зависимая	линейно-ограниченный	редко вручную в коде
0	неограниченная	машина Тьюринга	всё, что алгоритмически порождаемо

Чем мощнее класс, тем больше выразительность — и тем больше неразрешимых вопросов.

Конечный автомат

Регулярные языки

Правила вида A → aB или A → a (праволинейная форма). Распознаются конечными автоматами (ДКА / НКА, эквивалентны по мощности).

Применение: лексический анализ, regex, простые протоколы, модели состояний (сессия, фаза обработки).

Не хватает для вложенных структур: «скобки сбалансированы» — уже не регулярный язык.

Контекстно-свободные языки

Правило A → α, где α — строка терминалов и нетерминалов. Описывает большинство синтаксисов языков программирования:

E → E + T | T
T → T * F | F
F → ( E ) | digit

Распознаются магазинным автоматом (стек). Парсеры (LR, LL, PEG) — инженерная реализация этой идеи.

Машина Тьюринга

Универсальная модель вычисления: лента, головка, конечное управление. Тезис Чёрча–Тьюринга: всё интуитивно алгоритмическое вычислимо на машине Тьюринга.

Не для программирования напрямую, а для доказательства границ: что принципиально нельзя автоматизировать полностью.

Разрешимость

• Разрешимый язык — есть алгоритм, который для любой строки за конечное время отвечает «да / нет».
• Рекурсивно перечислимый — алгоритм может зациклиться на «нет» (полупроверка).

Проблема останова

Нельзя построить универсальную программу, которая для произвольной (P, x) решает, остановится ли P на x. Доказательство Тьюринга — диагональный аргумент.

Следствия для практики:

• статический анализ никогда не будет полным без компромиссов (false positive / false negative);
• эквивалентность двух программ в общем случае неразрешима;
• сложные баги могут проявляться только в конкретном рантайме.

Разрешимы многие задачи для регулярных языков (пустота, эквивалентность автоматов) и часть — для КС (принадлежность строки), но не эквивалентность двух КС-грамматик.

Практический вывод

• Regex и ДКА — для токенов и простых паттернов.
• Парсер — для синтаксиса с вложенностью.
• Не ждите от IDE/анализатора полного понимания поведения произвольной программы — это не лень разработчиков, а математический предел.

Дальше: Теория информации.

---