Что такое формальный язык

Pumping lemma доказывает: ни один regex не может надёжно распарсить HTML. Не потому что regex слабый. Это математическая теорема о классах формальных языков. Именно поэтому в браузере отдельный HTML-парсер - и это правильно, а не костыль. LLM-токенизатор (BPE, tiktoken) - это детерминированный конечный автомат (DFA). Компилятор Python - CFG с LR(1)-парсером. POSIX grep и Perl-regex - разные классы автоматов с разными гарантиями по скорости. Всё это иерархия Хомского. Сегодня - фундамент.

• **LLM-токенизация (tiktoken, BPE):** GPT-4 разбивает текст на токены через DFA - конечный автомат над алфавитом Unicode. Словарь из 100 277 токенов = 100 277-элементный алфавит выходного языка
• **Python-компилятор:** лексер (регулярные языки, тип 3) → парсер (контекстно-свободные, тип 2) → семантический анализ. Три уровня иерархии Хомского в одном `python script.py`
• **POSIX grep vs Perl regex:** POSIX гарантирует O(n) по длине строки - это регулярный язык с DFA. Perl-обратные ссылки выходят за тип 3 и могут быть экспоненциальными - ReDoS атаки на веб-серверы
• **Биоинформатика:** BLAST ищет гены в геноме через регулярные паттерны над Σ = {A, T, G, C}. Выравнивание с gap-penalty - это уже КС-грамматика

Алфавит: из чего строятся слова

Прежде чем писать regex, прежде чем запускать компилятор, прежде чем токенизировать текст в GPT - нужно договориться о символах. Python: буквы, цифры, операторы, пробелы. ДНК: {A, T, G, C}. Машинный код: {0, 1}. Этот набор - **алфавит** - первый и единственный параметр, от которого зависит вся теория формальных языков. Меняется алфавит - меняется всё.

**Алфавит (alphabet)** - конечное непустое множество символов. Обозначается **Σ** (sigma). Элементы алфавита называются **символами** или **буквами**. Примеры: Σ = {0, 1} - двоичный алфавит, Σ = {a, b, c, ..., z} - латиница, Σ = {A, T, G, C} - генетический алфавит.

Ограничение одно: алфавит должен быть **конечным**. Натуральные числа {1, 2, 3, ...} - не алфавит. {0, 1, 2, ..., 9} - алфавит. Из конечного алфавита в два символа вырастает бесконечное Σ* - все возможные строки. Именно это делает теорию мощной: маленький алфавит, бесконечно богатый язык.

Строки: слова над алфавитом

Буквы алфавита склеиваются в **строки** - конечные последовательности символов. «011» над {0, 1}: три символа. «GATTACA» над {A, T, G, C}: семь символов, одноимённый фильм о генетике. Отдельный важный случай - **пустая строка** ε: ноль символов. Она есть в каждом языке из звезды Клини, и это часто удивляет.

**Строка (string/word)** w над алфавитом Σ - конечная последовательность символов из Σ. **Длина** строки |w| - число символов. **Пустая строка** ε (epsilon) - строка длины 0: |ε| = 0. **Конкатенация** - склеивание: если w = «ab» и v = «cd», то wv = «abcd». Свойство: wε = εw = w.

**Σ*** - множество всех строк над Σ, включая ε. Счётно бесконечное, даже если алфавит из одного символа. Для Σ = {0, 1}: Σ* = {ε, 0, 1, 00, 01, 10, 11, 000, ...} - начинается с коротких строк и идёт в бесконечность. Именно в этом пространстве живут все формальные языки - как подмножества Σ*.

Язык: множество строк

Σ* - это вся вселенная строк. **Формальный язык** - это выборка из этой вселенной: какие строки проходят, какие нет. Python-код - язык: одни строки синтаксически корректны, другие нет. Email-адрес - язык. Допустимые ходы в шахматах в нотации PGN - язык. Биты правильного JPEG-файла - язык. Всё это просто подмножества Σ*.

**Формальный язык** L над алфавитом Σ - любое подмножество Σ*: **L ⊆ Σ***. Язык - это множество строк, удовлетворяющих некоторому свойству. Примеры: L₁ = {0, 1, 00, 11} (конечный), L₂ = {0ⁿ1ⁿ : n ≥ 1} = {01, 0011, 000111, ...} (бесконечный), L₃ = {} = ∅ (пустой язык), L₄ = {ε} (язык из одной пустой строки).

