Нумерационная теорема Хомского – Шютценбергера. - Chomsky–Schützenberger enumeration theorem

В формальная теория языка, то Нумерационная теорема Хомского – Шютценбергера. это теорема, полученная Ноам Хомский и Марсель-Пауль Шютценбергер о количестве слов заданной длины, созданных однозначная контекстно-свободная грамматика. Теорема обеспечивает неожиданную связь между теорией формальные языки и абстрактная алгебра.

Заявление

Чтобы сформулировать теорему, необходимы несколько понятий из алгебры и теории формального языка.

Позволять ${\displaystyle \mathbb {N} }$ обозначают множество неотрицательных целых чисел. А степенной ряд над ${\displaystyle \mathbb {N} }$ является бесконечная серия формы

${\displaystyle f=f(x)=\sum _{k=0}^{\infty }a_{k}x^{k}=a_{0}+a_{1}x^{1}+a_{2}x^{2}+a_{3}x^{3}+\cdots }$

с коэффициентами ${\displaystyle a_{k}}$ в ${\displaystyle \mathbb {N} }$. В умножение двух официальных степенной ряд ${\displaystyle f}$ и ${\displaystyle g}$ определяется ожидаемым образом как свертка последовательностей ${\displaystyle a_{n}}$ и ${\displaystyle b_{n}}$:

${\displaystyle f(x)\cdot g(x)=\sum _{k=0}^{\infty }\left(\sum _{i=0}^{k}a_{i}b_{k-i}\right)x^{k}.}$

В частности, мы пишем ${\displaystyle f^{2}=f(x)\cdot f(x)}$, ${\displaystyle f^{3}=f(x)\cdot f(x)\cdot f(x)}$, и так далее. По аналогии с алгебраические числа, степенной ряд ${\displaystyle f(x)}$ называется алгебраический над ${\displaystyle \mathbb {Q} (x)}$, если существует конечный набор многочленов ${\displaystyle p_{0}(x),p_{1}(x),p_{2}(x),\ldots ,p_{n}(x)}$ каждый с рациональный коэффициенты такие, что

${\displaystyle p_{0}(x)+p_{1}(x)\cdot f+p_{2}(x)\cdot f^{2}+\cdots +p_{n}(x)\cdot f^{n}=0.}$

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

Теорема Хомского – Шютценбергера.. Если ${\displaystyle L}$ это контекстно-свободный язык допущение однозначной контекстно-свободной грамматики, и ${\displaystyle a_{k}:=|L\ \cap \Sigma ^{k}|}$ это количество слов длины ${\displaystyle k}$ в ${\displaystyle L}$, тогда ${\displaystyle G(x)=\sum _{k=0}^{\infty }a_{k}x^{k}}$ это степенной ряд над ${\displaystyle \mathbb {N} }$ что алгебраически над ${\displaystyle \mathbb {Q} (x)}$.

Доказательства этой теоремы даются Куич и Саломаа (1985), и по Панхольцер (2005).

использование

Асимптотические оценки

Теорема может быть использована в аналитическая комбинаторика оценить количество слов длины п генерируется заданной однозначной контекстно-свободной грамматикой, как п становится большим. Следующий пример дается Грубер, Ли и Шаллит (2012): недвусмысленная контекстно-свободная грамматика грамм над алфавитом {0,1} имеет начальный символ S и следующие правила

S → M | U

M → 0M1M | ε

U → 0S | 0M1U.

Чтобы получить алгебраическое представление степенного ряда ${\displaystyle G(x)}$ связанный с заданной контекстно-свободной грамматикой грамм, грамматика преобразуется в систему уравнений. Это достигается заменой каждого символа терминала на Икс, каждое появление ε на целое число «1», каждое вхождение «→» на «=» и каждое вхождение «|» на '+' соответственно. Операция конкатенации в правой части каждого правила соответствует операции умножения в полученных таким образом уравнениях. Это дает следующую систему уравнений:

S = M + U

M = M²Икс² + 1

U = Sx + MUx²

