Теорема Парика

Используемые определения

В этом разделе предполагается, что зафиксирован некоторый линейный порядок на алфавите [math]\Sigma[/math]. Пусть [math]\Sigma = \{a_{1},...,a_{n}\}[/math].

Определение:

Через [math]\Psi_{\Sigma}[/math] будем обозначать функцию [math]\Psi_{\Sigma} : \Sigma^{*} \rightarrow \mathbb {N}^{m}[/math], определённую следующим образом: [math]\Psi_{\Sigma}(w) = \langle |w|_{a_{1}} ,..., |w|_{a_{m}} \rangle[/math], где [math]|w|_{a_{i}}[/math] — количество появлений символа [math]a_{i}[/math] в слове [math]w[/math]. Аналогично, каждому языку [math]L \subset \Sigma^{*}[/math] ставится в соответствие множество [math]\Psi_{\Sigma}(L) \subset \mathbb {N}^{m}[/math], определённое так: [math]\Psi_{\Sigma}(L) = \{\Psi_{\Sigma}(w) \mid w \in L\}[/math].

Пусть [math]\Sigma = \{a, b\}[/math] и [math]L = \{a, abb, bba\}[/math]. Тогда [math]\Psi_{\Sigma}(L) = \{\langle 1, 0 \rangle, \langle 1, 2 \rangle\}[/math].

Определение:

Пусть [math]x_{0}, x_{1},..., x_{p}[/math] при [math]0 \leq p \lt \infty[/math] — вектора в множестве [math]\mathbb {N}^{m}[/math]. Множество [math]L = \{b + \sum_{i=1}^{p}k_{i} x_{i} \mid b \in B, k \geq 0, k_{1},...,k_{p} \in \mathbb {N}\} = x_{0} + \{x_{1},..., x_{p}\}^{*}[/math] называется линейным (англ. linear) подмножеством множества [math]\mathbb {N}^{m}[/math].

Говоря проще, линейное подмножество [math]\mathbb {N}^{m}[/math] может быть построено с помощью любого m-размерного вектора [math]x_{0}[/math] добавлением к нему произвольного числа m-размерных векторов из конечного множества, например, 1 раз [math]x_{1}[/math] и 0 раз остальные вектора, 1 раз [math]x_{1}[/math], 1 раз [math]x_{2}[/math] и 0 раз остальные, и так далее.
Множество [math]L = \{(0, 0) + k_{1}(0, 2) + k_{2}(2, 0) \mid k_{1},k_{2} \in \mathbb {N}\} [/math] [math] = \{(2k_{1}, 2k_{2}) \mid k_{1},k_{2} \in \mathbb {N}\}[/math] является линейным.

Определение:

Подмножество множества [math]\mathbb {N}[/math] называется полулинейным (англ. semilinear), если оно является объединением конечного числа линейных множеств.

• Любое конечное подмножество [math]\mathbb {N}^{m}[/math] — полулинейно.
• Полулинейные множества замкнуты относительно операции объединения, пересечения, разности и проекции.
• Полулинейные множества по теореме Гинзбурга-Спаниера (англ. Ginsburg and Spanier theorem) — те, которые определяемы в арифметика Пресбургера (англ. Presburger arithmetic).

Пусть [math]L_{1} = (1, 2) + \{(3, 5), (7, 11)\}^{*}[/math], [math]L_{2} = (1, 1) + \{(2, 3), (5, 7), (4, 0)\}^{*}[/math], [math]L_{1}[/math] и [math]L_{2}[/math] линейные подмножества [math]\mathbb {N}^{2}[/math], а [math]L = L_{1} \cup L_{2}[/math] является полулинейным подмножеством [math]\mathbb {N}^{2}[/math].

Теорема Парика

Теорема (Парика, англ. Parikh's theorem):

Если язык [math]L \subset \Sigma^{*}[/math] является контекстно-свободным, то множество [math]\Psi_{\Sigma}(L)[/math] является полулинейным.

Доказательство:

[math]\triangleright[/math]

Для доказательства будем пользоваться леммой о накачке для контекстно-свободных языков. //Пусть [math]\Gamma =\langle \Sigma, N, S, P\rangle[/math] — неукорачивающая контекстно-свободная грамматика, порождающая множество [math]L[/math], и пусть [math]n[/math] — константа из леммы о накачке. //Для каждого набора нетерминалов [math]U[/math], содержащих [math]S[/math],

[math]\triangleleft[/math]

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

Примеры

Язык [math]\{a^{p} \mid p[/math] — простое число[math]\}[/math] не является контекстно-свободным, так как множество простых чисел не является полулинейным (в арифметике Пресбургера нельзя определить множество простых чисел).

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

См. также

• Лемма о разрастании для КС-грамматик

Источники

• Гинзбург С. — Математическая теория контекстно-свободных языков