Теорема Париха

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

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

Пусть будет алфавитом . Вектор Париха слова определяется как функция , заданная формулой [1] , где обозначает количество вхождений символа в слово . Σ = { а 1 , а 2 , … , а к } {\displaystyle \Сигма =\{a_{1},a_{2},\ldots ,a_{k}\}} п : Σ ∗ → Н к {\textstyle p:\Sigma ^{*}\to \mathbb {N} ^{k}} п ( ж ) = ( | ж | а 1 , | ж | а 2 , … , | ж | а к ) {\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}} ты 0 + Н ты 1 + ⋯ + Н ты м = { ты 0 + т 1 ты 1 + ⋯ + т м ты м ∣ т 1 , … , т м ∈ Н } {\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} \}} ты 0 , … , ты м {\textstyle u_{0},\ldots ,u_{m}} Н к {\displaystyle \mathbb {N} ^{k}}

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

Если — любое полулинейное множество, то существует регулярный язык (который a fortiori является контекстно-свободным), векторы Париха которого равны . С {\displaystyle S} С {\displaystyle S}

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

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

Доказательство

Вторую часть легко доказать.

Доказательство

Для заданного полулинейного множества построить регулярный язык, множество векторов Париха которого равно . С {\displaystyle S} С {\displaystyle S}

С {\displaystyle S} является объединением 0 или более линейных множеств. Поскольку пустой язык является регулярным, а объединение регулярных языков является регулярным, достаточно доказать, что любое линейное множество является множеством векторов Париха регулярного языка.

Пусть , тогда это множество векторов Париха , где каждый имеет вектор Париха . С = { ты 0 + т 1 ты 1 + ⋯ + т м ты м ∣ т 1 , … , т м ∈ Н } {\displaystyle S=\{u_{0}+t_{1}u_{1}+\dots +t_{m}u_{m}\mid t_{1},\ldots ,t_{m}\in \mathbb {N} \}} { з 0 } ⋅ ( ∪ я = 1 м { з я } ) ∗ {\displaystyle \{z_{0}\}\cdot (\cup _{i=1}^{m}\{z_{i}\})^{*}} з я {\displaystyle z_{i}} ты я {\displaystyle u_{i}}

Первая часть менее проста. Следующее доказательство приписывается Голдстайну. [5]

Сначала нам нужно небольшое усиление леммы о накачке для контекстно-свободных языков :

Лемма  —  Если порождается грамматикой нормальной формы Хомского, то , такой что Л {\displaystyle L} ∃ Н ≥ 1 {\displaystyle \exists N\geq 1}

Для любого и для любого с , существует способ разбиения на сегменты и нетерминальный символ , такой что к ≥ 1 {\displaystyle k\geq 1} ж ∈ Л {\displaystyle w\in L} | ж | ≥ Н к {\displaystyle |w|\geq N^{k}} ж {\displaystyle w} ты х 1 ⋯ х к з у к ⋯ у 1 в {\displaystyle ux_{1}\cdots x_{k}zy_{k}\cdots y_{1}v} А {\displaystyle А}

| х я у я | ≥ 1 {\displaystyle |x_{i}y_{i}|\geq 1} для всех , и я {\displaystyle я} | х 1 ⋯ х к з у к ⋯ у 1 | ≤ Н к {\displaystyle |x_{1}\cdots x_{k}zy_{k}\cdots y_{1}|\leq N^{k}}

С ⇒ ∗ ты А в А ⇒ ∗ з ∀ я , А ⇒ ∗ х я А у я {\displaystyle S\Rightarrow ^{*}uAv\quad A\Rightarrow ^{*}z\quad \forall i,A\Rightarrow ^{*}x_{i}Ay_{i}}

Доказательство по сути такое же, как и в стандартной лемме о накачке: используем принцип ящика для поиска копий некоторого нетерминального символа в самом длинном пути в самом коротком дереве вывода. к {\displaystyle к} А {\displaystyle А}

Теперь докажем первую часть теоремы Париха, используя приведенную выше лемму.

Доказательство

Сначала построим грамматику нормальной формы Хомского для . Л {\displaystyle L}

