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

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

В этом разделе предполагается, что зафиксирован некоторый линейный порядок на алфавите [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 \geqslant 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].

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

Пусть [math]\Gamma =\langle \Sigma, N, S, P\rangle[/math] — контекстно-свободная грамматика.

Далее маленькими латинскими буквами [math]s, t, \ldots[/math] будем обозначать деревья разбора. Для деревьев результатом ([math]res(s)[/math]) будем называть строку из нетерминалов и терминалов, записанных в листьях, упорядоченную слева направо, глубина дерева ([math]dep(s)[/math]) — длина наибольшего пути от листов до корня дерева, будем писать [math]N(s)[/math], чтобы обозначить множество нетерминалов в дереве, а [math]root(s)[/math] — корень дерева.

Обозначим за [math]p[/math] деревья такого вида:

1. оно содержит хотя бы два узла.
2. [math]res(p) = u * root(p) * v[/math], где [math]u, v \in \Sigma^{*}[/math], то есть все листья помечены терминалами, за исключением одного, который совпадает с корнем дерева.

Будем обозначать [math]s \# t[/math] если [math]t[/math] может быть получен из [math]s[/math] вставкой дерева [math]p[/math] с нетерминалом [math]A[/math] в качестве корня на место нетерминала [math]A[/math] в дереве [math]s[/math], то есть, можно увеличить [math]s[/math] с помощью некоторого дерева [math]p[/math] так, чтобы получить [math]t[/math]. В [math]s[/math] строго меньше узлов, чем в [math]t[/math].

Пусть [math]p[/math] называется базовым, если оно [math]\#[/math]-минимально среди всех [math]p[/math], то есть не содержит в себе другое [math]p[/math], которое можно вырезать. Или, иначе, [math]p[/math] является базовым, если в [math]s \# t[/math] [math]s[/math] является только тривиальным деревом с одним узлом (который же является и корнем).

Лемма:

Если [math]p[/math] является базовым, то [math]dep(p) \leqslant 2n[/math], где [math]n[/math] количество нетерминалов в N.

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

[math]\triangleright[/math]

Обозначим за [math]\gamma[/math] путь от листа с нетерминалом [math]root(p)[/math] до корня. Пусть [math]\gamma[/math] не может быть длиннее, чем [math]n[/math], потому что если бы был, то он содержал бы повторяющийся нетерминал, и, тем самым, содержал бы в себе другое дерево [math]p'[/math], что противоречит тому, что [math]p[/math] базовое. Для других же листов путь должен не превышать [math]n+1[/math] по тем же причинам. Таким образом, длина любого пути не больше [math]2n[/math].

[math]\triangleleft[/math]

Из леммы и из конечности нетерминалов и продукций в грамматике [math]\Gamma[/math] следует, что количество таких базовых деревьев [math]p[/math] конечно.

Лемма:

Любое дерево разбора [math]t[/math] с [math]res(t) \in \Sigma^{*}[/math] либо [math]\#[/math]-минимально, либо содержит в себе базовое [math]p[/math].

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

[math]\triangleright[/math]

Пусть [math]t[/math] не [math]\#[/math]-минимально, тогда оно по определению содержит дерево [math]p[/math]. Пусть [math]p[/math] будет [math]\#[/math]-минимально среди всех [math]p[/math], содержащихся в [math]t[/math], тогда [math]p[/math] является базовым, так как если нет, то оно содержит в себе другое [math]p[/math], что противоречит [math]\#[/math]-минимальности.

[math]\triangleleft[/math]

Пусть [math]s \leqslant t[/math] если [math]t[/math] может быть получен из [math]s[/math] конечной последовательностью вставок базовых [math]p[/math], для которых [math]N(p) \subset N(s)[/math]. Другими словами, нам позволено выбирать любой нетерминал A в дереве и вставлять на это место базовое [math]p[/math] с корнем А в том случае, если [math]p[/math] содержит только те нетерминалы, что есть в [math]s[/math]. Если с помощью таких операций можно получить [math]t[/math], то [math]s \leqslant t[/math].

Если строка [math]\alpha = N^{*} \cup \Sigma^{*}[/math], то за [math]\Psi_{\Sigma}(\alpha)[/math] будем обозначать [math]\Psi_{\Sigma}(x)[/math], где [math]x[/math] получен из [math]\alpha[/math] удалением всех нетерминалов. За [math]\Psi_{\Sigma}(t)[/math] будем обозначать [math]\Psi_{\Sigma}(res(t))[/math].

Лемма:

Множество [math]\{\Psi_{\Sigma}(t) \mid s \leqslant t\}[/math] линейно.

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

[math]\triangleright[/math]

[math]\{\Psi_{\Sigma}(t) | s \leqslant t\} = \Psi_{\Sigma}(s) + \langle\{\Psi_{\Sigma}(p) \mid [/math] [math]p[/math] является базовым, и его [math]N(p) \subset N(s)[/math] [math]\}\rangle[/math].

[math]\triangleleft[/math]

Будем называть [math]s[/math] [math]\leqslant[/math]-минимальным, если оно не содержит в себе повторяющихся базовых [math]p[/math].

Лемма:

Если [math]s[/math] [math]\leqslant[/math]-минимально, то его [math]dep(s) \leqslant (k+1)(n+1)[/math], где [math]n[/math] — размер [math]N[/math], а [math]k[/math] — число различных базовых [math]p[/math] в дереве.

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

[math]\triangleright[/math]

Если путь длиннее, чем [math]dep(s) \leqslant (k+1)(n+1)[/math], то тогда он может быть поделен на [math]k+1[/math] сегмент, каждый из которых длины как минимум [math]n+1[/math], и каждый имеет повторяющийся нетерминал, а, следовательно, [math]s[/math] содержит [math]k+1[/math] непересекающееся поддерево [math]p[/math] (деревья называются непересекающимися в данном случае, если у них нет общих узлов, или если корень одного является листом другого дерева), каждое из которых, в соответствие с леммой, либо само является базовым, либо содержит базовое в себе, следовательно, в дереве [math]s[/math] содержится [math]k+1[/math] непересекающихся базовых [math]p[/math]. Но так как число различных базовых [math]p[/math] равно [math]k[/math], какое-то [math]p[/math] появляется в этом наборе дважды, что противоречит [math]\leqslant[/math]-минимальности.

[math]\triangleleft[/math]

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

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

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

[math]\triangleright[/math]

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

[math]\triangleleft[/math]

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

См. также

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

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

• Гинзбург С. — Математическая теория контекстно-свободных языков
• Dexter C. Kozen — Automata and Computability
• Stack Exchange — How to prove that a language is not context-free?