Теорема Париха - Википедия - 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 | w | _ {a_ {i}}}$ обозначает количество вхождений буквы ${ displaystyle a_ {i}}$ в слове ${ displaystyle w}$.

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

для некоторых векторов ${ 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 подмножество 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}$ и ${ displaystyle j_ {1}$соответственно, то их порядок нет ${ Displaystyle i_ {1}$. Полулинейное множество стратифицировано, если оно представляет собой объединение конечного числа стратифицированных линейных подмножеств.

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

Значимость

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

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