Автоматы и теория формальных языков: что скрывается за регулярными выражениями и иерархией Хомского

Грандиозная теория, лежащая в основе информатики — это автоматы (Automata) и теория формальных языков (Formal Language Theory).

Эта теория является основой всего: от регулярных выражений (Regular Expressions), которые мы пишем каждый день, и компиляторов, анализирующих исходный код языков программирования, до обработки естественного языка. В этой статье мы отправимся в глубокий мир, где само понятие вычислений определяется математически и абстрактно, опираясь на классификацию, известную как иерархия Хомского (Chomsky Hierarchy).

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

В отличие от «естественных языков», таких как русский или английский, которые мы используем в повседневной жизни, языки, строго определенные математическими правилами, называются формальными языками (Formal Language). Формальный язык состоит из следующих базовых компонентов.

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

В теории формальных языков алфавит (Alphabet) — это непустое конечное множество символов. Обычно он обозначается символом $ \Sigma $ (сигма).

$$ \Sigma = \{ 0, 1 \} $$

Выше представлен алфавит двоичных чисел. Конечная последовательность символов, сгенерированная из этого алфавита, называется строкой (String) или словом (Word).

Множество всех строк, образованных из алфавита $ \Sigma $ (включая пустую строку $ \epsilon $), обозначается как $ \Sigma^* $ с использованием замыкания Клини (Kleene Star).

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

Формальный язык $ L $ определяется как подмножество $ \Sigma^* $. То есть, $ L \subseteq \Sigma^* $.

Например, «множество строк, состоящих из 0 и 1 и обязательно заканчивающихся на 1» — это язык. Этот язык $ L $ можно описать следующим образом:

$$ L = \{ w1 \mid w \in \{ 0, 1 \}^* \} $$

Главная цель теории формальных языков — выяснить, как такие потенциально бесконечные множества строк (языки) можно представить и распознать с помощью конечных правил (грамматик) или машин с конечным числом состояний (автоматов).

2. Иерархия Хомского (Chomsky Hierarchy)

Лингвист Ноам Хомский (Noam Chomsky) в 1956 году классифицировал формальные языки на 4 уровня в зависимости от строгости ограничений их правил вывода. Это и есть иерархия Хомского.

Иерархия классифицируется следующим образом (от типа 0 до типа 3). Чем больше число, тем уже класс языков, который можно выразить, но тем легче его анализировать с помощью компьютера.

  flowchart TD
    "Type0"["Тип-0: Рекурсивно перечислимые языки\n(Машина Тьюринга)"]
    "Type1"["Тип-1: Контекстно-зависимые языки\n(Линейно ограниченный автомат)"]
    "Type2"["Тип-2: Контекстно-свободные языки\n(Магазинный автомат)"]
    "Type3"["Тип-3: Регулярные языки\n(Конечный автомат)"]

    "Type0" --- "Type1"
    "Type1" --- "Type2"
    "Type2" --- "Type3"

    style "Type0" fill:#f9f9f9,stroke:#333,stroke-width:2px
    style "Type1" fill:#e9e9e9,stroke:#333,stroke-width:2px
    style "Type2" fill:#d9d9d9,stroke:#333,stroke-width:2px
    style "Type3" fill:#c9c9c9,stroke:#333,stroke-width:2px

Тип 3 (Регулярные языки) : Могут быть выражены регулярными выражениями и распознаны конечным автоматом.
Тип 2 (Контекстно-свободные языки) : Используются в синтаксисе языков программирования и т.д., распознаются магазинным автоматом (pushdown automaton).
Тип 1 (Контекстно-зависимые языки) : Распознаются линейно ограниченным автоматом.
Тип 0 (Рекурсивно перечислимые языки) : Распознаются машиной Тьюринга. Все вычислимые языки.

Со следующей главы мы подробно рассмотрим эту иерархию снизу вверх (начиная с наиболее ограниченного Типа 3).

3. Регулярные языки и конечные автоматы (Тип 3)

Конечные автоматы (DFA / NFA)

На самом внутреннем уровне иерархии Хомского находятся регулярные языки (Regular Languages). Вычислительная модель, распознающая эти языки — это конечный автомат (Finite Automata, FA).

