|statement=Если язык <tex>L \subset \Sigma^{*}</tex> является [[Контекстно-свободные грамматики, вывод, лево- и правосторонний вывод, дерево разбора|контекстно-свободным]], то множество <tex>\Psi_{\Sigma}(L)</tex> является полулинейным.
|proof=
Для доказательства будем пользоваться [[Лемма Пусть <tex>\Gamma =\langle \Sigma, N, S, P\rangle</tex> {{---}} контекстно-свободная грамматика. Вместо того, чтобы рассматривать <tex>L(\Gamma)</tex>, рассмотрим язык <tex>L^{\sim}(\Gamma)</tex>, содержащий только строки, порожденные выводами, в которых встречаются все нетерминалы грамматики.Так как теорема Парика говорит о разрастании том, что для <tex>L(\Gamma)</tex> множество <tex>\Psi_{\Sigma}(L)</tex> полулинейно, то же самое должно сохраняться и для КС-грамматик<tex>L^{\sim}(\Gamma)</tex>. <br>{{Лемма|леммой о накачке statement=Если множество <tex>\Psi_{\Sigma}(L^{\sim}(\Gamma))</tex> полулинейно для всех контекстно-свободных языков]], тогда множество <tex>\Psi_{\Sigma}(L(\Gamma))</tex> также полулинейно.|proof=Построим грамматики <tex>\Gamma_{1},...\Gamma_{k}</tex> для какого-то <tex>k \in \mathbb {N}^{+}</Пусть tex> путем удаления из грамматики <tex>\Gamma</tex> нетерминалов. Тогда <tex>L(\Gamma ) =L^{\sim}(\Gamma_{1}) \cup ... \cup L^{\sim}(\Gamma_{k})</tex>. Так как для каждого из языков <tex>L^{\sim}(\Gamma_{p})</tex> множество <tex>\Psi_{\Sigma}</tex> полулинейно, то, по свойствам полулинейных множеств, для <tex>L(\Gamma)</tex> <tex>\langle Psi_{\Sigma}</tex> также полулинейно.}} Стоит заметить, что число таких языков в лемме ограничено числом нетерминалов в грамматике: <tex>k = 2^{|N|} - 1</tex>. Вычитание происходит из-за того, что начальный нетерминал <tex>S</tex> не должен быть удален. <br>Теперь определим три множества деревьев разбора. {{Определение|definition = Пусть <tex>T</tex> {{---}} множество всех терминальных деревьев разбора с корнем <tex>S</tex>, Pкоторые удовлетворяют двум условиям:1. Каждый нетерминал <tex>N</tex> встречается в в дереве.2. Каждый нетерминал <tex>N</tex> встречается не более чем <tex>k = |N|</tex> раз в дереве.}}Деревья из этого множества соотносятся с деревьями разбора языка <tex>L^{\sim}(\rangleGamma)</tex>, так как при выводе каждого слова из этого языка также используются все нетерминалы грамматики. В отличие от предыдущего определения, для следующего множества число <tex>k</tex> для любого нетерминала не ограничено.{{Определение|definition = Пусть <tex>T'</tex> {{---}} неукорачивающая контекстно-свободная грамматикамножество всех терминальных деревьев разбора с корнем <tex>S</tex>, порождающая которые удовлетворяют первому условию из предыдущего определения.}} Последнее множество относится к тем правилам грамматики, которые делают строку больше в процессе вывода, то есть <tex>A \Rightarrow uAv</tex>, где <tex>u, v \in \Sigma</tex>. Эти деревья могут быть использованы, чтобы увеличить дерево разбора в множестве <tex>T'</tex> замещением нетерминала <tex>A</tex> в некотором дереве <tex>Lt'</tex> на дерево из множества <tex>I</tex>, и пусть определение которого написано ниже.{{Определение|definition = Пусть <tex>nI</tex> {{---}} константа множество всех деревьев разбора с корнем <tex>A \in N</tex>, содержащих только один нетерминальный лист, который также помечен как <tex>A</tex>.}}В дополнение, деревья разбора множества <tex>I</tex> должны удовлетворять условию 2 в определении <tex>T</tex>. Еще можно заметить, что деревья из леммы о накачке<tex>T</tex> и <tex>I</tex> имеют конечную высоту. <br>Теперь перейдем к доказательству теоремы. <br>Пусть <tex>w_{1},...,w_{q}</tex> при <tex>q \in \mathbb {N}^{+}</tex> будут множеством строк, порожденных деревьями из <tex>T</tex>, и множество <tex>W</tex> {{---}} набором всех строк <tex>uv</tex>, для которых <tex>uAv</tex> будет результатом, полученным с помощью дерева разбора из <tex>I</tex> с вершиной <tex>A \in N</tex>. Элементы множества <tex>W</tex> представляют возможные поддеревья, которые могут быть использованы для того, чтобы увеличить длину пути в некотором дереве. {{Лемма|statement=Для каждого набора нетерминалов языка <tex>L^{\sim}(\Gamma)</tex> выполняется равенство <tex>U\Psi_{\Sigma}(L^{\sim}(\Gamma)) = (\Psi_{\Sigma}(w_{1})+\Psi_{\Sigma}(W)^{*}) \cup ... \cup (\Psi_{\Sigma}(w_{q})+\Psi_{\Sigma}(W)^{*}) </tex>|proof=Можем заметить, содержащих пустая строка может быть удалена из множества <tex>SW</tex>, так как она не влияет на суммирование. Обозначим объединение сумм в лемме как <tex>\Phi</tex>. Доказывать лемму будем в две стадии по индукции. <tex>\Longrightarrow</tex> <tex>\Phi \subset L^{\sim}(\Gamma)</tex>. <tex>\Longleftarrow</tex> <tex>L^{\sim}(\Gamma) \subset \Phi</tex>. }}
}}
== См. также ==
*[[Лемма о разрастании для КС-грамматик|Лемма о разрастании для КС-грамматик]]
== Источники ==
*Гинзбург С. {{---}} Математическая теория контекстно-свободных языков
*[https://www8.cs.umu.se/kurser/TDBC92/VT06/final/3.pdf Håkan Lindqvist {{---}} Parikh’s theorem]
[[Категория: Теория формальных языков]]
[[Категория: Контекстно-свободные грамматики]]
[[Категория: Опровержение контекстно-свободности языка]]
