Формальные языки
Иерархия Хомского
Ноам Хомский и три модели описания языка
В 1956 году лингвист Ноам Хомский опубликовал работу 'Three models for the description of language'. Цель была - формализовать грамматику естественных языков. Но случайно получилось нечто большее: Хомский описал мощность вычислений. Его четыре типа грамматик точно соответствуют четырём классам автоматов - DFA, PDA, LBA, TM. Работа стала фундаментом теории формальных языков и теории вычислений.
Цели урока
- Различать четыре типа языков в иерархии Хомского и их распознаватели
- Определять тип задачи и выбирать правильный инструмент (regex/PDA/LBA/TM)
- Понимать, почему SQL injection нельзя защитить только regex
- Объяснять, почему TypeScript type checker завершается, а Agda - нет
Иерархия Хомского 1956 года не описывала человеческий язык. Она предсказала, что TypeScript type checker не может проверить все корректные программы (теорема Райса - Тип 0). Что JSON нельзя валидировать regex (Тип 2 vs Тип 3). Что SQL injection невозможно заблокировать паттернами. Одна бумага лингвиста - и 70 лет архитектурных решений.
- **Компиляторы** - lexer (regex, Тип 3) -> parser (CFG, Тип 2) -> семантический анализ (Тип 1+): три слоя иерархии в одном инструменте
- **SQL injection** - regex-защита (Тип 3) не может проверить КС-структуру SQL-запроса. Параметризованные запросы работают на правильном уровне
- **TypeScript** - type system Тьюринг-полна (Тип 0), но Microsoft ограничивает глубину рекурсии чтобы checker завершался
- **Биоинформатика** - RegexType 3 для поиска мотивов в ДНК, CFG для вторичной структуры РНК (стек = шпильки)
- **RE2/Rust regex** - гарантированное O(n) через DFA без backtracking: осознанное ограничение до Типа 3 ради предсказуемости
Предварительные знания
Тип 0: рекурсивно перечислимые языки
Начнём с самого мощного класса - **Тип 0**. Это языки, которые может распознать **машина Тьюринга** - теоретическая модель любого компьютера. Грамматика Типа 0 не имеет ограничений на правила: можно заменять любую подстроку на любую другую. Зависимые типы в Agda/Coq, полноценная type inference в HM - это вычисления на уровне Типа 0.
**Рекурсивно перечислимые языки (recursively enumerable, r.e.)** - языки, для которых существует машина Тьюринга (TM), принимающая строки из L. Грамматика Типа 0 (неограниченная): правила вида α -> β, где α содержит хотя бы один нетерминал. **Проблема:** TM может зацикливаться на строках из дополнения L - нет гарантии остановки.
**Рекурсивные языки** (подкласс r.e.) - те, для которых TM всегда останавливается: либо принимает, либо отвергает. Для рекурсивно перечислимых (но не рекурсивных) языков TM может работать вечно на строке вне L. Пример: язык 'программ, которые останавливаются' - r.e., но не рекурсивный (проблема остановки).
| Класс | TM останавливается? | Разрешимость | Пример |
|---|---|---|---|
| Рекурсивный | Всегда (на w из L и w вне L) | Разрешимый | {a^n b^n c^n} |
| Р.е., не рекурсивный | На w из L - да, на w вне L - может зацикливаться | Полуразрешимый | Проблема остановки |
| Не р.е. | Нет TM, распознающей L | Неразрешимый | Дополнение проблемы остановки |
Машина Тьюринга для рекурсивно перечислимого языка L получила строку w вне L. Что произойдёт?
Тип 1: контекстно-зависимые языки
**Тип 1** добавляет одно ограничение: правые части правил не короче левых. При выводе строка никогда не укорачивается. Это моделирует **контекстно-зависимые** подстановки: нетерминал заменяется по-разному в зависимости от соседей. HTML в полной спецификации - контекстно-зависимый: правило 'тег `<li>` допустим только внутри `<ul>` или `<ol>`' зависит от контекста.
**Контекстно-зависимые языки (context-sensitive, CSL)** - Тип 1 в иерархии Хомского. Грамматика: правила вида αAβ -> αγβ, где A - нетерминал, α и β - контекст, γ - непустая замена. Эквивалентно: |правая часть| >= |левая часть|. Распознаватель: **Linear Bounded Automaton (LBA)** - машина Тьюринга с лентой, ограниченной длиной входа.
**Почему 'контекстно-зависимые'?** В правиле αAβ -> αγβ нетерминал A заменяется на γ, но только если слева стоит α и справа β. Контекст управляет подстановкой. В SQL: выражение `ORDER BY` имеет разный смысл в зависимости от того, находится ли оно внутри `SELECT` или `CREATE VIEW` - это контекстно-зависимое поведение.
| Свойство | Тип 0 | Тип 1 (CSL) |
|---|---|---|
| Правила | α -> β (без ограничений) | |α| <= |β| (не укорачивающие) |
| Распознаватель | Машина Тьюринга | LBA (TM с ограниченной лентой) |
| Разрешимость | Полуразрешимые | Всегда разрешимые |
| Пример | Проблема остановки | {a^n b^n c^n}, {ww} |
Язык L = {ww : w из {a,b}*} (строки из двух одинаковых половин). К какому типу он относится?
Тип 2: контекстно-свободные языки
**Тип 2** - рабочая лошадка Computer Science. Правила: A -> γ, слева один нетерминал, справа что угодно. Контекст не важен. Именно КС-грамматики описывают синтаксис языков программирования: вложенные скобки, if-then-else, арифметические выражения. JSON, XML, большинство языков программирования - Тип 2. Parser в компиляторе (LL, LR, PEG) - это распознаватель Типа 2.
**Контекстно-свободные языки (context-free, CFL)** - Тип 2. Грамматика (CFG): правила A -> γ, где A - один нетерминал. Распознаватель: **автомат с магазинной памятью (PDA, pushdown automaton)** - конечный автомат со стеком. Стек позволяет отслеживать глубину вложенности.
| Язык | КС? | Почему |
|---|---|---|
| {a^n b^n : n >= 0} | Да | Стек считает a и сопоставляет с b |
| {скобочные выражения} | Да | Вложенность = стек |
| Синтаксис Python/Java/JSON | Да (приблизительно) | Рекурсивный спуск / LR-парсер |
| {a^n b^n c^n} | НЕТ | Стек не может считать три группы одновременно |
| {ww} | НЕТ | Стек - LIFO, нужен прямой доступ |
| {ww^R} (палиндромы) | Да | Push w, pop при w^R - стек идеален! |
**Почему SQL injection работает через regex-защиту?** Regex (Тип 3) не может проверить контекстно-свободную структуру SQL-запроса. Правильная защита - параметризованные запросы, которые работают на уровне синтаксиса (Тип 2), а не поверхностных паттернов.
Язык корректных скобочных выражений {(), (()), ()(), (()()), ...} является:
Тип 3: регулярные языки
**Тип 3** - самый простой, но самый практичный класс. Регулярные языки описываются **регулярными выражениями** и распознаются **конечными автоматами** (DFA/NFA). Ни стека, ни ленты - только конечное число состояний. grep, sed, awk, валидация форм, lexer в компиляторе - всё это Тип 3. RE2 (Google) и Rust regex - движки, гарантирующие O(n) время без экспоненциальных откатов.
**Регулярные языки** - Тип 3. Грамматика: правила A -> aB или A -> a (правая линейная). Распознаватель: **DFA/NFA**. Эквивалентное описание: **регулярные выражения** (объединение, конкатенация, звезда Клини). Три представления эквивалентны - теорема Клини.
| Описание | Regex | DFA состояний |
|---|---|---|
| Строки, начинающиеся с 0 | ^0.* | 2 |
| Чётное число символов | (..)* | 2 |
| Содержит подстроку 'ab' | .*ab.* | 3 |
| Email (упрощённо) | [a-z]+@[a-z]+\.[a-z]+ | ~7 |
| IP-адрес | (\d{1,3}\.){3}\d{1,3} | ~15 |
**Ограничения регулярных языков:** конечный автомат не имеет памяти кроме текущего состояния. Он не может считать, сравнивать подстроки, проверять вложенность. {a^n b^n}, {ww}, сбалансированные скобки - не регулярные языки. Именно поэтому нельзя написать regex для 'проверь, что HTML-теги правильно вложены'.
Какой из этих языков НЕ является регулярным?
Иерархия: вложенность и границы
Четыре типа образуют строгую **вложенную иерархию**: Regular < CF < CS < R.E. На каждой границе существуют языки, принадлежащие более широкому классу, но не более узкому. Эта иерархия - карта вычислительной мощности. Знание уровня задачи сразу говорит, какой инструмент нужен.
**Иерархия Хомского:** Тип 3 (Regular) - строгое подмножество Типа 2 (Context-Free) - строгое подмножество Типа 1 (Context-Sensitive) - строгое подмножество Типа 0 (Recursively Enumerable). Строгость: {a^n b^n} - КС, но не регулярный. {a^n b^n c^n} - КЗ, но не КС. Проблема остановки - Тип 0, но не Тип 1.
| Тип | Грамматика | Автомат | Практика |
|---|---|---|---|
| 3 - Регулярные | Правая линейная | DFA / NFA | grep, awk, lexer в компиляторе |
| 2 - КС | CFG | PDA (стек) | Parser, JSON/XML, большинство ЯП |
| 1 - КЗ | CSG | LBA | Полный синтаксис HTML, некоторые проверки типов |
| 0 - Р.Е. | Без ограничений | TM | Зависимые типы, общая type inference |
**Практическое значение:** email validation - O(n) за один проход (DFA). Парсинг JSON - O(n) со стеком (PDA). Проверка типов в TypeScript - завершается всегда (TypeScript Type System Тьюринг-полна, но Microsoft ограничивает глубину рекурсии). Знание иерархии мгновенно отвечает на вопрос 'какой инструмент применять'.
**За пределами иерархии** существуют языки, которые не являются даже рекурсивно перечислимыми. Пример: множество всех TM, которые не останавливаются (дополнение проблемы остановки). Таких языков 'больше' чем распознаваемых - в теоретико-множественном смысле.
HTML - контекстно-свободный язык, потому что у него есть теги с вложенностью
HTML в полной спецификации - контекстно-зависимый. Правила вроде 'тег li допустим только внутри ul или ol' зависят от контекста. Браузеры используют специальные (не КС) парсеры с error recovery.
КС-грамматика не может выразить правило 'тег X должен быть закрыт тем же тегом X'. Простая вложенность - КС, но соответствие имён тегов (div...div) - КЗ. HTML5 описывает парсер как state machine с древовидным конструктором.
JSON имеет вложенные объекты {}, массивы [] и рекурсивные структуры. К какому типу относится язык JSON?
Ключевые идеи
- **Тип 3 (регулярные):** DFA/NFA, regex - без памяти, только конечные состояния. grep, lexer, валидация форм
- **Тип 2 (КС):** PDA, CFG - стек позволяет обрабатывать вложенность. Парсеры, JSON, большинство ЯП
- **Тип 1 (КЗ):** LBA - лента ограниченной длины, контекстные подстановки. Полный HTML, часть проверок типов
- **Тип 0 (р.е.):** TM - максимальная мощность, может зацикливаться. Зависимые типы, общая type inference
- Строгая вложенность: Reg строгое подмножество CF строгое подмножество CS строгое подмножество RE
- SQL injection работает, потому что regex (Тип 3) не может проверить структуру SQL (Тип 2)
Связанные темы
Иерархия Хомского - карта всей теории формальных языков:
- Что такое формальный язык — Алфавиты, строки и операции - базовые понятия для всех типов
- Грамматики: порождение языков — Формальные правила генерации строк для каждого типа иерархии
- DFA и NFA — Распознаватели регулярных языков (Тип 3) - детально
Вопросы для размышления
- SQL - какого типа? Можно ли распарсить SELECT с вложенными подзапросами конечным автоматом?
- Можно ли написать regex для проверки, что строка - корректная арифметическая формула с вложенными скобками? Если нет, какой минимальный инструмент нужен?
- PCRE (Perl Compatible Regex) поддерживает рекурсию. Это нарушает иерархию Хомского? Почему PCRE формально не является 'регулярным' несмотря на название?
Связанные уроки
- fl-01-intro — Алфавиты и строки - базовые понятия для всех типов иерархии
- fl-03-grammars — Формальные правила порождения строк для каждого типа
- fl-06-dfa — DFA - распознаватель Типа 3, детальный разбор
- comp-02-language-processing — Lexer (Тип 3) и parser (Тип 2) - иерархия в компиляторе
- fl-23-halting-problem — Проблема остановки живёт на границе Типа 0 и за его пределами
- plt-02-type-systems — Мощность type systems коррелирует с уровнями иерархии Хомского
- ml-04
- comp-01-intro