Изменения

==Используемые определенияЛинейные множества==В этом разделе предполагается, что зафиксирован некоторый [[Отношение_порядка|линейный порядок ]] на алфавите <tex>\Sigma</tex>. Пусть <tex>\Sigma = \{a_{1},...\ldots,a_{m}\}</tex>.

Через <tex>\Psi_{\Sigma}</tex> будем обозначать функцию <tex>\Psi_{\Sigma} : \Sigma^{*} \rightarrow \mathbb {N}^{m}</tex>, определённую следующим образом: <tex>\Psi_{\Sigma}(w) = \langle |w|_{a_{1}} ,...\ldots, |w|_{a_{m}} \rangle</tex>, где <tex>|w|_{a_{i}}</tex> {{---}} количество число появлений символа <tex>a_{i}</tex> в слове <tex>w</tex>. Аналогично, каждому языку <tex>L \subset \Sigma^{*}</tex> ставится в соответствие множество <tex>\Psi_{\Sigma}(L) \subset \mathbb {N}^{m}</tex>, определённое так: <tex>\Psi_{\Sigma}(L) = \{\Psi_{\Sigma}(w) \mid w \in L\}</tex>. Функция называется '''отображением Парика''' (англ. ''Parikh's mapping'') соответственно слова и языка.

Пусть <tex>x_{0}, x_{1},...\ldots, x_{p}</tex> при <tex>0 \leq leqslant p < \infty</tex> {{---}} вектора в множестве <tex>\mathbb {N}^{m}</tex>. Множество <tex>L = \{b + \sum_{i=1}^{p}k_{i} x_{i} \mid b \in B, k \geq geqslant 0, k_{1},...\ldots,k_{p} \in \mathbb {N}\} = x_{0} + \{x_{1},...\ldots, x_{p}\}^{*}</tex> называется '''линейным''' (англ. ''linear'') подмножеством множества <tex>\mathbb {N}^{m}</tex>.

*Полулинейные множества по теореме Гинзбурга-Спаниера (англ. ''Ginsburg and Spanier theorem'') {{---}} те, которые определяемы в арифметика арифметике Пресбургера (англ. ''Presburger arithmetic'')<ref>[https://en.wikipedia.org/wiki/Presburger_arithmetic Wikipedia {{---}} Presburger arithmetic]</ref>.

 Пусть <tex>\Gamma =\langle \Sigma, N, S, P\rangle</tex> {{Теорема---}} контекстно-свободная грамматика. |about=ПарикаДалее маленькими латинскими буквами <tex>s, англt, \ldots</tex> будем обозначать деревья разбора. ''Parikh'Для деревьев результатом (<tex>res(s)</tex>) будем называть строку из нетерминалов и терминалов, записанных в листьях, упорядоченную слева направо, глубина дерева (<tex>dep(s)</tex>) {{---}} длина наибольшего пути от листов до корня дерева, будем писать <tex>N(s)</tex>, чтобы обозначить множество нетерминалов в дереве, а <tex>root(s theorem'')</tex> {{---}} корень дерева. Обозначим за <tex>p</tex> деревья такого вида:# оно содержит хотя бы два узла.|statement# <tex>res(p) =Если язык u * root(p) * v</tex>, где <tex>L u, v \subset in \Sigma^{*}</tex> является [[Контекстно-свободные грамматики, выводто есть все листья помечены терминалами, за исключением одного, который совпадает с корнем дерева. Будем обозначать <tex>s \# t</tex> если <tex>t</tex> может быть получен из <tex>s</tex> вставкой дерева <tex>p</tex> с нетерминалом <tex>A</tex> в качестве корня на место нетерминала <tex>A</tex> в дереве <tex>s</tex>, то есть, можно увеличить <tex>s</tex> с помощью некоторого дерева <tex>p</tex> так, чтобы получить <tex>t</tex>. В <tex>s</tex> строго меньше узлов, лево- и правосторонний выводчем в <tex>t</tex>. Пусть <tex>p</tex> называется ''базовым'', дерево разбора|контекстноесли оно <tex>\#</tex>-свободным]]минимально среди всех <tex>p</tex>, то множество есть не содержит в себе другое <tex>p</tex>, которое можно вырезать. Или, иначе, <tex>p</tex> является базовым, если в <tex>s \Psi_# t</tex> <tex>s</tex> является только тривиальным деревом с одним узлом (который же является и корнем). {{\Sigma}Лемма|statement=Если <tex>p</tex> является базовым, то <tex>dep(Lp)\leqslant 2n</tex>, где <tex>n</tex> является полулинейнымколичество нетерминалов в N.

Пусть Обозначим за <tex>\Gamma =\langle \Sigma, N, S, P\ranglegamma</tex> путь от листа с нетерминалом <tex>root(p)</tex> {{---}} контекстно-свободная грамматикадо корня. Вместо того, чтобы рассматривать Пусть <tex>L(\Gamma)gamma</tex>не может быть длиннее, рассмотрим язык чем <tex>L^{\sim}(\Gamma)n</tex>, содержащий только строкипотому что если бы был, то он содержал бы повторяющийся нетерминал, и, порожденные выводамитем самым, содержал бы в которых встречаются все нетерминалы грамматики.Так как теорема Парика говорит о томсебе другое дерево <tex>p'</tex>, что противоречит тому, что для <tex>L(\Gamma)p</tex> множество базовое.Для других же листов путь должен не превышать <tex>\Psi_{\Sigma}(L)n+1</tex> полулинейнопо тем же причинам. Таким образом, то же самое должно сохраняться длина любого пути не больше <tex>2n</tex>.}}Из леммы и из конечности нетерминалов и для продукций в грамматике <tex>L^{\sim}(\Gamma)</tex>следует, что количество таких базовых деревьев <tex>p</tex> конечно.

Если множество Любое дерево разбора <tex>t</tex> с <tex>res(t) \Psi_{in \Sigma}(L^{\sim*}(</tex> либо <tex>\Gamma))#</tex> полулинейно для всех контекстно-свободных языковминимально, тогда множество либо содержит в себе базовое <tex>\Psi_{\Sigma}(L(\Gamma))p</tex> также полулинейно.

Построим грамматики Пусть <tex>t</tex> не <tex>\Gamma_{1},...\Gamma_{k}#</tex> для какого-то минимально, тогда оно по определению содержит дерево <tex>k \in \mathbb {N}^{+}p</tex> путем удаления из грамматики . Пусть <tex>\Gammap</tex> нетерминалов. Тогда будет <tex>L(\Gamma) = L^{\sim}(\Gamma_{1}) \cup ... \cup L^{\sim}(\Gamma_{k})#</tex>. Так как для каждого из языков -минимально среди всех <tex>L^{\sim}(\Gamma_{p})</tex> множество , содержащихся в <tex>\Psi_{\Sigma}t</tex> полулинейно, тотогда <tex>p</tex> является базовым, по свойствам полулинейных множествтак как если нет, для то оно содержит в себе другое <tex>L(\Gamma)p</tex> , что противоречит <tex>\Psi_{\Sigma}#</tex> также полулинейно-минимальности.

Стоит заметитьПусть <tex>s \leqslant t</tex> если <tex>t</tex> может быть получен из <tex>s</tex> конечной последовательностью вставок базовых <tex>p</tex>, для которых <tex>N(p) \subset N(s)</tex>. Другими словами, нам позволено выбирать любой нетерминал A в дереве и вставлять на это место базовое <tex>p</tex> с корнем А в том случае, если <tex>p</tex> содержит только те нетерминалы, что число таких языков есть в лемме ограничено числом нетерминалов в грамматике: <tex>k = 2^{|N|} - 1s</tex>. Вычитание происходит из-за тогоЕсли с помощью таких операций можно получить <tex>t</tex>, что начальный нетерминал то <tex>Ss \leqslant t</tex> не должен быть удален.

Если строка <brtex>Теперь определим три множества деревьев разбора. \alpha = N^{*} \cup \Sigma^{Определение|definition = Пусть *}</tex>T, то за </tex> \Psi_{{---\Sigma}} множество всех терминальных деревьев разбора с корнем (\alpha)</tex>Sбудем обозначать <tex>\Psi_{\Sigma}(x)</tex>, которые удовлетворяют двум условиям:1. Каждый нетерминал где <tex>Nx</tex> встречается в в дереве.2. Каждый нетерминал получен из <tex>N\alpha</tex> встречается не более чем удалением всех нетерминалов. За <tex>k = |N|\Psi_{\Sigma}(t)</tex> раз в дереве.}}Деревья из этого множества соотносятся с деревьями разбора языка будем обозначать <tex>L^\Psi_{\simSigma}(\Gammares(t))</tex>, так как при выводе каждого слова из этого языка также используются все нетерминалы грамматики.