Существуют конечные автоматы с детерминированными переходами состояний — DFA (Deterministic Finite Automaton), и с недетерминированными — NFA (Nondeterministic Finite Automaton). Удивительно, но доказано, что классы языков, которые они могут распознавать, абсолютно равны (DFA и NFA эквивалентны).

Математически DFA определяется как следующая пятерка $ M = (Q, \Sigma, \delta, q_0, F) $:

$ Q $ : Конечное множество состояний
$ \Sigma $ : Алфавит
$ \delta $ : Функция переходов состояний ( $ \delta: Q \times \Sigma \rightarrow Q $ )
$ q_0 $ : Начальное состояние ( $ q_0 \in Q $ )
$ F $ : Множество допускающих (конечных) состояний ( $ F \subseteq Q $ )

Пример: DFA, допускающий строки, содержащие «101»

Рассмотрим DFA в алфавите $ \Sigma = \{ 0, 1 \} $, который распознает строки, содержащие подстроку «101».

  stateDiagram-v2
    [*] --> "q0"
    "q0" --> "q1" : "1"
    "q0" --> "q0" : "0"
    "q1" --> "q2" : "0"
    "q1" --> "q1" : "1"
    "q2" --> "q3" : "1"
    "q2" --> "q0" : "0"
    "q3" --> "q3" : "0, 1"
    "q3" --> [*]

Давайте реализуем эту диаграмму переходов состояний в виде программы на Python.

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
class DFA:
    def __init__(self):
        self.states = {'q0', 'q1', 'q2', 'q3'}
        self.alphabet = {'0', '1'}
        self.start_state = 'q0'
        self.accept_states = {'q3'}
        
        # Функция переходов состояний
        self.transitions = {
            'q0': {'0': 'q0', '1': 'q1'},
            'q1': {'0': 'q2', '1': 'q1'},
            'q2': {'0': 'q0', '1': 'q3'},
            'q3': {'0': 'q3', '1': 'q3'}
        }
        
    def accepts(self, string: str) -> bool:
        current_state = self.start_state
        for char in string:
            if char not in self.alphabet:
                return False
            current_state = self.transitions[current_state][char]
        return current_state in self.accept_states

# Тесты
dfa = DFA()
test_strings = ["001010", "11101", "1001", "010", "101"]

for s in test_strings:
    result = dfa.accepts(s)
    print(f"String '{s}': {'Accepted' if result else 'Rejected'}")

Связь с регулярными выражениями (Теорема Клини)

Регулярные выражения (Regular Expression), используемые в программировании, — это нотация для описания этих регулярных языков. Стивен Клини (Stephen Kleene) доказал теорему, гласящую, что «выразимость языка с помощью регулярного выражения эквивалентна его распознаваемости конечным автоматом».

Реальные движки регулярных выражений в языках программирования (например, модуль re в Python) внутренне строят NFA из заданного шаблона регулярного выражения и оценивают строку.

Ограничения леммы о разрастании (Pumping Lemma)

Регулярные языки очень удобны, но у них есть свои пределы. Например, «множество строк, в которых за $ n $ символами $ a $ следует $ n $ символов $ b $» ($ L = \{ a^n b^n \mid n \ge 0 \} $) не является регулярным языком. Это связано с тем, что конечные автоматы не имеют памяти (такой как стек) для «подсчета», поэтому они не могут бесконечно помнить, сколько символов $ a $ уже пришло. Математический метод для доказательства этого — лемма о разрастании для регулярных языков (Pumping Lemma).

4. Контекстно-свободные языки и магазинные автоматы (Тип 2)

Для выражения соответствия скобок или синтаксиса языков программирования (например, вложенности if-else), которые не могут быть выражены регулярными языками, необходимы контекстно-свободные языки (Context-Free Languages, CFL).

Магазинный автомат (PDA)

Вычислительная модель, распознающая контекстно-свободные языки, — это магазинный автомат (Pushdown Automaton, PDA). PDA — это конечный автомат с добавлением стека (Stack, память типа LIFO). Использование стека позволяет, например, «запоминать количество открытых скобок и расходовать их каждый раз, когда встречается закрывающая скобка».