Для каждого конечного непустого подмножества нетерминалов , определим как множество предложений в , такое, что существует вывод, который использует каждый нетерминал в , не больше и не меньше. Ясно, что , поэтому достаточно доказать, что каждое является полулинейным множеством. У {\displaystyle U} Л У {\displaystyle L_{U}} Л {\displaystyle L} У {\displaystyle U} Л = ∪ У Л У {\displaystyle L=\чашка _{U}L_{U}} п ( Л У ) {\displaystyle p(L_{U})}

Теперь зафиксируем некоторое , и пусть . Построим два конечных множества , таких, что , что, очевидно, полулинейно. У {\displaystyle U} к = | У | {\displaystyle k=|U|} Ф , Г {\displaystyle F,G} п ( Л У ) = п ( Ф ⋅ Г ∗ ) {\displaystyle p(L_{U})=p(F\cdot G^{*})}

Для ясности записи запишем так, чтобы это означало «существует вывод, использующий не более (но возможно и меньше) нетерминалов в » . При этом мы определяем следующим образом: ⇒ У ∗ {\displaystyle \Rightarrow _{U}^{*}} У {\displaystyle U} Ф , Г {\displaystyle F,G}

Ф = { ж ∈ Л У : | ж | < Н к } {\displaystyle F=\{w\in L_{U}:|w|<N^{k}\}} Г = { х у : 1 ≤ | х у | ≤ Н к  и существует  А ∈ У  такой что  А ⇒ У ∗ х А у } {\displaystyle G=\{xy:1\leq |xy|\leq N^{k}{\text{ и существует }}A\in U{\text{ такой, что }}A\Rightarrow _{U}^{*}xAy\}}

Для доказательства проведем индукцию по длине . п ( Л У ) ⊂ п ( Ф ⋅ Г ∗ ) {\displaystyle p(L_{U})\subset p(F\cdot G^{*})} ж ∈ Л У {\displaystyle w\in L_{U}}

Если , то , так что . В противном случае, по усиленной лемме о накачке, существует вывод, использующий именно элементы , и имеет вид | ж | < Н к {\displaystyle |w|<N^{k}} ж ∈ Ф {\displaystyle w\in F} п ( ж ) ∈ п ( Ф ⋅ Г ∗ ) {\displaystyle p(w)\in p(F\cdot G^{*})} ж {\displaystyle w} У {\displaystyle U}

С ⇒ ∗ г 0 ты А в ⇒ ∗ г 1 ты х 1 А у 1 в ⇒ ∗ г 2 ⋯ ⇒ ∗ г к ты х 1 ⋯ х к А у к ⋯ у 1 в ⇒ ∗ г к + 1 ты х 1 ⋯ х к з у к ⋯ у 1 в {\displaystyle S{\underset {d_{0}}{\stackrel {*}{\Rightarrow }}}uAv{\underset {d_{1}}{\stackrel {*}{\Rightarrow }}}ux_{1}Ay_{1}v{\underset {d_{2}}{\stackrel {*}{\Rightarrow }}}\cdots {\underset {d_{k}}{\stackrel {*}{\Rightarrow }}}ux_{1}\cdots x_{k}Ay_{k}\cdots y_{1}v{\underset {d_{k+1}}{\stackrel {*}{\Rightarrow }}}ux_{1}\cdots x_{k}zy_{k}\cdots y_{1}v}

