|
Пусть [math]\Gamma =\langle \Sigma, N, S, P\rangle[/math] — контекстно-свободная грамматика. Вместо того, чтобы рассматривать [math]L(\Gamma)[/math], рассмотрим язык [math]L^{\sim}(\Gamma)[/math], содержащий только строки, порожденные выводами, в которых встречаются все нетерминалы грамматики.
Так как теорема Парика говорит о том, что для [math]L(\Gamma)[/math] множество [math]\Psi_{\Sigma}(L)[/math] полулинейно, то же самое должно сохраняться и для [math]L^{\sim}(\Gamma)[/math].
| Лемма: |
Если множество [math]\Psi_{\Sigma}(L^{\sim}(\Gamma))[/math] полулинейно для всех контекстно-свободных языков, тогда множество [math]\Psi_{\Sigma}(L(\Gamma))[/math] также полулинейно. |
| Доказательство: |
| [math]\triangleright[/math] | |
Построим грамматики [math]\Gamma_{1},...\Gamma_{k}[/math] для какого-то [math]k \in \mathbb {N}^{+}[/math] путем удаления из грамматики [math]\Gamma[/math] нетерминалов. Тогда [math]L(\Gamma) = L^{\sim}(\Gamma_{1}) \cup \ldots \cup L^{\sim}(\Gamma_{k})[/math]. Так как для каждого из языков [math]L^{\sim}(\Gamma_{p})[/math] множество [math]\Psi_{\Sigma}[/math] полулинейно, то, по свойствам полулинейных множеств, для [math]L(\Gamma)[/math] [math]\Psi_{\Sigma}[/math] также полулинейно. | | [math]\triangleleft[/math] |
Стоит заметить, что число таких языков в лемме ограничено числом нетерминалов в грамматике: [math]k = 2^{|N|} - 1[/math]. Вычитание происходит из-за того, что начальный нетерминал [math]S[/math] не должен быть удален.
Теперь же сосредоточимся на языке [math]L^{\sim}(\Gamma)[/math]. Определим три множества деревьев разбора.
| Определение: |
| Пусть [math]T[/math] — множество всех терминальных деревьев разбора с корнем [math]S[/math], которые удовлетворяют двум условиям:
1. Каждый нетерминал [math]N[/math] встречается в в дереве.
2. Каждый нетерминал [math]N[/math] встречается не более чем [math]k = |N|[/math] раз в любом пути. |
Деревья из этого множества соотносятся с деревьями разбора языка [math]L^{\sim}(\Gamma)[/math], так как при выводе каждого слова из этого языка также используются все нетерминалы грамматики. В дальнейшем доказательстве [math]T[/math] используется для определения отображения Парика языка [math]L^{\sim}(\Gamma)[/math] как объединение индивидуальных отображений.
В отличие от предыдущего определения, для следующего множества число [math]k[/math] для любого нетерминала не ограничено.
| Определение: |
| Пусть [math]T'[/math] — множество всех терминальных деревьев разбора с корнем [math]S[/math], которые удовлетворяют первому условию из предыдущего определения. |
Последнее множество соотносится с теми правилами грамматики, которые делают строку больше в процессе вывода, то есть [math]A \Rightarrow uAv[/math], где [math]u, v \in \Sigma[/math]. Эти деревья могут быть использованы, чтобы увеличить дерево разбора в множестве [math]T'[/math] замещением нетерминала [math]A[/math] в некотором дереве [math]t'[/math] на дерево из множества [math]I[/math], определение которого написано ниже.
| Определение: |
| Пусть [math]I[/math] — множество всех деревьев разбора с корнем [math]A \in N[/math], содержащих только один нетерминальный лист, который также помечен как [math]A[/math]. В дополнение, деревья разбора множества [math]I[/math] должны удовлетворять условию 2 в определении [math]T[/math]. |
В деревьях из этого множества могут содержаться другие нетерминалы, но главное, чтобы среди листов содержался только корневой.
Можно заметить, что деревья из [math]T[/math] и [math]I[/math] имеют конечную высоту.
Теперь перейдем к доказательству теоремы.
Пусть [math]w_{1},\ldots,w_{q}[/math] при [math]q \in \mathbb {N}^{+}[/math] будут множеством строк, порожденных деревьями из [math]T[/math], и множество [math]W[/math] — набором всех строк [math]uv[/math], для которых [math]uAv[/math] будет результатом, полученным с помощью дерева разбора из [math]I[/math] с вершиной [math]A \in N[/math]. Элементы множества [math]W[/math] представляют возможные поддеревья, которые могут быть использованы для того, чтобы увеличить длину пути в некотором дереве.
| Лемма: |
Для языка [math]L^{\sim}(\Gamma)[/math] выполняется равенство [math]\Psi_{\Sigma}(L^{\sim}(\Gamma)) = (\Psi_{\Sigma}(w_{1})+\Psi_{\Sigma}(W)^{*}) \cup \ldots \cup (\Psi_{\Sigma}(w_{q})+\Psi_{\Sigma}(W)^{*}) [/math] |
| Доказательство: |
| [math]\triangleright[/math] | |
Можем заметить, пустая строка может быть удалена из множества [math]W[/math], так как она не влияет на суммирование. Обозначим объединение сумм в лемме как [math]\Phi[/math].
Также заметим, что [math]\Psi_{\Sigma}(w_{i})[/math] является некоторым вектором размера [math]m[/math], [math]W[/math] состоит из конечного набора строк (так как количество нетерминалов конечно, размер грамматики тоже конечен, высота деревьев из [math]I[/math] конечна и ограничена, а значит и объединение таких [math]uv[/math] для конечного числа нетерминалов конечно, и, следовательно, [math]W[/math] конечно), [math]\Psi_{\Sigma}(W)[/math] — конечный набор векторов размера [math]m[/math], и значит каждая такая сумма будет являться полулинейным множеством, а объединение полулинейных множеств полулинейно, в следствие чего можно сказать, что [math]L^{\sim}(\Gamma)[/math] полулинейно, и далее по первой лемме полулинеен будет язык [math]L(\Gamma)[/math].
Доказывать лемму будем в две стадии по индукции.
[math]\Longrightarrow[/math] [math]\Phi \subset L^{\sim}(\Gamma)[/math].
В этой части доказательства будет рассмотрен случай [math]m = (m_{1},\ldots,m_{m}) \in \Phi \rightarrow m \in \Psi_{\Sigma}(L^{\sim}(\Gamma)[/math].
База индукции:
Пусть [math]m=\Psi_{\Sigma}(w_{i})[/math] для некоторого [math]i[/math], [math]w_{i} \in L^{\sim}(\Gamma)[/math], и таким образом [math]\Psi_{\Sigma}(w_{i}) \in \Psi_{\Sigma}(L^{\sim}(\Gamma))[/math].
Предположим, что верно для некоторого [math]m'[/math], [math]m' \in \Psi_{\Sigma}(L^{\sim}(\Gamma))[/math].
Шаг индукции:
Теперь пусть [math]m = m'+\Psi_{\Sigma}(u)[/math] для некоторого [math]u \in W[/math]. Существует дерево [math]t \in T'[/math], порождающее [math]w[/math], такое, что [math]\Psi_{\Sigma}(w) = m'[/math].
Кроме того, существует дерево [math]t' \in I[/math], порождающее [math]u_{0}Av_{0}[/math], такое, что [math]u = u_{0}v_{0}[/math].
Построим дерево разбора, заменив некоторый узел [math]p[/math], помеченный [math]A[/math] в [math]t[/math], на дерево [math]t'[/math], подвесив к листу [math]A[/math] дерева [math]t'[/math] то, что раньше следовало за узлом [math]p[/math] в дереве разбора. В итоге получившееся дерево принадлежит [math]T'[/math], и его результат, [math]z[/math], удовлетворяет [math]\Psi_{\Sigma}(z) = \Psi_{\Sigma}(w)+\Psi_{\Sigma}(u) = m[/math]. Из-за того, что [math]z[/math] является порождением дерева, принадлежащего [math]T'[/math], значит, что оно принадлежит языку [math]L^{\sim}(\Gamma)[/math]. И так как получившийся результат совпадает с суммой, представленной в начале шага индукции, предположение индукции верно, и [math]\Phi \subset L^{\sim}(\Gamma)[/math].
[math]\Longleftarrow[/math] [math]L^{\sim}(\Gamma) \subset \Phi[/math].
В этой части будет доказано, что если [math]t \in T'[/math], и результатом [math]w[/math], то [math]\Psi_{\Sigma}(w) \in \Phi[/math].
База индукции:
Если [math]t \in T[/math], то [math]w = w_{i}[/math] для некоторого [math]i[/math], и значит [math]\Psi_{\Sigma}(w) \in \Phi[/math].
Предположим, что утверждение сохраняется для всех деревьев в [math]T'[/math], меньших [math]t[/math].
Шаг индукции:
Пусть [math]p_{1}, \ldots, p_{k}[/math] будут узлами на некотором пути дерева, и пусть индекс каждого узла будет указывать на его относительную позицию на этом пути. Более того, пусть все узлы будут помечены одним и тем же нетерминалом [math]A[/math], чтобы все правильные поддеревья, у которых корнем является узел [math]p_{1}[/math], удовлетворяли условию 2 в определении [math]T[/math]. | | [math]\triangleleft[/math] |
|
