Теорема Парика — различия между версиями

Материал из Викиконспекты
Перейти к: навигация, поиск
(не показаны 3 промежуточные версии этого же участника)
Строка 12: Строка 12:
 
{{Определение
 
{{Определение
 
|definition =  
 
|definition =  
Пусть <tex>x_{0},  x_{1},\ldots, x_{p}</tex> при <tex>0 \leqslant  p < \infty</tex> {{---}} вектора в множестве <tex>\mathbb {N}^{m}</tex>. Множество <tex>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}\}^{*}</tex> называется '''линейным''' (англ. ''linear'') подмножеством множества <tex>\mathbb {N}^{m}</tex>.
+
Пусть <tex>x_{0},  x_{1},\ldots, x_{p}</tex> при <tex>0 \leqslant  p < \infty</tex> {{---}} вектора в множестве <tex>\mathbb {N}^{m}</tex>. Множество <tex>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}\}^{*}</tex> называется '''линейным''' (англ. ''linear'') подмножеством множества <tex>\mathbb {N}^{m}</tex>.
 
}}
 
}}
  
Строка 30: Строка 30:
  
 
==Теорема Парика==
 
==Теорема Парика==
{{Теорема
+
 
|about=
+
Пусть <tex>\Gamma =\langle \Sigma, N, S, P\rangle</tex> {{---}} контекстно-свободная грамматика.
Парика, англ. ''Parikh's theorem''
+
 
|statement=Если язык <tex>L \subset \Sigma^{*}</tex> является  [[Контекстно-свободные грамматики, вывод, лево- и правосторонний вывод, дерево разбора|контекстно-свободным]], то множество <tex>\Psi_{\Sigma}(L)</tex> является полулинейным.
+
Далее маленькими латинскими буквами <tex>s, t, \ldots</tex> будем обозначать деревья разбора. Для деревьев результатом (<tex>res(s)</tex>) будем называть строку из нетерминалов и терминалов, записанных в листьях, упорядоченную слева направо, глубина дерева (<tex>dep(s)</tex>) {{---}} длина наибольшего пути от листов до корня дерева, будем писать <tex>N(s)</tex>, чтобы обозначить множество нетерминалов в дереве, а <tex>root(s)</tex> {{---}} корень дерева.
 +
 
 +
Обозначим за <tex>p</tex> деревья такого вида:
 +
# оно содержит хотя бы два узла.
 +
# <tex>res(p) = u * root(p) * v</tex>, где <tex>u, v \in \Sigma^{*}</tex>, то есть все листья помечены терминалами, за исключением одного, который совпадает с корнем дерева.
 +
 
 +
Будем обозначать <tex>s \# t</tex> если <tex>t</tex> может быть получен из <tex>s</tex> вставкой дерева <tex>p</tex> с нетерминалом <tex>A</tex> в качестве корня на место нетерминала <tex>A</tex> в дереве <tex>s</tex>, то есть, можно увеличить <tex>s</tex> с помощью некоторого дерева <tex>p</tex> так, чтобы получить <tex>t</tex>. В <tex>s</tex> строго меньше узлов, чем в <tex>t</tex>.
 +
 
 +
Пусть <tex>p</tex> называется ''базовым'', если оно <tex>\#</tex>-минимально среди всех <tex>p</tex>, то есть не содержит в себе другое <tex>p</tex>, которое можно вырезать. Или, иначе, <tex>p</tex> является базовым, если в <tex>s \# t</tex> <tex>s</tex> является только тривиальным деревом с одним узлом (который же является и корнем).
 +
 
 +
{{Лемма
 +
|statement=
 +
Если <tex>p</tex> является базовым, то <tex>dep(p) \leqslant 2n</tex>, где <tex>n</tex> количество нетерминалов в N.
 
|proof=
 
|proof=
Пусть <tex>\Gamma =\langle \Sigma, N, S, P\rangle</tex> {{---}} контекстно-свободная грамматика. Вместо того, чтобы рассматривать <tex>L(\Gamma)</tex>, рассмотрим язык <tex>L^{\sim}(\Gamma)</tex>, содержащий только строки, порожденные выводами, в которых встречаются все нетерминалы грамматики.
+
Обозначим за <tex>\gamma</tex> путь от листа с нетерминалом <tex>root(p)</tex> до корня. Пусть <tex>\gamma</tex> не может быть длиннее, чем <tex>n</tex>, потому что если бы был, то он содержал бы повторяющийся нетерминал, и, тем самым, содержал бы в себе другое дерево <tex>p'</tex>, что противоречит тому, что <tex>p</tex> базовое.
Так как теорема Парика говорит о том, что для <tex>L(\Gamma)</tex> множество <tex>\Psi_{\Sigma}(L)</tex> полулинейно, то же самое должно сохраняться и для <tex>L^{\sim}(\Gamma)</tex>.
+
Для других же листов путь должен не превышать <tex>n+1</tex> по тем же причинам. Таким образом, длина любого пути не больше <tex>2n</tex>.
 +
}}
 +
Из леммы и из конечности нетерминалов и продукций в грамматике <tex>\Gamma</tex> следует, что количество таких базовых деревьев <tex>p</tex> конечно.
  
<br>
 
 
{{Лемма
 
{{Лемма
 
|statement=
 
|statement=
Если множество <tex>\Psi_{\Sigma}(L^{\sim}(\Gamma))</tex> полулинейно для всех контекстно-свободных языков, тогда множество <tex>\Psi_{\Sigma}(L(\Gamma))</tex> также полулинейно.
+
Любое дерево разбора <tex>t</tex> с <tex>res(t) \in \Sigma^{*}</tex> либо <tex>\#</tex>-минимально, либо содержит в себе базовое <tex>p</tex>.
 
|proof=
 
|proof=
Построим грамматики <tex>\Gamma_{1},...\Gamma_{k}</tex> для какого-то <tex>k \in \mathbb {N}^{+}</tex> путем удаления из грамматики <tex>\Gamma</tex> нетерминалов. Тогда <tex>L(\Gamma) = L^{\sim}(\Gamma_{1}) \cup \ldots \cup L^{\sim}(\Gamma_{k})</tex>. Так как для каждого из языков <tex>L^{\sim}(\Gamma_{p})</tex> множество <tex>\Psi_{\Sigma}</tex> полулинейно, то, по свойствам полулинейных множеств, для <tex>L(\Gamma)</tex> <tex>\Psi_{\Sigma}</tex> также полулинейно.
+
Пусть <tex>t</tex> не <tex>\#</tex>-минимально, тогда оно по определению содержит дерево <tex>p</tex>. Пусть <tex>p</tex> будет <tex>\#</tex>-минимально среди всех <tex>p</tex>, содержащихся в <tex>t</tex>, тогда <tex>p</tex> является базовым, так как если нет, то оно содержит в себе другое <tex>p</tex>, что противоречит <tex>\#</tex>-минимальности.
 
}}
 
}}
  
Стоит заметить, что число таких языков в лемме ограничено числом нетерминалов в грамматике: <tex>k = 2^{|N|} - 1</tex>. Вычитание происходит из-за того, что начальный нетерминал <tex>S</tex> не должен быть удален.
+
Пусть <tex>s \leqslant t</tex> если <tex>t</tex> может быть получен из <tex>s</tex> конечной последовательностью вставок базовых <tex>p</tex>, для которых <tex>N(p) \subset N(s)</tex>. Другими словами, нам позволено выбирать любой нетерминал A в дереве и вставлять на это место базовое <tex>p</tex> с корнем А в том случае, если <tex>p</tex> содержит только те нетерминалы, что есть в <tex>s</tex>. Если с помощью таких операций можно получить <tex>t</tex>, то <tex>s \leqslant t</tex>.
  
<br>
+
Если строка <tex>\alpha = N^{*} \cup \Sigma^{*}</tex>, то за <tex>\Psi_{\Sigma}(\alpha)</tex> будем обозначать <tex>\Psi_{\Sigma}(x)</tex>, где <tex>x</tex> получен из <tex>\alpha</tex> удалением всех нетерминалов. За <tex>\Psi_{\Sigma}(t)</tex> будем обозначать <tex>\Psi_{\Sigma}(res(t))</tex>.
Теперь же сосредоточимся на языке <tex>L^{\sim}(\Gamma)</tex>. Определим три множества деревьев разбора.
 
{{Определение
 
|definition =
 
Пусть <tex>T</tex> {{---}} множество всех терминальных деревьев разбора с корнем <tex>S</tex>, которые удовлетворяют двум условиям:
 
1. Каждый нетерминал <tex>N</tex> встречается в в дереве.
 
2. Каждый нетерминал <tex>N</tex> встречается не более чем <tex>k = |N|</tex> раз в любом пути.
 
}}
 
Деревья из этого множества соотносятся с деревьями разбора языка <tex>L^{\sim}(\Gamma)</tex>, так как при выводе каждого слова из этого языка также используются все нетерминалы грамматики. В дальнейшем доказательстве <tex>T</tex> используется для определения отображения Парика языка <tex>L^{\sim}(\Gamma)</tex> как объединение индивидуальных отображений.
 
  
В отличие от предыдущего определения, для следующего множества число <tex>k</tex> для любого нетерминала не ограничено.
+
{{Лемма
{{Определение
+
|statement=
|definition =  
+
Множество <tex>\{\Psi_{\Sigma}(t) \mid s \leqslant t\}</tex> линейно.
Пусть <tex>T'</tex> {{---}} множество всех терминальных деревьев разбора с корнем <tex>S</tex>, которые удовлетворяют первому условию из предыдущего определения.
+
|proof=
}}
+
<tex>\{\Psi_{\Sigma}(t) | s \leqslant t\} = \Psi_{\Sigma}(s) + \langle\{\Psi_{\Sigma}(p) \mid </tex> <tex>p</tex> является базовым, и его <tex>N(p) \subset N(s)</tex> <tex>\}\rangle</tex>.  
 
 
Последнее множество соотносится с теми правилами грамматики, которые делают строку больше в процессе вывода, то есть <tex>A \Rightarrow uAv</tex>, где <tex>u, v \in \Sigma</tex>. Эти деревья могут быть использованы, чтобы увеличить дерево разбора в множестве <tex>T'</tex> замещением нетерминала <tex>A</tex> в некотором дереве <tex>t'</tex> на дерево из множества <tex>I</tex>, определение которого написано ниже.
 
{{Определение
 
|definition =  
 
Пусть <tex>I</tex> {{---}} множество всех деревьев разбора с корнем <tex>A \in N</tex>, содержащих только один нетерминальный лист, который также помечен как <tex>A</tex>. В дополнение, деревья разбора множества <tex>I</tex> должны удовлетворять условию 2 в определении <tex>T</tex>.
 
 
}}
 
}}
В деревьях из этого множества могут содержаться другие нетерминалы, но главное, чтобы среди листов содержался только корневой.
 
  
Можно заметить, что деревья из <tex>T</tex> и <tex>I</tex> имеют конечную высоту.
+
Будем называть <tex>s</tex> <tex>\leqslant</tex>-минимальным, если оно не содержит в себе повторяющихся базовых <tex>p</tex>.
 
 
<br>
 
Теперь перейдем к доказательству теоремы.
 
<br>
 
Пусть <tex>w_{1},\ldots,w_{q}</tex> при <tex>q \in \mathbb {N}^{+}</tex> будут множеством строк, порожденных деревьями из <tex>T</tex>, и множество <tex>W</tex> {{---}} набором всех строк <tex>uv</tex>, для которых <tex>uAv</tex> будет результатом, полученным с помощью дерева разбора из <tex>I</tex> с вершиной <tex>A \in N</tex>. Элементы множества <tex>W</tex> представляют возможные поддеревья, которые могут быть использованы для того, чтобы увеличить длину пути в некотором дереве.  
 
 
{{Лемма
 
{{Лемма
 
|statement=
 
|statement=
Для языка <tex>L^{\sim}(\Gamma)</tex> выполняется равенство <tex>\Psi_{\Sigma}(L^{\sim}(\Gamma)) = (\Psi_{\Sigma}(w_{1})+\Psi_{\Sigma}(W)^{*}) \cup \ldots \cup (\Psi_{\Sigma}(w_{q})+\Psi_{\Sigma}(W)^{*}) </tex>
+
Если <tex>s</tex> <tex>\leqslant</tex>-минимально, то его <tex>dep(s) \leqslant (k+1)(n+1)</tex>, где <tex>n</tex> {{---}} размер <tex>N</tex>, а <tex>k</tex> {{---}} число различных базовых <tex>p</tex> в дереве.
 
|proof=
 
|proof=
Можем заметить, пустая строка может быть удалена из множества <tex>W</tex>, так как она не влияет на суммирование. Обозначим объединение сумм в лемме как <tex>\Phi</tex>.
+
Если путь длиннее, чем <tex>dep(s) \leqslant (k+1)(n+1)</tex>, то тогда он может быть поделен на <tex>k+1</tex> сегмент, каждый из которых длины как минимум <tex>n+1</tex>, и каждый имеет повторяющийся нетерминал, а, следовательно, <tex>s</tex> содержит <tex>k+1</tex> непересекающееся поддерево <tex>p</tex> (деревья называются непересекающимися в данном случае, если у них нет общих узлов, или если корень одного является листом другого дерева), каждое из которых, в соответствие с леммой, либо само является базовым, либо содержит базовое в себе, следовательно, в дереве <tex>s</tex> содержится <tex>k+1</tex> непересекающихся базовых <tex>p</tex>. Но так как число различных базовых <tex>p</tex> равно <tex>k</tex>, какое-то <tex>p</tex> появляется в этом наборе дважды, что противоречит <tex>\leqslant</tex>-минимальности.  
Также заметим, что <tex>\Psi_{\Sigma}(w_{i})</tex> является некоторым вектором размера <tex>m</tex>, <tex>W</tex> состоит из конечного набора строк (так как количество нетерминалов конечно, размер грамматики тоже конечен, высота деревьев из <tex>I</tex> конечна и ограничена, а значит и объединение таких <tex>uv</tex> для конечного числа нетерминалов конечно, и, следовательно, <tex>W</tex> конечно), <tex>\Psi_{\Sigma}(W)</tex> {{---}} конечный набор векторов размера <tex>m</tex>, и значит каждая такая сумма будет являться полулинейным множеством, а объединение полулинейных множеств полулинейно, в следствие чего можно сказать, что <tex>L^{\sim}(\Gamma)</tex> полулинейно, и далее по первой лемме полулинеен будет язык <tex>L(\Gamma)</tex>.
+
}}
  
Доказывать лемму будем в две стадии по индукции.
+
{{Теорема
 +
|about=
 +
Парика, англ. ''Parikh's theorem''
 +
|statement=Если язык <tex>L \subset \Sigma^{*}</tex> является  [[Контекстно-свободные грамматики, вывод, лево- и правосторонний вывод, дерево разбора|контекстно-свободным]], то множество <tex>\Psi_{\Sigma}(L)</tex> является полулинейным.
 +
|proof=
  
<tex>\Longrightarrow</tex> <tex>\Phi \subset L^{\sim}(\Gamma)</tex>.
+
Воспользуемся ранее полученными результатами в доказательстве.
  
В этой части доказательства будет рассмотрен случай <tex>m = (m_{1},\ldots,m_{m}) \in \Phi \rightarrow m \in \Psi_{\Sigma}(L^{\sim}(\Gamma)</tex>.
+
Зададим <tex>M = \{s \mid s</tex> <tex>\leqslant</tex>-минимально, <tex>root(s) = S, res(s) \in \Sigma^{*}\}</tex>.
 
 
'''База индукции''':
 
Пусть <tex>m=\Psi_{\Sigma}(w_{i})</tex> для некоторого <tex>i</tex>, <tex>w_{i} \in L^{\sim}(\Gamma)</tex>, и таким образом <tex>\Psi_{\Sigma}(w_{i}) \in \Psi_{\Sigma}(L^{\sim}(\Gamma))</tex>.
 
 
 
Предположим, что верно для некоторого <tex>m'</tex>, <tex>m' \in \Psi_{\Sigma}(L^{\sim}(\Gamma))</tex>.
 
 
 
'''Шаг индукции''':
 
Теперь пусть <tex>m = m'+\Psi_{\Sigma}(u)</tex> для некоторого <tex>u \in W</tex>. Существует дерево <tex>t \in T'</tex>, порождающее <tex>w</tex>, такое, что <tex>\Psi_{\Sigma}(w) = m'</tex>.
 
Кроме того, существует дерево <tex>t' \in I</tex>, порождающее <tex>u_{0}Av_{0}</tex>, такое, что <tex>u = u_{0}v_{0}</tex>.
 
Построим дерево разбора, заменив некоторый узел <tex>p</tex>, помеченный <tex>A</tex> в <tex>t</tex>, на дерево <tex>t'</tex>, подвесив к листу <tex>A</tex> дерева <tex>t'</tex> то, что раньше следовало за узлом <tex>p</tex> в дереве разбора. В итоге получившееся дерево принадлежит <tex>T'</tex>, и его результат, <tex>z</tex>, удовлетворяет <tex>\Psi_{\Sigma}(z) = \Psi_{\Sigma}(w)+\Psi_{\Sigma}(u) = m</tex>. Из-за того, что <tex>z</tex> является порождением дерева, принадлежащего <tex>T'</tex>, значит, что оно принадлежит языку <tex>L^{\sim}(\Gamma)</tex>. И так как получившийся результат совпадает с суммой, представленной в начале шага индукции, предположение индукции верно, и <tex>\Phi \subset L^{\sim}(\Gamma)</tex>.
 
 
 
<tex>\Longleftarrow</tex> <tex>L^{\sim}(\Gamma) \subset \Phi</tex>.
 
 
 
В этой части будет доказано, что если <tex>t \in T'</tex>, и результатом <tex>w</tex>, то <tex>\Psi_{\Sigma}(w) \in \Phi</tex>.
 
 
 
'''База индукции''':
 
Если <tex>t \in T</tex>, то <tex>w = w_{i}</tex> для некоторого <tex>i</tex>, и значит <tex>\Psi_{\Sigma}(w) \in \Phi</tex>.
 
 
 
Предположим, что утверждение сохраняется для всех деревьев в <tex>T'</tex>, меньших <tex>t</tex>.
 
 
 
'''Шаг индукции''':
 
Пусть <tex>p_{1}, \ldots, p_{k}</tex> будут узлами на некотором пути дерева, и пусть индекс каждого узла будет указывать на его относительную позицию на этом пути. Более того, пусть все узлы будут помечены одним и тем же нетерминалом <tex>A</tex>, чтобы все правильные поддеревья, у которых корнем является узел <tex>p_{1}</tex>, удовлетворяли условию 2 в определении <tex>T</tex>.
 
 
 
}}
 
  
 +
Покажем, что  <tex>\Psi_{\Sigma}(L(\Gamma)) = \bigcup \limits_{s \in M} \{\Psi_{\Sigma}(t) \mid s \leqslant t\}</tex>. Это множество полулинейно по предпоследней и последней лемме (<tex>M</tex> по ней конечно, так как число базовых <tex>p</tex> конечно).
 +
Любое такое <tex>t</tex>, что <tex>s \leqslant t</tex>  для некоторого <tex>s \in M</tex> имеет корень <tex>root(t) = S</tex>, и его <tex>res(t) \in \Sigma^{*}</tex>, значит <tex>t \in L(\Gamma)</tex>, и значит <tex>\Psi_{\Sigma}(t) \in \Psi_{\Sigma}(L(\Gamma))</tex>. В обратную сторону, любая строка <tex>x \in L(\Gamma)</tex> имеет дерево разбора <tex>t</tex> с корнем <tex>root(t) = S</tex> и <tex>res(t) = x</tex>, и должно существовать <tex>\leqslant</tex>-минимальное <tex>s \leqslant t</tex> (в противном бы случае это означало, что <tex>t</tex> не содержит базовых <tex>p</tex>, и значит оно само является <tex>\leqslant</tex>-минимальным), и тогда <tex>\Psi_{\Sigma}(x) \in \{\Psi_{\Sigma}(t) \mid s \leqslant t\}</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>.
+
Теорема Парика связывает два понятия: функцию <tex>\Psi_{\Sigma}</tex> контекстно-свободного языка и полулинейное множество. Например, для языка <tex>\{a(a^{2}b)^{m}(b^{3}c^{2})^{n} \mid m,n \geqslant 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>.
+
<br>Эта теорема, так же, как и лемма о накачке и лемма Огдена, не является достаточной: язык <tex>\{0^{n}1^{n}2^{n} \mid n \geqslant 0\}</tex> [[Лемма о разрастании для КС-грамматик#Пример доказательства неконтекстно-свободности языка с использованием леммы|не является контекстно-свободным]], однако его множество <tex>\Psi_{\Sigma} = \{(n, n, n) \mid n \geqslant 0\}</tex> является полулинейным: <tex>\Psi_{\Sigma} = \{(n, n, n) \mid n \geqslant 0\} = (0, 0, 0) + \{(1, 1, 1)\}^{*}</tex>.
  
 
==Примеры==
 
==Примеры==
Строка 123: Строка 99:
 
Язык <tex>\{a^{p} \mid p</tex> {{---}} простое число<tex>\}</tex> не является контекстно-свободным, так как множество простых чисел не является полулинейным (в арифметике Пресбургера нельзя определить множество простых чисел).
 
Язык <tex>\{a^{p} \mid p</tex> {{---}} простое число<tex>\}</tex> не является контекстно-свободным, так как множество простых чисел не является полулинейным (в арифметике Пресбургера нельзя определить множество простых чисел).
  
Язык <tex>\{a^{m}b^{n} \mid m > n</tex> или <tex>m</tex> {{---}} простое и <tex>m \leq n\}</tex> не является контекстно свободным, так как множество, порождаемое функцией <tex>\Psi_{\Sigma}</tex>, не является полулинейным: множество таких пар <tex>\{(m, n) \mid m > n\} = (1, 0) + \{(1, 0), (1, 1)\}</tex> {{---}} линейно, множество таких пар <tex>\{(m, n) \mid m \leq n\} = (0, 0) + \{(1, 1), (0, 1)\}</tex> {{---}} линейно, при этом множество простых чисел не является полулинейным, и, как следствие, множество <tex>\{m</tex> {{---}} простое и <tex>m \leq n\}</tex> не является полулинейным, <tex>\Psi_{\Sigma}</tex> так же не полулинейно.
+
Язык <tex>\{a^{m}b^{n} \mid m > n</tex> или <tex>m</tex> {{---}} простое и <tex>m \leqslant n\}</tex> не является контекстно свободным, так как множество, порождаемое функцией <tex>\Psi_{\Sigma}</tex>, не является полулинейным: множество таких пар <tex>\{(m, n) \mid m > n\} = (1, 0) + \{(1, 0), (1, 1)\}</tex> {{---}} линейно, множество таких пар <tex>\{(m, n) \mid m \leqslant n\} = (0, 0) + \{(1, 1), (0, 1)\}</tex> {{---}} линейно, при этом множество простых чисел не является полулинейным, и, как следствие, множество <tex>\{m</tex> {{---}} простое и <tex>m \leqslant n\}</tex> не является полулинейным, <tex>\Psi_{\Sigma}</tex> так же не полулинейно.
  
 
== См. также ==
 
== См. также ==
Строка 134: Строка 110:
 
== Источники информации==
 
== Источники информации==
 
*Гинзбург С. {{---}} Математическая теория контекстно-свободных языков
 
*Гинзбург С. {{---}} Математическая теория контекстно-свободных языков
*[https://www8.cs.umu.se/kurser/TDBC92/VT06/final/3.pdf Håkan Lindqvist {{---}} Parikh’s theorem]
+
*Dexter C. Kozen {{---}} Automata and Computability
 
*[http://cs.stackexchange.com/questions/265/how-to-prove-that-a-language-is-not-context-free Stack Exchange {{---}} How to prove that a language is not context-free?]
 
*[http://cs.stackexchange.com/questions/265/how-to-prove-that-a-language-is-not-context-free Stack Exchange {{---}} How to prove that a language is not context-free?]
  

Версия 18:44, 30 декабря 2016

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

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

Пусть [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] так же не полулинейно.

См. также

Примечания

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