В отличие от предыдущего определения, для следующего множества число {{Лемма|statement=Множество <tex>k\{\Psi_{\Sigma}(t) \mid s \leqslant t\}</tex> для любого нетерминала не ограниченолинейно.|proof=<tex>\{\Psi_{Определение\Sigma}(t) |definition s \leqslant t\} = Пусть \Psi_{\Sigma}(s) + \langle\{\Psi_{\Sigma}(p) \mid </tex> <tex>p</tex> является базовым, и его <tex>T'N(p) \subset N(s)</tex> {{---}} множество всех терминальных деревьев разбора с корнем <tex>S\}\rangle</tex>, которые удовлетворяют первому условию из предыдущего определения.

Последнее множество относится к тем правилам грамматики, которые делают строку больше в процессе вывода, то есть Будем называть <tex>A \Rightarrow uAvs</tex>, где <tex>u, v \in \Sigma</tex>. Эти деревья могут быть использованы, чтобы увеличить дерево разбора в множестве <tex>T'leqslant</tex> замещением нетерминала <tex>A</tex> в некотором дереве <tex>t'</tex> на дерево из множества <tex>I</tex>, определение которого написано ниже.{{Определение|definition = Пусть <tex>I</tex> {{---}} множество всех деревьев разбора с корнем <tex>A \in N</tex>, содержащих только один нетерминальный лист, который также помечен как <tex>A</tex>.}}В дополнениеминимальным, деревья разбора множества <tex>I</tex> должны удовлетворять условию 2 если оно не содержит в определении себе повторяющихся базовых <tex>Tp</tex>. Еще можно заметить, что деревья из <tex>T</tex> и <tex>I</tex> имеют конечную высоту. <br>Теперь перейдем к доказательству теоремы.<br>Пусть <tex>w_{1},...,w_{q}</tex> при <tex>q \in \mathbb {N}^{+}</tex> будут множеством строк, порожденных деревьями из <tex>T</tex>, и множество <tex>W</tex> {{---}} набором всех строк <tex>uv</tex>, для которых <tex>uAv</tex> будет результатом, полученным с помощью дерева разбора из <tex>I</tex> с вершиной <tex>A \in N</tex>. Элементы множества <tex>W</tex> представляют возможные поддеревья, которые могут быть использованы для того, чтобы увеличить длину пути в некотором дереве.

Для языка Если <tex>s</tex> <tex>L^{\sim}(\Gamma)leqslant</tex> выполняется равенство -минимально, то его <tex>\Psi_{\Sigma}dep(L^{s) \sim}leqslant (\Gammak+1)) = (\Psi_{\Sigma}(w_{n+1})+\Psi_</tex>, где <tex>n</tex> {\Sigma}(W)^{*---}) \cup ... \cup (\Psi_{\Sigma}(w_размер <tex>N</tex>, а <tex>k</tex> {q})+\Psi_{\Sigma---}(W)^{*}) число различных базовых <tex>p</tex>в дереве.

Можем заметитьЕсли путь длиннее, пустая строка чем <tex>dep(s) \leqslant (k+1)(n+1)</tex>, то тогда он может быть удалена поделен на <tex>k+1</tex> сегмент, каждый из множества которых длины как минимум <tex>Wn+1</tex>, и каждый имеет повторяющийся нетерминал, а, следовательно, <tex>s</tex> содержит <tex>k+1</tex> непересекающееся поддерево <tex>p</tex> (деревья называются непересекающимися в данном случае, если у них нет общих узлов, или если корень одного является листом другого дерева), каждое из которых, в соответствие с леммой, либо само является базовым, либо содержит базовое в себе, следовательно, в дереве <tex>s</tex> содержится <tex>k+1</tex> непересекающихся базовых <tex>p</tex>. Но так как она не влияет на суммирование. Обозначим объединение сумм в лемме как число различных базовых <tex>p</tex> равно <tex>\Phik</tex>. Доказывать лемму будем в две стадии по индукции. , какое-то <tex>\Longrightarrowp</tex> появляется в этом наборе дважды, что противоречит <tex>\Phi \subset L^{\sim}(\Gamma)leqslant</tex>-минимальности.}}

