22
правки
Изменения
Нет описания правки
Пусть <tex>L_{1} = (1, 2) + \{(3, 5), (7, 11)\}^{*}</tex>, <tex>L_{2} = (1, 1) + \{(2, 3), (5, 7), (4, 0)\}^{*}</tex>, <tex>L_{1}</tex> и <tex>L_{2}</tex> линейные подмножества <tex>\mathbb {N}^{2}</tex>, а <tex>L = L_{1} \cup L_{2}</tex> является полулинейным подмножеством <tex>\mathbb {N}^{2}</tex>.
==Теорема Парика==
|proof=
Для доказательства будем пользоваться [[Лемма о разрастании для КС-грамматик|леммой о накачке для контекстно-свободных языков]].
//Пусть <tex>\Gamma =\langle \Sigma, N, S, P\rangle</tex> {{---}} неукорачивающая контекстно-свободная грамматика, порождающая множество <tex>L</tex>, и пусть <tex>n</tex> {{---}} константа из леммы о накачке. //Для каждого набора нетерминалов <tex>U</tex>, содержащих <tex>S</tex>,
}}
Теорема Парика связывает два понятия: функцию <tex>\Psi_{\Sigma}</tex> и полулинейное множество. Например, для языка <tex>\{a(a^{2}b)^{m}(b^{3}c^{2})^{n} \mid m,n \geq 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 0\}</tex> [[Лемма о разрастании для КС-грамматик#Пример доказательства неконтекстно-свободности языка с использованием леммы|не является контекстно-свободным]], однако его множество <tex>\Psi_{\Sigma} = \{(n, n, n) \mid n \geq 0\}</tex> является полулинейным: <tex>\Psi_{\Sigma} = \{(n, n, n) \mid n \geq 0\} = (0, 0, 0) + \{(1, 1, 1)\}^{*}</tex>.
==Примеры==
