Регулярная грамматика

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

Определение и формальное описание

Формально, регулярная грамматика — это четвёрка \( G = (N, \Sigma, P, S) \), где:

• \( N \) — конечное множество нетерминальных символов (переменных);
• \( \Sigma \) — конечный алфавит терминальных символов, причём \( N \cap \Sigma = \varnothing \);
• \( P \) — конечное множество правил вывода (продукций) определённого вида;
• \( S \in N \) — начальный нетерминал (аксиома).

Существует два основных типа регулярных грамматик, различающихся формой правил:

Правосторонняя (праволинейная) грамматика

В такой грамматике все правила имеют один из следующих видов:

1. \( A \rightarrow aB \), где \( A, B \in N \), \( a \in \Sigma \);
2. \( A \rightarrow a \), где \( A \in N \), \( a \in \Sigma \);
3. \( A \rightarrow \varepsilon \), где \( \varepsilon \) — пустая цепочка (допускается не всегда, обычно только для порождения пустого слова).

Левосторонняя (леволинейная) грамматика

В такой грамматике все правила имеют один из следующих видов:

1. \( A \rightarrow Ba \), где \( A, B \in N \), \( a \in \Sigma \);
2. \( A \rightarrow a \), где \( A \in N \), \( a \in \Sigma \);
3. \( A \rightarrow \varepsilon \).

Оба типа грамматик эквивалентны по выразительной мощности: любой язык, порождаемый левосторонней грамматикой, может быть порождён некоторой правосторонней грамматикой, и наоборот. Однако смешивать правила левостороннего и правостороннего типов в одной грамматике нельзя — такая грамматика уже не будет регулярной, а станет контекстно-свободной (тип 2).

Примеры

Пример 1: Язык идентификаторов

Рассмотрим язык, состоящий из буквы, за которой следует ноль или более букв или цифр. Пусть \( \Sigma = \{a, b, c, 0, 1\} \), \( N = \{S, L\} \). Правосторонняя грамматика:

• \( S \rightarrow aL \)
• \( S \rightarrow bL \)
• \( S \rightarrow cL \)
• \( L \rightarrow aL \)
• \( L \rightarrow bL \)
• \( L \rightarrow cL \)
• \( L \rightarrow 0L \)
• \( L \rightarrow 1L \)
• \( L \rightarrow \varepsilon \)

Эта грамматика порождает цепочки, начинающиеся с буквы, например: \( a \), \( bc0 \), \( c1a \).

Пример 2: Язык целых чисел

Рассмотрим язык целых чисел без знака (десятичная запись). Пусть \( \Sigma = \{0, 1, 2, 3, 4, 5, 6, 7, 8, 9\} \), \( N = \{S, D\} \). Правосторонняя грамматика:

• \( S \rightarrow 0D \)
• \( S \rightarrow 1D \)
• ...
• \( S \rightarrow 9D \)
• \( D \rightarrow 0D \)
• \( D \rightarrow 1D \)
• ...
• \( D \rightarrow 9D \)
• \( D \rightarrow \varepsilon \)

Эта грамматика порождает любую непустую последовательность цифр.

Связь с конечными автоматами

Регулярные грамматики и конечные автоматы (как детерминированные, так и недетерминированные) эквивалентны. Для любой регулярной грамматики можно построить конечный автомат, распознающий тот же язык, и наоборот.

Построение автомата по грамматике

Для правосторонней грамматики \( G = (N, \Sigma, P, S) \) строится недетерминированный конечный автомат (НКА) \( M = (Q, \Sigma, \delta, q_0, F) \):

• \( Q = N \cup \{q_f\} \), где \( q_f \) — новое допускающее состояние;
• \( q_0 = S \);
• Для каждого правила \( A \rightarrow aB \) добавляется переход \( \delta(A, a) = B \);
• Для каждого правила \( A \rightarrow a \) добавляется переход \( \delta(A, a) = q_f \);
• Для правила \( A \rightarrow \varepsilon \) состояние \( A \) объявляется допускающим.

Построение грамматики по автомату

Для НКА \( M = (Q, \Sigma, \delta, q_0, F) \) строится правосторонняя грамматика \( G = (N, \Sigma, P, S) \):

• \( N = Q \);
• \( S = q_0 \);
• Для каждого перехода \( \delta(p, a) = q \) добавляется правило \( p \rightarrow aq \);
• Для каждого допускающего состояния \( q \in F \) добавляется правило \( q \rightarrow \varepsilon \).

Связь с регулярными выражениями

Регулярные грамматики, конечные автоматы и регулярные выражения описывают один и тот же класс языков — регулярные языки. Существуют алгоритмы преобразования между этими формализмами:

• Из регулярного выражения в НКА (алгоритм Томпсона).
• Из НКА в регулярное выражение (алгоритм удаления состояний или метод Бжозовского).
• Из регулярной грамматики в регулярное выражение — через решение системы линейных уравнений в алгебре Клини.

Ограничения и выразительная мощность

Регулярные грамматики не могут описывать языки, требующие запоминания произвольного количества информации (например, языки с вложенными структурами). Классические примеры языков, не являющихся регулярными:

• Язык \( \{ a^n b^n \mid n \ge 0 \} \) — язык, состоящий из цепочек, содержащих одинаковое количество букв \( a \) и \( b \), где все \( a \) предшествуют всем \( b \). Этот язык требует подсчёта, что невозможно для конечного автомата.
• Язык правильно вложенных скобок — требует учёта глубины вложенности.

Для доказательства нерегулярности языка используется лемма о накачке (pumping lemma) для регулярных языков.

Применение

Регулярные грамматики широко применяются в информатике и лингвистике:

Лексический анализ

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

Обработка текста

Регулярные выражения, эквивалентные регулярным грамматикам, используются в текстовых редакторах, утилитах (grep, sed, awk) и языках программирования (Perl, Python, Java) для поиска и замены шаблонов.

Протоколы и форматы данных

Регулярные грамматики описывают синтаксис простых протоколов (например, HTTP-заголовки, SMTP-команды) и форматов данных (CSV, INI-файлы).

Морфология

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

Интересные факты

• Регулярные грамматики были введены Ноамом Хомским в 1956 году в рамках его иерархии формальных грамматик.
• Термин «регулярная грамматика» иногда путают с «регулярным выражением», но это разные, хотя и эквивалентные, формализмы.
• В некоторых учебниках регулярные грамматики называют «автоматными грамматиками» из-за их прямой связи с конечными автоматами.
• Существуют расширения регулярных грамматик, такие как грамматики с ограниченным контекстом (например, грамматики с проверкой контекста), но они уже выходят за рамки типа 3.

Источники

1. Хомский Н. «Три модели описания языка» (1956).
2. Хопкрофт Дж., Мотвани Р., Ульман Дж. «Введение в теорию автоматов, языков и вычислений» (3-е издание, 2006).
3. Ахо А., Лам М., Сети Р., Ульман Дж. «Компиляторы: принципы, технологии и инструменты» (2-е издание, 2008).
4. Льюис Г., Пападимитриу Х. «Элементы теории вычислений» (2-е издание, 1998).