22
правки
Изменения
Нет описания правки
<br>
Теперь определим же сосредоточимся на языке <tex>L^{\sim}(\Gamma)</tex>. Определим три множества деревьев разбора.
{{Определение
|definition =
}}
Последнее множество относится к тем правилам соотносится с теми правилами грамматики, которые делают строку больше в процессе вывода, то есть <tex>A \Rightarrow uAv</tex>, где <tex>u, v \in \Sigma</tex>. Эти деревья могут быть использованы, чтобы увеличить дерево разбора в множестве <tex>T'</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>T</tex>.
}}
В дополнениедеревьях из этого множества могут содержаться другие нетерминалы, деревья разбора множества <tex>I</tex> должны удовлетворять условию 2 в определении <tex>T</tex>но главное, чтобы среди листов содержался только корневой. Еще можно Можно заметить, что деревья из <tex>T</tex> и <tex>I</tex> имеют конечную высоту.
<br>
|proof=
Можем заметить, пустая строка может быть удалена из множества <tex>W</tex>, так как она не влияет на суммирование. Обозначим объединение сумм в лемме как <tex>\Phi</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>\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>.
}}