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

Линейные множества

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

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

Через [math]\Psi_{\Sigma}[/math] будем обозначать функцию [math]\Psi_{\Sigma} : \Sigma^{*} \rightarrow \mathbb {N}^{m}[/math], определённую следующим образом: [math]\Psi_{\Sigma}(w) = \langle |w|_{a_{1}} ,\ldots, |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]. Функция называется отображением Парика (англ. Parikh's mapping) соответственно слова и языка.

Пусть [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},\ldots, x_{p}[/math] при [math]0 \leqslant 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},\ldots,k_{p} \in \mathbb {N}\} = x_{0} + \{x_{1},\ldots, 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(\Gamma)[/math], рассмотрим язык [math]L^{\sim}(\Gamma)[/math], содержащий только строки, порожденные выводами, в которых встречаются все нетерминалы грамматики. Так как теорема Парика говорит о том, что для [math]L(\Gamma)[/math] множество [math]\Psi_{\Sigma}(L)[/math] полулинейно, то же самое должно сохраняться и для [math]L^{\sim}(\Gamma)[/math]. Лемма: Если множество [math]\Psi_{\Sigma}(L^{\sim}(\Gamma))[/math] полулинейно для всех контекстно-свободных языков, тогда множество [math]\Psi_{\Sigma}(L(\Gamma))[/math] также полулинейно. Доказательство: [math]\triangleright[/math] Построим грамматики [math]\Gamma_{1},...\Gamma_{k}[/math] для какого-то [math]k \in \mathbb {N}^{+}[/math] путем удаления из грамматики [math]\Gamma[/math] нетерминалов. Тогда [math]L(\Gamma) = L^{\sim}(\Gamma_{1}) \cup \ldots \cup L^{\sim}(\Gamma_{k})[/math]. Так как для каждого из языков [math]L^{\sim}(\Gamma_{p})[/math] множество [math]\Psi_{\Sigma}[/math] полулинейно, то, по свойствам полулинейных множеств, для [math]L(\Gamma)[/math] [math]\Psi_{\Sigma}[/math] также полулинейно. [math]\triangleleft[/math] Стоит заметить, что число таких языков в лемме ограничено числом нетерминалов в грамматике: [math]k = 2^{|N|} - 1[/math]. Вычитание происходит из-за того, что начальный нетерминал [math]S[/math] не должен быть удален. Теперь же сосредоточимся на языке [math]L^{\sim}(\Gamma)[/math]. Определим три множества деревьев разбора. Определение: Пусть [math]T[/math] — множество всех терминальных деревьев разбора с корнем [math]S[/math], которые удовлетворяют двум условиям: 1. Каждый нетерминал [math]N[/math] встречается в в дереве. 2. Каждый нетерминал [math]N[/math] встречается не более чем [math]k = |N|[/math] раз в любом пути. Деревья из этого множества соотносятся с деревьями разбора языка [math]L^{\sim}(\Gamma)[/math], так как при выводе каждого слова из этого языка также используются все нетерминалы грамматики. В дальнейшем доказательстве [math]T[/math] используется для определения отображения Парика языка [math]L^{\sim}(\Gamma)[/math] как объединение индивидуальных отображений. В отличие от предыдущего определения, для следующего множества число [math]k[/math] для любого нетерминала не ограничено. Определение: Пусть [math]T'[/math] — множество всех терминальных деревьев разбора с корнем [math]S[/math], которые удовлетворяют первому условию из предыдущего определения. Последнее множество соотносится с теми правилами грамматики, которые делают строку больше в процессе вывода, то есть [math]A \Rightarrow uAv[/math], где [math]u, v \in \Sigma[/math]. Эти деревья могут быть использованы, чтобы увеличить дерево разбора в множестве [math]T'[/math] замещением нетерминала [math]A[/math] в некотором дереве [math]t'[/math] на дерево из множества [math]I[/math], определение которого написано ниже. Определение: Пусть [math]I[/math] — множество всех деревьев разбора с корнем [math]A \in N[/math], содержащих только один нетерминальный лист, который также помечен как [math]A[/math]. В дополнение, деревья разбора множества [math]I[/math] должны удовлетворять условию 2 в определении [math]T[/math]. В деревьях из этого множества могут содержаться другие нетерминалы, но главное, чтобы среди листов содержался только корневой. Можно заметить, что деревья из [math]T[/math] и [math]I[/math] имеют конечную высоту. Теперь перейдем к доказательству теоремы. Пусть [math]w_{1},\ldots,w_{q}[/math] при [math]q \in \mathbb {N}^{+}[/math] будут множеством строк, порожденных деревьями из [math]T[/math], и множество [math]W[/math] — набором всех строк [math]uv[/math], для которых [math]uAv[/math] будет результатом, полученным с помощью дерева разбора из [math]I[/math] с вершиной [math]A \in N[/math]. Элементы множества [math]W[/math] представляют возможные поддеревья, которые могут быть использованы для того, чтобы увеличить длину пути в некотором дереве. Лемма: Для языка [math]L^{\sim}(\Gamma)[/math] выполняется равенство [math]\Psi_{\Sigma}(L^{\sim}(\Gamma)) = (\Psi_{\Sigma}(w_{1})+\Psi_{\Sigma}(W)^{*}) \cup \ldots \cup (\Psi_{\Sigma}(w_{q})+\Psi_{\Sigma}(W)^{*}) [/math] Доказательство: [math]\triangleright[/math] Можем заметить, пустая строка может быть удалена из множества [math]W[/math], так как она не влияет на суммирование. Обозначим объединение сумм в лемме как [math]\Phi[/math]. Также заметим, что [math]\Psi_{\Sigma}(w_{i})[/math] является некоторым вектором размера [math]m[/math], [math]W[/math] состоит из конечного набора строк (так как количество нетерминалов конечно, размер грамматики тоже конечен, высота деревьев из [math]I[/math] конечна и ограничена, а значит и объединение таких [math]uv[/math] для конечного числа нетерминалов конечно, и, следовательно, [math]W[/math] конечно), [math]\Psi_{\Sigma}(W)[/math] — конечный набор векторов размера [math]m[/math], и значит каждая такая сумма будет являться полулинейным множеством, а объединение полулинейных множеств полулинейно, в следствие чего можно сказать, что [math]L^{\sim}(\Gamma)[/math] полулинейно, и далее по первой лемме полулинеен будет язык [math]L(\Gamma)[/math]. Доказывать лемму будем в две стадии по индукции. [math]\Longrightarrow[/math] [math]\Phi \subset L^{\sim}(\Gamma)[/math]. В этой части доказательства будет рассмотрен случай [math]m = (m_{1},\ldots,m_{m}) \in \Phi \rightarrow m \in \Psi_{\Sigma}(L^{\sim}(\Gamma)[/math]. База индукции: Пусть [math]m=\Psi_{\Sigma}(w_{i})[/math] для некоторого [math]i[/math], [math]w_{i} \in L^{\sim}(\Gamma)[/math], и таким образом [math]\Psi_{\Sigma}(w_{i}) \in \Psi_{\Sigma}(L^{\sim}(\Gamma))[/math]. Предположим, что верно для некоторого [math]m'[/math], [math]m' \in \Psi_{\Sigma}(L^{\sim}(\Gamma))[/math]. Шаг индукции: Теперь пусть [math]m = m'+\Psi_{\Sigma}(u)[/math] для некоторого [math]u \in W[/math]. Существует дерево [math]t \in T'[/math], порождающее [math]w[/math], такое, что [math]\Psi_{\Sigma}(w) = m'[/math]. Кроме того, существует дерево [math]t' \in I[/math], порождающее [math]u_{0}Av_{0}[/math], такое, что [math]u = u_{0}v_{0}[/math]. Построим дерево разбора, заменив некоторый узел [math]p[/math], помеченный [math]A[/math] в [math]t[/math], на дерево [math]t'[/math], подвесив к листу [math]A[/math] дерева [math]t'[/math] то, что раньше следовало за узлом [math]p[/math] в дереве разбора. В итоге получившееся дерево принадлежит [math]T'[/math], и его результат, [math]z[/math], удовлетворяет [math]\Psi_{\Sigma}(z) = \Psi_{\Sigma}(w)+\Psi_{\Sigma}(u) = m[/math]. Из-за того, что [math]z[/math] является порождением дерева, принадлежащего [math]T'[/math], значит, что оно принадлежит языку [math]L^{\sim}(\Gamma)[/math]. И так как получившийся результат совпадает с суммой, представленной в начале шага индукции, предположение индукции верно, и [math]\Phi \subset L^{\sim}(\Gamma)[/math]. [math]\Longleftarrow[/math] [math]L^{\sim}(\Gamma) \subset \Phi[/math]. В этой части будет доказано, что если [math]t \in T'[/math], и результатом [math]w[/math], то [math]\Psi_{\Sigma}(w) \in \Phi[/math]. База индукции: Если [math]t \in T[/math], то [math]w = w_{i}[/math] для некоторого [math]i[/math], и значит [math]\Psi_{\Sigma}(w) \in \Phi[/math]. Предположим, что утверждение сохраняется для всех деревьев в [math]T'[/math], меньших [math]t[/math]. Шаг индукции: Пусть [math]p_{1}, \ldots, p_{k}[/math] будут узлами на некотором пути дерева, и пусть индекс каждого узла будет указывать на его относительную позицию на этом пути. Более того, пусть все узлы будут помечены одним и тем же нетерминалом [math]A[/math], чтобы все правильные поддеревья, у которых корнем является узел [math]p_{1}[/math], удовлетворяли условию 2 в определении [math]T[/math]. [math]\triangleleft[/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] так же не полулинейно.

См. также

• Лемма о разрастании для КС-грамматик
• Доказательство нерегулярности языков: лемма о разрастании

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

• Гинзбург С. — Математическая теория контекстно-свободных языков
• Håkan Lindqvist — Parikh’s theorem
• Stack Exchange — How to prove that a language is not context-free?