22
правки
Изменения
Нет описания правки
{{Определение
|definition =
Через <tex>\Psi_{\Sigma}</tex> будем обозначать функцию <tex>\Psi_{\Sigma} : \Sigma^{*} \rightarrow \mathbb {N}^{m}</tex>, определённую следующим образом: <tex>\Psi_{\Sigma}(w) = \langle |w|_{a_{1}} ,\ldots, |w|_{a_{m}} \rangle</tex>, где <tex>|w|_{a_{i}}</tex> {{---}} число появлений символа <tex>a_{i}</tex> в слове <tex>w</tex>. Аналогично, каждому языку <tex>L \subset \Sigma^{*}</tex> ставится в соответствие множество <tex>\Psi_{\Sigma}(L) \subset \mathbb {N}^{m}</tex>, определённое так: <tex>\Psi_{\Sigma}(L) = \{\Psi_{\Sigma}(w) \mid w \in L\}</tex>. Функция называется '''отображением Парика''' (англ. ''Parikh's mapping'') соответственно слова и языка.
}}
Пусть <tex>T</tex> {{---}} множество всех терминальных деревьев разбора с корнем <tex>S</tex>, которые удовлетворяют двум условиям:
1. Каждый нетерминал <tex>N</tex> встречается в в дереве.
2. Каждый нетерминал <tex>N</tex> встречается не более чем <tex>k = |N|</tex> раз в деревелюбом пути.
}}
Деревья из этого множества соотносятся с деревьями разбора языка <tex>L^{\sim}(\Gamma)</tex>, так как при выводе каждого слова из этого языка также используются все нетерминалы грамматики. В дальнейшем доказательстве <tex>T</tex> используется для определения отображения Парика языка <tex>L^{\sim}(\Gamma)</tex> как объединение индивидуальных отображений.
В отличие от предыдущего определения, для следующего множества число <tex>k</tex> для любого нетерминала не ограничено.
|proof=
Можем заметить, пустая строка может быть удалена из множества <tex>W</tex>, так как она не влияет на суммирование. Обозначим объединение сумм в лемме как <tex>\Phi</tex>.
Также заметим, что <tex>\Psi_{\Sigma}(w_{i})</tex> является некоторым вектором размера <tex>m</tex>, <tex>W</tex> состоит из конечного набора строк (так как количество нетерминалов конечно, размер грамматики тоже конечен, тогда множество таких <tex>uv: A \rightarrow uAv</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>\Phi \subset L^{\sim}(\Gamma)</tex>.
В этой части доказательства будет рассмотрен случай <tex>m = (m_{1},\ldots,m_{m}) \in \Phi \rightarrow m \in \Psi_{\Sigma}(L^{\sim}(\Gamma)</tex>.
<tex>\Longleftarrow</tex> <tex>L^{\sim}(\Gamma) \subset \Phi</tex>.
