Формальные языки
Операции над языками
Каждый regex, который код пишете - это комбинация ровно трёх операций: `|` (объединение), склеивание символов (конкатенация) и `*` (звезда Клини). Стивен Клини доказал в 1956 году, что этих трёх операций ДОСТАТОЧНО для описания любого регулярного языка. Сегодня мы разберёмся, как из трёх простых операций возникает вся мощь регулярных выражений.
- **Regex в коде:** `(GET|POST|PUT)\s+/api/.*` - объединение методов, конкатенация с путём, звезда Клини для произвольного суффикса
- **Компиляторы:** лексер строит токены через объединение (ключевое слово | идентификатор | число) и конкатенацию (знак + цифры = число со знаком)
- **Сетевые фильтры:** firewall-правила комбинируют IP-шаблоны через объединение и конкатенацию - это операции над формальными языками пакетов
Звезда Клини и рождение теории формальных языков
В 1956 году Стивен Клини опубликовал статью "Representation of events in nerve nets and finite automata", где ввёл три операции над языками: объединение, конкатенация и итерация (звезда Клини). Клини доказал, что этих трёх операций достаточно для описания всех языков, распознаваемых конечными автоматами. В 1968 году Кен Томпсон (создатель Unix) использовал эти операции для построения regex движка в редакторе ed. Алгоритм Томпсона - конструкция NFA из regex - прямое применение теоремы Клини. Все современные regex движки (RE2, PCRE, std::regex) восходят к этой работе 1956 года.
Предварительные знания
Объединение языков
Представьте два фильтра в почтовом ящике: один пропускает письма от коллег, другой - письма с пометкой «Срочно». Если код хотите видеть письма, подходящие **хотя бы под один** фильтр, код **объединяете** их. Точно так же работает объединение формальных языков.
**Объединение (union)** языков L₁ и L₂ - это язык L₁ ∪ L₂ = {w : w ∈ L₁ **или** w ∈ L₂}. Строка принадлежит объединению, если она входит хотя бы в один из языков. Это стандартная теоретико-множественная операция.
**Объединение всегда «расширяет» язык:** |L₁ ∪ L₂| ≥ max(|L₁|, |L₂|). Если языки не пересекаются (L₁ ∩ L₂ = ∅), то |L₁ ∪ L₂| = |L₁| + |L₂|. Если один язык - подмножество другого (L₁ ⊆ L₂), то L₁ ∪ L₂ = L₂.
| L₁ | L₂ | L₁ ∪ L₂ | Комментарий |
|---|---|---|---|
| {a, ab} | {b, ba} | {a, ab, b, ba} | Непересекающиеся языки |
| {0, 1} | {1, 00} | {0, 1, 00} | Общий элемент: 1 |
| ∅ | L | L | ∅ - нейтральный элемент |
| Σ* | L | Σ* | Σ* поглощает всё |
| {ε} | {a} | {ε, a} | Пустая строка + символ |
В регулярных выражениях объединение записывается как **|** (вертикальная черта). Regex `cat|dog` описывает язык {cat, dog} = {cat} ∪ {dog}. Символ `|` в regex - это именно объединение формальных языков.
L₁ = {a, bc}, L₂ = {bc, d}. Что такое L₁ ∪ L₂?
Конкатенация языков
Объединение берёт строки «как есть». Конкатенация - принципиально другая операция: она **склеивает** строки попарно. Возьмите одну строку из первого языка, одну из второго, соедините - получите строку нового языка. И так для **всех** комбинаций.
**Конкатенация (concatenation)** языков L₁ и L₂: **L₁·L₂ = {xy : x ∈ L₁, y ∈ L₂}**. Для каждой пары строк (одна из L₁, одна из L₂) создаётся новая строка - результат их склеивания. Порядок важен: L₁·L₂ ≠ L₂·L₁ в общем случае.
Обратите внимание: |L₁·L₂| ≤ |L₁| × |L₂|. Равенство достигается не всегда - разные пары могут давать одинаковый результат. Например, если L = {a, aa}, то L² = {aa, aaa, aaaa} - три строки, а не четыре, потому что a·aa = aa·a = aaa.
| L₁ | L₂ | L₁·L₂ | |L₁·L₂| |
|---|---|---|---|
| {a, b} | {0, 1} | {a0, a1, b0, b1} | 4 |
| {ε} | L | L | |L| |
| ∅ | L | ∅ | 0 |
| {a, aa} | {a, aa} | {aa, aaa, aaaa} | 3 (не 4!) |
| {0, 1} | {0, 1} | {00, 01, 10, 11} | 4 |
**Два особых случая конкатенации:** 1. L·{ε} = {ε}·L = L - пустая строка как нейтральный элемент. 2. L·∅ = ∅·L = ∅ - пустой язык «уничтожает» конкатенацию. Не путайте: {ε} сохраняет язык, ∅ аннулирует его.
L₁ = {0, 11}, L₂ = {ε, 0}. Сколько строк содержит L₁·L₂?
Звезда Клини
есть набор LEGO-деталей (конечный язык). код можете собрать конструкцию из **любого количества** деталей, **в любом порядке**, **с повторениями**. Или не использовать ни одной - поставить пустую полку. Это и есть **звезда Клини** - самая мощная из трёх базовых операций.
**Звезда Клини (Kleene star):** L* = L⁰ ∪ L¹ ∪ L² ∪ L³ ∪ ... = ∪_{n≥0} Lⁿ. Это бесконечное объединение всех степеней языка. L⁰ = {ε} (всегда!), поэтому **ε ∈ L* для любого L**, включая L = ∅. **Плюс Клини:** L⁺ = L¹ ∪ L² ∪ L³ ∪ ... = L* \ {ε} (если ε ∉ L).
**Связь с Σ*.** Если Σ = {a, b}, то Σ* - это множество ВСЕХ строк над этим алфавитом. Но {a, b}* - это тоже множество всех строк! Значит Σ* в определении формального языка - это в буквальном смысле звезда Клини от алфавита.
| Язык L | L* | Описание |
|---|---|---|
| {0, 1} | {ε, 0, 1, 00, 01, 10, 11, ...} | Все двоичные строки = Σ* |
| {a} | {ε, a, aa, aaa, ...} | Строки из одних a: a* |
| {ab} | {ε, ab, abab, ababab, ...} | Повторения «ab»: (ab)* |
| ∅ | {ε} | Единственный элемент - ε |
| {ε} | {ε} | Повторение ε даёт ε |
| {0, 11} | {ε, 0, 11, 00, 011, 110, 1111, ...} | Произвольные комбинации 0 и 11 |
**Мнемоника:** L***** = «**ноль** или более»; L**⁺** = «**один** или более». В regex: `a*` матчит пустую строку, `a+` - нет. Это напрямую из формального определения.
L = {01}. Какие из строк принадлежат L*?
Замкнутость классов языков
Мы изучили три операции: объединение, конкатенацию, звезду Клини. Возникает вопрос: если взять два **регулярных** языка и объединить их - останется ли результат регулярным? А если взять **контекстно-свободный** язык и применить звезду Клини? Ответ на эти вопросы называется **замкнутостью**.
**Замкнутость (closure)** класса языков относительно операции означает: если применить операцию к языкам из этого класса, результат тоже будет в этом классе. Класс C **замкнут** относительно операции ⊕, если для любых L₁, L₂ ∈ C выполняется L₁ ⊕ L₂ ∈ C.
| Операция | Регулярные | Контекстно-свободные | Контекстно-зависимые |
|---|---|---|---|
| Объединение ∪ | ✓ Замкнуты | ✓ Замкнуты | ✓ Замкнуты |
| Конкатенация · | ✓ Замкнуты | ✓ Замкнуты | ✓ Замкнуты |
| Звезда Клини * | ✓ Замкнуты | ✓ Замкнуты | ✓ Замкнуты |
| Пересечение ∩ | ✓ Замкнуты | ✗ НЕ замкнуты | ✓ Замкнуты |
| Дополнение ¬ | ✓ Замкнуты | ✗ НЕ замкнуты | ✓ Замкнуты |
**Регулярные языки - самые «прочные»:** замкнуты относительно всех пяти операций. Это делает их удобными для практики - можно комбинировать regex как угодно, результат всегда будет регулярным. **Контекстно-свободные языки** слабее: они разрушаются при пересечении и дополнении.
Стивен Клини и его звезда
Стивен Клини (Stephen Kleene, 1909-1994) ввёл звезду Клини в 1956 году в статье «Representation of events in nerve nets and finite automata». Он изучал модели нервных сетей Маккаллока-Питтса и формализовал понятие «регулярного события» - множества, описываемого комбинацией объединения, конкатенации и итерации. Его нотация пережила десятилетия и сегодня используется миллионами программистов - каждый раз, когда код пишете `.*` в regex.
**Замкнутость - мощный инструмент доказательства.** Если код показали, что язык L - пересечение двух КС-языков, это НЕ доказывает, что L контекстно-свободный (КС-языки не замкнуты по ∩). Но если L - объединение двух регулярных языков, он точно регулярный (регулярные замкнуты по ∪).
Если два языка из одного класса, результат операции тоже будет в этом классе
Замкнутость зависит от КОНКРЕТНОЙ операции и КОНКРЕТНОГО класса. Контекстно-свободные языки замкнуты по объединению и конкатенации, но НЕ замкнуты по пересечению и дополнению
Каждая пара (класс, операция) нужно проверять отдельно. Пересечение двух КС-языков может дать язык {aⁿbⁿcⁿ}, который не описывается ни одной КС-грамматикой. Замкнутость - свойство, которое нужно доказывать, а не предполагать.
Ключевые идеи
- **Объединение L₁ ∪ L₂** - строки из первого ИЛИ второго языка; в regex это `|`
- **Конкатенация L₁·L₂** - склеивание всех пар строк; {ε} - нейтральный элемент, ∅ - аннулятор
- **Звезда Клини L*** = ∪ Lⁿ - ноль или более повторений; **всегда содержит ε**; L⁺ = L* без ε
- **Замкнутость** - регулярные языки замкнуты по всем операциям; КС-языки ломаются на пересечении и дополнении
Связанные темы
Операции над языками - мост между абстрактными множествами и практическими инструментами:
- Регулярные выражения — Три базовые операции (∪, ·, *) - это ровно три оператора regex. Следующий урок покажет формальный синтаксис
- Конечные автоматы — NFA/DFA строятся через объединение, конкатенацию и звезду - конструкция Томпсона
- Иерархия Хомского — Замкнутость операций определяет границы каждого уровня иерархии
Вопросы для размышления
- Вернёмся к regex из начала: `(GET|POST|PUT)\s+/api/.*`. Найдите в нём все три операции: объединение, конкатенацию и звезду Клини.
- Почему ∅* = {ε}? Если пустой язык не содержит строк, откуда берётся ε? Подсказка: L⁰ = {ε} по определению.
- Контекстно-свободные языки замкнуты по объединению, но не по пересечению. Используя закон де Моргана (A ∩ B = ¬(¬A ∪ ¬B)), объясните, почему они также не замкнуты по дополнению.