Пример: PDA, допускающий $ a^n b^n $

Давайте реализуем PDA, который допускает строки с одинаковым количеством идущих подряд $ a $ и $ b $ в алфавите $ \Sigma = \{ a, b \} $.

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
class PDA:
    def __init__(self):
        self.stack = []
        self.state = 'q0'
        
    def accepts(self, string: str) -> bool:
        self.stack = []
        self.state = 'q_a' # Состояние чтения a
        
        for char in string:
            if self.state == 'q_a':
                if char == 'a':
                    self.stack.append('A') # Поместить в стек
                elif char == 'b':
                    self.state = 'q_b'
                    if not self.stack:
                        return False
                    self.stack.pop() # Извлечь из стека
                else:
                    return False
            elif self.state == 'q_b':
                if char == 'b':
                    if not self.stack:
                        return False
                    self.stack.pop()
                else:
                    return False
                    
        # Если после прочтения строки стек пуст, допускаем
        return len(self.stack) == 0

# Тесты
pda = PDA()
print("aaabbb:", pda.accepts("aaabbb")) # True
print("aabbb:", pda.accepts("aabbb"))   # False
print("ab:", pda.accepts("ab"))         # True
print("a:", pda.accepts("a"))           # False

Контекстно-свободные грамматики (CFG) и BNF

Правила, порождающие контекстно-свободные языки, называются контекстно-свободной грамматикой (Context-Free Grammar, CFG). CFG определяется как $ (V, \Sigma, R, S) $. Здесь $ R $ — множество правил вывода вида $ A \rightarrow \gamma $ (где $ A $ — нетерминальный символ, а $ \gamma $ — последовательность терминальных и нетерминальных символов).

BNF (Backus-Naur Form), часто встречающаяся в спецификациях языков программирования, — это метаязык для описания контекстно-свободных грамматик. Ниже приведен пример BNF для определения математического выражения.

1
2
3
4
<expr>   ::= <expr> "+" <term> | <term>
<term>   ::= <term> "*" <factor> | <factor>
<factor> ::= "(" <expr> ")" | <number>
<number> ::= "0" | "1" | "2" | ... | "9"

На этапе синтаксического анализа (Parsing) компилятора алгоритмы, применяющие принципы PDA (такие как LL-анализ или LR-анализ), проверяют, соответствует ли последовательность токенов, сгенерированная лексическим анализатором, этой контекстно-свободной грамматике, и строят абстрактное синтаксическое дерево (AST).

5. Контекстно-зависимые языки и линейно ограниченные автоматы (Тип 1)

Контекстно-свободные языки могут выразить большую часть синтаксиса языков программирования, но они не способны выразить ограничения, зависящие от окружающего контекста (семантические ограничения), такие как «можно использовать только объявленные переменные». С этим справляются контекстно-зависимые языки (Context-Sensitive Languages, CSL).

Линейно ограниченный автомат (LBA)

Контекстно-зависимые языки распознаются линейно ограниченными автоматами (Linear Bounded Automaton, LBA). LBA — это разновидность машины Тьюринга, но с той особенностью, что длина ее ленты ограничена размером, пропорциональным (линейным) длине входной строки.

Типичным примером контекстно-зависимого языка является $ L = \{ a^n b^n c^n \mid n \ge 1 \} $. Поскольку у PDA только один стек, он может сопоставить количество $ a $ и $ b $, но не может сопоставить следующее за ними количество $ c $ (так как, подсчитав $ a $, он полностью извлечет их из стека). LBA может перемещаться по ленте вперед и назад, поэтому он способен распознать этот язык.

Считается, что естественные языки (человеческие языки) в целом сложнее контекстно-свободных языков и обладают свойствами, более близкими к контекстно-зависимым языкам.

6. Рекурсивно перечислимые языки и машина Тьюринга (Тип 0)

Наконец, мы дошли до рекурсивно перечислимых языков (Recursively Enumerable Languages) и машины Тьюринга (Turing Machine).

