Изменения

Теперь определим же сосредоточимся на языке <tex>L^{\sim}(\Gamma)</tex>. Определим три множества деревьев разбора.

Последнее множество относится к тем правилам соотносится с теми правилами грамматики, которые делают строку больше в процессе вывода, то есть <tex>A \Rightarrow uAv</tex>, где <tex>u, v \in \Sigma</tex>. Эти деревья могут быть использованы, чтобы увеличить дерево разбора в множестве <tex>T'</tex> замещением нетерминала <tex>A</tex> в некотором дереве <tex>t'</tex> на дерево из множества <tex>I</tex>, определение которого написано ниже.

Пусть <tex>I</tex> {{---}} множество всех деревьев разбора с корнем <tex>A \in N</tex>, содержащих только один нетерминальный лист, который также помечен как <tex>A</tex>. В дополнение, деревья разбора множества <tex>I</tex> должны удовлетворять условию 2 в определении <tex>T</tex>.

В дополнениедеревьях из этого множества могут содержаться другие нетерминалы, деревья разбора множества <tex>I</tex> должны удовлетворять условию 2 в определении <tex>T</tex>но главное, чтобы среди листов содержался только корневой. Еще можно  Можно заметить, что деревья из <tex>T</tex> и <tex>I</tex> имеют конечную высоту.

Также заметим, что <tex>\Psi_{\Sigma}(w_{i})</tex> является некоторым вектором размера <tex>m</tex>, <tex>W</tex> состоит из конечного набора строк (так как количество нетерминалов конечно, размер грамматики тоже конечен, тогда множество таких высота деревьев из <tex>uv: A \rightarrow uAvI</tex> для любого нетерминала A не может быть бесконечнымконечна и ограничена, а значит и объединение таких <tex>uv</tex> для конечного числа нетерминалов конечно, и, следовательно, <tex>W</tex> конечно), <tex>\Psi_{\Sigma}(W)</tex> {{---}} конечный набор векторов размера <tex>m</tex>, и значит каждая такая сумма будет являться полулинейным множеством, а объединение полулинейных множеств полулинейно, в следствие чего можно сказать, что <tex>L^{\sim}(\Gamma)</tex> полулинейно, и далее по первой лемме полулинеен будет язык <tex>L(\Gamma)</tex>.

<tex>\Longrightarrow</tex> <tex>\Phi \subset L^{\sim}(\Gamma)</tex>.

В этой части доказательства будет рассмотрен случай <tex>m = (m_{1},\ldots,m_{m}) \in \Phi \subset rightarrow m \in \Psi_{\Sigma}(L^{\sim}(\Gamma)</tex>.

В этой части доказательства будет рассмотрен случай '''База индукции''':Пусть <tex>m = \Psi_{\Sigma}(m_w_{i})</tex> для некоторого <tex>i</tex>, <tex>w_{i} \in L^{1\sim}(\Gamma)</tex>,и таким образом <tex>\Psi_{\Sigma}(w_{i}) \in \Psi_{\Sigma}(L^{\ldotssim}(\Gamma))</tex>.  Предположим,m_что верно для некоторого <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>, такое, что <tex>\Phi Psi_{\rightarrow 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}(u) = m</tex>. Из-за того, что <tex>z</tex> является порождением дерева, принадлежащего <tex>T'</tex>, значит, что оно принадлежит языку <tex>L^{\sim}(\Gamma)</tex>. И так как получившийся результат совпадает с суммой, представленной в начале шага индукции, предположение индукции верно, и <tex>\Phi \subset L^{\sim}(\Gamma)</tex>.