22
правки
Изменения
Нет описания правки
==Используемые определения==
В этом разделе предполагается, что зафиксирован некоторый линейный порядок на алфавите <tex>\Sigma</tex>. Пусть <tex>\Sigma = \{a_{1},...,a_{nm}\}</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>.