В этой системе уравнений S, M, и U являются функциями Икс, так что можно также написать ${\displaystyle S(x)}$, ${\displaystyle M(x)}$, и ${\displaystyle U(x)}$. Система уравнений может быть решена после S, в результате чего получается одно алгебраическое уравнение:

${\displaystyle x(2x-1)S^{2}+(2x-1)S+1=0}$.

Это квадратное уравнение имеет два решения для S, одним из которых является алгебраический степенной ряд ${\displaystyle G(x)}$. Применяя методы комплексного анализа к этому уравнению, число ${\displaystyle a_{n}}$ слов длины п создано грамм можно оценить, как п становится большим. В этом случае получаем${\displaystyle a_{n}\in O(2+\epsilon )^{n}}$ но ${\displaystyle a_{n}\notin O(2-\epsilon )^{n}}$ для каждого ${\displaystyle \epsilon >0}$. Видеть (Грубер, Ли и Шаллит 2012 ) для подробного изложения.

Присущая двусмысленность

В классической теории формальных языков эту теорему можно использовать для доказательства того, что некоторые контекстно-свободные языки являются по своей сути неоднозначный. Например, Язык Голдстайна ${\displaystyle L_{G}}$ по алфавиту ${\displaystyle \{a,b\}}$ состоит из слов${\displaystyle a^{n_{1}}ba^{n_{2}}b\cdots a^{n_{p}}b}$с ${\displaystyle p\geq 1}$, ${\displaystyle n_{i}>0}$ за ${\displaystyle i\in \{1,2,\ldots ,p\}}$, и ${\displaystyle n_{j}\neq j}$ для некоторых ${\displaystyle j\in \{1,2,\ldots ,p\}}$.

Сравнительно легко показать, что язык ${\displaystyle L_{G}}$ не зависит от контекста (Berstel & Boasson, 1990 г. ). Сложнее показать, что не существует однозначной грамматики, которая порождает ${\displaystyle L_{G}}$. Это можно доказать следующим образом: если ${\displaystyle g_{k}}$ обозначает количество слов длины ${\displaystyle k}$ в ${\displaystyle L_{G}}$, то для соответствующего степенного ряда выполняется${\displaystyle G(x)=\sum _{k=0}^{\infty }g_{k}x^{k}={\frac {1-x}{1-2x}}-{\frac {1}{x}}\sum _{k\geq 1}x^{k(k+1)/2-1}}$. Используя методы из комплексный анализ, можно доказать, что эта функция не алгебраична над ${\displaystyle \mathbb {Q} (x)}$. По теореме Хомского-Шютценбергера можно заключить, что ${\displaystyle L_{G}}$ не допускает однозначной контекстно-свободной грамматики. Видеть (Berstel & Boasson, 1990 г. ) для подробного отчета.

Рекомендации

Берстель, Жан; Боассон, Люк (1990). «Контекстно-свободные языки» (PDF). В ван Леувен, Ян (ред.). Справочник по теоретической информатике, Том B: Формальные модели и семантика. Elsevier и MIT press. С. 59–102. ISBN  0-444-88074-7.

Хомский, Ноам; Шютценбергер, Марсель-Поль (1963). «Алгебраическая теория контекстно-свободных языков» (PDF). В P. Braffort and D. Hirschberg, eds., Компьютерное программирование и формальные системы (стр. 118–161). Амстердам: Северная Голландия.

Флажоле, Филипп; Седжвик, Роберт (2009). Аналитическая комбинаторика. Кембридж: Издательство Кембриджского университета. ISBN  978-0-521-89806-5.

Грубер, Германн; Ли, Джонатан; Шаллит, Джеффри (2012). «Перечисление регулярных выражений и их языков». arXiv:1204.4982 [cs.FL ].

Куич, Вернер; Саломаа, Арто (1985). Полукольца, Автоматы, Языки. Берлин: Springer-Verlag. ISBN  978-3-642-69961-0.

Панхольцер, Алоис (2005). "Основы Грёбнера и определяющий полином контекстно-свободной грамматической производящей функции". Журнал автоматов, языков и комбинаторики. 10: 79–97.