Изменения

Пусть <tex>x_{0}, x_{1},\ldots, x_{p}</tex> при <tex>0 \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>.

 Пусть <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 \ldots \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> не должен быть удален.

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

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

Можно заметить, что деревья из <tex>T</tex> и <tex>I</tex> имеют конечную высоту. <br>Теперь перейдем к доказательству теоремы.<br>Пусть Будем называть <tex>w_{1},\ldots,w_{q}s</tex> при <tex>q \in \mathbb {N}^{+}leqslant</tex> будут множеством строк, порожденных деревьями из <tex>T</tex>, и множество <tex>W</tex> {{---}} набором всех строк <tex>uv</tex>минимальным, для которых если оно не содержит в себе повторяющихся базовых <tex>uAvp</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 \ldots \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>Wk+1</tex>сегмент, так как она не влияет на суммирование. Обозначим объединение сумм в лемме каждый из которых длины как минимум <tex>\Phin+1</tex>.Также заметим, что и каждый имеет повторяющийся нетерминал, а, следовательно, <tex>\Psi_{\Sigma}(w_{i})s</tex> является некоторым вектором размера содержит <tex>mk+1</tex>, непересекающееся поддерево <tex>Wp</tex> состоит из конечного набора строк (так как количество нетерминалов конечнодеревья называются непересекающимися в данном случае, размер грамматики тоже конеченесли у них нет общих узлов, высота деревьев или если корень одного является листом другого дерева), каждое из которых, в соответствие с леммой, либо само является базовым, либо содержит базовое в себе, следовательно, в дереве <tex>Is</tex> конечна и ограничена, а значит и объединение таких содержится <tex>uvk+1</tex> для конечного числа нетерминалов конечно, и, следовательно, непересекающихся базовых <tex>Wp</tex> конечно), . Но так как число различных базовых <tex>\Psi_{\Sigma}(W)p</tex> {{---}} конечный набор векторов размера равно <tex>mk</tex>, и значит каждая такая сумма будет являться полулинейным множеством, а объединение полулинейных множеств полулинейно, в следствие чего можно сказать, что какое-то <tex>L^{\sim}(\Gamma)p</tex> полулинейнопоявляется в этом наборе дважды, и далее по первой лемме полулинеен будет язык что противоречит <tex>L(\Gamma)leqslant</tex>-минимальности.}}

Доказывать лемму будем в две стадии по индукции{{Теорема|about=Парика, англ.''Parikh's theorem''|statement=Если язык <tex>L \subset \Sigma^{*}</tex> является [[Контекстно-свободные грамматики, вывод, лево- и правосторонний вывод, дерево разбора|контекстно-свободным]], то множество <tex>\Psi_{\Sigma}(L)</tex> является полулинейным.|proof=

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

В этой части доказательства будет рассмотрен случай Зададим <tex>m M = (m_{1},\ldots,m_{m}) \in \Phi \rightarrow m \in \Psi_{\Sigma}(L^{s \sim}(\Gamma)mid s</tex>. '''База индукции''':Пусть <tex>m=\Psi_{\Sigma}(w_{i})</tex> для некоторого <tex>ileqslant</tex>-минимально, <tex>w_{i} \in L^{\sim}root(\Gammas)</tex>, и таким образом <tex>\Psi_{\Sigma}(w_{i}) \in \Psi_{\Sigma}(L^{\sim}(\Gamma))</tex>.  Предположим, что верно для некоторого <tex>m'</tex>, <tex>m' \in \Psi_{\Sigma}(L^{\sim}(\Gamma))</tex>. '''Шаг индукции''':Теперь пусть <tex>m = m'+\Psi_{\Sigma}(u)</tex> для некоторого <tex>u \in W</tex>. Существует дерево <tex>t \in T'</tex>, порождающее <tex>w</tex>, такоеS, что <tex>\Psi_{\Sigma}res(ws) = m'</tex>.Кроме того, существует дерево <tex>t' \in I</tex>, порождающее <tex>u_{0}Av_{0}</tex>, такое, что <tex>u = u_{0}v_{0}</tex>. Построим дерево разбора, заменив некоторый узел <tex>p</tex>, помеченный <tex>A</tex> в <tex>t</tex>, на дерево <tex>t'</tex>, подвесив к листу <tex>A</tex> дерева <tex>t'</tex> то, что раньше следовало за узлом <tex>p</tex> в дереве разбора. В итоге получившееся дерево принадлежит <tex>T'</tex>, и его результат, <tex>z</tex>, удовлетворяет <tex>\Psi_{\Sigma}(z) = \Psi_{\Sigma}(w)+\Psi_{\Sigma}(u) = m</tex>. Из-за того, что <tex>z</tex> является порождением дерева, принадлежащего <tex>T'</tex>, значит, что оно принадлежит языку <tex>L^{\sim*}(\Gamma)</tex>. И так как получившийся результат совпадает с суммой, представленной в начале шага индукции, предположение индукции верно, и <tex>\Phi \subset L^{\sim}(\Gamma)</tex>. <tex>\Longleftarrow</tex> <tex>L^{\sim}(\Gamma) \subset \Phi</tex>. В этой части будет доказано, что если <tex>t \in T'</tex>, и результатом <tex>w</tex>, то <tex>\Psi_{\Sigma}(w) \in \Phi</tex>. '''База индукции''':Если <tex>t \in T</tex>, то <tex>w = w_{i}</tex> для некоторого <tex>i</tex>, и значит <tex>\Psi_{\Sigma}(w) \in \Phi</tex>. Предположим, что утверждение сохраняется для всех деревьев в <tex>T'</tex>, меньших <tex>t</tex>.  '''Шаг индукции''':Пусть <tex>p_{1}, \ldots, p_{k}</tex> будут узлами на некотором пути дерева, и пусть индекс каждого узла будет указывать на его относительную позицию на этом пути. Более того, пусть все узлы будут помечены одним и тем же нетерминалом <tex>A</tex>, чтобы все правильные поддеревья, у которых корнем является узел <tex>p_{1}</tex>, удовлетворяли условию 2 в определении <tex>T</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> так же не полулинейно.

*[https://www8Dexter C.cs.umu.se/kurser/TDBC92/VT06/final/3.pdf Håkan Lindqvist Kozen {{---}} Parikh’s theorem]Automata and Computability