**∅ ≠ {ε}** - это не педантизм, это принципиальный момент. ∅ - пустое множество, ноль строк. {ε} - одна строка (пустая). При конкатенации языков: ∅ · L = ∅ (ноль строк), {ε} · L = L (строки из L без изменений). Как в арифметике: 0 × x = 0, но 1 × x = x.

**Формальный язык - это множество, а не правило.** Язык {01, 0011, 000111, ...} можно описать правилом «n нулей, потом n единиц», но сам язык - это множество строк. Разные правила могут описывать один и тот же язык.

Операции над языками

Языки - множества, значит объединение, пересечение, дополнение работают автоматически. Но есть две операции, специфичные для строк: **конкатенация** языков (склейка каждой строки с каждой) и **звезда Клини** (ноль или более повторений). Именно эти три операции - объединение, конкатенация, звезда - порождают все регулярные выражения. Буквально все: `[a-z]+`, `\d{3}-\d{4}`, `(foo|bar)*` - это алгебра над этими тремя.

**Операции над языками L₁, L₂ ⊆ Σ*:** 1. **Объединение** L₁ ∪ L₂ = {w : w ∈ L₁ или w ∈ L₂} 2. **Пересечение** L₁ ∩ L₂ = {w : w ∈ L₁ и w ∈ L₂} 3. **Дополнение** L̄ = Σ* \ L 4. **Конкатенация** L₁L₂ = {uv : u ∈ L₁, v ∈ L₂} 5. **Звезда Клини** L* = {ε} ∪ L ∪ LL ∪ LLL ∪ ... = ∪_{n≥0} Lⁿ.

**Звезда Клини L*** - ноль или более повторений строк из L в любом порядке. Для L = {a, b}: L* = все строки над {a, b}. Именно поэтому `.*` в regex означает «что угодно»: это ({все символы})*. Клини придумал звезду для математического описания регулярных языков в 1956-м. Сегодня его нотация стоит в каждом `re.compile()`, `grep -E`, `sed`, `awk`.

**L* всегда содержит ε** (пустую строку), даже если L не содержит ε. По определению: L⁰ = {ε} ⊆ L*. Но **∅* = {ε}** - звезда Клини пустого языка - это не пустой язык, а {ε}! Это частая ловушка на экзаменах.

Ключевые идеи

• **Алфавит Σ** - конечное непустое множество символов. Σ* - все строки над ним, бесконечное множество. Из двух символов {0,1} вырастает бесконечный Σ*
• **Формальный язык L ⊆ Σ*** - любое подмножество строк. Язык - это множество, не правило. Разные правила описывают один язык
• **Звезда Клини L*** = ноль или более повторений из L. Всегда содержит ε. Основа regex: `(a|b)*` = ({a}∪{b})*
• **Иерархия Хомского:** regex = тип 3 (DFA). HTML/скобки = тип 2 (CFG, стек). Натуральный язык ≈ тип 1-2. Тьюринг-полные программы = тип 0. Почему браузер не парсит HTML regex-ом - это следствие этой иерархии

Связанные темы

Формальные языки - фундамент для иерархии Хомского, автоматов и теории вычислимости:

• Иерархия Хомского — Классификация языков по сложности: регулярные → КС → КЗ → рекурсивно перечислимые
• Грамматики — Формальное описание правил порождения строк языка
• Регулярные выражения — Практическое применение: объединение, конкатенация и звезда Клини в grep/sed/awk

Вопросы для размышления

• Множество всех грамматически правильных предложений на русском языке - это формальный язык? Если да, какой алфавит?
• ∅* = {ε}. Объясните интуитивно, почему звезда Клини пустого языка непуста.
• Вернёмся к grep из начала: regex ^[0-9]{3}-[0-9]{4}$ описывает формальный язык. Опишите этот язык через операции объединения, конкатенации и звезды Клини.

Связанные уроки

• aut-01-fsm — Конечные автоматы - исполнители регулярных языков (теорема Клини)
• comp-01-intro — Компилятор использует разные уровни иерархии Хомского на каждой фазе
• alg-01-big-o — Сложность распознавания языка - это сложность алгоритма: O(n) для DFA, O(n³) для CYK
• dm-01 — Теория множеств и операции над множествами - математический язык формальных языков
• ml-01
• ml-04