Теорема Париха - Parikhs theorem

Теорема Париха в теоретическая информатика говорит, что если смотреть только на количество вхождений каждого символ терминала в контекстно-свободный язык безотносительно к их порядку, то язык неотличим от обычный язык.^[1] Это полезно для принятия решения о том, что строки с заданным количеством терминалов не принимаются контекстно-независимой грамматикой.^[2] Впервые это было доказано Рохит Парих в 1961 г.^[3] и переиздан в 1966 году.^[4]

Определения и формальное заявление

Позволять ${\displaystyle \Sigma =\{a_{1},a_{2},\ldots ,a_{k}\}}$ быть алфавит. В Вектор Париха слова определяется как функция ${\textstyle p:\Sigma ^{*}\to \mathbb {N} ^{k}}$, данный^[1]

$${\displaystyle p(w)=(|w|_{a_{1}},|w|_{a_{2}},\ldots ,|w|_{a_{k}})}$$

куда ${\displaystyle |w|_{a_{i}}}$ обозначает количество вхождений буквы ${\displaystyle a_{i}}$ в слове ${\displaystyle w}$.

Подмножество ${\displaystyle \mathbb {N} ^{k}}$ как говорят линейный если это имеет форму

$${\displaystyle u_{0}+\mathbb {N} u_{1}+\dots +\mathbb {N} u_{m}=\{u_{0}+t_{1}u_{1}+\dots +t_{m}u_{m}\mid t_{1},\ldots ,t_{m}\in \mathbb {N} \}}$$

для некоторых векторов ${\textstyle u_{0},\ldots ,u_{m}}$Подмножество ${\displaystyle \mathbb {N} ^{k}}$ как говорят полулинейный если это объединение конечного числа линейных подмножеств.

Положение 1: Позволять ${\displaystyle L}$ быть контекстно-свободным языком. ${\displaystyle P(L)}$ - множество векторов Париха слов в ${\displaystyle L}$, то есть, ${\textstyle P(L)=\{p(w)\mid w\in L\}}$. потом ${\displaystyle P(L)}$ - полулинейное множество.

Говорят, что два языка коммутативно эквивалентный если они имеют одинаковый набор векторов Париха.

Положение 2: Если ${\displaystyle S}$ - любое полулинейное множество, язык слов, векторы Париха которых лежат в ${\displaystyle S}$ коммутативно эквивалентен некоторому регулярному языку. Таким образом, любой контекстно-свободный язык коммутативно эквивалентен некоторому регулярному языку.

Эти два эквивалентных утверждения можно резюмировать, сказав, что изображение под ${\displaystyle p}$ контекстно-свободных языков и регулярных языков одно и то же, и оно равно множеству полулинейных множеств.

Усиление для ограниченных языков

Язык ${\displaystyle L}$ является ограниченный если ${\displaystyle L\subset w_{1}^{*}\ldots w_{k}^{*}}$ для некоторых фиксированных слов ${\displaystyle w_{1},\ldots ,w_{k}}$Гинзбург и Спаниер ^[5]дал необходимое и достаточное условие, подобное теореме Париха, для ограниченных языков.

Назовите линейный набор стратифицированный, если в его определении для каждого ${\displaystyle i\geq 1}$ вектор ${\displaystyle u_{i}}$ имеет свойство иметь не более двух ненулевых координат, и для каждой ${\displaystyle i,j\geq 1}$ если каждый из векторов ${\displaystyle u_{i},u_{j}}$ имеет две ненулевые координаты, ${\displaystyle i_{1}<i_{2}}$ и ${\displaystyle j_{1}<j_{2}}$соответственно, то их порядок нет ${\displaystyle i_{1}<j_{1}<i_{2}<j_{2}}$. Полулинейное множество стратифицировано, если оно представляет собой объединение конечного числа стратифицированных линейных подмножеств.

Теорема Гинзбурга-Спаниера утверждает, что ограниченный язык ${\displaystyle L}$ контекстно-свободно тогда и только тогда, когда ${\displaystyle \{(n_{1},\ldots ,n_{k})\mid w_{1}^{n_{1}}\ldots w_{k}^{n_{k}}\in L\}}$ - стратифицированное полулинейное множество.

Значимость

Теорема имеет несколько интерпретаций. Это показывает, что контекстно-свободный язык над одноэлементным алфавитом должен быть обычный язык и что некоторые контекстно-свободные языки могут иметь только неоднозначные грамматики^{[требуется дальнейшее объяснение ]}. Такие языки называются по своей сути неоднозначные языки. Из формальная грамматика перспективы, это означает, что некоторые неоднозначные контекстно-свободные грамматики не могут быть преобразованы в эквивалентные однозначные контекстно-свободные грамматики.

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

1. Козен, Декстер (1997). Автоматы и вычислимость. Нью-Йорк: Springer-Verlag. ISBN  3-540-78105-6.
2. Хокан Линдквист. «Теорема Париха» (PDF). Umeå Universitet.
3. Парих, Рохит (1961). «Устройства для генерации языков». Ежеквартальный отчет, Исследовательская лаборатория электроники, Массачусетский технологический институт.
4. Парих, Рохит (1966). «На контекстно-свободных языках». Журнал Ассоциация вычислительной техники. 13 (4).
5. Гинзбург, Сеймур; Спаниер, Эдвин Х. (1966). «Формулы Пресбургера и языки». Тихоокеанский математический журнал. 16 (2): 285–296.