Изменения

Если множество <tex>\Psi_{\Sigma}(L^{\sim}p</tex> является базовым, то <tex>dep(p) \Gamma))leqslant 2n</tex> полулинейно для всех контекстно-свободных языков, тогда множество где <tex>\Psi_{\Sigma}(L(\Gamma))n</tex> также полулинейноколичество нетерминалов в N.

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

Стоит заметить, что число таких языков в лемме ограничено числом нетерминалов в грамматике: {{Лемма|statement=Любое дерево разбора <tex>t</tex> с <tex>k = 2res(t) \in \Sigma^{|N|*} </tex> либо <tex>\#</tex>- 1минимально, либо содержит в себе базовое <tex>p</tex>. Вычитание происходит из|proof=Пусть <tex>t</tex> не <tex>\#</tex>-за тогоминимально, тогда оно по определению содержит дерево <tex>p</tex>. Пусть <tex>p</tex> будет <tex>\#</tex>-минимально среди всех <tex>p</tex>, содержащихся в <tex>t</tex>, тогда <tex>p</tex> является базовым, так как если нет, то оно содержит в себе другое <tex>p</tex>, что начальный нетерминал противоречит <tex>S\#</tex> не должен быть удален-минимальности.}}

Пусть <tex>s \leqslant t<br/tex>Теперь же сосредоточимся на языке если <tex>L^{\sim}(\Gamma)t</tex>. Определим три множества деревьев разбора. {{Определение|definition = Пусть может быть получен из <tex>Ts</tex> {{---}} множество всех терминальных деревьев разбора с корнем конечной последовательностью вставок базовых <tex>Sp</tex>, которые удовлетворяют двум условиям:1. Каждый нетерминал для которых <tex>N(p) \subset N(s)</tex> встречается в . Другими словами, нам позволено выбирать любой нетерминал A в дереве.2. Каждый нетерминал и вставлять на это место базовое <tex>Np</tex> встречается не более чем с корнем А в том случае, если <tex>k = |N|p</tex> раз содержит только те нетерминалы, что есть в любом пути.}}Деревья из этого множества соотносятся с деревьями разбора языка <tex>L^{\sim}(\Gamma)s</tex>, так как при выводе каждого слова из этого языка также используются все нетерминалы грамматики. В дальнейшем доказательстве Если с помощью таких операций можно получить <tex>Tt</tex> используется для определения отображения Парика языка , то <tex>L^{s \sim}(\Gamma)leqslant t</tex> как объединение индивидуальных отображений.

В отличие от предыдущего определения, для следующего множества число Если строка <tex>k\alpha = N^{*} \cup \Sigma^{*}</tex> для любого нетерминала не ограничено., то за <tex>\Psi_{{Определение|definition = Пусть \Sigma}(\alpha)</tex>T'будем обозначать </tex> \Psi_{{---\Sigma}} множество всех терминальных деревьев разбора с корнем (x)</tex>, где <tex>Sx</tex>, которые удовлетворяют первому условию получен из предыдущего определения<tex>\alpha</tex> удалением всех нетерминалов.За <tex>\Psi_{\Sigma}(t)</tex> будем обозначать <tex>\Psi_{\Sigma}(res(t))</tex>.

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

<tex>\Longrightarrow</tex> <tex>\Phi \subset L^{\sim}(\Gamma)</tex>.{Теорема|about=В этой части доказательства будет рассмотрен случай <tex>m = (m_{1},\ldotsПарика,m_{m}) \in \Phi \rightarrow m \in \Psi_{\Sigma}(L^{\sim}(\Gamma)</tex>англ. '''База индукцииParikh's theorem'':Пусть <tex>m|statement=\Psi_{\Sigma}(w_{i})</tex> для некоторого <tex>i</tex>, Если язык <tex>w_{i} \in L^{\sim}(\Gamma)</tex>, и таким образом <tex>\Psi_{\Sigma}(w_{i}) \in \Psi_{\Sigma}(L^{\sim}(\Gamma))</tex>.  Предположим, что верно для некоторого <tex>m'</tex>, <tex>m' \in \Psi_{subset \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>является [[Контекстно-свободные грамматики, такоевывод, что <tex>\Psi_{\Sigma}(w) = 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}(uL) = 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>.|proof=

'''База индукции''':Если <tex>t \in T</tex>, то <tex>w = w_{i}</tex> для некоторого <tex>i</tex>, и значит <tex>\Psi_{\Sigma}(w) \in \Phi</tex>Воспользуемся ранее полученными результатами в доказательстве.

Предположим, что утверждение сохраняется для всех деревьев в Зададим <tex>M = \{s \mid s</tex> <tex>T'\leqslant</tex>-минимально, меньших <tex>troot(s) = S, res(s) \in \Sigma^{*}\}</tex>.

'''Шаг индукции''':Покажем, что <tex>\Psi_{\Sigma}(L(\Gamma)) = \bigcup \limits_{s \in M} \{\Psi_{\Sigma}(t) \mid s \leqslant t\}</tex>. Это множество полулинейно по предпоследней и последней лемме (<tex>M</tex> по ней конечно, так как число базовых <tex>p</tex> конечно).Пусть Любое такое <tex>p_t</tex>, что <tex>s \leqslant t</tex> для некоторого <tex>s \in M</tex> имеет корень <tex>root(t) = S</tex>, и его <tex>res(t) \in \Sigma^{1*}</tex>, значит <tex>t \ldotsin L(\Gamma)</tex>, p_и значит <tex>\Psi_{\Sigma}(t) \in \Psi_{k\Sigma}(L(\Gamma))</tex> будут узлами на некотором пути дерева. В обратную сторону, любая строка <tex>x \in L(\Gamma)</tex> имеет дерево разбора <tex>t</tex> с корнем <tex>root(t) = S</tex> и пусть индекс каждого узла будет указывать на его относительную позицию на этом пути. Более того<tex>res(t) = x</tex>, пусть все узлы будут помечены одним и тем же нетерминалом должно существовать <tex>leqslant</tex>-минимальное <tex>As \leqslant t</tex>(в противном бы случае это означало, чтобы все правильные поддеревьячто <tex>t</tex> не содержит базовых <tex>p</tex>, у которых корнем и значит оно само является узел <tex>p_{1}\leqslant</tex>-минимальным), удовлетворяли условию 2 в определении и тогда <tex>T\Psi_{\Sigma}(x) \in \{\Psi_{\Sigma}(t) \mid s \leqslant t\}</tex>.

<br>Эта теорема, так же, как и лемма о накачке и лемма Огдена, не является достаточной: язык <tex>\{0^{n}1^{n}2^{n} \mid n \geq 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 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> так же не полулинейно.