<tex>\Longleftarrow</tex> <tex>L^{\sim}(\Gamma) \subset \Phi</tex>Воспользуемся ранее полученными результатами в доказательстве.

Зададим <tex>M = \{s \mid s</tex> <tex>\leqslant</tex>-минимально, <tex>root(s) = S, res(s) \in \Sigma^{*}\}</tex>.

Теорема Парика связывает два понятия: функцию <tex>\Psi_{\Sigma}</tex> контекстно-свободного языка и полулинейное множество. Например, для языка <tex>\{a(a^{2}b)^{m}(b^{3}c^{2})^{n} \mid m,n \geq geqslant 0\})</tex> функция <tex>\Psi_{\Sigma} = (1,0,0)+\{(2,1,0), (0,3,2)\}^{*}</tex>.<br>Эта теорема, так же, как и лемма о накачке и лемма Огдена, не является достаточной: язык <tex>\{0^{n}1^{n}2^{n} \mid n \geq geqslant 0\}</tex> [[Лемма о разрастании для КС-грамматик#Пример доказательства неконтекстно-свободности языка с использованием леммы|не является контекстно-свободным]], однако его множество <tex>\Psi_{\Sigma} = \{(n, n, n) \mid n \geq geqslant 0\}</tex> является полулинейным: <tex>\Psi_{\Sigma} = \{(n, n, n) \mid n \geq geqslant 0\} = (0, 0, 0) + \{(1, 1, 1)\}^{*}</tex>.

Язык <tex>\{a^{m}b^{n} \mid m > n</tex> или <tex>m</tex> {{---}} простое и <tex>m \leq leqslant n\}</tex> не является контекстно свободным, так как множество, порождаемое функцией <tex>\Psi_{\Sigma}</tex>, не является полулинейным: множество таких пар <tex>\{(m, n) \mid m > n\} = (1, 0) + \{(1, 0), (1, 1)\}</tex> {{---}} линейно, множество таких пар <tex>\{(m, n) \mid m \leq leqslant n\} = (0, 0) + \{(1, 1), (0, 1)\}</tex> {{---}} линейно, при этом множество простых чисел не является полулинейным, и, как следствие, множество <tex>\{m</tex> {{---}} простое и <tex>m \leq leqslant n\}</tex> не является полулинейным, <tex>\Psi_{\Sigma}</tex> так же не полулинейно.

== Источники информации==

*Dexter C. Kozen {{---}} Automata and Computability*[httpshttp://www8.cs.umustackexchange.secom/kurserquestions/TDBC92265/VT06/final/3.pdf Håkan Lindqvist how-to-prove-that-a-language-is-not-context-free Stack Exchange {{---}} Parikh’s theoremHow to prove that a language is not context-free?]