где , , и . А ∈ У {\displaystyle A\in U} 1 ≤ | х я у я | {\displaystyle 1\leq |x_{i}y_{i}|} | х 1 ⋯ х к з у к ⋯ у 1 | ≤ Н к {\displaystyle |x_{1}\cdots x_{k}zy_{k}\cdots y_{1}|\leq N^{k}}
Так как в , но в середине есть подвыводы , мы можем удалить один подвывод и получить более короткий , который все еще находится в , с к − 1 {\displaystyle к-1} У ∖ { А } {\displaystyle U\setminus \{A\}} к {\displaystyle к} г 1 , . . . , г к {\displaystyle d_{1},...,d_{k}} г я {\displaystyle d_{i}} ж ′ {\displaystyle w'} Л У {\displaystyle L_{U}}

п ( ж ) = п ( ты з в ) + п ( х 1 у 1 ) + ⋯ + п ( х к у к ) = п ( ж ′ ) + п ( х я у я ) {\displaystyle p(w)=p(uzv)+p(x_{1}y_{1})+\cdots +p(x_{k}y_{k})=p(w')+p(x_{i}y_{i})}

По индукции, , и по построению, , поэтому . п ( ж ′ ) ∈ п ( Ф ⋅ Г ∗ ) {\displaystyle p(w')\in p(F\cdot G^{*})} х я у я ∈ Г {\displaystyle x_{i}y_{i}\in G} p ( w ) ∈ p ( F ⋅ G ∗ ) {\displaystyle p(w)\in p(F\cdot G^{*})}

Чтобы доказать , рассмотрим элемент . Нам нужно показать, что . Мы выводим из минимального числа факторов, которое необходимо для идентификации как элемента . p ( L U ) ⊃ p ( F ⋅ G ∗ ) {\displaystyle p(L_{U})\supset p(F\cdot G^{*})} w ∈ F ⋅ G ∗ {\displaystyle w\in F\cdot G^{*}} p ( w ) ∈ p ( L U ) {\displaystyle p(w)\in p(L_{U})} G {\displaystyle G} w {\displaystyle w} F ⋅ G ∗ {\displaystyle F\cdot G^{*}}

Если фактор из не нужен, то . G {\displaystyle G} w ∈ F ⊂ L U {\displaystyle w\in F\subset L_{U}}
В противном случае для некоторых и , где требуется меньше факторов из , чем . w = w ′ x y {\displaystyle w=w'xy} w ′ ∈ F ⋅ G ∗ {\displaystyle w'\in F\cdot G^{*}} x y ∈ G {\displaystyle xy\in G} w ′ {\displaystyle w'} G {\displaystyle G} w {\displaystyle w}
По индукции, для некоторого . По построению , существует такое, что . p ( w ′ ) = p ( w ″ ) {\displaystyle p(w')=p(w'')} w ″ ∈ L U {\displaystyle w''\in L_{U}} G {\displaystyle G} A ∈ U {\displaystyle A\in U} A ⇒ U ∗ x A y {\displaystyle A\Rightarrow _{U}^{*}xAy}
По построению , символ появляется в выводе с использованием точно всех . Затем мы можем интерполировать в этот вывод, чтобы получить некоторые такие, что L U {\displaystyle L_{U}} A {\displaystyle A} w ″ {\displaystyle w''} U {\displaystyle U} A ⇒ U ∗ x A y {\displaystyle A\Rightarrow _{U}^{*}xAy} w ‴ ∈ L U {\displaystyle w'''\in L_{U}}

p ( w ‴ ) = p ( w ″ ) + p ( x y ) = p ( w ′ ) + p ( x y ) = p ( w ) {\displaystyle p(w''')=p(w'')+p(xy)=p(w')+p(xy)=p(w)}

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

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

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

Гинзбург-Спениер  —  Ограниченный язык является контекстно-свободным тогда и только тогда, когда является стратифицированным полулинейным множеством. L {\displaystyle L} { ( n 1 , … , n k ) ∣ w 1 n 1 … w k n k ∈ 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) . Университет Умео.
  3. ^ Парих, Рохит (1961). «Устройства генерации языка». Ежеквартальный отчет о ходе работ, Исследовательская лаборатория электроники, Массачусетский технологический институт .
  4. ^ Парих, Рохит (1966). «О контекстно-свободных языках». Журнал Ассоциации вычислительной техники . 13 (4): 570–581. doi : 10.1145/321356.321364 . S2CID  12263468.
  5. ^ Голдстайн, Дж. (1977-01-01). «Упрощенное доказательство теоремы Париха». Дискретная математика . 19 (3): 235–239. doi :10.1016/0012-365X(77)90103-0. ISSN  0012-365X.
  6. ^ Гинзбург, Сеймур; Спаниер, Эдвин Х. (1966). «Формулы Пресбургера и языки». Pacific Journal of Mathematics . 16 (2): 285–296. doi : 10.2140/pjm.1966.16.285 .
Retrieved from "https://en.wikipedia.org/w/index.php?title=Parikh%27s_theorem&oldid=1249874253"