Алфавиты, строки и языки

Прежде чем строить автоматы, договоримся о словаре: что такое алфавит, строка и язык в строгом смысле.

Язык над алфавитом Σ — это любое множество строк, составленных из символов Σ (возможно, бесконечное, возможно, пустое).

Алфавит и строки

Алфавит Σ — конечное непустое множество символов. Например, Σ = {0, 1} для двоичных строк или Σ = {a, b, c}. Строка (или слово) над Σ — конечная последовательность символов из Σ. Длину строки w обозначают |w|. Особая строка — пустое слово ε длины 0: в ней ноль символов. Не путайте ε с пустым языком ∅ — это строка, а не множество.

Множество всех строк над Σ (включая ε) обозначают Σ^* — это замыкание Клини. Оно бесконечно, но счётно. Множество непустых строк — Σ⁺ = Σ^* \ {ε}.

Σ = {a, b}
Σ* = { ε, a, b, aa, ab, ba, bb, aaa, ... }   ← бесконечно, но счётно
|ε| = 0     |ab| = 2     |aab| = 3

Операции над строками

Главная операция — конкатенация: приписывание одной строки к другой. Если x = «ab», y = «ba», то xy = «abba». Пустое слово — нейтральный элемент: εw = wε = w. Степень строки — повтор: a³ = «aaa», a⁰ = ε. Это даёт компактную запись языков вроде {aⁿbⁿ | n ≥ 0} = {ε, ab, aabb, aaabbb, ...}.

def power(s, n):
    return s * n          # 'a'*3 == 'aaa'

def concat(x, y):
    return x + y

print(power("a", 0) or "ε")
print(power("a", 3))
print(concat("ab", "ba"))
# язык a^n b^n для n от 0 до 3
for n in range(4):
    print(repr(power("a", n) + power("b", n)))

Вывод:

ε
aaa
abba
''
'ab'
'aabb'
'aaabbb'

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

Язык L — это любое подмножество Σ^*. Примеры языков над {0, 1}: «все строки чётной длины», «все строки, начинающиеся с 1», «двоичные записи чисел, кратных 3», «∅ (пустой язык, ноль строк)», «{ε} (язык из одного пустого слова)». Обратите внимание: ∅ и {ε} — разные языки. В первом нет ни одной строки, во втором ровно одна (пустая).

Операции над языками наследуются из теории множеств (объединение, пересечение, дополнение) плюс две специфические: конкатенация языков L·M = {xy | x ∈ L, y ∈ M} и звезда Клини L^* = все конкатенации нуля и более строк из L. Эти операции — кирпичики, из которых строятся регулярные выражения.

Как работает под капотом

Почему теоретики так педантичны с ε и ∅? Потому что от этого зависит корректность доказательств. Звезда Клини L^* по определению всегда содержит ε (как конкатенацию нуля строк), даже если L = ∅: ∅^* = {ε}. Это спасает базовый случай индукции. А язык {aⁿbⁿ}, который кажется простым, окажется не регулярным — именно потому, что требует «памяти» под счётчик n, которой у конечного автомата нет. Формальный язык множеств позволяет такие тонкости сформулировать точно.

Частые ошибки

Путать ε и ∅. ε — строка (элемент Σ^*), ∅ — язык (подмножество Σ^*). |ε| = 0, но ∅ вообще не имеет длины.

Считать, что язык обязан быть конечным. Большинство интересных языков бесконечны: «все палиндромы», «все корректные программы на Python».

Забывать ε в звезде. L^* всегда содержит пустое слово, что бы ни было в L.

Итог

Алфавит Σ — конечное множество символов; строка — конечная последовательность над ним; ε — пустое слово.
Σ^* — все строки над Σ (бесконечно, счётно); язык — любое подмножество Σ^*.
Операции: конкатенация, степень, звезда Клини; ∅^* = {ε}.
∅ и {ε} — разные языки; путать их — частая ошибка.