Изменения

==Используемые определенияЛинейные множества==В этом разделе предполагается, что зафиксирован некоторый [[Отношение_порядка|линейный порядок ]] на алфавите <tex>\Sigma</tex>. Пусть <tex>\Sigma = \{a_{1},...\ldots,a_{m}\}</tex>.

Через <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>x_{0}, x_{1},...\ldots, x_{p}</tex> при <tex>0 \leq leqslant p < \infty</tex> {{---}} вектора в множестве <tex>\mathbb {N}^{m}</tex>. Множество <tex>L = \{b + \sum_{i=1}^{p}k_{i} x_{i} \mid b \in B, k \geq geqslant 0, k_{1},...\ldots,k_{p} \in \mathbb {N}\} = x_{0} + \{x_{1},...\ldots, x_{p}\}^{*}</tex> называется '''линейным''' (англ. ''linear'') подмножеством множества <tex>\mathbb {N}^{m}</tex>.

*Полулинейные множества по теореме Гинзбурга-Спаниера (англ. ''Ginsburg and Spanier theorem'') {{---}} те, которые определяемы в арифметика арифметике Пресбургера (англ. ''Presburger arithmetic'')<ref>[https://en.wikipedia.org/wiki/Presburger_arithmetic Wikipedia {{---}} Presburger arithmetic]</ref>.

Для доказательства будем пользоваться [[Лемма о разрастании для КС-грамматик|леммой о накачке для контекстно-свободных языков]]Воспользуемся ранее полученными результатами в доказательстве. Зададим <tex>M = \{s \mid s</tex> <tex>\leqslant</Пусть tex>-минимально, <tex>root(s) = S, res(s) \in \Sigma^{*}\}</tex>.  Покажем, что <tex>\Psi_{\Sigma}(L(\Gamma )) =\langle bigcup \limits_{s \in M} \{\Psi_{\Sigma}(t) \mid s \leqslant t\}</tex>. Это множество полулинейно по предпоследней и последней лемме (<tex>M</tex> по ней конечно, Nтак как число базовых <tex>p</tex> конечно).Любое такое <tex>t</tex>, что <tex>s \leqslant t</tex> для некоторого <tex>s \in M</tex> имеет корень <tex>root(t) = S</tex>, и его <tex>res(t) \in \Sigma^{*}</tex>, Pзначит <tex>t \in L(\rangleGamma)</tex> , и значит <tex>\Psi_{\Sigma}(t) \in \Psi_{---\Sigma}} неукорачивающая контекстно-свободная грамматика(L(\Gamma))</tex>. В обратную сторону, порождающая множество любая строка <tex>x \in L(\Gamma)</tex> имеет дерево разбора <tex>t</tex> с корнем <tex>root(t) = S</tex> и <tex>res(t) = x</tex>, и пусть должно существовать <tex>n\leqslant</tex> {{---}} константа из леммы о накачке. минимальное <tex>s \leqslant t</tex> (в противном бы случае это означало, что <tex>t</Для каждого набора нетерминалов tex> не содержит базовых <tex>Up</tex>, содержащих и значит оно само является <tex>S\leqslant</tex>-минимальным), и тогда <tex>\Psi_{\Sigma}(x) \in \{\Psi_{\Sigma}(t) \mid s \leqslant t\}</tex>.

Теорема Парика связывает два понятия: функцию <tex>\Psi_{\Sigma}</tex> контекстно-свободного языка и полулинейное множество. Например, для языка <tex>\{a(a^{2}b)^{m}(b^{3}c^{2})^{n} \mid m,n \geq geqslant 0\})</tex> функция <tex>\Psi_{\Sigma} = (1,0,0)+\{(2,1,0), (0,3,2)\}^{*}</tex>.<br>Эта теорема, так же, как и лемма о накачке и лемма Огдена, не является достаточной: язык <tex>\{0^{n}1^{n}2^{n} \mid n \geq geqslant 0\}</tex> [[Лемма о разрастании для КС-грамматик#Пример доказательства неконтекстно-свободности языка с использованием леммы|не является контекстно-свободным]], однако его множество <tex>\Psi_{\Sigma} = \{(n, n, n) \mid n \geq geqslant 0\}</tex> является полулинейным: <tex>\Psi_{\Sigma} = \{(n, n, n) \mid n \geq geqslant 0\} = (0, 0, 0) + \{(1, 1, 1)\}^{*}</tex>.

Язык <tex>\{a^{m}b^{n} \mid m > n</tex> или <tex>m</tex> {{---}} простое и <tex>m \leq leqslant n\}</tex> не является контекстно свободным, так как множество, порождаемое функцией <tex>\Psi_{\Sigma}</tex>, не является полулинейным: множество таких пар <tex>\{(m, n) \mid m > n\} = (1, 0) + \{(1, 0), (1, 1)\}</tex> {{---}} линейно, множество таких пар <tex>\{(m, n) \mid m \leq leqslant n\} = (0, 0) + \{(1, 1), (0, 1)\}</tex> {{---}} линейно, при этом множество простых чисел не является полулинейным, и, как следствие, множество <tex>\{m</tex> {{---}} простое и <tex>m \leq leqslant n\}</tex> не является полулинейным, <tex>\Psi_{\Sigma}</tex> так же не полулинейно.

== Источники информации==