Неограниченная грамматика

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

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

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

• \( N \) — конечное множество нетерминальных символов (переменных, обозначающих синтаксические категории);
• \( \Sigma \) — конечное множество терминальных символов (алфавит языка, не пересекающийся с \( N \));
• \( P \) — конечное множество правил вывода (продукций) вида \( \alpha \rightarrow \beta \), где \( \alpha \) и \( \beta \) — произвольные строки, составленные из символов \( N \cup \Sigma \), причём строка \( \alpha \) не может быть пустой (то есть \( \alpha \in (N \cup \Sigma)^+ \), а \( \beta \in (N \cup \Sigma)^* \));
• \( S \in N \) — начальный символ (аксиома).

Ключевое отличие неограниченной грамматики от грамматик более низких типов (контекстно-зависимых, контекстно-свободных, регулярных) заключается в том, что левая часть правила \( \alpha \) может содержать как терминальные, так и нетерминальные символы, а её длина не обязательно равна единице. Это позволяет правилам «переписывать» не только отдельные символы, но и целые контексты, что даёт возможность моделировать произвольные алгоритмические процессы.

Место в иерархии Хомского

Иерархия Хомского, предложенная Ноамом Хомским в 1956 году, включает четыре типа грамматик, упорядоченных по возрастанию выразительной силы:

1. Тип 3 (Регулярные грамматики): Правила имеют вид \( A \rightarrow aB \) или \( A \rightarrow a \). Порождают регулярные языки, распознаваемые конечными автоматами.
2. Тип 2 (Контекстно-свободные грамматики): Правила имеют вид \( A \rightarrow \gamma \), где \( A \) — один нетерминал. Порождают контекстно-свободные языки, распознаваемые автоматами с магазинной памятью.
3. Тип 1 (Контекстно-зависимые грамматики): Правила имеют вид \( \alpha A \beta \rightarrow \alpha \gamma \beta \), где \( A \) — нетерминал, а \( \alpha, \beta, \gamma \) — строки. Порождают контекстно-зависимые языки, распознаваемые линейно ограниченными автоматами.
4. Тип 0 (Неограниченные грамматики): Без ограничений на вид правил. Порождают рекурсивно перечислимые языки, распознаваемые машинами Тьюринга.

Неограниченная грамматика является надмножеством всех остальных типов: любой язык, порождаемый грамматикой типа 1, 2 или 3, может быть порождён и грамматикой типа 0, но обратное неверно. Существуют рекурсивно перечислимые языки, которые не являются контекстно-зависимыми.

Связь с машинами Тьюринга

Главное теоретическое значение неограниченных грамматик заключается в их эквивалентности по выразительной силе машинам Тьюринга. В 1959 году американский математик Джон Майхилл доказал, что для любой неограниченной грамматики существует машина Тьюринга, которая распознаёт язык, порождаемый этой грамматикой, и наоборот, для любой машины Тьюринга существует неограниченная грамматика, порождающая язык, распознаваемый этой машиной.

Эта связь устанавливает, что неограниченные грамматики являются формальным эквивалентом алгоритмов в смысле тезиса Чёрча — Тьюринга. Любой язык, для которого существует алгоритм его распознавания (то есть рекурсивно перечислимый язык), может быть порождён некоторой неограниченной грамматикой. Однако, как и для машин Тьюринга, для неограниченных грамматик неразрешима проблема остановки: невозможно в общем случае определить, порождает ли данная грамматика данную строку за конечное число шагов.

Пример неограниченной грамматики

Рассмотрим неограниченную грамматику, порождающую язык \( L = \{ a^n b^n c^n \mid n \ge 1 \} \), который не является контекстно-свободным. Эта грамматика демонстрирует возможность «перемещения» символов для проверки равенства количеств трёх различных букв.

Пусть \( N = \{ S, A, B, C, X, Y, Z \} \), \( \Sigma = \{ a, b, c \} \). Правила:

1. \( S \rightarrow aXBC \)
2. \( X \rightarrow aXBC \)
3. \( X \rightarrow aYC \)
4. \( aY \rightarrow ab \)
5. \( bY \rightarrow Yb \)
6. \( BY \rightarrow YB \)
7. \( CY \rightarrow YC \)
8. \( Y \rightarrow bZ \)
9. \( bZ \rightarrow Zb \)
10. \( BZ \rightarrow ZB \)
11. \( CZ \rightarrow Zc \)
12. \( Z \rightarrow c \)

Процесс вывода для строки \( a^2 b^2 c^2 \):

• \( S \xrightarrow{1} aXBC \xrightarrow{2} aaXBCBC \xrightarrow{3} aaaYCBC \)
• Далее, используя правила 4–8, символ \( Y \) «перемещается» вправо, заменяя \( a \) на \( b \), а затем \( b \) на \( Y \), пока не достигнет позиции перед \( C \). После этого \( Y \) переходит в \( Z \), и процесс повторяется для \( Z \), который заменяет \( C \) на \( c \).
• В результате получается строка \( aaabbbccc \), что соответствует \( n=3 \).

Этот пример показывает, как неограниченные грамматики могут моделировать сложные зависимости между символами, недоступные для контекстно-свободных грамматик.

Применение

Несмотря на свою теоретическую фундаментальность, неограниченные грамматики редко используются на практике для описания синтаксиса языков программирования или естественных языков из-за своей неэффективности: алгоритмы разбора для них имеют экспоненциальную сложность или не гарантируют завершения.

Основные области применения:

• Теория вычислимости: Неограниченные грамматики служат инструментом для доказательства неразрешимости различных проблем, связанных с формальными языками.
• Математическая лингвистика: Используются для моделирования синтаксических структур, требующих неконтекстно-свободных механизмов, таких как перекрёстные зависимости в некоторых естественных языках (например, в швейцарском немецком или нидерландском).
• Формальные модели в биоинформатике: Применяются для описания некоторых структур РНК, которые могут иметь сложные вложенные и перекрёстные зависимости, выходящие за рамки контекстно-свободных грамматик.
• Теоретические основы компиляции: В некоторых подходах к оптимизации кода и анализу программ используются более мощные, чем контекстно-свободные, формализмы, основанные на идеях неограниченных грамматик.

Критика и ограничения

Основной недостаток неограниченных грамматик — их алгоритмическая неразрешимость. Для них не существует общего алгоритма, который бы для произвольной грамматики и произвольной строки определял, принадлежит ли строка языку, порождаемому этой грамматикой. Это делает их непригодными для прямого использования в задачах синтаксического анализа, где требуется детерминированное и быстрое распознавание.

Кроме того, неограниченные грамматики не обладают свойством конечной представимости в том смысле, что для описания многих рекурсивно перечислимых языков требуется бесконечное количество правил или же правила становятся крайне громоздкими. На практике предпочтение отдаётся грамматикам более низких уровней, которые, хотя и менее выразительны, но допускают эффективные алгоритмы разбора.

Источники

1. Хомский, Н. (1956). Три модели описания языка. IRE Transactions on Information Theory, 2(3), 113–124.
2. Хопкрофт, Дж., Мотвани, Р., Ульман, Дж. (2001). Введение в теорию автоматов, языков и вычислений. 2-е изд. — М.: Вильямс.
3. Майхилл, Дж. (1959). Конечные автоматы и представление событий. WADC Technical Report, 57-624.
4. Саломаа, А. (1973). Формальные языки. — М.: Мир.
5. Гинзбург, С. (1966). Математическая теория контекстно-свободных языков. — М.: Мир.