Машина Тьюринга: совершенная вычислительная модель

Машина Тьюринга, предложенная Аланом Тьюрингом (Alan Turing) в 1936 году, обладает вычислительной мощностью, эквивалентной теоретическим пределам любого современного компьютера (компьютера фон Неймановской архитектуры).

Машина Тьюринга состоит из бесконечной «ленты», «головки», которая перемещается влево и вправо, читая и записывая на ленту, а также конечного числа «состояний».

  flowchart LR
    subgraph "Tape"
        direction LR
        "T1"["..."] --- "T2"["0"] --- "T3"["1"] --- "T4"["1"] --- "T5"["0"] --- "T6"["..."]
    end
    "Head"(("Head")) --> "T3"
    "State"["Состояние: q_read\n(Конечное управление)"] --- "Head"

Проблема остановки (Halting Problem)

Одно из самых важных открытий в рамках машин Тьюринга — это существование невычислимости (Undecidability). Известная проблема остановки гласит, что «не существует программы (алгоритма), которая могла бы для любой произвольной программы и ее входных данных определить, остановится ли эта программа когда-нибудь, или же она попадет в бесконечный цикл».

Это указывает на математический предел, означающий, что насколько бы мощный ИИ или компьютер мы ни создали, «абсолютно невозможно создать идеальный инструмент статического анализа, который бы автоматически заранее обнаруживал все ошибки и бесконечные циклы».

7. Пересечение современной разработки ПО и теории формальных языков

Рассмотренные нами теории ни в коем случае не ограничиваются академической башней из слоновой кости. Они активно применяются повсюду в современной программной инженерии.

Автоматическая генерация лексических анализаторов (Lexer) : Инструменты, такие как Lex и Flex, преобразуют регулярные выражения, написанные разработчиком, в DFA и автоматически генерируют быстрый код на языке C.
Автоматическая генерация синтаксических анализаторов (Parser) : Инструменты, такие как Yacc и Bison, автоматически генерируют LR-парсеры (применение PDA) из BNF (контекстно-свободной грамматики), написанной разработчиком.
Парсинг JSON и XML : Валидация и парсинг этих форматов данных также основаны на алгоритмах теории формальных языков.
Подсветка синтаксиса в редакторах : IDE могут так быстро подсвечивать код именно потому, что за кулисами работают конечные автоматы.

Подводные камни движков Regex (Катастрофический возврат)

Движки регулярных выражений, встроенные во многие языки программирования (Java, Python, Ruby, JavaScript и др.), реализованы не как теоретически чистые DFA, а на базе NFA с возвратом (backtracking) (или как движки с возвратом).

Из-за этого, если передать хитроумно составленную строку в регулярное выражение определенного шаблона (например: (a+)+$), вычислительная сложность может экспоненциально возрасти, вызывая уязвимость ReDoS (Regular Expression Denial of Service), из-за которой система зависает. Зная теорию, можно логически осмыслить, почему происходит возврат и как переписать шаблон так, чтобы свести его к безопасной обработке, эквивалентной DFA.

Заключение: Эстетика абстракции

Теория автоматов и формальных языков полностью исключает физическую структуру компьютера (процессор и память) и является вершиной абстракции, превращаясь в чистую математическую модель, отвечающую на вопросы «что такое вычисление» и «что такое язык».

Type-3 (DFA) : Машина без памяти (регулярные выражения)
Type-2 (PDA) : Машина со стековой памятью (синтаксический анализ)
Type-1 (LBA) : Машина с конечной лентой
Type-0 (TM) : Машина с бесконечной лентой (универсальный компьютер)

Исходный код, который мы пишем каждый день, разбирается группой гигантских автоматов, называемых компиляторами, от Типа 2 (синтаксис) до Типа 3 (лексика), и в конечном итоге переводится в машинный код.

Даже когда поверхностные фреймворки и популярные языки меняются, эта прочная математическая основа, заложенная в 1950-х годах, остается неизменной. Иногда, сталкиваясь со сложными головоломками регулярных выражений или имея возможность написать новый парсер, почему бы не задуматься о великих теориях Тьюринга и Хомского, лежащих в их основе?