http://neerc.ifmo.ru/wiki/api.php?action=feedcontributions&user=Alice&feedformat=atomВикиконспекты - Вклад участника [ru]2024-03-28T10:22:21ZВклад участникаMediaWiki 1.30.0http://neerc.ifmo.ru/wiki/index.php?title=%D0%A2%D0%B5%D0%BE%D1%80%D0%B5%D0%BC%D0%B0_%D0%9F%D0%B0%D1%80%D0%B8%D0%BA%D0%B0&diff=58433Теорема Парика2016-12-30T15:44:22Z<p>Alice: </p>
<hr />
<div>==Линейные множества==<br />
В этом разделе предполагается, что зафиксирован некоторый [[Отношение_порядка|линейный порядок]] на алфавите <tex>\Sigma</tex>. Пусть <tex>\Sigma = \{a_{1},\ldots,a_{m}\}</tex>.<br />
<br />
{{Определение<br />
|definition = <br />
Через <tex>\Psi_{\Sigma}</tex> будем обозначать функцию <tex>\Psi_{\Sigma} : \Sigma^{*} \rightarrow \mathbb {N}^{m}</tex>, определённую следующим образом: <tex>\Psi_{\Sigma}(w) = \langle |w|_{a_{1}} ,\ldots, |w|_{a_{m}} \rangle</tex>, где <tex>|w|_{a_{i}}</tex> {{---}} число появлений символа <tex>a_{i}</tex> в слове <tex>w</tex>. Аналогично, каждому языку <tex>L \subset \Sigma^{*}</tex> ставится в соответствие множество <tex>\Psi_{\Sigma}(L) \subset \mathbb {N}^{m}</tex>, определённое так: <tex>\Psi_{\Sigma}(L) = \{\Psi_{\Sigma}(w) \mid w \in L\}</tex>. Функция называется '''отображением Парика''' (англ. ''Parikh's mapping'') соответственно слова и языка.<br />
}}<br />
<br />
Пусть <tex>\Sigma = \{a, b\}</tex> и <tex>L = \{a, abb, bba\}</tex>. Тогда <tex>\Psi_{\Sigma}(L) = \{\langle 1, 0 \rangle, \langle 1, 2 \rangle\}</tex>.<br />
<br />
<br />
{{Определение<br />
|definition = <br />
Пусть <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>.<br />
}}<br />
<br />
Говоря проще, линейное подмножество <tex>\mathbb {N}^{m}</tex> может быть построено с помощью любого m-размерного вектора <tex>x_{0}</tex> добавлением к нему произвольного числа m-размерных векторов из конечного множества, например, 1 раз <tex>x_{1}</tex> и 0 раз остальные вектора, 1 раз <tex>x_{1}</tex>, 1 раз <tex>x_{2}</tex> и 0 раз остальные, и так далее.<br />
<br>Множество <tex>L = \{(0, 0) + k_{1}(0, 2) + k_{2}(2, 0) \mid k_{1},k_{2} \in \mathbb {N}\} </tex> <tex> = \{(2k_{1}, 2k_{2}) \mid k_{1},k_{2} \in \mathbb {N}\}</tex> является линейным.<br />
<br />
{{Определение<br />
|definition = <br />
Подмножество множества <tex>\mathbb {N}</tex> называется '''полулинейным''' (англ. ''semilinear''), если оно является объединением конечного числа линейных множеств.<br />
}}<br />
Полулинейное множество имеет следующие свойства:<br />
*Любое конечное подмножество <tex>\mathbb {N}^{m}</tex> {{---}} полулинейно.<br />
*Полулинейные множества замкнуты относительно операции объединения, пересечения, разности и проекции.<br />
*Полулинейные множества по теореме Гинзбурга-Спаниера (англ. ''Ginsburg and Spanier theorem'') {{---}} те, которые определяемы в арифметике Пресбургера (англ. ''Presburger arithmetic'')<ref>[https://en.wikipedia.org/wiki/Presburger_arithmetic Wikipedia {{---}} Presburger arithmetic]</ref>.<br />
<br />
Пусть <tex>L_{1} = (1, 2) + \{(3, 5), (7, 11)\}^{*}</tex>, <tex>L_{2} = (1, 1) + \{(2, 3), (5, 7), (4, 0)\}^{*}</tex>, <tex>L_{1}</tex> и <tex>L_{2}</tex> линейные подмножества <tex>\mathbb {N}^{2}</tex>, а <tex>L = L_{1} \cup L_{2}</tex> является полулинейным подмножеством <tex>\mathbb {N}^{2}</tex>.<br />
<br />
==Теорема Парика==<br />
<br />
Пусть <tex>\Gamma =\langle \Sigma, N, S, P\rangle</tex> {{---}} контекстно-свободная грамматика. <br />
<br />
Далее маленькими латинскими буквами <tex>s, t, \ldots</tex> будем обозначать деревья разбора. Для деревьев результатом (<tex>res(s)</tex>) будем называть строку из нетерминалов и терминалов, записанных в листьях, упорядоченную слева направо, глубина дерева (<tex>dep(s)</tex>) {{---}} длина наибольшего пути от листов до корня дерева, будем писать <tex>N(s)</tex>, чтобы обозначить множество нетерминалов в дереве, а <tex>root(s)</tex> {{---}} корень дерева.<br />
<br />
Обозначим за <tex>p</tex> деревья такого вида:<br />
# оно содержит хотя бы два узла.<br />
# <tex>res(p) = u * root(p) * v</tex>, где <tex>u, v \in \Sigma^{*}</tex>, то есть все листья помечены терминалами, за исключением одного, который совпадает с корнем дерева.<br />
<br />
Будем обозначать <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>.<br />
<br />
Пусть <tex>p</tex> называется ''базовым'', если оно <tex>\#</tex>-минимально среди всех <tex>p</tex>, то есть не содержит в себе другое <tex>p</tex>, которое можно вырезать. Или, иначе, <tex>p</tex> является базовым, если в <tex>s \# t</tex> <tex>s</tex> является только тривиальным деревом с одним узлом (который же является и корнем).<br />
<br />
{{Лемма<br />
|statement=<br />
Если <tex>p</tex> является базовым, то <tex>dep(p) \leqslant 2n</tex>, где <tex>n</tex> количество нетерминалов в N.<br />
|proof=<br />
Обозначим за <tex>\gamma</tex> путь от листа с нетерминалом <tex>root(p)</tex> до корня. Пусть <tex>\gamma</tex> не может быть длиннее, чем <tex>n</tex>, потому что если бы был, то он содержал бы повторяющийся нетерминал, и, тем самым, содержал бы в себе другое дерево <tex>p'</tex>, что противоречит тому, что <tex>p</tex> базовое.<br />
Для других же листов путь должен не превышать <tex>n+1</tex> по тем же причинам. Таким образом, длина любого пути не больше <tex>2n</tex>.<br />
}}<br />
Из леммы и из конечности нетерминалов и продукций в грамматике <tex>\Gamma</tex> следует, что количество таких базовых деревьев <tex>p</tex> конечно.<br />
<br />
{{Лемма<br />
|statement=<br />
Любое дерево разбора <tex>t</tex> с <tex>res(t) \in \Sigma^{*}</tex> либо <tex>\#</tex>-минимально, либо содержит в себе базовое <tex>p</tex>.<br />
|proof=<br />
Пусть <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>-минимальности.<br />
}}<br />
<br />
Пусть <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 />
<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>.<br />
<br />
{{Лемма<br />
|statement=<br />
Множество <tex>\{\Psi_{\Sigma}(t) \mid s \leqslant t\}</tex> линейно.<br />
|proof=<br />
<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>. <br />
}}<br />
<br />
Будем называть <tex>s</tex> <tex>\leqslant</tex>-минимальным, если оно не содержит в себе повторяющихся базовых <tex>p</tex>.<br />
{{Лемма<br />
|statement=<br />
Если <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> в дереве.<br />
|proof=<br />
Если путь длиннее, чем <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>-минимальности. <br />
}}<br />
<br />
{{Теорема<br />
|about=<br />
Парика, англ. ''Parikh's theorem''<br />
|statement=Если язык <tex>L \subset \Sigma^{*}</tex> является [[Контекстно-свободные грамматики, вывод, лево- и правосторонний вывод, дерево разбора|контекстно-свободным]], то множество <tex>\Psi_{\Sigma}(L)</tex> является полулинейным.<br />
|proof=<br />
<br />
Воспользуемся ранее полученными результатами в доказательстве.<br />
<br />
Зададим <tex>M = \{s \mid s</tex> <tex>\leqslant</tex>-минимально, <tex>root(s) = S, res(s) \in \Sigma^{*}\}</tex>. <br />
<br />
Покажем, что <tex>\Psi_{\Sigma}(L(\Gamma)) = \bigcup \limits_{s \in M} \{\Psi_{\Sigma}(t) \mid s \leqslant t\}</tex>. Это множество полулинейно по предпоследней и последней лемме (<tex>M</tex> по ней конечно, так как число базовых <tex>p</tex> конечно).<br />
Любое такое <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>.<br />
}}<br />
<br />
Теорема Парика связывает два понятия: функцию <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 />
<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>.<br />
<br />
==Примеры==<br />
<br />
Язык <tex>\{a^{p} \mid p</tex> {{---}} простое число<tex>\}</tex> не является контекстно-свободным, так как множество простых чисел не является полулинейным (в арифметике Пресбургера нельзя определить множество простых чисел).<br />
<br />
Язык <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> так же не полулинейно.<br />
<br />
== См. также ==<br />
*[[Лемма о разрастании для КС-грамматик|Лемма о разрастании для КС-грамматик]]<br />
*[[Доказательство нерегулярности языков: лемма о разрастании|Доказательство нерегулярности языков: лемма о разрастании]]<br />
<br />
==Примечания==<br />
<references/><br />
<br />
== Источники информации==<br />
*Гинзбург С. {{---}} Математическая теория контекстно-свободных языков<br />
*Dexter C. Kozen {{---}} Automata and Computability<br />
*[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?]<br />
<br />
[[Категория: Теория формальных языков]]<br />
[[Категория: Контекстно-свободные грамматики]]<br />
[[Категория: Опровержение контекстно-свободности языка]]</div>Alicehttp://neerc.ifmo.ru/wiki/index.php?title=%D0%A2%D0%B5%D0%BE%D1%80%D0%B5%D0%BC%D0%B0_%D0%9F%D0%B0%D1%80%D0%B8%D0%BA%D0%B0&diff=58402Теорема Парика2016-12-29T01:05:51Z<p>Alice: </p>
<hr />
<div>==Линейные множества==<br />
В этом разделе предполагается, что зафиксирован некоторый [[Отношение_порядка|линейный порядок]] на алфавите <tex>\Sigma</tex>. Пусть <tex>\Sigma = \{a_{1},\ldots,a_{m}\}</tex>.<br />
<br />
{{Определение<br />
|definition = <br />
Через <tex>\Psi_{\Sigma}</tex> будем обозначать функцию <tex>\Psi_{\Sigma} : \Sigma^{*} \rightarrow \mathbb {N}^{m}</tex>, определённую следующим образом: <tex>\Psi_{\Sigma}(w) = \langle |w|_{a_{1}} ,\ldots, |w|_{a_{m}} \rangle</tex>, где <tex>|w|_{a_{i}}</tex> {{---}} число появлений символа <tex>a_{i}</tex> в слове <tex>w</tex>. Аналогично, каждому языку <tex>L \subset \Sigma^{*}</tex> ставится в соответствие множество <tex>\Psi_{\Sigma}(L) \subset \mathbb {N}^{m}</tex>, определённое так: <tex>\Psi_{\Sigma}(L) = \{\Psi_{\Sigma}(w) \mid w \in L\}</tex>. Функция называется '''отображением Парика''' (англ. ''Parikh's mapping'') соответственно слова и языка.<br />
}}<br />
<br />
Пусть <tex>\Sigma = \{a, b\}</tex> и <tex>L = \{a, abb, bba\}</tex>. Тогда <tex>\Psi_{\Sigma}(L) = \{\langle 1, 0 \rangle, \langle 1, 2 \rangle\}</tex>.<br />
<br />
<br />
{{Определение<br />
|definition = <br />
Пусть <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>.<br />
}}<br />
<br />
Говоря проще, линейное подмножество <tex>\mathbb {N}^{m}</tex> может быть построено с помощью любого m-размерного вектора <tex>x_{0}</tex> добавлением к нему произвольного числа m-размерных векторов из конечного множества, например, 1 раз <tex>x_{1}</tex> и 0 раз остальные вектора, 1 раз <tex>x_{1}</tex>, 1 раз <tex>x_{2}</tex> и 0 раз остальные, и так далее.<br />
<br>Множество <tex>L = \{(0, 0) + k_{1}(0, 2) + k_{2}(2, 0) \mid k_{1},k_{2} \in \mathbb {N}\} </tex> <tex> = \{(2k_{1}, 2k_{2}) \mid k_{1},k_{2} \in \mathbb {N}\}</tex> является линейным.<br />
<br />
{{Определение<br />
|definition = <br />
Подмножество множества <tex>\mathbb {N}</tex> называется '''полулинейным''' (англ. ''semilinear''), если оно является объединением конечного числа линейных множеств.<br />
}}<br />
Полулинейное множество имеет следующие свойства:<br />
*Любое конечное подмножество <tex>\mathbb {N}^{m}</tex> {{---}} полулинейно.<br />
*Полулинейные множества замкнуты относительно операции объединения, пересечения, разности и проекции.<br />
*Полулинейные множества по теореме Гинзбурга-Спаниера (англ. ''Ginsburg and Spanier theorem'') {{---}} те, которые определяемы в арифметике Пресбургера (англ. ''Presburger arithmetic'')<ref>[https://en.wikipedia.org/wiki/Presburger_arithmetic Wikipedia {{---}} Presburger arithmetic]</ref>.<br />
<br />
Пусть <tex>L_{1} = (1, 2) + \{(3, 5), (7, 11)\}^{*}</tex>, <tex>L_{2} = (1, 1) + \{(2, 3), (5, 7), (4, 0)\}^{*}</tex>, <tex>L_{1}</tex> и <tex>L_{2}</tex> линейные подмножества <tex>\mathbb {N}^{2}</tex>, а <tex>L = L_{1} \cup L_{2}</tex> является полулинейным подмножеством <tex>\mathbb {N}^{2}</tex>.<br />
<br />
==Теорема Парика==<br />
<br />
Пусть <tex>\Gamma =\langle \Sigma, N, S, P\rangle</tex> {{---}} контекстно-свободная грамматика. <br />
<br />
Далее маленькими латинскими буквами <tex>s, t, \ldots</tex> будем обозначать деревья разбора. Для деревьев результатом (<tex>res(s)</tex>) будем называть строку из нетерминалов и терминалов, записанных в листьях, упорядоченную слева направо, глубина дерева (<tex>dep(s)</tex>) {{---}} длина наибольшего пути от листов до корня дерева, будем писать <tex>N(s)</tex>, чтобы обозначить множество нетерминалов в дереве, а <tex>root(s)</tex> {{---}} корень дерева.<br />
<br />
Обозначим за <tex>p</tex> деревья такого вида:<br />
# оно содержит хотя бы два узла.<br />
# <tex>res(p) = u * root(p) * v</tex>, где <tex>u, v \in \Sigma^{*}</tex>, то есть все листья помечены терминалами, за исключением одного, который совпадает с корнем дерева.<br />
<br />
Будем обозначать <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>.<br />
<br />
Пусть <tex>p</tex> называется ''базовым'', если оно <tex>\#</tex>-минимально среди всех <tex>p</tex>, то есть не содержит в себе другое <tex>p</tex>, которое можно вырезать. Или, иначе, <tex>p</tex> является базовым, если в <tex>s \# t</tex> <tex>s</tex> является только тривиальным деревом с одним узлом (который же является и корнем).<br />
<br />
{{Лемма<br />
|statement=<br />
Если <tex>p</tex> является базовым, то <tex>dep(p) \leqslant 2n</tex>, где <tex>n</tex> количество нетерминалов в N.<br />
|proof=<br />
Обозначим за <tex>\gamma</tex> путь от листа с нетерминалом <tex>root(p)</tex> до корня. Пусть <tex>\gamma</tex> не может быть длиннее, чем <tex>n</tex>, потому что если бы был, то он содержал бы повторяющийся нетерминал, и, тем самым, содержал бы в себе другое дерево <tex>p'</tex>, что противоречит тому, что <tex>p</tex> базовое.<br />
Для других же листов путь должен не превышать <tex>n+1</tex> по тем же причинам. Таким образом, длина любого пути не больше <tex>2n</tex>.<br />
}}<br />
Из леммы и из конечности нетерминалов и продукций в грамматике <tex>\Gamma</tex> следует, что количество таких базовых деревьев <tex>p</tex> конечно.<br />
<br />
{{Лемма<br />
|statement=<br />
Любое дерево разбора <tex>t</tex> с <tex>res(t) \in \Sigma^{*}</tex> либо <tex>\#</tex>-минимально, либо содержит в себе базовое <tex>p</tex>.<br />
|proof=<br />
Пусть <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>-минимальности.<br />
}}<br />
<br />
Пусть <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 />
<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>.<br />
<br />
{{Лемма<br />
|statement=<br />
Множество <tex>\{\Psi_{\Sigma}(t) \mid s \leqslant t\}</tex> линейно.<br />
|proof=<br />
<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>. <br />
}}<br />
<br />
Будем называть <tex>s</tex> <tex>\leqslant</tex>-минимальным, если оно не содержит в себе повторяющихся базовых <tex>p</tex>.<br />
{{Лемма<br />
|statement=<br />
Если <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> в дереве.<br />
|proof=<br />
Если путь длиннее, чем <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>-минимальности. <br />
}}<br />
<br />
{{Теорема<br />
|about=<br />
Парика, англ. ''Parikh's theorem''<br />
|statement=Если язык <tex>L \subset \Sigma^{*}</tex> является [[Контекстно-свободные грамматики, вывод, лево- и правосторонний вывод, дерево разбора|контекстно-свободным]], то множество <tex>\Psi_{\Sigma}(L)</tex> является полулинейным.<br />
|proof=<br />
<br />
Воспользуемся ранее полученными результатами в доказательстве.<br />
<br />
Зададим <tex>M = \{s \mid s</tex> <tex>\leqslant</tex>-минимально, <tex>root(s) = S, res(s) \in \Sigma^{*}\}</tex>. <br />
<br />
Покажем, что <tex>\Psi_{\Sigma}(L(\Gamma)) = \bigcup \limits_{s \in M} \{\Psi_{\Sigma}(t) \mid s \leqslant t\}</tex>. Это множество полулинейно по предпоследней и последней лемме (<tex>M</tex> по ней конечно, так как число базовых <tex>p</tex> конечно).<br />
Любое такое <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>.<br />
}}<br />
<br />
Теорема Парика связывает два понятия: функцию <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 />
<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>.<br />
<br />
==Примеры==<br />
<br />
Язык <tex>\{a^{p} \mid p</tex> {{---}} простое число<tex>\}</tex> не является контекстно-свободным, так как множество простых чисел не является полулинейным (в арифметике Пресбургера нельзя определить множество простых чисел).<br />
<br />
Язык <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> так же не полулинейно.<br />
<br />
== См. также ==<br />
*[[Лемма о разрастании для КС-грамматик|Лемма о разрастании для КС-грамматик]]<br />
*[[Доказательство нерегулярности языков: лемма о разрастании|Доказательство нерегулярности языков: лемма о разрастании]]<br />
<br />
==Примечания==<br />
<references/><br />
<br />
== Источники информации==<br />
*Гинзбург С. {{---}} Математическая теория контекстно-свободных языков<br />
*Dexter C. Kozen {{---}} Automata and Computability<br />
*[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?]<br />
<br />
[[Категория: Теория формальных языков]]<br />
[[Категория: Контекстно-свободные грамматики]]<br />
[[Категория: Опровержение контекстно-свободности языка]]</div>Alicehttp://neerc.ifmo.ru/wiki/index.php?title=%D0%A2%D0%B5%D0%BE%D1%80%D0%B8%D1%8F_%D1%84%D0%BE%D1%80%D0%BC%D0%B0%D0%BB%D1%8C%D0%BD%D1%8B%D1%85_%D1%8F%D0%B7%D1%8B%D0%BA%D0%BE%D0%B2&diff=58401Теория формальных языков2016-12-29T01:01:37Z<p>Alice: /* Опровержение контекстно-свободности языка */</p>
<hr />
<div>[[Категория: Теория формальных языков]]<br />
Символом <tex> \star </tex> помечены дополнительные темы (возможно, сложные), которые не были подробно рассмотрены (или вообще рассмотрены) в рамках курса.<br />
== Автоматы и регулярные языки ==<br />
=== Регулярные языки и ДКА ===<br />
*[[Основные определения: алфавит, слово, язык, конкатенация, свободный моноид слов; операции над языками]]<br />
*[[Регулярные языки: два определения и их эквивалентность | Регулярные языки: два определения и их эквивалентность, регулярные выражения]]<br />
*[[Детерминированные конечные автоматы]]<br />
*[[Прямое произведение ДКА]]<br />
*[[Простой сопоставитель регулярных выражений]] <tex> \star </tex><br />
<br />
=== НКА ===<br />
*[[Недетерминированные конечные автоматы]]<br />
*[[Построение по НКА эквивалентного ДКА, алгоритм Томпсона]]<br />
*[[Автоматы с eps-переходами. Eps-замыкание]]<br />
*[[Теорема Клини (совпадение классов автоматных и регулярных языков)]]<br />
*[[Альтернативное доказательство теоремы Клини (через систему уравнений в регулярных выражениях)]]<br />
=== Минимизация ДКА ===<br />
*[[Эквивалентность состояний ДКА]]<br />
*[[Минимизация ДКА, алгоритм за O(n^2) с построением пар различимых состояний]]<br />
*[[Минимизация ДКА, алгоритм Хопкрофта (сложность O(n log n))]]<br />
*[[Алгоритм Бржозовского]]<tex> ^\star </tex><br />
=== Свойства конечных автоматов ===<br />
*[[Доказательство нерегулярности языков: лемма о разрастании]]<br />
*[[Интерпретация булевых формул с кванторами как игр для двух игроков]]<br />
*[[Решение уравнений в регулярных выражениях]]<br />
*[[Замкнутость регулярных языков относительно различных операций]]<br />
*[[Анализ свойств регулярных языков (пустота, совпадение, включение, конечность, подсчет числа слов)]]<br />
*[[Контексты и синтаксические моноиды]]<br />
=== Другие автоматы ===<br />
*[[Локальные автоматы]]<tex> ^\star </tex><br />
*[[Двусторонний детерминированный конечный автомат]]<tex> ^\star </tex><br />
*[[Квантовые конечные автоматы]]<tex> ^\star </tex><br />
*[[Автоматы Мура и Мили]]<tex> ^\star </tex><br />
<br />
== Контекстно-свободные грамматики ==<br />
=== Базовые понятия о грамматиках ===<br />
*[[Формальные грамматики]]<br />
*[[Иерархия Хомского формальных грамматик]]<br />
*[[Неукорачивающие и контекстно-зависимые грамматики, эквивалентность]]<br />
*[[Правоконтекстные грамматики, эквивалентность автоматам]]<br />
*[[Контекстно-свободные грамматики, вывод, лево- и правосторонний вывод, дерево разбора]]<br />
*[[Замкнутость КС-языков относительно различных операций]]<br />
*[[Регулярная аппроксимация КС-языков]]<tex> ^\star </tex><br />
<br />
=== Нормальные формы КС-грамматик ===<br />
*[[Удаление бесполезных символов из грамматики]]<br />
*[[Удаление длинных правил из грамматики]]<br />
*[[Удаление eps-правил из грамматики]]<br />
*[[Удаление цепных правил из грамматики]]<br />
*[[Нормальная форма Хомского]]<br />
*[[Устранение левой рекурсии]]<br />
*[[Приведение грамматики к ослабленной нормальной форме Грейбах]]<br />
*[[Нормальная форма Куроды]]<tex> ^\star </tex><br />
<br />
=== Алгоритмы разбора ===<br />
*[[Алгоритм Кока-Янгера-Касами разбора грамматики в НФХ]]<br />
*[[Алгоритм Кока-Янгера-Касами, модификация для произвольной грамматики]]<br />
*[[Алгоритм Эрли]]<br />
*[[Алгоритм Эрли, доказательство оценки O(n^2) для однозначной грамматики]]<br />
<br />
=== Опровержение контекстно-свободности языка ===<br />
*[[Лемма о разрастании для КС-грамматик]]<br />
*[[Лемма Огдена]]<br />
*[[Существенно неоднозначные языки]]<br />
*[[Теорема Парика]]<br />
<br />
=== МП-автоматы ===<br />
*[[Автоматы с магазинной памятью]]<br />
*[[МП-автоматы, допуск по пустому стеку и по допускающему состоянию, эквивалентность]]<br />
*[[Совпадение множества языков МП-автоматов и контекстно-свободных языков]]<br />
*[[Детерминированные автоматы с магазинной памятью]]<br />
*[[Детерминированные автоматы с магазинной памятью, допуск по пустому стеку]]<br />
*[[Нормальная форма ДМП-автомата]]<br />
*[[Несовпадение класса языков, распознаваемых ДМП автоматами и произвольными МП автоматами]]<br />
*[[ДМП-автоматы и неоднозначность]]<br />
<br />
== Теория вычислимости ==<br />
=== Разрешимые и перечислимые языки ===<br />
*[[Разрешимые (рекурсивные) языки]]<br />
*[[Перечислимые языки]]<br />
*[[Замкнутость разрешимых и перечислимых языков относительно теоретико-множественных и алгебраических операций]]<br />
*[[Вычислимые функции]]<br />
*[[Вычислимые числа]]<br />
*[[Универсальная функция|Универсальная функция и главные нумерации]] <br />
*[[Свойства перечислимых языков. Теорема Успенского-Райса]]<br />
*[[Неотделимые множества]]<br />
*[[Иммунные и простые множества]]<br />
*[[Теорема о рекурсии]]<br />
*[[Квайны]]<tex> ^\star </tex><br />
*[[Busy beaver]]<br />
*[[Колмогоровская сложность]]<tex> ^\star </tex><br />
<br />
=== Вычислительные формализмы ===<br />
*[[Машина Тьюринга]]<br />
*[[Лямбда-исчисление]]<tex> ^\star </tex><br />
*[[Рекурсивные функции, представимость в формальной арифметике | Примитивно рекурсивные функции]]<tex> ^\star </tex><br />
*[[Частично рекурсивные функции]]<tex> ^\star </tex><br />
*[[Стековые машины, эквивалентность двухстековой машины МТ]]<br />
*[[Счетчиковые машины, эквивалентность двухсчетчиковой машины МТ]]<br />
*[[Линейный клеточный автомат, эквивалентность МТ]]<br />
*[[Возможность порождения формальной грамматикой произвольного перечислимого языка]]<br />
*[[Линейный ограниченный автомат]]<br />
*[[Сверхтьюринговые вычисления (гипервычисления)]]<tex> ^\star </tex><br />
<br />
=== Примеры неразрешимых задач ===<br />
*[[m-сводимость]]<br />
*[[Примеры неразрешимых задач: проблема соответствий Поста |Проблема соответствий Поста]]<br />
*[[Примеры неразрешимых задач: однозначность грамматики|Однозначность КС-грамматики]]<br />
*[[Неразрешимость задачи об эквивалентности КС-грамматик|Эквивалентность КС-грамматик]]<br />
*[[Примеры неразрешимых задач: задача о замощении|Задача о замощении полимино]]<br />
*[[Примеры неразрешимых задач: задача о выводе в полусистеме Туэ|Задача о выводе в полусистеме Туэ]]<br />
*[[Неразрешимость исчисления предикатов первого порядка]]<br />
*[[Неразрешимость проблемы существования решения диофантова уравнения в целых числах]]<br />
*[[Игра «Жизнь»]]<tex>^\star</tex><br />
*[[Неразрешимость игры Braid]]<tex>^\star</tex><br />
*[[Теорема Райса-Шапиро]]</div>Alicehttp://neerc.ifmo.ru/wiki/index.php?title=%D0%A2%D0%B5%D0%BE%D1%80%D0%B5%D0%BC%D0%B0_%D0%9F%D0%B0%D1%80%D0%B8%D0%BA%D0%B0&diff=58400Теорема Парика2016-12-29T01:00:46Z<p>Alice: </p>
<hr />
<div>==Линейные множества==<br />
В этом разделе предполагается, что зафиксирован некоторый [[Отношение_порядка|линейный порядок]] на алфавите <tex>\Sigma</tex>. Пусть <tex>\Sigma = \{a_{1},\ldots,a_{m}\}</tex>.<br />
<br />
{{Определение<br />
|definition = <br />
Через <tex>\Psi_{\Sigma}</tex> будем обозначать функцию <tex>\Psi_{\Sigma} : \Sigma^{*} \rightarrow \mathbb {N}^{m}</tex>, определённую следующим образом: <tex>\Psi_{\Sigma}(w) = \langle |w|_{a_{1}} ,\ldots, |w|_{a_{m}} \rangle</tex>, где <tex>|w|_{a_{i}}</tex> {{---}} число появлений символа <tex>a_{i}</tex> в слове <tex>w</tex>. Аналогично, каждому языку <tex>L \subset \Sigma^{*}</tex> ставится в соответствие множество <tex>\Psi_{\Sigma}(L) \subset \mathbb {N}^{m}</tex>, определённое так: <tex>\Psi_{\Sigma}(L) = \{\Psi_{\Sigma}(w) \mid w \in L\}</tex>. Функция называется '''отображением Парика''' (англ. ''Parikh's mapping'') соответственно слова и языка.<br />
}}<br />
<br />
Пусть <tex>\Sigma = \{a, b\}</tex> и <tex>L = \{a, abb, bba\}</tex>. Тогда <tex>\Psi_{\Sigma}(L) = \{\langle 1, 0 \rangle, \langle 1, 2 \rangle\}</tex>.<br />
<br />
<br />
{{Определение<br />
|definition = <br />
Пусть <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>.<br />
}}<br />
<br />
Говоря проще, линейное подмножество <tex>\mathbb {N}^{m}</tex> может быть построено с помощью любого m-размерного вектора <tex>x_{0}</tex> добавлением к нему произвольного числа m-размерных векторов из конечного множества, например, 1 раз <tex>x_{1}</tex> и 0 раз остальные вектора, 1 раз <tex>x_{1}</tex>, 1 раз <tex>x_{2}</tex> и 0 раз остальные, и так далее.<br />
<br>Множество <tex>L = \{(0, 0) + k_{1}(0, 2) + k_{2}(2, 0) \mid k_{1},k_{2} \in \mathbb {N}\} </tex> <tex> = \{(2k_{1}, 2k_{2}) \mid k_{1},k_{2} \in \mathbb {N}\}</tex> является линейным.<br />
<br />
{{Определение<br />
|definition = <br />
Подмножество множества <tex>\mathbb {N}</tex> называется '''полулинейным''' (англ. ''semilinear''), если оно является объединением конечного числа линейных множеств.<br />
}}<br />
Полулинейное множество имеет следующие свойства:<br />
*Любое конечное подмножество <tex>\mathbb {N}^{m}</tex> {{---}} полулинейно.<br />
*Полулинейные множества замкнуты относительно операции объединения, пересечения, разности и проекции.<br />
*Полулинейные множества по теореме Гинзбурга-Спаниера (англ. ''Ginsburg and Spanier theorem'') {{---}} те, которые определяемы в арифметике Пресбургера (англ. ''Presburger arithmetic'')<ref>[https://en.wikipedia.org/wiki/Presburger_arithmetic Wikipedia {{---}} Presburger arithmetic]</ref>.<br />
<br />
Пусть <tex>L_{1} = (1, 2) + \{(3, 5), (7, 11)\}^{*}</tex>, <tex>L_{2} = (1, 1) + \{(2, 3), (5, 7), (4, 0)\}^{*}</tex>, <tex>L_{1}</tex> и <tex>L_{2}</tex> линейные подмножества <tex>\mathbb {N}^{2}</tex>, а <tex>L = L_{1} \cup L_{2}</tex> является полулинейным подмножеством <tex>\mathbb {N}^{2}</tex>.<br />
<br />
==Теорема Парика==<br />
<br />
Пусть <tex>\Gamma =\langle \Sigma, N, S, P\rangle</tex> {{---}} контекстно-свободная грамматика. <br />
<br />
Далее маленькими латинскими буквами <tex>s, t, \ldots</tex> будем обозначать деревья разбора. Для деревьев результатом (<tex>res(s)</tex>) будем называть строку из нетерминалов и терминалов, записанных в листьях, упорядоченную слева направо, глубина дерева (<tex>dep(s)</tex>) {{---}} длина наибольшего пути от листов до корня дерева, будем писать <tex>N(s)</tex>, чтобы обозначить множество нетерминалов в дереве, а <tex>root(s)</tex> {{---}} корень дерева.<br />
<br />
Обозначим за <tex>p</tex> деревья такого вида:<br />
# оно содержит хотя бы два узла.<br />
# <tex>res(p) = u * root(p) * v</tex>, где <tex>u, v \in \Sigma^{*}</tex>, то есть все листья помечены терминалами, за исключением одного, который совпадает с корнем дерева.<br />
<br><br />
Будем обозначать <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>.<br />
<br />
Пусть <tex>p</tex> называется ''базовым'', если оно <tex>\#</tex>-минимально среди всех <tex>p</tex>, то есть не содержит в себе другое <tex>p</tex>, которое можно вырезать. Или, иначе, <tex>p</tex> является базовым, если в <tex>s \# t</tex> <tex>s</tex> является только тривиальным деревом с одним узлом (который же является и корнем).<br />
<br />
{{Лемма<br />
|statement=<br />
Если <tex>p</tex> является базовым, то <tex>dep(p) \leqslant 2n</tex>, где <tex>n</tex> количество нетерминалов в N.<br />
|proof=<br />
Обозначим за <tex>\gamma</tex> путь от листа с нетерминалом <tex>root(p)</tex> до корня. Пусть <tex>\gamma</tex> не может быть длиннее, чем <tex>n</tex>, потому что если бы был, то он содержал бы повторяющийся нетерминал, и, тем самым, содержал бы в себе другое дерево <tex>p'</tex>, что противоречит тому, что <tex>p</tex> базовое.<br />
Для других же листов путь должен не превышать <tex>n+1</tex> по тем же причинам. Таким образом, длина любого пути не больше <tex>2n</tex>.<br />
}}<br />
Из леммы и из конечности нетерминалов и продукций в грамматике <tex>\Gamma</tex> следует, что количество таких базовых деревьев <tex>p</tex> конечно.<br />
<br />
{{Лемма<br />
|statement=<br />
Любое дерево разбора <tex>t</tex> с <tex>res(t) \in \Sigma^{*}</tex> либо <tex>\#</tex>-минимально, либо содержит в себе базовое <tex>p</tex>.<br />
|proof=<br />
Пусть <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>-минимальности.<br />
}}<br />
<br />
Пусть <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 />
<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>.<br />
<br />
{{Лемма<br />
|statement=<br />
Множество <tex>\{\Psi_{\Sigma}(t) \mid s \leqslant t\}</tex> линейно.<br />
|proof=<br />
<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>. <br />
}}<br />
<br />
Будем называть <tex>s</tex> <tex>\leqslant</tex>-минимальным, если оно не содержит в себе повторяющихся базовых <tex>p</tex>.<br />
{{Лемма<br />
|statement=<br />
Если <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> в дереве.<br />
|proof=<br />
Если путь длиннее, чем <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>-минимальности. <br />
}}<br />
<br />
<br />
{{Теорема<br />
|about=<br />
Парика, англ. ''Parikh's theorem''<br />
|statement=Если язык <tex>L \subset \Sigma^{*}</tex> является [[Контекстно-свободные грамматики, вывод, лево- и правосторонний вывод, дерево разбора|контекстно-свободным]], то множество <tex>\Psi_{\Sigma}(L)</tex> является полулинейным.<br />
|proof=<br />
<br />
Воспользуемся ранее полученными результатами в доказательстве.<br />
<br />
Зададим <tex>M = \{s \mid s</tex> <tex>\leqslant</tex>-минимально, <tex>root(s) = S, res(s) \in \Sigma^{*}\}</tex>. <br />
<br />
Покажем, что <tex>\Psi_{\Sigma}(L(\Gamma)) = \bigcup \limits_{s \in M} \{\Psi_{\Sigma}(t) \mid s \leqslant t\}</tex>. Это множество полулинейно по предпоследней и последней лемме (<tex>M</tex> по ней конечно, так как число базовых <tex>p</tex> конечно).<br />
Любое такое <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>.<br />
<br />
<br />
}}<br />
<br />
Теорема Парика связывает два понятия: функцию <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 />
<br>Эта теорема, так же, как и лемма о накачке и лемма Огдена, не является достаточной: язык <tex>\{0^{n}1^{n}2^{n} \mid n \geq 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>.<br />
<br />
==Примеры==<br />
<br />
Язык <tex>\{a^{p} \mid p</tex> {{---}} простое число<tex>\}</tex> не является контекстно-свободным, так как множество простых чисел не является полулинейным (в арифметике Пресбургера нельзя определить множество простых чисел).<br />
<br />
Язык <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 \leqslant n\} = (0, 0) + \{(1, 1), (0, 1)\}</tex> {{---}} линейно, при этом множество простых чисел не является полулинейным, и, как следствие, множество <tex>\{m</tex> {{---}} простое и <tex>m \leqslant n\}</tex> не является полулинейным, <tex>\Psi_{\Sigma}</tex> так же не полулинейно.<br />
<br />
== См. также ==<br />
*[[Лемма о разрастании для КС-грамматик|Лемма о разрастании для КС-грамматик]]<br />
*[[Доказательство нерегулярности языков: лемма о разрастании|Доказательство нерегулярности языков: лемма о разрастании]]<br />
<br />
==Примечания==<br />
<references/><br />
<br />
== Источники информации==<br />
*Гинзбург С. {{---}} Математическая теория контекстно-свободных языков<br />
*Dexter C. Kozen {{---}} Automata and Computability<br />
*[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?]<br />
<br />
[[Категория: Теория формальных языков]]<br />
[[Категория: Контекстно-свободные грамматики]]<br />
[[Категория: Опровержение контекстно-свободности языка]]</div>Alicehttp://neerc.ifmo.ru/wiki/index.php?title=%D0%A2%D0%B5%D0%BE%D1%80%D0%B5%D0%BC%D0%B0_%D0%9F%D0%B0%D1%80%D0%B8%D0%BA%D0%B0&diff=58399Теорема Парика2016-12-29T00:57:38Z<p>Alice: </p>
<hr />
<div>==Линейные множества==<br />
В этом разделе предполагается, что зафиксирован некоторый [[Отношение_порядка|линейный порядок]] на алфавите <tex>\Sigma</tex>. Пусть <tex>\Sigma = \{a_{1},\ldots,a_{m}\}</tex>.<br />
<br />
{{Определение<br />
|definition = <br />
Через <tex>\Psi_{\Sigma}</tex> будем обозначать функцию <tex>\Psi_{\Sigma} : \Sigma^{*} \rightarrow \mathbb {N}^{m}</tex>, определённую следующим образом: <tex>\Psi_{\Sigma}(w) = \langle |w|_{a_{1}} ,\ldots, |w|_{a_{m}} \rangle</tex>, где <tex>|w|_{a_{i}}</tex> {{---}} число появлений символа <tex>a_{i}</tex> в слове <tex>w</tex>. Аналогично, каждому языку <tex>L \subset \Sigma^{*}</tex> ставится в соответствие множество <tex>\Psi_{\Sigma}(L) \subset \mathbb {N}^{m}</tex>, определённое так: <tex>\Psi_{\Sigma}(L) = \{\Psi_{\Sigma}(w) \mid w \in L\}</tex>. Функция называется '''отображением Парика''' (англ. ''Parikh's mapping'') соответственно слова и языка.<br />
}}<br />
<br />
Пусть <tex>\Sigma = \{a, b\}</tex> и <tex>L = \{a, abb, bba\}</tex>. Тогда <tex>\Psi_{\Sigma}(L) = \{\langle 1, 0 \rangle, \langle 1, 2 \rangle\}</tex>.<br />
<br />
<br />
{{Определение<br />
|definition = <br />
Пусть <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>.<br />
}}<br />
<br />
Говоря проще, линейное подмножество <tex>\mathbb {N}^{m}</tex> может быть построено с помощью любого m-размерного вектора <tex>x_{0}</tex> добавлением к нему произвольного числа m-размерных векторов из конечного множества, например, 1 раз <tex>x_{1}</tex> и 0 раз остальные вектора, 1 раз <tex>x_{1}</tex>, 1 раз <tex>x_{2}</tex> и 0 раз остальные, и так далее.<br />
<br>Множество <tex>L = \{(0, 0) + k_{1}(0, 2) + k_{2}(2, 0) \mid k_{1},k_{2} \in \mathbb {N}\} </tex> <tex> = \{(2k_{1}, 2k_{2}) \mid k_{1},k_{2} \in \mathbb {N}\}</tex> является линейным.<br />
<br />
{{Определение<br />
|definition = <br />
Подмножество множества <tex>\mathbb {N}</tex> называется '''полулинейным''' (англ. ''semilinear''), если оно является объединением конечного числа линейных множеств.<br />
}}<br />
Полулинейное множество имеет следующие свойства:<br />
*Любое конечное подмножество <tex>\mathbb {N}^{m}</tex> {{---}} полулинейно.<br />
*Полулинейные множества замкнуты относительно операции объединения, пересечения, разности и проекции.<br />
*Полулинейные множества по теореме Гинзбурга-Спаниера (англ. ''Ginsburg and Spanier theorem'') {{---}} те, которые определяемы в арифметике Пресбургера (англ. ''Presburger arithmetic'')<ref>[https://en.wikipedia.org/wiki/Presburger_arithmetic Wikipedia {{---}} Presburger arithmetic]</ref>.<br />
<br />
Пусть <tex>L_{1} = (1, 2) + \{(3, 5), (7, 11)\}^{*}</tex>, <tex>L_{2} = (1, 1) + \{(2, 3), (5, 7), (4, 0)\}^{*}</tex>, <tex>L_{1}</tex> и <tex>L_{2}</tex> линейные подмножества <tex>\mathbb {N}^{2}</tex>, а <tex>L = L_{1} \cup L_{2}</tex> является полулинейным подмножеством <tex>\mathbb {N}^{2}</tex>.<br />
<br />
==Теорема Парика==<br />
<br />
Пусть <tex>\Gamma =\langle \Sigma, N, S, P\rangle</tex> {{---}} контекстно-свободная грамматика. <br />
<br />
Далее маленькими латинскими буквами <tex>s, t, \ldots</tex> будем обозначать деревья разбора. Для деревьев результатом (<tex>res(s)</tex>) будем называть строку из нетерминалов и терминалов, записанных в листьях, упорядоченную слева направо, глубина дерева (<tex>dep(s)</tex>) {{---}} длина наибольшего пути от листов до корня дерева, будем писать <tex>N(s)</tex>, чтобы обозначить множество нетерминалов в дереве, а <tex>root(s)</tex> {{---}} корень дерева.<br />
<br />
Обозначим за <tex>p</tex> деревья такого вида:<br />
# оно содержит хотя бы два узла.<br />
# <tex>res(p) = u * root(p) * v</tex>, где <tex>u, v \in \Sigma^{*}</tex>, то есть все листья помечены терминалами, за исключением одного, который совпадает с корнем дерева.<br />
<br><br />
Будем обозначать <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>.<br />
<br />
Пусть <tex>p</tex> называется ''базовым'', если оно <tex>\#</tex>-минимально среди всех <tex>p</tex>, то есть не содержит в себе другое <tex>p</tex>, которое можно вырезать. Или, иначе, <tex>p</tex> является базовым, если в <tex>s \# t</tex> <tex>s</tex> является только тривиальным деревом с одним узлом (который же является и корнем).<br />
<br />
{{Лемма<br />
|statement=<br />
Если <tex>p</tex> является базовым, то <tex>dep(p) \leqslant 2n</tex>, где <tex>n</tex> количество нетерминалов в N.<br />
|proof=<br />
Обозначим за <tex>\gamma</tex> путь от листа с нетерминалом <tex>root(p)</tex> до корня. Пусть <tex>\gamma</tex> не может быть длиннее, чем <tex>n</tex>, потому что если бы был, то он содержал бы повторяющийся нетерминал, и, тем самым, содержал бы в себе другое дерево <tex>p'</tex>, что противоречит тому, что <tex>p</tex> базовое.<br />
Для других же листов путь должен не превышать <tex>n+1</tex> по тем же причинам. Таким образом, длина любого пути не больше <tex>2n</tex>.<br />
}}<br />
Из леммы и из конечности нетерминалов и продукций в грамматике <tex>\Gamma</tex> следует, что количество таких базовых деревьев <tex>p</tex> конечно.<br />
<br />
{{Лемма<br />
|statement=<br />
Любое дерево разбора <tex>t</tex> с <tex>res(t) \in \Sigma^{*}</tex> либо <tex>\#</tex>-минимально, либо содержит в себе базовое <tex>p</tex>.<br />
|proof=<br />
Пусть <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>-минимальности.<br />
}}<br />
<br />
Пусть <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 />
<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>.<br />
<br />
{{Лемма<br />
|statement=<br />
Множество <tex>\{\Psi_{\Sigma}(t) \mid s \leqslant t\}</tex> линейно.<br />
|proof=<br />
<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>. <br />
}}<br />
<br />
Будем называть <tex>s</tex> <tex>\leqslant</tex>-минимальным, если оно не содержит в себе повторяющихся базовых <tex>p</tex>.<br />
{{Лемма<br />
|statement=<br />
Если <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> в дереве.<br />
|proof=<br />
Если путь длиннее, чем <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>-минимальности. <br />
}}<br />
<br />
<br />
{{Теорема<br />
|about=<br />
Парика, англ. ''Parikh's theorem''<br />
|statement=Если язык <tex>L \subset \Sigma^{*}</tex> является [[Контекстно-свободные грамматики, вывод, лево- и правосторонний вывод, дерево разбора|контекстно-свободным]], то множество <tex>\Psi_{\Sigma}(L)</tex> является полулинейным.<br />
|proof=<br />
<br />
Воспользуемся ранее полученными результатами в доказательстве.<br />
<br />
Зададим <tex>M = \{s \mid s</tex> <tex>\leqslant</tex>-минимально, <tex>root(s) = S, res(s) \in \Sigma^{*}\}</tex>. <br />
<br />
Покажем, что <tex>\Psi_{\Sigma}(L(\Gamma)) = \bigcup \limits_{s \in M} \{\Psi_{\Sigma}(t) \mid s \leqslant t\}</tex>. Это множество полулинейно по предпоследней и последней лемме (<tex>M</tex> по ней конечно, так как число базовых <tex>p</tex> конечно).<br />
Любое такое <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>.<br />
<br />
<br />
}}<br />
<br />
Теорема Парика связывает два понятия: функцию <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 />
<br>Эта теорема, так же, как и лемма о накачке и лемма Огдена, не является достаточной: язык <tex>\{0^{n}1^{n}2^{n} \mid n \geq 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>.<br />
<br />
==Примеры==<br />
<br />
Язык <tex>\{a^{p} \mid p</tex> {{---}} простое число<tex>\}</tex> не является контекстно-свободным, так как множество простых чисел не является полулинейным (в арифметике Пресбургера нельзя определить множество простых чисел).<br />
<br />
Язык <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 \leqslant n\} = (0, 0) + \{(1, 1), (0, 1)\}</tex> {{---}} линейно, при этом множество простых чисел не является полулинейным, и, как следствие, множество <tex>\{m</tex> {{---}} простое и <tex>m \leqslant n\}</tex> не является полулинейным, <tex>\Psi_{\Sigma}</tex> так же не полулинейно.<br />
<br />
== См. также ==<br />
*[[Лемма о разрастании для КС-грамматик|Лемма о разрастании для КС-грамматик]]<br />
*[[Доказательство нерегулярности языков: лемма о разрастании|Доказательство нерегулярности языков: лемма о разрастании]]<br />
<br />
==Примечания==<br />
<references/><br />
<br />
== Источники информации==<br />
*Гинзбург С. {{---}} Математическая теория контекстно-свободных языков<br />
*[https://www8.cs.umu.se/kurser/TDBC92/VT06/final/3.pdf Håkan Lindqvist {{---}} Parikh’s theorem]<br />
*[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?]<br />
<br />
[[Категория: Теория формальных языков]]<br />
[[Категория: Контекстно-свободные грамматики]]<br />
[[Категория: Опровержение контекстно-свободности языка]]</div>Alicehttp://neerc.ifmo.ru/wiki/index.php?title=%D0%A2%D0%B5%D0%BE%D1%80%D0%B5%D0%BC%D0%B0_%D0%9F%D0%B0%D1%80%D0%B8%D0%BA%D0%B0&diff=58366Теорема Парика2016-12-27T21:29:37Z<p>Alice: </p>
<hr />
<div>==Линейные множества==<br />
В этом разделе предполагается, что зафиксирован некоторый [[Отношение_порядка|линейный порядок]] на алфавите <tex>\Sigma</tex>. Пусть <tex>\Sigma = \{a_{1},\ldots,a_{m}\}</tex>.<br />
<br />
{{Определение<br />
|definition = <br />
Через <tex>\Psi_{\Sigma}</tex> будем обозначать функцию <tex>\Psi_{\Sigma} : \Sigma^{*} \rightarrow \mathbb {N}^{m}</tex>, определённую следующим образом: <tex>\Psi_{\Sigma}(w) = \langle |w|_{a_{1}} ,\ldots, |w|_{a_{m}} \rangle</tex>, где <tex>|w|_{a_{i}}</tex> {{---}} число появлений символа <tex>a_{i}</tex> в слове <tex>w</tex>. Аналогично, каждому языку <tex>L \subset \Sigma^{*}</tex> ставится в соответствие множество <tex>\Psi_{\Sigma}(L) \subset \mathbb {N}^{m}</tex>, определённое так: <tex>\Psi_{\Sigma}(L) = \{\Psi_{\Sigma}(w) \mid w \in L\}</tex>. Функция называется '''отображением Парика''' (англ. ''Parikh's mapping'') соответственно слова и языка.<br />
}}<br />
<br />
Пусть <tex>\Sigma = \{a, b\}</tex> и <tex>L = \{a, abb, bba\}</tex>. Тогда <tex>\Psi_{\Sigma}(L) = \{\langle 1, 0 \rangle, \langle 1, 2 \rangle\}</tex>.<br />
<br />
<br />
{{Определение<br />
|definition = <br />
Пусть <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>.<br />
}}<br />
<br />
Говоря проще, линейное подмножество <tex>\mathbb {N}^{m}</tex> может быть построено с помощью любого m-размерного вектора <tex>x_{0}</tex> добавлением к нему произвольного числа m-размерных векторов из конечного множества, например, 1 раз <tex>x_{1}</tex> и 0 раз остальные вектора, 1 раз <tex>x_{1}</tex>, 1 раз <tex>x_{2}</tex> и 0 раз остальные, и так далее.<br />
<br>Множество <tex>L = \{(0, 0) + k_{1}(0, 2) + k_{2}(2, 0) \mid k_{1},k_{2} \in \mathbb {N}\} </tex> <tex> = \{(2k_{1}, 2k_{2}) \mid k_{1},k_{2} \in \mathbb {N}\}</tex> является линейным.<br />
<br />
{{Определение<br />
|definition = <br />
Подмножество множества <tex>\mathbb {N}</tex> называется '''полулинейным''' (англ. ''semilinear''), если оно является объединением конечного числа линейных множеств.<br />
}}<br />
Полулинейное множество имеет следующие свойства:<br />
*Любое конечное подмножество <tex>\mathbb {N}^{m}</tex> {{---}} полулинейно.<br />
*Полулинейные множества замкнуты относительно операции объединения, пересечения, разности и проекции.<br />
*Полулинейные множества по теореме Гинзбурга-Спаниера (англ. ''Ginsburg and Spanier theorem'') {{---}} те, которые определяемы в арифметике Пресбургера (англ. ''Presburger arithmetic'')<ref>[https://en.wikipedia.org/wiki/Presburger_arithmetic Wikipedia {{---}} Presburger arithmetic]</ref>.<br />
<br />
Пусть <tex>L_{1} = (1, 2) + \{(3, 5), (7, 11)\}^{*}</tex>, <tex>L_{2} = (1, 1) + \{(2, 3), (5, 7), (4, 0)\}^{*}</tex>, <tex>L_{1}</tex> и <tex>L_{2}</tex> линейные подмножества <tex>\mathbb {N}^{2}</tex>, а <tex>L = L_{1} \cup L_{2}</tex> является полулинейным подмножеством <tex>\mathbb {N}^{2}</tex>.<br />
<br />
==Теорема Парика==<br />
{{Теорема<br />
|about=<br />
Парика, англ. ''Parikh's theorem''<br />
|statement=Если язык <tex>L \subset \Sigma^{*}</tex> является [[Контекстно-свободные грамматики, вывод, лево- и правосторонний вывод, дерево разбора|контекстно-свободным]], то множество <tex>\Psi_{\Sigma}(L)</tex> является полулинейным.<br />
|proof=<br />
Пусть <tex>\Gamma =\langle \Sigma, N, S, P\rangle</tex> {{---}} контекстно-свободная грамматика. Вместо того, чтобы рассматривать <tex>L(\Gamma)</tex>, рассмотрим язык <tex>L^{\sim}(\Gamma)</tex>, содержащий только строки, порожденные выводами, в которых встречаются все нетерминалы грамматики.<br />
Так как теорема Парика говорит о том, что для <tex>L(\Gamma)</tex> множество <tex>\Psi_{\Sigma}(L)</tex> полулинейно, то же самое должно сохраняться и для <tex>L^{\sim}(\Gamma)</tex>.<br />
<br />
<br><br />
{{Лемма<br />
|statement=<br />
Если множество <tex>\Psi_{\Sigma}(L^{\sim}(\Gamma))</tex> полулинейно для всех контекстно-свободных языков, тогда множество <tex>\Psi_{\Sigma}(L(\Gamma))</tex> также полулинейно.<br />
|proof=<br />
Построим грамматики <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> также полулинейно.<br />
}}<br />
<br />
Стоит заметить, что число таких языков в лемме ограничено числом нетерминалов в грамматике: <tex>k = 2^{|N|} - 1</tex>. Вычитание происходит из-за того, что начальный нетерминал <tex>S</tex> не должен быть удален.<br />
<br />
<br><br />
Теперь же сосредоточимся на языке <tex>L^{\sim}(\Gamma)</tex>. Определим три множества деревьев разбора. <br />
{{Определение<br />
|definition = <br />
Пусть <tex>T</tex> {{---}} множество всех терминальных деревьев разбора с корнем <tex>S</tex>, которые удовлетворяют двум условиям:<br />
1. Каждый нетерминал <tex>N</tex> встречается в в дереве.<br />
2. Каждый нетерминал <tex>N</tex> встречается не более чем <tex>k = |N|</tex> раз в любом пути.<br />
}}<br />
Деревья из этого множества соотносятся с деревьями разбора языка <tex>L^{\sim}(\Gamma)</tex>, так как при выводе каждого слова из этого языка также используются все нетерминалы грамматики. В дальнейшем доказательстве <tex>T</tex> используется для определения отображения Парика языка <tex>L^{\sim}(\Gamma)</tex> как объединение индивидуальных отображений.<br />
<br />
В отличие от предыдущего определения, для следующего множества число <tex>k</tex> для любого нетерминала не ограничено.<br />
{{Определение<br />
|definition = <br />
Пусть <tex>T'</tex> {{---}} множество всех терминальных деревьев разбора с корнем <tex>S</tex>, которые удовлетворяют первому условию из предыдущего определения.<br />
}}<br />
<br />
Последнее множество соотносится с теми правилами грамматики, которые делают строку больше в процессе вывода, то есть <tex>A \Rightarrow uAv</tex>, где <tex>u, v \in \Sigma</tex>. Эти деревья могут быть использованы, чтобы увеличить дерево разбора в множестве <tex>T'</tex> замещением нетерминала <tex>A</tex> в некотором дереве <tex>t'</tex> на дерево из множества <tex>I</tex>, определение которого написано ниже.<br />
{{Определение<br />
|definition = <br />
Пусть <tex>I</tex> {{---}} множество всех деревьев разбора с корнем <tex>A \in N</tex>, содержащих только один нетерминальный лист, который также помечен как <tex>A</tex>. В дополнение, деревья разбора множества <tex>I</tex> должны удовлетворять условию 2 в определении <tex>T</tex>.<br />
}}<br />
В деревьях из этого множества могут содержаться другие нетерминалы, но главное, чтобы среди листов содержался только корневой. <br />
<br />
Можно заметить, что деревья из <tex>T</tex> и <tex>I</tex> имеют конечную высоту.<br />
<br />
<br><br />
Теперь перейдем к доказательству теоремы.<br />
<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> представляют возможные поддеревья, которые могут быть использованы для того, чтобы увеличить длину пути в некотором дереве. <br />
{{Лемма<br />
|statement=<br />
Для языка <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><br />
|proof=<br />
Можем заметить, пустая строка может быть удалена из множества <tex>W</tex>, так как она не влияет на суммирование. Обозначим объединение сумм в лемме как <tex>\Phi</tex>.<br />
Также заметим, что <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>.<br />
<br />
Доказывать лемму будем в две стадии по индукции.<br />
<br />
<tex>\Longrightarrow</tex> <tex>\Phi \subset L^{\sim}(\Gamma)</tex>.<br />
<br />
В этой части доказательства будет рассмотрен случай <tex>m = (m_{1},\ldots,m_{m}) \in \Phi \rightarrow m \in \Psi_{\Sigma}(L^{\sim}(\Gamma)</tex>.<br />
<br />
'''База индукции''':<br />
Пусть <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>. <br />
<br />
Предположим, что верно для некоторого <tex>m'</tex>, <tex>m' \in \Psi_{\Sigma}(L^{\sim}(\Gamma))</tex>.<br />
<br />
'''Шаг индукции''':<br />
Теперь пусть <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>.<br />
Кроме того, существует дерево <tex>t' \in I</tex>, порождающее <tex>u_{0}Av_{0}</tex>, такое, что <tex>u = u_{0}v_{0}</tex>. <br />
Построим дерево разбора, заменив некоторый узел <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>.<br />
<br />
<tex>\Longleftarrow</tex> <tex>L^{\sim}(\Gamma) \subset \Phi</tex>.<br />
<br />
В этой части будет доказано, что если <tex>t \in T'</tex>, и результатом <tex>w</tex>, то <tex>\Psi_{\Sigma}(w) \in \Phi</tex>.<br />
<br />
'''База индукции''':<br />
Если <tex>t \in T</tex>, то <tex>w = w_{i}</tex> для некоторого <tex>i</tex>, и значит <tex>\Psi_{\Sigma}(w) \in \Phi</tex>.<br />
<br />
Предположим, что утверждение сохраняется для всех деревьев в <tex>T'</tex>, меньших <tex>t</tex>. <br />
<br />
'''Шаг индукции''':<br />
Пусть <tex>p_{1}, \ldots, p_{k}</tex> будут узлами на некотором пути дерева, и пусть индекс каждого узла будет указывать на его относительную позицию на этом пути. Более того, пусть все узлы будут помечены одним и тем же нетерминалом <tex>A</tex>, чтобы все правильные поддеревья, у которых корнем является узел <tex>p_{1}</tex>, удовлетворяли условию 2 в определении <tex>T</tex>.<br />
<br />
}}<br />
<br />
}}<br />
<br />
Теорема Парика связывает два понятия: функцию <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 />
<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 />
<br />
==Примеры==<br />
<br />
Язык <tex>\{a^{p} \mid p</tex> {{---}} простое число<tex>\}</tex> не является контекстно-свободным, так как множество простых чисел не является полулинейным (в арифметике Пресбургера нельзя определить множество простых чисел).<br />
<br />
Язык <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> так же не полулинейно.<br />
<br />
== См. также ==<br />
*[[Лемма о разрастании для КС-грамматик|Лемма о разрастании для КС-грамматик]]<br />
*[[Доказательство нерегулярности языков: лемма о разрастании|Доказательство нерегулярности языков: лемма о разрастании]]<br />
<br />
==Примечания==<br />
<references/><br />
<br />
== Источники информации==<br />
*Гинзбург С. {{---}} Математическая теория контекстно-свободных языков<br />
*[https://www8.cs.umu.se/kurser/TDBC92/VT06/final/3.pdf Håkan Lindqvist {{---}} Parikh’s theorem]<br />
*[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?]<br />
<br />
[[Категория: Теория формальных языков]]<br />
[[Категория: Контекстно-свободные грамматики]]<br />
[[Категория: Опровержение контекстно-свободности языка]]</div>Alicehttp://neerc.ifmo.ru/wiki/index.php?title=%D0%A2%D0%B5%D0%BE%D1%80%D0%B5%D0%BC%D0%B0_%D0%9F%D0%B0%D1%80%D0%B8%D0%BA%D0%B0&diff=58153Теорема Парика2016-12-20T23:43:05Z<p>Alice: </p>
<hr />
<div>==Линейные множества==<br />
В этом разделе предполагается, что зафиксирован некоторый [[Отношение_порядка|линейный порядок]] на алфавите <tex>\Sigma</tex>. Пусть <tex>\Sigma = \{a_{1},\ldots,a_{m}\}</tex>.<br />
<br />
{{Определение<br />
|definition = <br />
Через <tex>\Psi_{\Sigma}</tex> будем обозначать функцию <tex>\Psi_{\Sigma} : \Sigma^{*} \rightarrow \mathbb {N}^{m}</tex>, определённую следующим образом: <tex>\Psi_{\Sigma}(w) = \langle |w|_{a_{1}} ,\ldots, |w|_{a_{m}} \rangle</tex>, где <tex>|w|_{a_{i}}</tex> {{---}} число появлений символа <tex>a_{i}</tex> в слове <tex>w</tex>. Аналогично, каждому языку <tex>L \subset \Sigma^{*}</tex> ставится в соответствие множество <tex>\Psi_{\Sigma}(L) \subset \mathbb {N}^{m}</tex>, определённое так: <tex>\Psi_{\Sigma}(L) = \{\Psi_{\Sigma}(w) \mid w \in L\}</tex>. Функция называется '''отображением Парика''' (англ. ''Parikh's mapping'') соответственно слова и языка.<br />
}}<br />
<br />
Пусть <tex>\Sigma = \{a, b\}</tex> и <tex>L = \{a, abb, bba\}</tex>. Тогда <tex>\Psi_{\Sigma}(L) = \{\langle 1, 0 \rangle, \langle 1, 2 \rangle\}</tex>.<br />
<br />
<br />
{{Определение<br />
|definition = <br />
Пусть <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>.<br />
}}<br />
<br />
Говоря проще, линейное подмножество <tex>\mathbb {N}^{m}</tex> может быть построено с помощью любого m-размерного вектора <tex>x_{0}</tex> добавлением к нему произвольного числа m-размерных векторов из конечного множества, например, 1 раз <tex>x_{1}</tex> и 0 раз остальные вектора, 1 раз <tex>x_{1}</tex>, 1 раз <tex>x_{2}</tex> и 0 раз остальные, и так далее.<br />
<br>Множество <tex>L = \{(0, 0) + k_{1}(0, 2) + k_{2}(2, 0) \mid k_{1},k_{2} \in \mathbb {N}\} </tex> <tex> = \{(2k_{1}, 2k_{2}) \mid k_{1},k_{2} \in \mathbb {N}\}</tex> является линейным.<br />
<br />
{{Определение<br />
|definition = <br />
Подмножество множества <tex>\mathbb {N}</tex> называется '''полулинейным''' (англ. ''semilinear''), если оно является объединением конечного числа линейных множеств.<br />
}}<br />
Полулинейное множество имеет следующие свойства:<br />
*Любое конечное подмножество <tex>\mathbb {N}^{m}</tex> {{---}} полулинейно.<br />
*Полулинейные множества замкнуты относительно операции объединения, пересечения, разности и проекции.<br />
*Полулинейные множества по теореме Гинзбурга-Спаниера (англ. ''Ginsburg and Spanier theorem'') {{---}} те, которые определяемы в арифметике Пресбургера (англ. ''Presburger arithmetic'')<ref>[https://en.wikipedia.org/wiki/Presburger_arithmetic Wikipedia {{---}} Presburger arithmetic]</ref>.<br />
<br />
Пусть <tex>L_{1} = (1, 2) + \{(3, 5), (7, 11)\}^{*}</tex>, <tex>L_{2} = (1, 1) + \{(2, 3), (5, 7), (4, 0)\}^{*}</tex>, <tex>L_{1}</tex> и <tex>L_{2}</tex> линейные подмножества <tex>\mathbb {N}^{2}</tex>, а <tex>L = L_{1} \cup L_{2}</tex> является полулинейным подмножеством <tex>\mathbb {N}^{2}</tex>.<br />
<br />
==Теорема Парика==<br />
{{Теорема<br />
|about=<br />
Парика, англ. ''Parikh's theorem''<br />
|statement=Если язык <tex>L \subset \Sigma^{*}</tex> является [[Контекстно-свободные грамматики, вывод, лево- и правосторонний вывод, дерево разбора|контекстно-свободным]], то множество <tex>\Psi_{\Sigma}(L)</tex> является полулинейным.<br />
|proof=<br />
Пусть <tex>\Gamma =\langle \Sigma, N, S, P\rangle</tex> {{---}} контекстно-свободная грамматика. Вместо того, чтобы рассматривать <tex>L(\Gamma)</tex>, рассмотрим язык <tex>L^{\sim}(\Gamma)</tex>, содержащий только строки, порожденные выводами, в которых встречаются все нетерминалы грамматики.<br />
Так как теорема Парика говорит о том, что для <tex>L(\Gamma)</tex> множество <tex>\Psi_{\Sigma}(L)</tex> полулинейно, то же самое должно сохраняться и для <tex>L^{\sim}(\Gamma)</tex>.<br />
<br />
<br><br />
{{Лемма<br />
|statement=<br />
Если множество <tex>\Psi_{\Sigma}(L^{\sim}(\Gamma))</tex> полулинейно для всех контекстно-свободных языков, тогда множество <tex>\Psi_{\Sigma}(L(\Gamma))</tex> также полулинейно.<br />
|proof=<br />
Построим грамматики <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> также полулинейно.<br />
}}<br />
<br />
Стоит заметить, что число таких языков в лемме ограничено числом нетерминалов в грамматике: <tex>k = 2^{|N|} - 1</tex>. Вычитание происходит из-за того, что начальный нетерминал <tex>S</tex> не должен быть удален.<br />
<br />
<br><br />
Теперь определим три множества деревьев разбора. <br />
{{Определение<br />
|definition = <br />
Пусть <tex>T</tex> {{---}} множество всех терминальных деревьев разбора с корнем <tex>S</tex>, которые удовлетворяют двум условиям:<br />
1. Каждый нетерминал <tex>N</tex> встречается в в дереве.<br />
2. Каждый нетерминал <tex>N</tex> встречается не более чем <tex>k = |N|</tex> раз в любом пути.<br />
}}<br />
Деревья из этого множества соотносятся с деревьями разбора языка <tex>L^{\sim}(\Gamma)</tex>, так как при выводе каждого слова из этого языка также используются все нетерминалы грамматики. В дальнейшем доказательстве <tex>T</tex> используется для определения отображения Парика языка <tex>L^{\sim}(\Gamma)</tex> как объединение индивидуальных отображений.<br />
<br />
В отличие от предыдущего определения, для следующего множества число <tex>k</tex> для любого нетерминала не ограничено.<br />
{{Определение<br />
|definition = <br />
Пусть <tex>T'</tex> {{---}} множество всех терминальных деревьев разбора с корнем <tex>S</tex>, которые удовлетворяют первому условию из предыдущего определения.<br />
}}<br />
<br />
Последнее множество относится к тем правилам грамматики, которые делают строку больше в процессе вывода, то есть <tex>A \Rightarrow uAv</tex>, где <tex>u, v \in \Sigma</tex>. Эти деревья могут быть использованы, чтобы увеличить дерево разбора в множестве <tex>T'</tex> замещением нетерминала <tex>A</tex> в некотором дереве <tex>t'</tex> на дерево из множества <tex>I</tex>, определение которого написано ниже.<br />
{{Определение<br />
|definition = <br />
Пусть <tex>I</tex> {{---}} множество всех деревьев разбора с корнем <tex>A \in N</tex>, содержащих только один нетерминальный лист, который также помечен как <tex>A</tex>.<br />
}}<br />
В дополнение, деревья разбора множества <tex>I</tex> должны удовлетворять условию 2 в определении <tex>T</tex>. Еще можно заметить, что деревья из <tex>T</tex> и <tex>I</tex> имеют конечную высоту.<br />
<br />
<br><br />
Теперь перейдем к доказательству теоремы.<br />
<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> представляют возможные поддеревья, которые могут быть использованы для того, чтобы увеличить длину пути в некотором дереве. <br />
{{Лемма<br />
|statement=<br />
Для языка <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><br />
|proof=<br />
Можем заметить, пустая строка может быть удалена из множества <tex>W</tex>, так как она не влияет на суммирование. Обозначим объединение сумм в лемме как <tex>\Phi</tex>.<br />
Также заметим, что <tex>\Psi_{\Sigma}(w_{i})</tex> является некоторым вектором размера <tex>m</tex>, <tex>W</tex> состоит из конечного набора строк (так как количество нетерминалов конечно, размер грамматики тоже конечен, тогда множество таких <tex>uv: A \rightarrow uAv</tex> для любого нетерминала A не может быть бесконечным, а значит и объединение таких <tex>uv</tex> для конечного числа нетерминалов конечно, и, следовательно, <tex>W</tex> конечно), <tex>\Psi_{\Sigma}(W)</tex> {{---}} конечный набор векторов размера <tex>m</tex>, и значит каждая такая сумма будет являться полулинейным множеством, а объединение полулинейных множеств полулинейно, в следствие чего можно сказать, что <tex>L^{\sim}(\Gamma)</tex> полулинейно, и далее по первой лемме полулинеен будет язык <tex>L(\Gamma)</tex>.<br />
<br />
Доказывать лемму будем в две стадии по индукции.<br />
<br />
<tex>\Longrightarrow</tex> <br />
<br />
<tex>\Phi \subset L^{\sim}(\Gamma)</tex>.<br />
<br />
В этой части доказательства будет рассмотрен случай <tex>m = (m_{1},\ldots,m_{m}) \in \Phi \rightarrow m \in \Psi_{\Sigma}(L^{\sim}(\Gamma)</tex>.<br />
<br />
<tex>\Longleftarrow</tex> <tex>L^{\sim}(\Gamma) \subset \Phi</tex>.<br />
<br />
}}<br />
<br />
}}<br />
<br />
Теорема Парика связывает два понятия: функцию <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 />
<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 />
<br />
==Примеры==<br />
<br />
Язык <tex>\{a^{p} \mid p</tex> {{---}} простое число<tex>\}</tex> не является контекстно-свободным, так как множество простых чисел не является полулинейным (в арифметике Пресбургера нельзя определить множество простых чисел).<br />
<br />
Язык <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> так же не полулинейно.<br />
<br />
== См. также ==<br />
*[[Лемма о разрастании для КС-грамматик|Лемма о разрастании для КС-грамматик]]<br />
*[[Доказательство нерегулярности языков: лемма о разрастании|Доказательство нерегулярности языков: лемма о разрастании]]<br />
<br />
==Примечания==<br />
<references/><br />
<br />
== Источники информации==<br />
*Гинзбург С. {{---}} Математическая теория контекстно-свободных языков<br />
*[https://www8.cs.umu.se/kurser/TDBC92/VT06/final/3.pdf Håkan Lindqvist {{---}} Parikh’s theorem]<br />
*[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?]<br />
<br />
[[Категория: Теория формальных языков]]<br />
[[Категория: Контекстно-свободные грамматики]]<br />
[[Категория: Опровержение контекстно-свободности языка]]</div>Alicehttp://neerc.ifmo.ru/wiki/index.php?title=%D0%A2%D0%B5%D0%BE%D1%80%D0%B5%D0%BC%D0%B0_%D0%9F%D0%B0%D1%80%D0%B8%D0%BA%D0%B0&diff=58148Теорема Парика2016-12-20T22:28:30Z<p>Alice: </p>
<hr />
<div>==Линейные множества==<br />
В этом разделе предполагается, что зафиксирован некоторый [[Отношение_порядка|линейный порядок]] на алфавите <tex>\Sigma</tex>. Пусть <tex>\Sigma = \{a_{1},\ldots,a_{m}\}</tex>.<br />
<br />
{{Определение<br />
|definition = <br />
Через <tex>\Psi_{\Sigma}</tex> будем обозначать функцию <tex>\Psi_{\Sigma} : \Sigma^{*} \rightarrow \mathbb {N}^{m}</tex>, определённую следующим образом: <tex>\Psi_{\Sigma}(w) = \langle |w|_{a_{1}} ,\ldots, |w|_{a_{m}} \rangle</tex>, где <tex>|w|_{a_{i}}</tex> {{---}} число появлений символа <tex>a_{i}</tex> в слове <tex>w</tex>. Аналогично, каждому языку <tex>L \subset \Sigma^{*}</tex> ставится в соответствие множество <tex>\Psi_{\Sigma}(L) \subset \mathbb {N}^{m}</tex>, определённое так: <tex>\Psi_{\Sigma}(L) = \{\Psi_{\Sigma}(w) \mid w \in L\}</tex>.<br />
}}<br />
<br />
Пусть <tex>\Sigma = \{a, b\}</tex> и <tex>L = \{a, abb, bba\}</tex>. Тогда <tex>\Psi_{\Sigma}(L) = \{\langle 1, 0 \rangle, \langle 1, 2 \rangle\}</tex>.<br />
<br />
<br />
{{Определение<br />
|definition = <br />
Пусть <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>.<br />
}}<br />
<br />
Говоря проще, линейное подмножество <tex>\mathbb {N}^{m}</tex> может быть построено с помощью любого m-размерного вектора <tex>x_{0}</tex> добавлением к нему произвольного числа m-размерных векторов из конечного множества, например, 1 раз <tex>x_{1}</tex> и 0 раз остальные вектора, 1 раз <tex>x_{1}</tex>, 1 раз <tex>x_{2}</tex> и 0 раз остальные, и так далее.<br />
<br>Множество <tex>L = \{(0, 0) + k_{1}(0, 2) + k_{2}(2, 0) \mid k_{1},k_{2} \in \mathbb {N}\} </tex> <tex> = \{(2k_{1}, 2k_{2}) \mid k_{1},k_{2} \in \mathbb {N}\}</tex> является линейным.<br />
<br />
{{Определение<br />
|definition = <br />
Подмножество множества <tex>\mathbb {N}</tex> называется '''полулинейным''' (англ. ''semilinear''), если оно является объединением конечного числа линейных множеств.<br />
}}<br />
Полулинейное множество имеет следующие свойства:<br />
*Любое конечное подмножество <tex>\mathbb {N}^{m}</tex> {{---}} полулинейно.<br />
*Полулинейные множества замкнуты относительно операции объединения, пересечения, разности и проекции.<br />
*Полулинейные множества по теореме Гинзбурга-Спаниера (англ. ''Ginsburg and Spanier theorem'') {{---}} те, которые определяемы в арифметике Пресбургера (англ. ''Presburger arithmetic'')<ref>[https://en.wikipedia.org/wiki/Presburger_arithmetic Wikipedia {{---}} Presburger arithmetic]</ref>.<br />
<br />
Пусть <tex>L_{1} = (1, 2) + \{(3, 5), (7, 11)\}^{*}</tex>, <tex>L_{2} = (1, 1) + \{(2, 3), (5, 7), (4, 0)\}^{*}</tex>, <tex>L_{1}</tex> и <tex>L_{2}</tex> линейные подмножества <tex>\mathbb {N}^{2}</tex>, а <tex>L = L_{1} \cup L_{2}</tex> является полулинейным подмножеством <tex>\mathbb {N}^{2}</tex>.<br />
<br />
==Теорема Парика==<br />
{{Теорема<br />
|about=<br />
Парика, англ. ''Parikh's theorem''<br />
|statement=Если язык <tex>L \subset \Sigma^{*}</tex> является [[Контекстно-свободные грамматики, вывод, лево- и правосторонний вывод, дерево разбора|контекстно-свободным]], то множество <tex>\Psi_{\Sigma}(L)</tex> является полулинейным.<br />
|proof=<br />
Пусть <tex>\Gamma =\langle \Sigma, N, S, P\rangle</tex> {{---}} контекстно-свободная грамматика. Вместо того, чтобы рассматривать <tex>L(\Gamma)</tex>, рассмотрим язык <tex>L^{\sim}(\Gamma)</tex>, содержащий только строки, порожденные выводами, в которых встречаются все нетерминалы грамматики.<br />
Так как теорема Парика говорит о том, что для <tex>L(\Gamma)</tex> множество <tex>\Psi_{\Sigma}(L)</tex> полулинейно, то же самое должно сохраняться и для <tex>L^{\sim}(\Gamma)</tex>.<br />
<br />
<br><br />
{{Лемма<br />
|statement=<br />
Если множество <tex>\Psi_{\Sigma}(L^{\sim}(\Gamma))</tex> полулинейно для всех контекстно-свободных языков, тогда множество <tex>\Psi_{\Sigma}(L(\Gamma))</tex> также полулинейно.<br />
|proof=<br />
Построим грамматики <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> также полулинейно.<br />
}}<br />
<br />
Стоит заметить, что число таких языков в лемме ограничено числом нетерминалов в грамматике: <tex>k = 2^{|N|} - 1</tex>. Вычитание происходит из-за того, что начальный нетерминал <tex>S</tex> не должен быть удален.<br />
<br />
<br><br />
Теперь определим три множества деревьев разбора. <br />
{{Определение<br />
|definition = <br />
Пусть <tex>T</tex> {{---}} множество всех терминальных деревьев разбора с корнем <tex>S</tex>, которые удовлетворяют двум условиям:<br />
1. Каждый нетерминал <tex>N</tex> встречается в в дереве.<br />
2. Каждый нетерминал <tex>N</tex> встречается не более чем <tex>k = |N|</tex> раз в дереве.<br />
}}<br />
Деревья из этого множества соотносятся с деревьями разбора языка <tex>L^{\sim}(\Gamma)</tex>, так как при выводе каждого слова из этого языка также используются все нетерминалы грамматики.<br />
<br />
В отличие от предыдущего определения, для следующего множества число <tex>k</tex> для любого нетерминала не ограничено.<br />
{{Определение<br />
|definition = <br />
Пусть <tex>T'</tex> {{---}} множество всех терминальных деревьев разбора с корнем <tex>S</tex>, которые удовлетворяют первому условию из предыдущего определения.<br />
}}<br />
<br />
Последнее множество относится к тем правилам грамматики, которые делают строку больше в процессе вывода, то есть <tex>A \Rightarrow uAv</tex>, где <tex>u, v \in \Sigma</tex>. Эти деревья могут быть использованы, чтобы увеличить дерево разбора в множестве <tex>T'</tex> замещением нетерминала <tex>A</tex> в некотором дереве <tex>t'</tex> на дерево из множества <tex>I</tex>, определение которого написано ниже.<br />
{{Определение<br />
|definition = <br />
Пусть <tex>I</tex> {{---}} множество всех деревьев разбора с корнем <tex>A \in N</tex>, содержащих только один нетерминальный лист, который также помечен как <tex>A</tex>.<br />
}}<br />
В дополнение, деревья разбора множества <tex>I</tex> должны удовлетворять условию 2 в определении <tex>T</tex>. Еще можно заметить, что деревья из <tex>T</tex> и <tex>I</tex> имеют конечную высоту.<br />
<br />
<br><br />
Теперь перейдем к доказательству теоремы.<br />
<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> представляют возможные поддеревья, которые могут быть использованы для того, чтобы увеличить длину пути в некотором дереве. <br />
{{Лемма<br />
|statement=<br />
Для языка <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><br />
|proof=<br />
Можем заметить, пустая строка может быть удалена из множества <tex>W</tex>, так как она не влияет на суммирование. Обозначим объединение сумм в лемме как <tex>\Phi</tex>.<br />
<br />
Доказывать лемму будем в две стадии по индукции.<br />
<br />
<tex>\Longrightarrow</tex> <tex>\Phi \subset L^{\sim}(\Gamma)</tex>.<br />
<br />
<br />
<tex>\Longleftarrow</tex> <tex>L^{\sim}(\Gamma) \subset \Phi</tex>.<br />
<br />
}}<br />
<br />
}}<br />
<br />
Теорема Парика связывает два понятия: функцию <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 />
<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 />
<br />
==Примеры==<br />
<br />
Язык <tex>\{a^{p} \mid p</tex> {{---}} простое число<tex>\}</tex> не является контекстно-свободным, так как множество простых чисел не является полулинейным (в арифметике Пресбургера нельзя определить множество простых чисел).<br />
<br />
Язык <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> так же не полулинейно.<br />
<br />
== См. также ==<br />
*[[Лемма о разрастании для КС-грамматик|Лемма о разрастании для КС-грамматик]]<br />
*[[Доказательство нерегулярности языков: лемма о разрастании|Доказательство нерегулярности языков: лемма о разрастании]]<br />
<br />
==Примечания==<br />
<references/><br />
<br />
== Источники информации==<br />
*Гинзбург С. {{---}} Математическая теория контекстно-свободных языков<br />
*[https://www8.cs.umu.se/kurser/TDBC92/VT06/final/3.pdf Håkan Lindqvist {{---}} Parikh’s theorem]<br />
*[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?]<br />
<br />
[[Категория: Теория формальных языков]]<br />
[[Категория: Контекстно-свободные грамматики]]<br />
[[Категория: Опровержение контекстно-свободности языка]]</div>Alicehttp://neerc.ifmo.ru/wiki/index.php?title=%D0%A2%D0%B5%D0%BE%D1%80%D0%B5%D0%BC%D0%B0_%D0%9F%D0%B0%D1%80%D0%B8%D0%BA%D0%B0&diff=58147Теорема Парика2016-12-20T21:51:36Z<p>Alice: </p>
<hr />
<div>==Используемые определения==<br />
В этом разделе предполагается, что зафиксирован некоторый линейный порядок на алфавите <tex>\Sigma</tex>. Пусть <tex>\Sigma = \{a_{1},...,a_{m}\}</tex>.<br />
<br />
{{Определение<br />
|definition = <br />
Через <tex>\Psi_{\Sigma}</tex> будем обозначать функцию <tex>\Psi_{\Sigma} : \Sigma^{*} \rightarrow \mathbb {N}^{m}</tex>, определённую следующим образом: <tex>\Psi_{\Sigma}(w) = \langle |w|_{a_{1}} ,..., |w|_{a_{m}} \rangle</tex>, где <tex>|w|_{a_{i}}</tex> {{---}} количество появлений символа <tex>a_{i}</tex> в слове <tex>w</tex>. Аналогично, каждому языку <tex>L \subset \Sigma^{*}</tex> ставится в соответствие множество <tex>\Psi_{\Sigma}(L) \subset \mathbb {N}^{m}</tex>, определённое так: <tex>\Psi_{\Sigma}(L) = \{\Psi_{\Sigma}(w) \mid w \in L\}</tex>.<br />
}}<br />
<br />
Пусть <tex>\Sigma = \{a, b\}</tex> и <tex>L = \{a, abb, bba\}</tex>. Тогда <tex>\Psi_{\Sigma}(L) = \{\langle 1, 0 \rangle, \langle 1, 2 \rangle\}</tex>.<br />
<br />
<br />
{{Определение<br />
|definition = <br />
Пусть <tex>x_{0}, x_{1},..., x_{p}</tex> при <tex>0 \leq 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},...,k_{p} \in \mathbb {N}\} = x_{0} + \{x_{1},..., x_{p}\}^{*}</tex> называется '''линейным''' (англ. ''linear'') подмножеством множества <tex>\mathbb {N}^{m}</tex>.<br />
}}<br />
<br />
Говоря проще, линейное подмножество <tex>\mathbb {N}^{m}</tex> может быть построено с помощью любого m-размерного вектора <tex>x_{0}</tex> добавлением к нему произвольного числа m-размерных векторов из конечного множества, например, 1 раз <tex>x_{1}</tex> и 0 раз остальные вектора, 1 раз <tex>x_{1}</tex>, 1 раз <tex>x_{2}</tex> и 0 раз остальные, и так далее.<br />
<br>Множество <tex>L = \{(0, 0) + k_{1}(0, 2) + k_{2}(2, 0) \mid k_{1},k_{2} \in \mathbb {N}\} </tex> <tex> = \{(2k_{1}, 2k_{2}) \mid k_{1},k_{2} \in \mathbb {N}\}</tex> является линейным.<br />
<br />
{{Определение<br />
|definition = <br />
Подмножество множества <tex>\mathbb {N}</tex> называется '''полулинейным''' (англ. ''semilinear''), если оно является объединением конечного числа линейных множеств.<br />
}}<br />
*Любое конечное подмножество <tex>\mathbb {N}^{m}</tex> {{---}} полулинейно.<br />
*Полулинейные множества замкнуты относительно операции объединения, пересечения, разности и проекции.<br />
*Полулинейные множества по теореме Гинзбурга-Спаниера (англ. ''Ginsburg and Spanier theorem'') {{---}} те, которые определяемы в арифметика Пресбургера (англ. ''Presburger arithmetic'').<br />
<br />
Пусть <tex>L_{1} = (1, 2) + \{(3, 5), (7, 11)\}^{*}</tex>, <tex>L_{2} = (1, 1) + \{(2, 3), (5, 7), (4, 0)\}^{*}</tex>, <tex>L_{1}</tex> и <tex>L_{2}</tex> линейные подмножества <tex>\mathbb {N}^{2}</tex>, а <tex>L = L_{1} \cup L_{2}</tex> является полулинейным подмножеством <tex>\mathbb {N}^{2}</tex>.<br />
<br />
==Теорема Парика==<br />
{{Теорема<br />
|about=<br />
Парика, англ. ''Parikh's theorem''<br />
|statement=Если язык <tex>L \subset \Sigma^{*}</tex> является [[Контекстно-свободные грамматики, вывод, лево- и правосторонний вывод, дерево разбора|контекстно-свободным]], то множество <tex>\Psi_{\Sigma}(L)</tex> является полулинейным.<br />
|proof=<br />
Пусть <tex>\Gamma =\langle \Sigma, N, S, P\rangle</tex> {{---}} контекстно-свободная грамматика. Вместо того, чтобы рассматривать <tex>L(\Gamma)</tex>, рассмотрим язык <tex>L^{\sim}(\Gamma)</tex>, содержащий только строки, порожденные выводами, в которых встречаются все нетерминалы грамматики.<br />
Так как теорема Парика говорит о том, что для <tex>L(\Gamma)</tex> множество <tex>\Psi_{\Sigma}(L)</tex> полулинейно, то же самое должно сохраняться и для <tex>L^{\sim}(\Gamma)</tex>.<br />
<br />
<br><br />
{{Лемма<br />
|statement=<br />
Если множество <tex>\Psi_{\Sigma}(L^{\sim}(\Gamma))</tex> полулинейно для всех контекстно-свободных языков, тогда множество <tex>\Psi_{\Sigma}(L(\Gamma))</tex> также полулинейно.<br />
|proof=<br />
Построим грамматики <tex>\Gamma_{1},...\Gamma_{k}</tex> для какого-то <tex>k \in \mathbb {N}^{+}</tex> путем удаления из грамматики <tex>\Gamma</tex> нетерминалов. Тогда <tex>L(\Gamma) = L^{\sim}(\Gamma_{1}) \cup ... \cup L^{\sim}(\Gamma_{k})</tex>. Так как для каждого из языков <tex>L^{\sim}(\Gamma_{p})</tex> множество <tex>\Psi_{\Sigma}</tex> полулинейно, то, по свойствам полулинейных множеств, для <tex>L(\Gamma)</tex> <tex>\Psi_{\Sigma}</tex> также полулинейно.<br />
}}<br />
<br />
Стоит заметить, что число таких языков в лемме ограничено числом нетерминалов в грамматике: <tex>k = 2^{|N|} - 1</tex>. Вычитание происходит из-за того, что начальный нетерминал <tex>S</tex> не должен быть удален.<br />
<br />
<br><br />
Теперь определим три множества деревьев разбора. <br />
{{Определение<br />
|definition = <br />
Пусть <tex>T</tex> {{---}} множество всех терминальных деревьев разбора с корнем <tex>S</tex>, которые удовлетворяют двум условиям:<br />
1. Каждый нетерминал <tex>N</tex> встречается в в дереве.<br />
2. Каждый нетерминал <tex>N</tex> встречается не более чем <tex>k = |N|</tex> раз в дереве.<br />
}}<br />
Деревья из этого множества соотносятся с деревьями разбора языка <tex>L^{\sim}(\Gamma)</tex>, так как при выводе каждого слова из этого языка также используются все нетерминалы грамматики.<br />
<br />
В отличие от предыдущего определения, для следующего множества число <tex>k</tex> для любого нетерминала не ограничено.<br />
{{Определение<br />
|definition = <br />
Пусть <tex>T'</tex> {{---}} множество всех терминальных деревьев разбора с корнем <tex>S</tex>, которые удовлетворяют первому условию из предыдущего определения.<br />
}}<br />
<br />
Последнее множество относится к тем правилам грамматики, которые делают строку больше в процессе вывода, то есть <tex>A \Rightarrow uAv</tex>, где <tex>u, v \in \Sigma</tex>. Эти деревья могут быть использованы, чтобы увеличить дерево разбора в множестве <tex>T'</tex> замещением нетерминала <tex>A</tex> в некотором дереве <tex>t'</tex> на дерево из множества <tex>I</tex>, определение которого написано ниже.<br />
{{Определение<br />
|definition = <br />
Пусть <tex>I</tex> {{---}} множество всех деревьев разбора с корнем <tex>A \in N</tex>, содержащих только один нетерминальный лист, который также помечен как <tex>A</tex>.<br />
}}<br />
В дополнение, деревья разбора множества <tex>I</tex> должны удовлетворять условию 2 в определении <tex>T</tex>. Еще можно заметить, что деревья из <tex>T</tex> и <tex>I</tex> имеют конечную высоту.<br />
<br />
<br><br />
Теперь перейдем к доказательству теоремы.<br />
<br><br />
Пусть <tex>w_{1},...,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> представляют возможные поддеревья, которые могут быть использованы для того, чтобы увеличить длину пути в некотором дереве. <br />
{{Лемма<br />
|statement=<br />
Для языка <tex>L^{\sim}(\Gamma)</tex> выполняется равенство <tex>\Psi_{\Sigma}(L^{\sim}(\Gamma)) = (\Psi_{\Sigma}(w_{1})+\Psi_{\Sigma}(W)^{*}) \cup ... \cup (\Psi_{\Sigma}(w_{q})+\Psi_{\Sigma}(W)^{*}) </tex><br />
|proof=<br />
Можем заметить, пустая строка может быть удалена из множества <tex>W</tex>, так как она не влияет на суммирование. Обозначим объединение сумм в лемме как <tex>\Phi</tex>.<br />
<br />
Доказывать лемму будем в две стадии по индукции.<br />
<br />
<tex>\Longrightarrow</tex> <tex>\Phi \subset L^{\sim}(\Gamma)</tex>.<br />
<br />
<br />
<tex>\Longleftarrow</tex> <tex>L^{\sim}(\Gamma) \subset \Phi</tex>.<br />
<br />
}}<br />
<br />
}}<br />
<br />
Теорема Парика связывает два понятия: функцию <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 />
<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 />
<br />
==Примеры==<br />
<br />
Язык <tex>\{a^{p} \mid p</tex> {{---}} простое число<tex>\}</tex> не является контекстно-свободным, так как множество простых чисел не является полулинейным (в арифметике Пресбургера нельзя определить множество простых чисел).<br />
<br />
Язык <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> так же не полулинейно.<br />
<br />
== См. также ==<br />
*[[Лемма о разрастании для КС-грамматик|Лемма о разрастании для КС-грамматик]]<br />
<br />
<br />
== Источники ==<br />
*Гинзбург С. {{---}} Математическая теория контекстно-свободных языков<br />
*[https://www8.cs.umu.se/kurser/TDBC92/VT06/final/3.pdf Håkan Lindqvist {{---}} Parikh’s theorem]<br />
<br />
[[Категория: Теория формальных языков]]<br />
[[Категория: Контекстно-свободные грамматики]]<br />
[[Категория: Опровержение контекстно-свободности языка]]</div>Alicehttp://neerc.ifmo.ru/wiki/index.php?title=%D0%A2%D0%B5%D0%BE%D1%80%D0%B5%D0%BC%D0%B0_%D0%9F%D0%B0%D1%80%D0%B8%D0%BA%D0%B0&diff=57770Теорема Парика2016-12-12T22:00:15Z<p>Alice: </p>
<hr />
<div>==Используемые определения==<br />
В этом разделе предполагается, что зафиксирован некоторый линейный порядок на алфавите <tex>\Sigma</tex>. Пусть <tex>\Sigma = \{a_{1},...,a_{m}\}</tex>.<br />
<br />
{{Определение<br />
|definition = <br />
Через <tex>\Psi_{\Sigma}</tex> будем обозначать функцию <tex>\Psi_{\Sigma} : \Sigma^{*} \rightarrow \mathbb {N}^{m}</tex>, определённую следующим образом: <tex>\Psi_{\Sigma}(w) = \langle |w|_{a_{1}} ,..., |w|_{a_{m}} \rangle</tex>, где <tex>|w|_{a_{i}}</tex> {{---}} количество появлений символа <tex>a_{i}</tex> в слове <tex>w</tex>. Аналогично, каждому языку <tex>L \subset \Sigma^{*}</tex> ставится в соответствие множество <tex>\Psi_{\Sigma}(L) \subset \mathbb {N}^{m}</tex>, определённое так: <tex>\Psi_{\Sigma}(L) = \{\Psi_{\Sigma}(w) \mid w \in L\}</tex>.<br />
}}<br />
<br />
Пусть <tex>\Sigma = \{a, b\}</tex> и <tex>L = \{a, abb, bba\}</tex>. Тогда <tex>\Psi_{\Sigma}(L) = \{\langle 1, 0 \rangle, \langle 1, 2 \rangle\}</tex>.<br />
<br />
<br />
{{Определение<br />
|definition = <br />
Пусть <tex>x_{0}, x_{1},..., x_{p}</tex> при <tex>0 \leq 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},...,k_{p} \in \mathbb {N}\} = x_{0} + \{x_{1},..., x_{p}\}^{*}</tex> называется '''линейным''' (англ. ''linear'') подмножеством множества <tex>\mathbb {N}^{m}</tex>.<br />
}}<br />
<br />
Говоря проще, линейное подмножество <tex>\mathbb {N}^{m}</tex> может быть построено с помощью любого m-размерного вектора <tex>x_{0}</tex> добавлением к нему произвольного числа m-размерных векторов из конечного множества, например, 1 раз <tex>x_{1}</tex> и 0 раз остальные вектора, 1 раз <tex>x_{1}</tex>, 1 раз <tex>x_{2}</tex> и 0 раз остальные, и так далее.<br />
<br>Множество <tex>L = \{(0, 0) + k_{1}(0, 2) + k_{2}(2, 0) \mid k_{1},k_{2} \in \mathbb {N}\} </tex> <tex> = \{(2k_{1}, 2k_{2}) \mid k_{1},k_{2} \in \mathbb {N}\}</tex> является линейным.<br />
<br />
{{Определение<br />
|definition = <br />
Подмножество множества <tex>\mathbb {N}</tex> называется '''полулинейным''' (англ. ''semilinear''), если оно является объединением конечного числа линейных множеств.<br />
}}<br />
*Любое конечное подмножество <tex>\mathbb {N}^{m}</tex> {{---}} полулинейно.<br />
*Полулинейные множества замкнуты относительно операции объединения, пересечения, разности и проекции.<br />
*Полулинейные множества по теореме Гинзбурга-Спаниера (англ. ''Ginsburg and Spanier theorem'') {{---}} те, которые определяемы в арифметика Пресбургера (англ. ''Presburger arithmetic'').<br />
<br />
Пусть <tex>L_{1} = (1, 2) + \{(3, 5), (7, 11)\}^{*}</tex>, <tex>L_{2} = (1, 1) + \{(2, 3), (5, 7), (4, 0)\}^{*}</tex>, <tex>L_{1}</tex> и <tex>L_{2}</tex> линейные подмножества <tex>\mathbb {N}^{2}</tex>, а <tex>L = L_{1} \cup L_{2}</tex> является полулинейным подмножеством <tex>\mathbb {N}^{2}</tex>.<br />
<br />
==Теорема Парика==<br />
{{Теорема<br />
|about=<br />
Парика, англ. ''Parikh's theorem''<br />
|statement=Если язык <tex>L \subset \Sigma^{*}</tex> является [[Контекстно-свободные грамматики, вывод, лево- и правосторонний вывод, дерево разбора|контекстно-свободным]], то множество <tex>\Psi_{\Sigma}(L)</tex> является полулинейным.<br />
|proof=<br />
Для доказательства будем пользоваться [[Лемма о разрастании для КС-грамматик|леммой о накачке для контекстно-свободных языков]].<br />
//Пусть <tex>\Gamma =\langle \Sigma, N, S, P\rangle</tex> {{---}} неукорачивающая контекстно-свободная грамматика, порождающая множество <tex>L</tex>, и пусть <tex>n</tex> {{---}} константа из леммы о накачке. <br />
//Для каждого набора нетерминалов <tex>U</tex>, содержащих <tex>S</tex>, <br />
}}<br />
<br />
Теорема Парика связывает два понятия: функцию <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 />
<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 />
<br />
==Примеры==<br />
<br />
Язык <tex>\{a^{p} \mid p</tex> {{---}} простое число<tex>\}</tex> не является контекстно-свободным, так как множество простых чисел не является полулинейным (в арифметике Пресбургера нельзя определить множество простых чисел).<br />
<br />
Язык <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> так же не полулинейно.<br />
<br />
== См. также ==<br />
*[[Лемма о разрастании для КС-грамматик|Лемма о разрастании для КС-грамматик]]<br />
<br />
== Источники ==<br />
*Гинзбург С. {{---}} Математическая теория контекстно-свободных языков<br />
<br />
[[Категория: Теория формальных языков]]<br />
[[Категория: Контекстно-свободные грамматики]]<br />
[[Категория: Опровержение контекстно-свободности языка]]</div>Alicehttp://neerc.ifmo.ru/wiki/index.php?title=%D0%A2%D0%B5%D0%BE%D1%80%D0%B5%D0%BC%D0%B0_%D0%9F%D0%B0%D1%80%D0%B8%D0%BA%D0%B0&diff=57765Теорема Парика2016-12-12T21:45:31Z<p>Alice: </p>
<hr />
<div>==Используемые определения==<br />
В этом разделе предполагается, что зафиксирован некоторый линейный порядок на алфавите <tex>\Sigma</tex>. Пусть <tex>\Sigma = \{a_{1},...,a_{n}\}</tex>.<br />
<br />
{{Определение<br />
|definition = <br />
Через <tex>\Psi_{\Sigma}</tex> будем обозначать функцию <tex>\Psi_{\Sigma} : \Sigma^{*} \rightarrow \mathbb {N}^{m}</tex>, определённую следующим образом: <tex>\Psi_{\Sigma}(w) = \langle |w|_{a_{1}} ,..., |w|_{a_{m}} \rangle</tex>, где <tex>|w|_{a_{i}}</tex> {{---}} количество появлений символа <tex>a_{i}</tex> в слове <tex>w</tex>. Аналогично, каждому языку <tex>L \subset \Sigma^{*}</tex> ставится в соответствие множество <tex>\Psi_{\Sigma}(L) \subset \mathbb {N}^{m}</tex>, определённое так: <tex>\Psi_{\Sigma}(L) = \{\Psi_{\Sigma}(w) \mid w \in L\}</tex>.<br />
}}<br />
<br />
Пусть <tex>\Sigma = \{a, b\}</tex> и <tex>L = \{a, abb, bba\}</tex>. Тогда <tex>\Psi_{\Sigma}(L) = \{\langle 1, 0 \rangle, \langle 1, 2 \rangle\}</tex>.<br />
<br />
<br />
{{Определение<br />
|definition = <br />
Пусть <tex>x_{0}, x_{1},..., x_{p}</tex> при <tex>0 \leq 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},...,k_{p} \in \mathbb {N}\} = x_{0} + \{x_{1},..., x_{p}\}^{*}</tex> называется '''линейным''' (англ. ''linear'') подмножеством множества <tex>\mathbb {N}^{m}</tex>.<br />
}}<br />
<br />
Говоря проще, линейное подмножество <tex>\mathbb {N}^{m}</tex> может быть построено с помощью любого m-размерного вектора <tex>x_{0}</tex> добавлением к нему произвольного числа m-размерных векторов из конечного множества, например, 1 раз <tex>x_{1}</tex> и 0 раз остальные вектора, 1 раз <tex>x_{1}</tex>, 1 раз <tex>x_{2}</tex> и 0 раз остальные, и так далее.<br />
<br>Множество <tex>L = \{(0, 0) + k_{1}(0, 2) + k_{2}(2, 0) \mid k_{1},k_{2} \in \mathbb {N}\} </tex> <tex> = \{(2k_{1}, 2k_{2}) \mid k_{1},k_{2} \in \mathbb {N}\}</tex> является линейным.<br />
<br />
{{Определение<br />
|definition = <br />
Подмножество множества <tex>\mathbb {N}</tex> называется '''полулинейным''' (англ. ''semilinear''), если оно является объединением конечного числа линейных множеств.<br />
}}<br />
*Любое конечное подмножество <tex>\mathbb {N}^{m}</tex> {{---}} полулинейно.<br />
*Полулинейные множества замкнуты относительно операции объединения, пересечения, разности и проекции.<br />
*Полулинейные множества по теореме Гинзбурга-Спаниера (англ. ''Ginsburg and Spanier theorem'') {{---}} те, которые определяемы в арифметика Пресбургера (англ. ''Presburger arithmetic'').<br />
<br />
Пусть <tex>L_{1} = (1, 2) + \{(3, 5), (7, 11)\}^{*}</tex>, <tex>L_{2} = (1, 1) + \{(2, 3), (5, 7), (4, 0)\}^{*}</tex>, <tex>L_{1}</tex> и <tex>L_{2}</tex> линейные подмножества <tex>\mathbb {N}^{2}</tex>, а <tex>L = L_{1} \cup L_{2}</tex> является полулинейным подмножеством <tex>\mathbb {N}^{2}</tex>.<br />
<br />
==Теорема Парика==<br />
{{Теорема<br />
|about=<br />
Парика, англ. ''Parikh's theorem''<br />
|statement=Если язык <tex>L \subset \Sigma^{*}</tex> является [[Контекстно-свободные грамматики, вывод, лево- и правосторонний вывод, дерево разбора|контекстно-свободным]], то множество <tex>\Psi_{\Sigma}(L)</tex> является полулинейным.<br />
|proof=<br />
Для доказательства будем пользоваться [[Лемма о разрастании для КС-грамматик|леммой о накачке для контекстно-свободных языков]].<br />
//Пусть <tex>\Gamma =\langle \Sigma, N, S, P\rangle</tex> {{---}} неукорачивающая контекстно-свободная грамматика, порождающая множество <tex>L</tex>, и пусть <tex>n</tex> {{---}} константа из леммы о накачке. <br />
//Для каждого набора нетерминалов <tex>U</tex>, содержащих <tex>S</tex>, <br />
}}<br />
<br />
Теорема Парика связывает два понятия: функцию <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 />
<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 />
<br />
==Примеры==<br />
<br />
Язык <tex>\{a^{p} \mid p</tex> {{---}} простое число<tex>\}</tex> не является контекстно-свободным, так как множество простых чисел не является полулинейным (в арифметике Пресбургера нельзя определить множество простых чисел).<br />
<br />
Язык <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> так же не полулинейно.<br />
<br />
== См. также ==<br />
*[[Лемма о разрастании для КС-грамматик|Лемма о разрастании для КС-грамматик]]<br />
<br />
== Источники ==<br />
*Гинзбург С. {{---}} Математическая теория контекстно-свободных языков<br />
<br />
[[Категория: Теория формальных языков]]<br />
[[Категория: Контекстно-свободные грамматики]]<br />
[[Категория: Опровержение контекстно-свободности языка]]</div>Alicehttp://neerc.ifmo.ru/wiki/index.php?title=%D0%A2%D0%B5%D0%BE%D1%80%D0%B5%D0%BC%D0%B0_%D0%9F%D0%B0%D1%80%D0%B8%D0%BA%D0%B0&diff=57763Теорема Парика2016-12-12T21:31:15Z<p>Alice: Новая страница: «==Используемые определения== В этом разделе предполагается, что зафиксирован некоторый л...»</p>
<hr />
<div>==Используемые определения==<br />
В этом разделе предполагается, что зафиксирован некоторый линейный порядок на алфавите <tex>\Sigma</tex>. Пусть <tex>\Sigma = \{a_{1},...,a_{n}\}</tex>.<br />
<br />
{{Определение<br />
|definition = <br />
Через <tex>\Psi_{\Sigma}</tex> будем обозначать функцию <tex>\Psi_{\Sigma} : \Sigma^{*} \rightarrow \mathbb {N}^{m}</tex>, определённую следующим образом: <tex>\Psi_{\Sigma}(w) = \langle |w|_{a_{1}} ,..., |w|_{a_{m}} \rangle</tex>, где <tex>|w|_{a_{i}}</tex> {{---}} количество появлений символа <tex>a_{i}</tex> в слове <tex>w</tex>. Аналогично, каждому языку <tex>L \subset \Sigma^{*}</tex> ставится в соответствие множество <tex>\Psi_{\Sigma}(L) \subset \mathbb {N}^{m}</tex>, определённое так: <tex>\Psi_{\Sigma}(L) = \{\Psi_{\Sigma}(w) \mid w \in L\}</tex>.<br />
}}<br />
<br />
Пусть <tex>\Sigma = \{a, b\}</tex> и <tex>L = \{a, abb, bba\}</tex>. Тогда <tex>\Psi_{\Sigma}(L) = \{\langle 1, 0 \rangle, \langle 1, 2 \rangle\}</tex>.<br />
<br />
<br />
{{Определение<br />
|definition = <br />
Пусть <tex>x_{0}, x_{1},..., x_{p}</tex> при <tex>0 \leq 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},...,k_{p} \in \mathbb {N}\} = x_{0} + \{x_{1},..., x_{p}\}^{*}</tex> называется '''линейным''' (англ. ''linear'') подмножеством множества <tex>\mathbb {N}^{m}</tex>.<br />
}}<br />
<br />
Говоря проще, линейное подмножество <tex>\mathbb {N}^{m}</tex> может быть построено с помощью любого m-размерного вектора <tex>x_{0}</tex> добавлением к нему произвольного числа m-размерных векторов из конечного множества, например, 1 раз <tex>x_{1}</tex> и 0 раз остальные вектора, 1 раз <tex>x_{1}</tex>, 1 раз <tex>x_{2}</tex> и 0 раз остальные, и так далее.<br />
<br>Множество <tex>L = \{(0, 0) + k_{1}(0, 2) + k_{2}(2, 0) \mid k_{1},k_{2} \in \mathbb {N}\} </tex> <tex> = \{(2k_{1}, 2k_{2}) \mid k_{1},k_{2} \in \mathbb {N}\}</tex> является линейным.<br />
<br />
{{Определение<br />
|definition = <br />
Подмножество множества <tex>\mathbb {N}</tex> называется '''полулинейным''' (англ. ''semilinear''), если оно является объединением конечного числа линейных множеств.<br />
}}<br />
*Любое конечное подмножество <tex>\mathbb {N}^{m}</tex> {{---}} полулинейно.<br />
*Полулинейные множества замкнуты относительно операции объединения, пересечения, разности и проекции.<br />
*Полулинейные множества по теореме Гинзбурга-Спаниера (англ. ''Ginsburg and Spanier theorem'') {{---}} те, которые определяемы в арифметика Пресбургера (англ. ''Presburger arithmetic'').<br />
<br />
Пусть <tex>L_{1} = (1, 2) + \{(3, 5), (7, 11)\}^{*}</tex>, <tex>L_{2} = (1, 1) + \{(2, 3), (5, 7), (4, 0)\}^{*}</tex>, <tex>L_{1}</tex> и <tex>L_{2}</tex> линейные подмножества <tex>\mathbb {N}^{2}</tex>, а <tex>L = L_{1} \cup L_{2}</tex> является полулинейным подмножеством <tex>\mathbb {N}^{2}</tex>.<br />
<br />
С помощью линейного множества можно представить функцию <tex>\Psi_{\Sigma}</tex>: <tex>L = (1,0,0)+\{(2,1,0), (0,3,2)\}^{*} = \Psi_{\Sigma}\{a(a^{2}b)^{m}(b^{3}c^{2})^{n} \mid m,n \geq 0\})</tex>.<br />
<br />
==Теорема Парика==<br />
{{Теорема<br />
|about=<br />
Парика, англ. ''Parikh's theorem''<br />
|statement=Если язык <tex>L \subset \Sigma^{*}</tex> является [[Контекстно-свободные грамматики, вывод, лево- и правосторонний вывод, дерево разбора|контекстно-свободным]], то множество <tex>\Psi_{\Sigma}(L)</tex> является полулинейным.<br />
|proof=<br />
Для доказательства будем пользоваться [[Лемма о разрастании для КС-грамматик|леммой о накачке для контекстно-свободных языков]].<br />
Пусть <tex>\Gamma =\langle \Sigma, N, S, P\rangle</tex> {{---}} неукорачивающая контекстно-свободная грамматика, порождающая множество <tex>L</tex>, и пусть <tex>n</tex> {{---}} константа из леммы о накачке. <br />
Для каждого набора нетерминалов <tex>U</tex>, содержащих <tex>S</tex>, <br />
}}<br />
<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 />
<br />
==Примеры==<br />
<br />
Язык <tex>\{a^{p} \mid p</tex> {{---}} простое число<tex>\}</tex> не является контекстно-свободным, так как множество простых чисел не является полулинейным (в арифметике Пресбургера нельзя определить множество простых чисел).<br />
<br />
Язык <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> так же не полулинейно.<br />
<br />
== См. также ==<br />
*[[Лемма о разрастании для КС-грамматик|Лемма о разрастании для КС-грамматик]]<br />
<br />
== Источники ==<br />
*Гинзбург С. {{---}} Математическая теория контекстно-свободных языков<br />
<br />
[[Категория: Теория формальных языков]]<br />
[[Категория: Контекстно-свободные грамматики]]<br />
[[Категория: Опровержение контекстно-свободности языка]]</div>Alicehttp://neerc.ifmo.ru/wiki/index.php?title=%D0%9E%D0%B1%D1%8A%D0%B5%D0%B4%D0%B8%D0%BD%D0%B5%D0%BD%D0%B8%D0%B5_%D0%BC%D0%B0%D1%82%D1%80%D0%BE%D0%B8%D0%B4%D0%BE%D0%B2,_%D0%BF%D1%80%D0%BE%D0%B2%D0%B5%D1%80%D0%BA%D0%B0_%D0%BC%D0%BD%D0%BE%D0%B6%D0%B5%D1%81%D1%82%D0%B2%D0%B0_%D0%BD%D0%B0_%D0%BD%D0%B5%D0%B7%D0%B0%D0%B2%D0%B8%D1%81%D0%B8%D0%BC%D0%BE%D1%81%D1%82%D1%8C&diff=54242Объединение матроидов, проверка множества на независимость2016-05-28T15:35:42Z<p>Alice: </p>
<hr />
<div>{{Определение<br />
|definition = <br />
Пусть <tex>M_1 = \langle X, \mathcal{I}_1 \rangle </tex> и <tex> M_2 = \langle X, \mathcal{I}_2 \rangle </tex> {{---}} два матроида на множестве элементов <tex>X</tex> с наборами независимых множеств <tex>\mathcal{I}_1</tex> и <tex>\mathcal{I}_2</tex>. Положим <tex> \mathcal{I} = \mathcal {f} A \mid A = A_1 \cup A_2, A_1 \in \mathcal{I}_1, A_2 \in \mathcal{I}_2 \mathcal {g} </tex>. Множество <tex>\mathcal{I}</tex> удовлетворяет [[Объединение матроидов, доказательство того, что объединение является матроидом|аксиомам независимости]], следовательно, <tex>\langle X, \mathcal{I} \rangle </tex> {{---}} матроид, для которого <tex>\mathcal{I}</tex> служит набором независимых множеств. Этот матроид называется '''объединением матроидов''' (англ. ''matroid union'') <tex>M_1</tex> и <tex>M_2</tex>, и обозначается <tex>M = M_1 \cup M_2 </tex><br />
}}<br />
Обычно термин «объединение» применяется, когда носители <tex>X</tex> в обоих матроидах одинаковы, однако это не является необходимым, мы можем дополнить их до объединения, заметим, что от этого <tex>M_1</tex> и <tex>M_2</tex> не перестанут быть матроидами. Если в <tex>M_1</tex> и <tex>M_2</tex> носители непересекающиеся, то это будет являться [[Прямая сумма матроидов|прямой суммой матроидов]].<br />
<br />
Верны следующие утверждения про объединение матроидов:<br />
* Операция объединения матроидов ассоциативна, следовательно, можно говорить об объединении нескольких матроидов.<br />
* В отличие от [[Пересечение матроидов, определение, примеры|пересечения матроидов]], объединение двух '''конечных матроидов''' (англ. ''finite matroid'') всегда является матроидом, однако объединение двух '''бесконечных матроидов''' (англ. ''infinite matroid'') не обязательно будет им.<br />
* Объединение применяется к независимым множествам, а не к матроидам в целом, то есть это операция на другом уровне, по сравнению с пересечением матроидов.<br />
<br />
<br />
==Проверка множества на независимость==<br />
<br />
{{Задача<br />
|definition=<br />
Дан матроид <tex>M = M_1 \cup M_2, M = \langle X, \mathcal{I}\rangle</tex>. Необходимо проверить, является ли некоторое множество <tex>U \in X</tex> независимым, то есть, лежит ли оно в <tex>\mathcal{I}</tex>.<br />
}}<br />
<br />
Для решения этой задачи преобразуем каждый элемент множества <tex>X</tex> в матроиде <tex>M_1</tex> в <tex>(x, 1)</tex>, а каждый элемент множества <tex>X</tex> в матроиде <tex>M_2</tex> в <tex>(x, 2)</tex>. Мы получили два матроида <tex>M'_1 = \langle (X \times \{1\}), \mathcal{I}_1 \rangle </tex> и <tex> M'_2 = \langle (X \times \{2\}), \mathcal{I}_2 \rangle </tex>. <br />
<br />
Определим функцию <tex>P_1</tex> : <tex> X \times Y \rightarrow X</tex>, при этом <tex>P_1((x, y)) = x</tex>, а для множества <tex>B \in X \times Y</tex> выполняется <tex>P_1(B) = \{A \subset X \mid \forall x \in A </tex> <tex> \exists b \in B : P_1(b) = x\}</tex>. <br />
Тогда функция <tex>P_1</tex> на носителях матроидов <tex>M'_1</tex> и <tex>M'_2</tex> будет являться естественным отображением <tex>(x, i) \rightarrow x</tex>, где <tex>i \in \{1, 2\}</tex>.<br />
<br />
Затем определим два матроида, которые нам далее понадобятся: <br />
<br />
# <tex>M_{\oplus} = M'_1 \oplus M'_2 = \langle (X \times \{1\}) \cup (X \times \{2\}),</tex> <tex> \mathcal{I}_{\oplus} = \{A \mid A = A_1 \cup A_2, A_1 \in \mathcal{I}_1, A_2 \in \mathcal{I}_2\} \rangle</tex> {{---}} прямая сумма двух матроидов (носители матроидов <tex>M'_1</tex> и <tex>M'_2</tex> при пересечении будут давать пустое множество).<br />
# <tex>M_{P_1} = \langle (X \times \{1\}) \cup (X \times \{2\}),</tex> <tex> \mathcal{I}_{P_1} = \{A \mid |P_1(A)| = |A|\} \rangle</tex> {{---}} <tex>\mathcal{I}_{P_1}</tex> в данном случае будет содержать такие независимые множества, что мощность любого множества <tex>A</tex> из <tex>\mathcal{I}_{P_1}</tex> будет равна мощности множества, получаемого функцией <tex>P_1</tex> над <tex>A</tex>, то есть <tex>A</tex> не будет содержать одновременно <tex>(x, 1)</tex> и <tex>(x, 2)</tex>.<br />
<br />
<br />
Теперь перейдём к нашей задаче.<br />
<br />
Множество <tex>U</tex> является независимым, если [[Ранговая функция, полумодулярность|ранговая функция]] <tex> r(U) = |U|</tex>.<br />
Можно заметить, что в матроиде <tex>M</tex> выполняется <tex>r(U) = \max\limits_{A \mid A \in \mathcal{I}_{\oplus}, A \in \mathcal{I}_{P_1}, P_1(A) \subset U} |A|</tex>. <br />
Таким образом, мы свели задачу о проверке множества на независимость в объединении к нахождению мощности максимального независимого множества в пересечении матроидов <tex>M_{\oplus}</tex> и <tex>M_{P_1}</tex>. С помощью [[Алгоритм построения базы в пересечении матроидов|алгоритма построения базы в пересечении матроидов]] найдем размер максимального подмножества <tex>U' \mid P_1(U') = U</tex> в пересечении наборов независимых множеств матроидов.<br />
<br />
==См. также==<br />
* [[Пересечение матроидов, определение, примеры]]<br />
* [[Алгоритм построения базы в пересечении матроидов]]<br />
<br />
==Источники информации ==<br />
* Емеличев В. А., Мельников О. И., Сарванов В. И., Тышкевич Р. И. {{---}} Лекции по теории графов<br />
* [https://courses.engr.illinois.edu/cs598csc/sp2010/Lectures/Lecture19.pdf Chandra Chekuri {{---}} Combinatorial Optimization]<br />
* [http://math.mit.edu/~goemans/18438F09/lec13.pdf Michel X. Goemans {{---}} Advanced Combinatorial Optimization]<br />
* [https://en.wikipedia.org/wiki/Matroid Wikipedia {{---}} Matroid]<br />
<br />
[[Категория:Алгоритмы и структуры данных]]<br />
[[Категория:Матроиды]]<br />
[[Категория:Объединение матроидов]]</div>Alicehttp://neerc.ifmo.ru/wiki/index.php?title=%D0%9E%D0%B1%D1%8A%D0%B5%D0%B4%D0%B8%D0%BD%D0%B5%D0%BD%D0%B8%D0%B5_%D0%BC%D0%B0%D1%82%D1%80%D0%BE%D0%B8%D0%B4%D0%BE%D0%B2,_%D0%BF%D1%80%D0%BE%D0%B2%D0%B5%D1%80%D0%BA%D0%B0_%D0%BC%D0%BD%D0%BE%D0%B6%D0%B5%D1%81%D1%82%D0%B2%D0%B0_%D0%BD%D0%B0_%D0%BD%D0%B5%D0%B7%D0%B0%D0%B2%D0%B8%D1%81%D0%B8%D0%BC%D0%BE%D1%81%D1%82%D1%8C&diff=54240Объединение матроидов, проверка множества на независимость2016-05-28T15:06:41Z<p>Alice: </p>
<hr />
<div>{{Определение<br />
|definition = <br />
Пусть <tex>M_1 = \langle X, \mathcal{I}_1 \rangle </tex> и <tex> M_2 = \langle X, \mathcal{I}_2 \rangle </tex> {{---}} два матроида на множестве элементов <tex>X</tex> с наборами независимых множеств <tex>\mathcal{I}_1</tex> и <tex>\mathcal{I}_2</tex>. Положим <tex> \mathcal{I} = \mathcal {f} A \mid A = A_1 \cup A_2, A_1 \in \mathcal{I}_1, A_2 \in \mathcal{I}_2 \mathcal {g} </tex>. Множество <tex>\mathcal{I}</tex> удовлетворяет [[Объединение матроидов, доказательство того, что объединение является матроидом|аксиомам независимости]], следовательно, <tex>\langle X, \mathcal{I} \rangle </tex> {{---}} матроид, для которого <tex>\mathcal{I}</tex> служит набором независимых множеств. Этот матроид называется '''объединением матроидов''' (англ. ''matroid union'') <tex>M_1</tex> и <tex>M_2</tex>, и обозначается <tex>M = M_1 \cup M_2 </tex><br />
}}<br />
Обычно термин «объединение» применяется, когда носители <tex>X</tex> в обоих матроидах одинаковы, однако это не является необходимым, мы можем дополнить их до объединения, заметим, что от этого <tex>M_1</tex> и <tex>M_2</tex> не перестанут быть матроидами. Если в <tex>M_1</tex> и <tex>M_2</tex> носители непересекающиеся, то это будет являться [[Прямая сумма матроидов|прямой суммой матроидов]].<br />
<br />
Верны следующие утверждения про объединение матроидов:<br />
* Операция объединения матроидов ассоциативна, следовательно, можно говорить об объединении нескольких матроидов.<br />
* В отличие от [[Пересечение матроидов, определение, примеры|пересечения матроидов]], объединение двух '''конечных матроидов''' (англ. ''finite matroid'') всегда является матроидом, однако объединение двух '''бесконечных матроидов''' (англ. ''infinite matroid'') не обязательно будет им.<br />
* Объединение применяется к независимым множествам, а не к матроидам в целом, то есть это операция на другом уровне, по сравнению с пересечением матроидов.<br />
<br />
<br />
==Проверка множества на независимость==<br />
<br />
{{Задача<br />
|definition=<br />
Дан матроид <tex>M = M_1 \cup M_2, M = \langle X, \mathcal{I}\rangle</tex>. Необходимо проверить, является ли некоторое множество <tex>U \in X</tex> независимым, то есть, лежит ли оно в <tex>\mathcal{I}</tex>.<br />
}}<br />
<br />
Для решения этой задачи преобразуем каждый элемент множества <tex>X</tex> в матроиде <tex>M_1</tex> в <tex>(x, 1)</tex>, а каждый элемент множества <tex>X</tex> в матроиде <tex>M_2</tex> в <tex>(x, 2)</tex>. Мы получили два матроида <tex>M'_1 = \langle (X \times \{1\}), \mathcal{I}_1 \rangle </tex> и <tex> M'_2 = \langle (X \times \{2\}), \mathcal{I}_2 \rangle </tex>. <br />
<br />
Определим функцию <tex>P_1</tex> : <tex> X \times Y \rightarrow X</tex> : <tex>P_1((x, y)) = x</tex>, а для множества <tex>B \in X \times Y</tex> выполняется <tex>P_1(B) = \{A \subset X \mid \forall x \in A </tex> <tex> \exists b \in B : P_1(b) = x\}</tex>. <br />
Тогда функция <tex>P_1</tex> на носителях матроидов <tex>M'_1</tex> и <tex>M'_2</tex> будет являться естественным отображением <tex>(x, i) \rightarrow x</tex>, где <tex>i \in \{1, 2\}</tex>.<br />
<br />
Затем определим два матроида, которые нам далее понадобятся: <br />
<br />
# <tex>M_{\oplus} = M'_1 \oplus M'_2 = \langle (X \times \{1\}) \cup (X \times \{2\}),</tex> <tex> \mathcal{I}_{\oplus} = \{A \mid A = A_1 \cup A_2, A_1 \in \mathcal{I}_1, A_2 \in \mathcal{I}_2\} \rangle</tex> {{---}} прямая сумма двух матроидов (носители матроидов <tex>M'_1</tex> и <tex>M'_2</tex> при пересечении будут давать пустое множество).<br />
# <tex>M_{P_1} = \langle (X \times \{1\}) \cup (X \times \{2\}),</tex> <tex> \mathcal{I}_{P_1} = \{A \mid |P_1(A)| = |A|\} \rangle</tex> {{---}} <tex>\mathcal{I}_{P_1}</tex> в данном случае будет содержать такие независимые множества, что мощность любого множества <tex>A</tex> из <tex>\mathcal{I}_{P_1}</tex> будет равна мощности множества, получаемого функцией <tex>P_1</tex> над <tex>A</tex>, то есть <tex>A</tex> не будет содержать одновременно <tex>(x, 1)</tex> и <tex>(x, 2)</tex>.<br />
<br />
<br />
Теперь перейдём к нашей задаче.<br />
<br />
Множество <tex>U</tex> является независимым, если [[Ранговая функция, полумодулярность|ранговая функция]] <tex> r(U) = |U|</tex>.<br />
Можно заметить, что в матроиде <tex>M</tex> выполняется <tex>r(U) = \max\limits_{A \mid A \in \mathcal{I}_{\oplus}, A \in \mathcal{I}_{P_1}, P_1(A) \subset U} |A|</tex>. <br />
Таким образом, мы свели задачу о проверке множества на независимость в объединении к нахождению мощности максимального независимого множества в пересечении матроидов <tex>M_{\oplus}</tex> и <tex>M_{P_1}</tex>. С помощью [[Алгоритм построения базы в пересечении матроидов|алгоритма построения базы в пересечении матроидов]] найдем размер максимального подсета множества <tex>U' \mid P_1(U') = U</tex> в пересечении наборов независимых множеств матроидов.<br />
<br />
==См. также==<br />
* [[Пересечение матроидов, определение, примеры]]<br />
* [[Алгоритм построения базы в пересечении матроидов]]<br />
<br />
==Источники информации ==<br />
* Емеличев В. А., Мельников О. И., Сарванов В. И., Тышкевич Р. И. {{---}} Лекции по теории графов<br />
* Chandra Chekuri {{---}} [https://courses.engr.illinois.edu/cs598csc/sp2010/Lectures/Lecture19.pdf '''Combinatorial Optimization''']<br />
* Michel X. Goemans {{---}} [http://math.mit.edu/~goemans/18438F09/lec13.pdf '''Advanced Combinatorial Optimization''']<br />
* Wikipedia {{---}} [https://en.wikipedia.org/wiki/Matroid '''Matroid''']<br />
<br />
[[Категория:Алгоритмы и структуры данных]]<br />
[[Категория:Матроиды]]<br />
[[Категория:Объединение матроидов]]</div>Alicehttp://neerc.ifmo.ru/wiki/index.php?title=%D0%9E%D0%B1%D1%8A%D0%B5%D0%B4%D0%B8%D0%BD%D0%B5%D0%BD%D0%B8%D0%B5_%D0%BC%D0%B0%D1%82%D1%80%D0%BE%D0%B8%D0%B4%D0%BE%D0%B2,_%D0%BF%D1%80%D0%BE%D0%B2%D0%B5%D1%80%D0%BA%D0%B0_%D0%BC%D0%BD%D0%BE%D0%B6%D0%B5%D1%81%D1%82%D0%B2%D0%B0_%D0%BD%D0%B0_%D0%BD%D0%B5%D0%B7%D0%B0%D0%B2%D0%B8%D1%81%D0%B8%D0%BC%D0%BE%D1%81%D1%82%D1%8C&diff=54239Объединение матроидов, проверка множества на независимость2016-05-28T14:05:29Z<p>Alice: </p>
<hr />
<div>{{Определение<br />
|definition = <br />
Пусть <tex>M_1 = \langle X, \mathcal{I}_1 \rangle </tex> и <tex> M_2 = \langle X, \mathcal{I}_2 \rangle </tex> {{---}} два матроида на множестве элементов <tex>X</tex> с наборами независимых множеств <tex>\mathcal{I}_1</tex> и <tex>\mathcal{I}_2</tex>. Положим <tex> \mathcal{I} = \mathcal {f} A \mid A = A_1 \cup A_2, A_1 \in \mathcal{I}_1, A_2 \in \mathcal{I}_2 \mathcal {g} </tex>. Множество <tex>\mathcal{I}</tex> удовлетворяет [[Объединение матроидов, доказательство того, что объединение является матроидом|аксиомам независимости]], следовательно, <tex>\langle X, \mathcal{I} \rangle </tex> {{---}} матроид, для которого <tex>\mathcal{I}</tex> служит набором независимых множеств. Этот матроид называется '''объединением матроидов''' (англ. ''matroid union'') <tex>M_1</tex> и <tex>M_2</tex>, и обозначается <tex>M = M_1 \cup M_2 </tex><br />
}}<br />
Обычно термин "объединение" применяется, когда носители <tex>X</tex> в обоих матроидах одинаковы, однако это не является необходимым, мы можем дополнить их до объединения, заметим, что от этого <tex>M_1</tex> и <tex>M_2</tex> не перестанут быть матроидами. Если в <tex>M_1</tex> и <tex>M_2</tex> носители непересекающиеся, тогда это будет являться [[Прямая сумма матроидов|прямой суммой матроидов]].<br />
<br />
* Операция объединения матроидов ассоциативна, следовательно, можно говорить об объединении нескольких матроидов.<br />
* В отличие от пересечения матроидов, объединение двух конечных (англ. ''finite matroid'') матроидов всегда является матроидом, однако объединение двух бесконечных матроидов (англ. ''infinite matroid'') не обязательно будет им.<br />
* Объединение применяется к независимым множествам, а не к матроидам в целом, то есть это операция на другом уровне, по сравнению с пересечение матроидов.<br />
<br />
<br />
==Проверка множества на независимость==<br />
<br />
Определим функцию <tex>P_1</tex> : <tex> X \times Y \rightarrow X</tex> : <tex>P_1((x, y)) = x</tex>, а для множества <tex>B \in X \times Y</tex> выполняется <tex>P_1(B) = \{A \subset X \mid \forall x \in A </tex> <tex> \exists b \in B : P_1(b) = x\}</tex>. <br />
<br />
Преобразуем каждый элемент множества <tex>X</tex> в матроиде <tex>M_1</tex> в <tex>(x, 1)</tex>, а каждый элемент множества <tex>X</tex> в матроиде <tex>M_2</tex> в <tex>(x, 2)</tex>. Мы получили два матроида <tex>M'_1 = \langle (X \times \{1\}), \mathcal{I}_1 \rangle </tex> и <tex> M'_2 = \langle (X \times \{2\}), \mathcal{I}_2 \rangle </tex>. Наша функция <tex>P_1</tex> будет являться естественным отображением <tex>(x, i) \rightarrow x</tex>, где <tex>i \in \{1, 2\}</tex>.<br />
<br />
Затем определим два матроида, которые нам далее понадобятся: <br />
<br />
# <tex>M_{\oplus} = M'_1 \oplus M'_2 = \langle (X \times \{1\}) \cup (X \times \{2\}),</tex> <tex> \mathcal{I}_{\oplus} = \{A \mid A = A_1 \cup A_2, A_1 \in \mathcal{I}_1, A_2 \in \mathcal{I}_2\} \rangle</tex> {{---}} прямая сумма двух матроидов (носители матроидов <tex>M'_1</tex> и <tex>M'_2</tex> при пересечении будут давать пустое множество).<br />
# <tex>M_{P_1} = \langle (X \times \{1\}) \cup (X \times \{2\}),</tex> <tex> \mathcal{I}_{P_1} = \{A \mid |P_1(A)| = |A|\} \rangle</tex> {{---}} <tex>\mathcal{I}_{P_1}</tex> в данном случае будет содержать такие независимые множества, что мощность любого множества <tex>A</tex> из <tex>\mathcal{I}_{P_1}</tex> будет равна мощности множества, получаемого функцией <tex>P_1</tex> над <tex>A</tex>, то есть <tex>A</tex> не будет содержать одновременно <tex>(x, 1)</tex> и <tex>(x, 2)</tex>.<br />
<br />
<br />
Теперь перейдём к нашей задаче. У нас есть некоторое множество в <tex>X</tex>, и нужно проверить его независимость в объединении матроидов (то есть, лежит ли оно в <tex>\mathcal{I}</tex>). <br />
<br />
Множество <tex>U</tex> является независимым, если <tex>r(U) = |U|</tex>.<br />
Можно заметить, что в матроиде <tex>M</tex> выполняется <tex>r(U) = \max\limits_{A \mid A \in \mathcal{I}_{\oplus}, A \in \mathcal{I}_{P_1}, P_1(A) \subset U} |A|</tex>. <br />
Таким образом, мы свели задачу о проверке множества на независимость в объединении к нахождению мощности максимального независимого множества в пересечении матроидов <tex>M_{\oplus}</tex> и <tex>M_{P_1}</tex>. С помощью [[Алгоритм построения базы в пересечении матроидов|алгоритма построения базы в пересечении матроидов]] мы будем искать размер максимального подсета множества <tex>U' \mid P_1(U') = U</tex> в пересечении набора независимых множеств матроидов.<br />
<br />
== См. также==<br />
* [[Пересечение матроидов, определение, примеры]]<br />
<br />
== Литература ==<br />
* Емеличев В. А., Мельников О. И., Сарванов В. И., Тышкевич Р. И. {{---}} Лекции по теории графов<br />
* Chandra Chekuri {{---}} [https://courses.engr.illinois.edu/cs598csc/sp2010/Lectures/Lecture19.pdf '''Combinatorial Optimization''']<br />
* Michel X. Goemans {{---}} [http://math.mit.edu/~goemans/18438F09/lec13.pdf '''Advanced Combinatorial Optimization''']<br />
* https://en.wikipedia.org/wiki/Matroid<br />
<br />
[[Категория:Алгоритмы и структуры данных]]<br />
[[Категория:Матроиды]]</div>Alicehttp://neerc.ifmo.ru/wiki/index.php?title=%D0%9E%D0%B1%D1%8A%D0%B5%D0%B4%D0%B8%D0%BD%D0%B5%D0%BD%D0%B8%D0%B5_%D0%BC%D0%B0%D1%82%D1%80%D0%BE%D0%B8%D0%B4%D0%BE%D0%B2,_%D0%BF%D1%80%D0%BE%D0%B2%D0%B5%D1%80%D0%BA%D0%B0_%D0%BC%D0%BD%D0%BE%D0%B6%D0%B5%D1%81%D1%82%D0%B2%D0%B0_%D0%BD%D0%B0_%D0%BD%D0%B5%D0%B7%D0%B0%D0%B2%D0%B8%D1%81%D0%B8%D0%BC%D0%BE%D1%81%D1%82%D1%8C&diff=54237Объединение матроидов, проверка множества на независимость2016-05-28T13:57:35Z<p>Alice: </p>
<hr />
<div>{{Определение<br />
|definition = <br />
Пусть <tex>M_1 = \langle X, \mathcal{I}_1 \rangle </tex> и <tex> M_2 = \langle X, \mathcal{I}_2 \rangle </tex> {{---}} два матроида на множестве элементов <tex>X</tex> с наборами независимых множеств <tex>\mathcal{I}_1</tex> и <tex>\mathcal{I}_2</tex>. Положим <tex> \mathcal{I} = \mathcal {f} A \mid A = A_1 \cup A_2, A_1 \in \mathcal{I}_1, A_2 \in \mathcal{I}_2 \mathcal {g} </tex>. Множество <tex>\mathcal{I}</tex> удовлетворяет [[Объединение матроидов, доказательство того, что объединение является матроидом|аксиомам независимости]], следовательно, <tex>\langle X, \mathcal{I} \rangle </tex> {{---}} матроид, для которого <tex>\mathcal{I}</tex> служит набором независимых множеств. Этот матроид называется '''объединением матроидов''' (англ. ''matroid union'') <tex>M_1</tex> и <tex>M_2</tex>, и обозначается <tex>M = M_1 \cup M_2 </tex><br />
}}<br />
Обычно термин "объединение" применяется, когда носители <tex>X</tex> в обоих матроидах одинаковы, однако это не является необходимым, мы можем дополнить их до объединения, заметим, что от этого <tex>M_1</tex> и <tex>M_2</tex> не перестанут быть матроидами. Если в <tex>M_1</tex> и <tex>M_2</tex> носители непересекающиеся, тогда это будет являться [[Прямая сумма матроидов|прямой суммой матроидов]].<br />
<br />
* Операция объединения матроидов ассоциативна, следовательно, можно говорить об объединении нескольких матроидов.<br />
* В отличие от пересечения матроидов, объединение двух конечных (англ. ''finite matroid'') матроидов всегда является матроидом, однако объединение двух бесконечных матроидов (англ. ''infinite matroid'') не обязательно будет им.<br />
* Объединение применяется к независимым множествам, а не к матроидам в целом, то есть это операция на другом уровне, по сравнению с пересечение матроидов.<br />
<br />
<br />
==Проверка множества на независимость==<br />
<br />
Зададим функцию <tex>P_1</tex> : <tex> X \times Y \rightarrow X</tex> : <tex>P_1((x, y)) = x</tex>, а для множества <tex>B \in X \times Y</tex> выполняется <tex>P_1(B) = \{A \subset X \mid \forall x \in A </tex> <tex> \exists b \in B : P_1(b) = x\}</tex>. <br />
<br />
Преобразуем каждый элемент множества <tex>X</tex> в матроиде <tex>M_1</tex> в <tex>(x, 1)</tex>, а каждый элемент множества <tex>X</tex> в матроиде <tex>M_2</tex> в <tex>(x, 2)</tex>. Мы получили два матроида <tex>M'_1 = \langle (X \times \{1\}), \mathcal{I}_1 \rangle </tex> и <tex> M'_2 = \langle (X \times \{2\}), \mathcal{I}_2 \rangle </tex>. Наша функция <tex>P_1</tex> будет являться естественным отображением <tex>(x, i) \rightarrow x</tex>, где <tex>i \in \{1, 2\}</tex>.<br />
<br />
Затем определим два матроида, которые нам далее понадобятся: <br />
<br />
# <tex>M_{\oplus} = M'_1 \oplus M'_2 = \langle (X \times \{1\}) \cup (X \times \{2\}),</tex> <tex> \mathcal{I}_{\oplus} = \{A \mid A = A_1 \cup A_2, A_1 \in \mathcal{I}_1, A_2 \in \mathcal{I}_2\} \rangle</tex> {{---}} прямая сумма двух матроидов (носители матроидов <tex>M'_1</tex> и <tex>M'_2</tex> при пересечении будут давать пустое множество).<br />
# <tex>M_{P_1} = \langle (X \times \{1\}) \cup (X \times \{2\}),</tex> <tex> \mathcal{I}_{P_1} = \{A \mid |P_1(A)| = |A|\} \rangle</tex> {{---}} <tex>\mathcal{I}_{P_1}</tex> в данном случае будет содержать такие независимые множества, что мощность любого множества <tex>A</tex> из <tex>\mathcal{I}_{P_1}</tex> будет равна мощности множества, получаемого функцией <tex>P_1</tex> над <tex>A</tex>, то есть <tex>A</tex> не будет содержать одновременно <tex>(x, 1)</tex> и <tex>(x, 2)</tex>.<br />
<br />
<br />
Теперь перейдём к нашей задаче. У нас есть некоторое множество в <tex>X</tex>, и нужно проверить его независимость в объединении матроидов (то есть, лежит ли оно в <tex>\mathcal{I}</tex>). <br />
<br />
Множество <tex>U</tex> является независимым, если <tex>r(U) = |U|</tex>.<br />
Можно заметить, что в матроиде <tex>M</tex> выполняется <tex>r(U) = \max\limits_{A \mid A \in \mathcal{I}_{\oplus}, A \in \mathcal{I}_{P_1}, P_1(A) \subset U} |A|</tex>. <br />
Таким образом, мы свели задачу о проверке множества на независимость в объединении к нахождению мощности максимального независимого множества в пересечении матроидов <tex>M_{\oplus}</tex> и <tex>M_{P_1}</tex>. С помощью [[Алгоритм построения базы в пересечении матроидов|алгоритма построения базы в пересечении матроидов]] мы будем искать размер максимального подсета множества <tex>U' \mid P_1(U') = U</tex> в пересечении набора независимых множеств матроидов.<br />
<br />
== См. также==<br />
* [[Пересечение матроидов, определение, примеры]]<br />
<br />
== Литература ==<br />
* Емеличев В. А., Мельников О. И., Сарванов В. И., Тышкевич Р. И. {{---}} Лекции по теории графов<br />
* Chandra Chekuri {{---}} [https://courses.engr.illinois.edu/cs598csc/sp2010/Lectures/Lecture19.pdf '''Combinatorial Optimization''']<br />
* Michel X. Goemans {{---}} [http://math.mit.edu/~goemans/18438F09/lec13.pdf '''Advanced Combinatorial Optimization''']<br />
* https://en.wikipedia.org/wiki/Matroid<br />
<br />
[[Категория:Алгоритмы и структуры данных]]<br />
[[Категория:Матроиды]]</div>Alicehttp://neerc.ifmo.ru/wiki/index.php?title=%D0%90%D0%BB%D0%B3%D0%BE%D1%80%D0%B8%D1%82%D0%BC_%D0%A4%D0%B0%D1%80%D0%B0%D1%85%D0%B0&diff=54147Алгоритм Фараха2016-05-21T22:10:33Z<p>Alice: </p>
<hr />
<div>'''Алгоритм Фараха''', разработанный в 1997 году американским ученым Мартином Фарах-Колтоном (Martin Farach-Colton) {{---}} алгоритм построения [[Сжатое суффиксное дерево|суффиксного дерева]] для заданной строки <tex>s</tex> длины <tex>N</tex>. Сам алгоритм выполняется за время <tex>O(N)</tex>, причём даже не требуется выполнение условия конечности алфавита. Такая эффективность достигается за счёт того, что строковые последовательности определяются на индексированном алфавите или, что эквивалентно, на целочисленном алфавите <tex>\Sigma = \{1, 2 \dots , k\}</tex>. При этом накладывается дополнительное условие, что <tex>k = O(N)</tex>. Такие алфавиты часто встречаются на практике. <br />
Важно помнить, что алгоритм скорее теоретический, нежели практический, а основная его ценность заключается в том, что размер алфавита может быть произвольным.<br />
<br />
== Описание алгоритма ==<br />
<br />
Идея алгоритма состоит в том, что мы уменьшаем размер исходной строки, строим суффиксное дерево для неё рекурсивно, а потом получаем из построенного дерево для текущей строки. Для этого мы разбиваем символы исходной строки на пары и нумеруем их, а из полученных номеров составляем новую строку, которая уже в <tex>2</tex> раза короче.<br />
<br />
Алгоритм Фараха будет описан в виде пяти выполняемых шагов. Используем в качестве примера строку <tex>s = 121112212221</tex>, определенную на алфавите <tex>\Sigma = \{1, 2\} </tex> (в этом примере <tex>N = 12</tex>).<br />
=== Шаг 1: суффиксное дерево для сжатой строки===<br />
<br />
[[Файл:tree101232.png|thumb|300px|Суффиксное дерево для сжатой строки]]<br />
* Строка <tex>s</tex> разбивается на пары подряд идущих символов: <tex> \langle 12\rangle \langle 11\rangle \langle 12\rangle \langle 21\rangle \langle 22\rangle \langle 21\rangle </tex><br />
*: (если символов нечётное число {{---}} последняя пара дополняется специальным символом <tex>\$</tex>).<br />
* Пары сортируются устойчивой сортировкой (удобно сортировать [[Цифровая_сортировка | поразрядной]], так как число разрядов мало, размер алфавита — <tex>O(n)</tex>, то время работы сортировки — линейное): <tex> \langle 11 \rangle \langle 12\rangle \langle 12\rangle \langle 21\rangle \langle 21\rangle \langle22\rangle </tex>.<br />
* Удаляются копии: <tex> \langle 11\rangle \langle 12\rangle \langle 21\rangle \langle 22\rangle </tex>.<br />
* Парам даются номера (условно, в массиве они и так есть): <tex>\langle 11 \rangle -(0), \langle 12\rangle -(1), \langle 21\rangle - (2), \langle 22\rangle-(3)</tex>.<br />
* В исходной строке пары заменяются на номера: <tex>1 0 1 2 3 2</tex>.<br />
* Из полученной строки вдвое меньшего размера рекурсивно создаётся [[Сжатое суффиксное дерево | суффикcное дерево]] тем же алгоритмом.<br />
* Рекурсия не продолжается, если строка имеет длину, равную единице: суффиксное дерево строится тривиально.<br />
<br />
=== Шаг 2: построение чётного дерева ===<br />
{{Определение<br />
|definition= Чётное дерево <tex>T^{even}_s</tex> является деревом суффиксов для строки <tex>s</tex>, узлы-листья <br />
которого ограничены чётными позициями <tex>0, 2, 4, 6, \dots </tex> строки <tex>s\$</tex>.}}<br />
<br />
[[Файл:Tree101232even-pre.png|thumb|300px|Раскрываем все пары в суффиксы]]<br />
[[Файл:Tree101232even.png|thumb|300px|Корректируем все развилки дерева]]<br />
<br />
Из дерева сжатой строки получаем частичное (чётное) дерево исходной строки. Частичное оно потому, что в нём будет только половина суффиксов, то есть те, которые стоят в чётных позициях.<br />
<br />
Номер каждой пары превращается в номер чётного суффикса исходной строки. Раскрываем все пары в суффиксы, из-за чего номера в листьях от этого умножатся на <tex>2</tex> очевидным образом.<br />
<br />
Корректируем все развилки дерева (так как они могут совпадать в первых символах):<br />
для всех внутренних вершин <tex>u</tex>, ребра всех детей которых начинаются с одинаковых символов, мы создадим новую вершину между <tex>u</tex> и ее детьми. Это можно сделать быстро, так как все ребра, исходящие из любой вершины, лексикографически отсортированы по своим первым двум символам (так как мы сортировали номера пар на прошлом шаге). Для каждого ребра нам достаточно проверить, что его первый символ соответствует первому символу соседнего ребра, и, если так, сделать необходимые исправления. Может случиться, что ребра ко всем детям <tex>u</tex> начинаются с одинакового символа, и в этом случае у вершины <tex>u</tex> будет только один ребенок. Тогда удалим <tex>u</tex>.<br />
Эта процедура требует константное время на каждое ребро и константное время на каждую вершину, а значит, на нее требуется линейное время.<br />
<br />
Итак, если <tex>T(n)</tex> {{---}} это время, которое потребуется нашему алгоритму, чтобы построить суффиксное дерево для строки <tex>S</tex>, то <tex>T_{even}</tex> может быть построено за время <tex>T(n/2) + O(n)</tex><br />
<br />
<br />
<br />
<br />
<br />
<br />
<br />
<br />
<br />
<br />
<br />
<br />
<br />
<br />
<br />
<br />
=== Шаг 3: построение нечётного по чётному ===<br />
{{Определение<br />
|definition= Нечётное дерево <tex>T^{odd}_s</tex> является деревом суффиксов для строки <tex>s</tex>, узлы-листья <br />
которого ограничены нечётными позициями <tex>1,3,5, \dots </tex> строки <tex>s\$</tex>.}}<br />
<br />
[[Файл:Odd.png|thumb|450px|Нечётное дерево]]<br />
<br />
Из чётного дерева нужно получить нечётное дерево (дерево из суффиксов в нечётных позициях). <br />
<br />
* [[Сжатое_суффиксное_дерево#.D0.9F.D0.BE.D1.81.D1.82.D1.80.D0.BE.D0.B5.D0.BD.D0.B8.D0.B5_.D0.B8.D0.B7_.D1.81.D1.83.D1.84.D1.84.D0.B8.D0.BA.D1.81.D0.BD.D0.BE.D0.B3.D0.BE_.D0.BC.D0.B0.D1.81.D1.81.D0.B8.D0.B2.D0.B0 | Строим по чётному дереву суффиксный массив]] — это можно сделать за <tex>О(n)</tex>. <br />
* Дописываем ко всем суффиксам (кроме того, что на нулевой позиции) символ, предшествующий ему в строке. <br />
* Заметим, что все нечётные суффиксы представляют собой один символ, за которым дальше следует чётный суффикс. А чётные суффиксы у нас уже были отсортированы в суффиксном массиве. Тогда отсортируем их по первому символу за линейное время.<br />
* [[Сжатое_суффиксное_дерево#.D0.9F.D0.BE.D1.81.D1.82.D1.80.D0.BE.D0.B5.D0.BD.D0.B8.D0.B5_.D0.B8.D0.B7_.D1.81.D1.83.D1.84.D1.84.D0.B8.D0.BA.D1.81.D0.BD.D0.BE.D0.B3.D0.BE_.D0.BC.D0.B0.D1.81.D1.81.D0.B8.D0.B2.D0.B0 | Построим из нового суффиксного массива дерево]], которое будет уже нечётным, что тоже делается за линейное время.<br />
<br />
Таким образом, <tex>T_{odd}</tex> может быть построено за линейное время по <tex>T_{even}</tex>.<br />
<br />
=== Шаг 4: слияние чётного и нечётного дерева ===<br />
<br />
[[Файл:Tree101232merged-pre.png|thumb|450px|Слитое дерево (условно)]]<br />
[[Файл:Tree101232merged-next.png|thumb|450px|Слитое дерево (в упрощённом виде)]]<br />
<br />
Далее необходимо найти эффективный способ слияния нечётного и чётного деревьев в одно дерево <tex>T_s</tex>. Слияние будем производить начиная с корней деревьев. <br />
Предположим, что для каждого узла деревьев <tex>T_s^{odd}</tex> и <tex>T_s^{even}</tex> выходящие из них ребра занесены в специальные списки, где они '''упорядочены''' в возрастающем лексикографическом порядке подстрок, которые представляют эти ребра. Пусть каждое ребро будет дополнительно "помечено" своим первым символом. Возьмем по одному ребру из этих списков с одинаковыми метками (в одном списке не может быть ребер с одинаковыми метками, так как это сжатые суффиксные деревья), обработаем их и рекурсивно спустимся в их поддеревья. Если для ребра из одного списка не оказалось ребра с такой же меткой из другого, то в поддеревья не спускаемся, так как там нечего сливать.<br />
Очевидно, манипуляции со списками работают за линейное время, так как сами списки упорядочены лексикографически.<br />
<br />
Алгоритм просматривает только первые буквы подстрок, представленных ребрами деревьев <tex>T_s^{odd}</tex> и <tex>T_s^{even}</tex>, пусть это будут буквы <tex>\lambda^{odd}</tex> и <tex>\lambda^{even}</tex>. Тогда:<br />
* если <tex>\lambda^{odd}</tex> <tex>\ne</tex> <tex>\lambda^{even}</tex>, определяется поддерево, соответствующее меньшей из этих букв, и без изменений присоединяется к узлу-родителю;<br />
* если <tex>\lambda^{odd}</tex> <tex>=</tex> <tex>\lambda^{even}</tex> и длины подстрок, представленных соответствующими ребрами, равны, в дерево слияния к текущему узлу добавляются два сына: один {{---}} из чётного дерева, другой {{---}} из нечётного;<br />
* если <tex>\lambda^{odd}</tex> <tex>=</tex> <tex>\lambda^{even}</tex> и длины подстрок, представленных соответствующими ребрами, различны, в дерево слияния к текущему узлу добавляются два узла, находящиеся на одном нисходящем пути, при этом ближайший узел будет соответствовать более короткой подстроке.<br />
<br />
Поскольку мы рассматриваем только первый символ каждого ребра (то есть делаем вид, что ребра равны, если первые символы у них равны), мы можем иногда слить рёбра, которые не должны были быть слиты. Однако те, которые надо было слить, точно сольем.<br />
<br />
Если начать эту процедуру для корней нечётного и чётного деревьев, она рекурсивно выполнится для корней всех поддеревьев, которые, возможно, уже содержат узлы из нечётного и чётного деревьев, поскольку ранее мог быть реализован случай <tex>\lambda^{odd}</tex> <tex>=</tex> <tex>\lambda^{even}</tex>. Так как время манипулирования любым ребром этих деревьев фиксировано, то общее время слияния деревьев составит <tex>O(N)</tex>.<br />
<br />
В результате описанных действий получится дерево <tex>M_x</tex>, в котором будут присутствовать поддеревья, которые прошли процедуру слияния, и которые ее избежали (то есть были перенесены в дерево <tex>M_x</tex> без изменений).<br />
<br />
=== Шаг 5: удаление двойных дуг ===<br />
<br />
[[Файл:Tree101232merged.png|thumb|500px|Откорректированное дерево строки <tex>121112212221</tex>]]<br />
[[Файл:Treestep5_1.jpg|thumb|550px|Пример]]<br />
<br />
Разбираемся с двойными дугами (в примере их три). Для этого мы должны выяснить, сколько начальных символов у них совпадает. Совпадать может любое число символов, даже все. Проверять их все по очереди нельзя, так как это даст квадратичное время. <br />
Если дуги совпадают полностью, тогда просто удаляем одну из копий. Если начало для двух дуг совпадает только частично, тогда нужно сделать для них общее начало, а ветки, которые на концах, снова развести по разным деревьям (для этого можно во время слияния запомнить их начальный цвет или просто сохранить ссылки на исходные ветки). <br />
<br />
Рассмотрим то, как это сделать, на примере строки <tex>10010010101000</tex>:<br />
<br />
Для того чтобы узнать общее начало двойной дуги, нужно взять одну чётную и одну нечётную вершину на дереве, для которых родителем является конец нашей двойной дуги. Например, на рисунке выше двойная дуга <tex>(1)</tex> (конец помечен зелёным) является общим родителем для вершин <tex>3</tex> и <tex>6</tex>. Чтобы узнать, на каком расстоянии будет расслаиваться двойная дуга, надо увеличить номера вершин на единицу и найти их родителя. Он будет находиться на единицу ближе к корню (и путь у вершин будет одинаковой строкой, не считая размера). Родитель вершин <tex>4</tex> и <tex>7</tex> помечен жёлтым, он находится на расстоянии <tex>1</tex> от корня, следовательно, дуга <tex>(1)</tex> должна расслаиваться в двух символах от корня, то есть обе дуги совпадают и их просто надо слить.<br />
<br />
Разберём дуги по порядку:<br />
<br />
# Расслоение находится на расстоянии <tex>2</tex> от корня, то есть дуга не расслаивается.<br />
# Конец является родителем вершин <tex>2</tex>, <tex>7</tex>. Родитель <tex>3</tex>, <tex>8</tex> после слияния дуги <tex>(1)</tex>, находится на глубине <tex>2</tex> символа. Значит, дуга <tex>(2)</tex> расслаивается на глубине <tex>3</tex> символа, то есть также не расслаивается. Дугу <tex>(2)</tex> нужно вычислять после обработки дуги <tex>(1)</tex>, потому что конец дуги <tex>(1)</tex> после обработки может оказаться на разной высоте, в зависимости от того на каком символе она расслоилась.<br />
# Конец является родителем <tex>2</tex>, <tex>9</tex>. Родитель <tex>3</tex>, <tex>10</tex> находится на расстоянии <tex>3</tex>, а наше расслоение на расстоянии <tex>4</tex>, то есть сливается первый символ двойной дуги. Дугу <tex>(3)</tex> надо вычислять после дуги <tex>(2)</tex>. Потому что если на дуге <tex>(2)</tex> появится разветвление, то компоненты дуги <tex>(3)</tex> придётся растащить по разным веткам дерева и сравнивать их будет не нужно.<br />
# Конец является родителем <tex>1</tex>, <tex>4</tex>. Расслаивается на втором символе.<br />
# Конец является родителем <tex>0</tex>, <tex>3</tex>. Дугу <tex>(5)</tex> можно обрабатывать только после дуги <tex>(4)</tex>, так как от неё будет зависеть глубина расслоения. <br />
<br />
[[Файл:Treestep5_2.jpg|thumb|center|650px|Итоговое дерево строки <tex>10010010101000</tex>]]<br />
<br />
Дерево строится рекурсивно, каждый раз длина строки уменьшается вдвое, а все фазы работают линейно.<br />
В итоге получается <tex> T(n) = T(n / 2) + \Theta (n) = \Theta (n) </tex>.<br />
<br />
==Сравнение с другими алгоритмами==<br />
<br />
===Достоинства===<br />
*Алгоритм Фараха является первым, имеющим асимптотически оптимальное время построения <tex>O(N)</tex> для строк длины <tex>N</tex> над полиномиальным алфавитом, то есть алфавитом мощности порядка <tex>O(N)</tex>.<br />
<br />
===Недостатки===<br />
<br />
*Данный алгоритм является больше теоретическим, нежели практическим. Как можно было заметить, основная идея алгоритма довольно проста и понятна. И хоть он и является асимптотически оптимальным, на практике его используют довольно редко. Это связано с тем, что алгоритм весьма сложен для реализации по сравнению с другими алгоритмами построения суффиксных деревьев, а также требует достаточно большой объем памяти.<br />
*Является offline-алгоритмом, то есть требует для начала работы всю строку целиком.<br />
<br />
==См. также==<br />
* [[Сжатое суффиксное дерево]]<br />
* [[Алгоритм Укконена]]<br />
* [[Суффиксный массив]]<br />
<br />
== Источники информации ==<br />
*[http://www.cs.rutgers.edu/~farach/pubs/Suffix.pdf Optimal suffix tree construction with large alphabets ]<br />
*[http://www.proteus2001.narod.ru/gen/txt/11/farach.html Суффиксное дерево {{---}} Алгоритм Фараха]<br />
*[http://books.google.ru/books/about/Computing_Patterns_in_Strings.html?id=iKR0EewiCu4C&redir_esc=y Computing Patterns in Strings]<br />
*[https://github.com/krzysztofp/Text-Algorithms/tree/master/Farach%20suffix%20tree Chris Parjaszewski's implementation]<br />
<br />
[[Категория: Дискретная математика и алгоритмы]]<br />
<br />
[[Категория: Словарные структуры данных]]<br />
<br />
[[Категория: Суффиксное дерево]]</div>Alicehttp://neerc.ifmo.ru/wiki/index.php?title=%D0%90%D0%BB%D0%B3%D0%BE%D1%80%D0%B8%D1%82%D0%BC_%D0%A4%D0%B0%D1%80%D0%B0%D1%85%D0%B0&diff=54145Алгоритм Фараха2016-05-21T22:00:20Z<p>Alice: </p>
<hr />
<div>'''Алгоритм Фараха''', разработанный в 1997 году американским ученым Мартином Фарах-Колтоном (Martin Farach-Colton) {{---}} алгоритм построения [[Сжатое суффиксное дерево|суффиксного дерева]] для заданной строки <tex>s</tex> длины <tex>N</tex>. Сам алгоритм выполняется за время <tex>O(N)</tex>, причём даже не требуется выполнение условия конечности алфавита. Такая эффективность достигается за счёт того, что строковые последовательности определяются на индексированном алфавите или, что эквивалентно, на целочисленном алфавите <tex>\Sigma = \{1, 2 \dots , k\}</tex>. При этом накладывается дополнительное условие, что <tex>k = O(N)</tex>. Такие алфавиты часто встречаются на практике. <br />
Важно помнить, что алгоритм скорее теоретический, нежели практический, а основная его ценность заключается в том, что размер алфавита может быть произвольным.<br />
<br />
== Описание алгоритма ==<br />
<br />
Идея алгоритма заключается в том, что мы уменьшаем размер исходной строки, строим суффиксное дерево для неё рекурсивно, а потом получаем из построенного дерево для текущей строки. Для этого мы разбиваем символы исходной строки на пары и нумеруем их, а из полученных номеров составляем новую строку, которая уже в <tex>2</tex> раза короче.<br />
<br />
Алгоритм Фараха будет описан в виде пяти выполняемых шагов. Используем в качестве примера строку <tex>s = 121112212221</tex>, определенную на алфавите <tex>\Sigma = \{1, 2\} </tex> (в этом примере <tex>N = 12</tex>).<br />
=== Шаг 1: суффиксное дерево для сжатой строки===<br />
<br />
[[Файл:tree101232.png|thumb|300px|Суффиксное дерево для сжатой строки]]<br />
* Строка <tex>s</tex> разбивается на пары подряд идущих символов: <tex> \langle 12\rangle \langle 11\rangle \langle 12\rangle \langle 21\rangle \langle 22\rangle \langle 21\rangle </tex><br />
*: (если символов нечётное число {{---}} последняя пара дополняется специальным символом <tex>\$</tex>).<br />
* Пары сортируются устойчивой сортировкой (удобно сортировать [[Цифровая_сортировка | поразрядной]], так как число разрядов мало, размер алфавита — <tex>O(n)</tex>, то время работы сортировки — линейное): <tex> \langle 11 \rangle \langle 12\rangle \langle 12\rangle \langle 21\rangle \langle 21\rangle \langle22\rangle </tex>.<br />
* Удаляются копии: <tex> \langle 11\rangle \langle 12\rangle \langle 21\rangle \langle 22\rangle </tex>.<br />
* Парам даются номера (условно, в массиве они и так есть): <tex>\langle 11 \rangle -(0), \langle 12\rangle -(1), \langle 21\rangle - (2), \langle 22\rangle-(3)</tex>.<br />
* В исходной строке пары заменяются на номера: <tex>1 0 1 2 3 2</tex>.<br />
* Из полученной строки вдвое меньшего размера рекурсивно создаётся [[Сжатое суффиксное дерево | суффикcное дерево]] тем же алгоритмом.<br />
* Рекурсия не продолжается, если строка имеет длину, равную единице: суффиксное дерево строится тривиально.<br />
<br />
=== Шаг 2: построение чётного дерева ===<br />
{{Определение<br />
|definition= Чётное дерево <tex>T^{even}_s</tex> является деревом суффиксов для строки <tex>s</tex>, узлы-листья <br />
которого ограничены чётными позициями <tex>0, 2, 4, 6, \dots </tex> строки <tex>s\$</tex>.}}<br />
<br />
[[Файл:Tree101232even-pre.png|thumb|300px|Раскрываем все пары в суффиксы]]<br />
[[Файл:Tree101232even.png|thumb|300px|Корректируем все развилки дерева]]<br />
<br />
Из дерева сжатой строки получаем частичное (чётное) дерево исходной строки. Частичное оно потому, что в нём будет только половина суффиксов, то есть те, которые стоят в чётных позициях.<br />
<br />
Номер каждой пары превращается в номер чётного суффикса исходной строки. Раскрываем все пары в суффиксы, из-за чего номера в листьях от этого умножатся на <tex>2</tex> очевидным образом.<br />
<br />
Корректируем все развилки дерева (так как они могут совпадать в первых символах):<br />
для всех внутренних вершин <tex>u</tex>, ребра всех детей которых начинаются с одинаковых символов, мы создадим новую вершину между <tex>u</tex> и ее детьми. Это можно сделать быстро, так как все ребра, исходящие из любой вершины, лексикографически отсортированы по своим первым двум символам (так как мы сортировали номера пар на прошлом шаге). Для каждого ребра нам достаточно проверить, что его первый символ соответствует первому символу соседнего ребра, и, если так, сделать необходимые исправления. Может случиться, что ребра ко всем детям <tex>u</tex> начинаются с одинакового символа, и в этом случае у вершины <tex>u</tex> будет только один ребенок. Тогда удалим <tex>u</tex>.<br />
Эта процедура требует константное время на каждое ребро и константное время на каждую вершину, а значит, на нее требуется линейное время.<br />
<br />
Итак, если <tex>T(n)</tex> {{---}} это время, которое потребуется нашему алгоритму, чтобы построить суффиксное дерево для строки <tex>S</tex>, то <tex>T_{even}</tex> может быть построено за время <tex>T(n/2) + O(n)</tex><br />
<br />
<br />
<br />
<br />
<br />
<br />
<br />
<br />
<br />
<br />
<br />
<br />
<br />
<br />
<br />
<br />
=== Шаг 3: построение нечётного по чётному ===<br />
{{Определение<br />
|definition= Нечётное дерево <tex>T^{odd}_s</tex> является деревом суффиксов для строки <tex>s</tex>, узлы-листья <br />
которого ограничены нечётными позициями <tex>1,3,5, \dots </tex> строки <tex>s\$</tex>.}}<br />
<br />
[[Файл:Odd.png|thumb|450px|Нечётное дерево]]<br />
<br />
Из чётного дерева нужно получить нечётное дерево (дерево из суффиксов в нечётных позициях). <br />
<br />
* [[Сжатое_суффиксное_дерево#.D0.9F.D0.BE.D1.81.D1.82.D1.80.D0.BE.D0.B5.D0.BD.D0.B8.D0.B5_.D0.B8.D0.B7_.D1.81.D1.83.D1.84.D1.84.D0.B8.D0.BA.D1.81.D0.BD.D0.BE.D0.B3.D0.BE_.D0.BC.D0.B0.D1.81.D1.81.D0.B8.D0.B2.D0.B0 | Строим по чётному дереву суффиксный массив]] — это можно сделать за <tex>О(n)</tex>. <br />
* Дописываем ко всем суффиксам (кроме того, что на нулевой позиции) символ, предшествующий ему в строке. <br />
* Заметим, что все нечётные суффиксы представляют собой один символ, за которым дальше следует чётный суффикс. А чётные суффиксы у нас уже были отсортированы в суффиксном массиве. Тогда отсортируем их по первому символу за линейное время.<br />
* [[Сжатое_суффиксное_дерево#.D0.9F.D0.BE.D1.81.D1.82.D1.80.D0.BE.D0.B5.D0.BD.D0.B8.D0.B5_.D0.B8.D0.B7_.D1.81.D1.83.D1.84.D1.84.D0.B8.D0.BA.D1.81.D0.BD.D0.BE.D0.B3.D0.BE_.D0.BC.D0.B0.D1.81.D1.81.D0.B8.D0.B2.D0.B0 | Построим из нового суффиксного массива дерево]], которое будет уже нечётным, что тоже делается за линейное время.<br />
<br />
Таким образом, <tex>T_{odd}</tex> может быть построено за линейное время по <tex>T_{even}</tex>.<br />
<br />
=== Шаг 4: слияние чётного и нечётного дерева ===<br />
<br />
[[Файл:Tree101232merged-pre.png|thumb|450px|Слитое дерево (условно)]]<br />
[[Файл:Tree101232merged-next.png|thumb|450px|Слитое дерево (в упрощённом виде)]]<br />
<br />
Далее необходимо найти эффективный способ слияния нечётного и чётного деревьев в одно дерево <tex>T_s</tex>. Слияние будем производить начиная с корней деревьев. <br />
Предположим, что для каждого узла деревьев <tex>T_s^{odd}</tex> и <tex>T_s^{even}</tex> выходящие из них ребра занесены в специальные списки, где они '''упорядочены''' в возрастающем лексикографическом порядке подстрок, которые представляют эти ребра. Пусть каждое ребро будет дополнительно "помечено" своим первым символом. Возьмем по одному ребру из этих списков с одинаковыми метками (в одном списке не может быть ребер с одинаковыми метками, так как это сжатые суффиксные деревья), обработаем их и рекурсивно спустимся в их поддеревья. Если для ребра из одного списка не оказалось ребра с такой же меткой из другого, то в поддеревья не спускаемся, так как там нечего сливать.<br />
Очевидно, манипуляции со списками работают за линейное время, так как сами списки упорядочены лексикографически.<br />
<br />
Алгоритм просматривает только первые буквы подстрок, представленных ребрами деревьев <tex>T_s^{odd}</tex> и <tex>T_s^{even}</tex>, пусть это будут буквы <tex>\lambda^{odd}</tex> и <tex>\lambda^{even}</tex>. Тогда:<br />
* если <tex>\lambda^{odd}</tex> <tex>\ne</tex> <tex>\lambda^{even}</tex>, определяется поддерево, соответствующее меньшей из этих букв, и без изменений присоединяется к узлу-родителю;<br />
* если <tex>\lambda^{odd}</tex> <tex>=</tex> <tex>\lambda^{even}</tex> и длины подстрок, представленных соответствующими ребрами, равны, в дерево слияния к текущему узлу добавляются два сына: один {{---}} из чётного дерева, другой {{---}} из нечётного;<br />
* если <tex>\lambda^{odd}</tex> <tex>=</tex> <tex>\lambda^{even}</tex> и длины подстрок, представленных соответствующими ребрами, различны, в дерево слияния к текущему узлу добавляются два узла, находящиеся на одном нисходящем пути, при этом ближайший узел будет соответствовать более короткой подстроке.<br />
<br />
Поскольку мы рассматриваем только первый символ каждого ребра (то есть делаем вид, что ребра равны, если первые символы у них равны), мы можем иногда слить рёбра, которые не должны были быть слиты. Однако те, которые надо было слить, точно сольем.<br />
<br />
Если начать эту процедуру для корней нечётного и чётного деревьев, она рекурсивно выполнится для корней всех поддеревьев, которые, возможно, уже содержат узлы из нечётного и чётного деревьев, поскольку ранее мог быть реализован случай <tex>\lambda^{odd}</tex> <tex>=</tex> <tex>\lambda^{even}</tex>. Так как время манипулирования любым ребром этих деревьев фиксировано, то общее время слияния деревьев составит <tex>O(N)</tex>.<br />
<br />
В результате описанных действий получится дерево <tex>M_x</tex>, в котором будут присутствовать поддеревья, которые прошли процедуру слияния, и которые ее избежали (то есть были перенесены в дерево <tex>M_x</tex> без изменений).<br />
<br />
=== Шаг 5: удаление двойных дуг ===<br />
<br />
[[Файл:Tree101232merged.png|thumb|500px|Откорректированное дерево строки <tex>121112212221</tex>]]<br />
[[Файл:Treestep5_1.jpg|thumb|550px|Пример]]<br />
<br />
Разбираемся с двойными дугами (в примере их три). Для этого мы должны выяснить, сколько начальных символов у них совпадает. Совпадать может любое число символов, даже все. Проверять их все по очереди нельзя, так как это даст квадратичное время. <br />
Если дуги совпадают полностью, тогда просто удаляем одну из копий. Если начало для двух дуг совпадает только частично, тогда нужно сделать для них общее начало, а ветки, которые на концах, снова развести по разным деревьям (для этого можно во время слияния запомнить их начальный цвет или просто сохранить ссылки на исходные ветки). <br />
<br />
Рассмотрим то, как это сделать, на примере строки <tex>10010010101000</tex>:<br />
<br />
Для того чтобы узнать общее начало двойной дуги, нужно взять одну чётную и одну нечётную вершину на дереве, для которых родителем является конец нашей двойной дуги. Например, на рисунке выше двойная дуга <tex>(1)</tex> (конец помечен зелёным) является общим родителем для вершин <tex>3</tex> и <tex>6</tex>. Чтобы узнать, на каком расстоянии будет расслаиваться двойная дуга, надо увеличить номера вершин на единицу и найти их родителя. Он будет находиться на единицу ближе к корню (и путь у вершин будет одинаковой строкой, не считая размера). Родитель вершин <tex>4</tex> и <tex>7</tex> помечен жёлтым, он находится на расстоянии <tex>1</tex> от корня, следовательно, дуга <tex>(1)</tex> должна расслаиваться в двух символах от корня, то есть обе дуги совпадают и их просто надо слить.<br />
<br />
Разберём дуги по порядку:<br />
<br />
# расслоение находится на расстоянии <tex>2</tex> от корня, то есть дуга не расслаивается.<br />
# конец является родителем вершин <tex>2</tex>, <tex>7</tex>. Родитель <tex>3</tex>, <tex>8</tex> после слияния дуги <tex>(1)</tex>, находится на глубине <tex>2</tex> символа. Значит, дуга <tex>(2)</tex> расслаивается на глубине <tex>3</tex> символа, то есть также не расслаивается. Дугу <tex>(2)</tex> нужно вычислять после обработки дуги <tex>(1)</tex>, потому что конец дуги <tex>(1)</tex> после обработки может оказаться на разной высоте, в зависимости от того на каком символе она расслоилась.<br />
# конец является родителем <tex>2</tex>, <tex>9</tex>. Родитель <tex>3</tex>, <tex>10</tex> находится на расстоянии <tex>3</tex>, а наше расслоение на расстоянии <tex>4</tex>, то есть сливается первый символ двойной дуги. Дугу <tex>(3)</tex> надо вычислять после дуги <tex>(2)</tex>. Потому что если на дуге <tex>(2)</tex> появится разветвление, то компоненты дуги <tex>(3)</tex> придётся растащить по разным веткам дерева и сравнивать их будет не нужно.<br />
# конец является родителем <tex>1</tex>, <tex>4</tex>. Расслаивается на втором символе.<br />
# конец является родителем <tex>0</tex>, <tex>3</tex>. Дугу <tex>(5)</tex> можно обрабатывать только после дуги <tex>(4)</tex>, так как от неё будет зависеть глубина расслоения. <br />
<br />
[[Файл:Treestep5_2.jpg|thumb|center|650px|Итоговое дерево строки <tex>10010010101000</tex>]]<br />
<br />
Дерево строится рекурсивно, каждый раз длина строки уменьшается вдвое, а все фазы работают линейно.<br />
В итоге получается <tex> T(n) = T(n / 2) + \Theta (n) = \Theta (n) </tex>.<br />
<br />
==Сравнение с другими алгоритмами==<br />
<br />
===Достоинства===<br />
*Алгоритм Фараха является первым, имеющим асимптотически оптимальное время построения <tex>O(N)</tex> для строк длины <tex>N</tex> над полиномиальным алфавитом, то есть алфавитом мощности порядка <tex>O(N)</tex>.<br />
<br />
===Недостатки===<br />
<br />
*Данный алгоритм является больше теоретическим, нежели практическим. Как можно было заметить, основная идея алгоритма довольно проста и понятна. И хоть он и является асимптотически оптимальным, на практике его используют довольно редко. Это связано с тем, что алгоритм весьма сложен для реализации по сравнению с другими алгоритмами построения суффиксных деревьев, а также требует достаточно большой объем памяти.<br />
*Является offline-алгоритмом, то есть требует для начала работы всю строку целиком.<br />
<br />
==См. также==<br />
* [[Сжатое суффиксное дерево]]<br />
* [[Алгоритм Укконена]]<br />
* [[Суффиксный массив]]<br />
<br />
== Источники информации ==<br />
*[http://www.cs.rutgers.edu/~farach/pubs/Suffix.pdf Optimal suffix tree construction with large alphabets ]<br />
*[http://www.proteus2001.narod.ru/gen/txt/11/farach.html Суффиксное дерево {{---}} Алгоритм Фараха]<br />
*[http://books.google.ru/books/about/Computing_Patterns_in_Strings.html?id=iKR0EewiCu4C&redir_esc=y Computing Patterns in Strings]<br />
*[https://github.com/krzysztofp/Text-Algorithms/tree/master/Farach%20suffix%20tree Chris Parjaszewski's implementation]<br />
<br />
[[Категория: Дискретная математика и алгоритмы]]<br />
<br />
[[Категория: Словарные структуры данных]]<br />
<br />
[[Категория: Суффиксное дерево]]</div>Alicehttp://neerc.ifmo.ru/wiki/index.php?title=%D0%9E%D0%B1%D1%8A%D0%B5%D0%B4%D0%B8%D0%BD%D0%B5%D0%BD%D0%B8%D0%B5_%D0%BC%D0%B0%D1%82%D1%80%D0%BE%D0%B8%D0%B4%D0%BE%D0%B2,_%D0%BF%D1%80%D0%BE%D0%B2%D0%B5%D1%80%D0%BA%D0%B0_%D0%BC%D0%BD%D0%BE%D0%B6%D0%B5%D1%81%D1%82%D0%B2%D0%B0_%D0%BD%D0%B0_%D0%BD%D0%B5%D0%B7%D0%B0%D0%B2%D0%B8%D1%81%D0%B8%D0%BC%D0%BE%D1%81%D1%82%D1%8C&diff=54143Объединение матроидов, проверка множества на независимость2016-05-21T17:04:38Z<p>Alice: </p>
<hr />
<div>{{Определение<br />
|definition = <br />
Пусть <tex>M_1 = \langle X, \mathcal{I}_1 \rangle </tex> и <tex> M_2 = \langle X, \mathcal{I}_2 \rangle </tex> {{---}} два матроида на множестве элементов <tex>X</tex> с наборами независимых множеств <tex>\mathcal{I}_1</tex> и <tex>\mathcal{I}_2</tex>. Положим <tex> \mathcal{I} = \mathcal {f} A \mid A = A_1 \cup A_2, A_1 \in \mathcal{I}_1, A_2 \in \mathcal{I}_2 \mathcal {g} </tex>. Множество <tex>\mathcal{I}</tex> удовлетворяет [[Объединение матроидов, доказательство того, что объединение является матроидом|аксиомам независимости]], следовательно, <tex>\langle X, \mathcal{I} \rangle </tex> {{---}} матроид, для которого <tex>\mathcal{I}</tex> служит набором независимых множеств. Этот матроид называется '''объединением матроидов''' (англ. ''matroid union'') <tex>M_1</tex> и <tex>M_2</tex>, и обозначается <tex> M_1 \cup M_2 </tex><br />
}}<br />
Обычно термин "объединение" применяется, когда носители <tex>X</tex> в обоих матроидах одинаковы, однако это не является необходимым, мы можем дополнить их до объединения, заметим, что от этого <tex>M_1</tex> и <tex>M_2</tex> не перестанут быть матроидами. Если в <tex>M_1</tex> и <tex>M_2</tex> носители непересекающиеся, тогда это будет являться [[Прямая сумма матроидов|прямой суммой матроидов]].<br />
<br />
* Операция объединения матроидов ассоциативна, следовательно, можно говорить об объединении нескольких матроидов.<br />
* В отличие от пересечения матроидов, объединение двух конечных (англ. ''finite matroid'') матроидов всегда является матроидом, однако объединение двух бесконечных матроидов (англ. ''infinite matroid'') не обязательно будет им.<br />
* Объединение применяется к независимым множествам, а не к матроидам в целом, то есть это операция на другом уровне, по сравнению с пересечение матроидов.<br />
<br />
<br />
Давайте зададим функцию <tex>P_1</tex> : <tex> X \times Y \rightarrow X</tex>: <tex>P_1((x, y)) = x</tex>, а для множества <tex>B \in X \times Y</tex> выполняется <tex>P_1(B) = \{A \subset X| \forall x \in A</tex> <tex>\exists y \in B : P_1(y) = x\}</tex>.<br />
<br />
Определим ещё несколько матроидов, которые нам понадобятся: <br />
<br />
<tex>M_{\oplus} = M_1 \oplus M_2 = \langle (X \times \{1\}) \cup (X \times \{2\}),</tex> <tex> I = \{A \mid A = A_1 \cup A_2, A_1 \in I_1, A_2 \in I_2\} \rangle</tex>.<br />
<br />
<tex>M_{P_1} = \langle (X \times \{1\}) \cup (X \times \{2\}),</tex> <tex> I_{P_1} = \{A \mid |P_1(A)| = |A|\} \rangle</tex>.<br />
<br />
Теперь перейдём к задаче. У нас есть множество и нужно проверить его независимость в объединении матроидов.<br />
Множество <tex>U</tex> - независимо, если <tex>r(U) = |U|</tex>.<br />
А можно заметить, что в матроиде <tex>M</tex> выполняется <tex>r(U) = \max\limits_{A \in I, A \in I_{P_1}, P_1(A) \subset U} |A|</tex>.<br />
Т.е. мы свели задачу о проверке множества на независимость в объединении к нахождению мощности максимального независимого множества в пересечении матроидов <tex>M_{\oplus}</tex> и <tex>M_{P_1}</tex>. Мы это уже умеем делать - [[Алгоритм построения базы в пересечении матроидов]].<br />
<br />
== См. также==<br />
* [[Пересечение матроидов, определение, примеры]]<br />
<br />
== Литература ==<br />
* Емеличев В. А., Мельников О. И., Сарванов В. И., Тышкевич Р. И. {{---}} Лекции по теории графов<br />
* Chandra Chekuri {{---}} [https://courses.engr.illinois.edu/cs598csc/sp2010/Lectures/Lecture19.pdf '''Combinatorial Optimization''']<br />
* https://en.wikipedia.org/wiki/Matroid<br />
<br />
[[Категория:Алгоритмы и структуры данных]]<br />
[[Категория:Матроиды]]</div>Alicehttp://neerc.ifmo.ru/wiki/index.php?title=%D0%90%D0%BB%D0%B3%D0%BE%D1%80%D0%B8%D1%82%D0%BC_%D0%A4%D0%B0%D1%80%D0%B0%D1%85%D0%B0&diff=54118Алгоритм Фараха2016-05-21T01:18:13Z<p>Alice: </p>
<hr />
<div>'''Алгоритм Фараха''', разработанный в 1997 году американским ученым Мартином Фарах-Колтоном (Martin Farach-Colton) {{---}} алгоритм построения [[Сжатое суффиксное дерево|суффиксного дерева]] для заданной строки <tex>s</tex> длины <tex>N</tex>. Сам алгоритм выполняется за время <tex>O(N)</tex>, причём даже не требуется выполнение условия конечности алфавита. Такая эффективность достигается за счет того, что строковые последовательности определяются на индексированном алфавите или, что эквивалентно, на целочисленном алфавите <tex>\Sigma = \{1, 2 \dots , k\}</tex>. При этом накладывается дополнительное условие, что <tex>k = O(N)</tex>. Такие алфавиты часто встречаются на практике. <br />
Важно помнить, что алгоритм скорее теоретический, нежели практический, а основная его ценность заключается в том, что размер алфавита может быть произвольным.<br />
<br />
== Описание алгоритма ==<br />
<br />
Идея алгоритма заключается в том, что мы уменьшаем размер исходной строки, строим суффиксное дерево для неё рекурсивно, а потом получаем из построенного дерево для текущей строки. Для этого мы разбиваем символы исходной строки на пары и нумеруем их, а из полученных номеров составляем новую строку, которая уже в <tex>2</tex> раза короче.<br />
<br />
Алгоритм Фараха будет описан в виде пяти выполняемых шагов. Используем в качестве примера строку <tex>s = 121112212221</tex>, определенную на алфавите <tex>\Sigma = \{1, 2\} </tex> (в этом примере <tex>N = 12</tex>).<br />
=== Шаг 1: суффиксное дерево для сжатой строки===<br />
<br />
[[Файл:tree101232.png|thumb|300px|суффиксное дерево для сжатой строки]]<br />
* Строка <tex>s</tex> разбивается на пары подряд идущих символов: <tex> \langle 12\rangle \langle 11\rangle \langle 12\rangle \langle 21\rangle \langle 22\rangle \langle 21\rangle </tex><br />
*: (если символов нечетное число {{---}} последняя пара дополняется специальным символом <tex>\$</tex>).<br />
* Пары сортируются устойчивой сортировкой (удобно сортировать [[Цифровая_сортировка | поразрядной]], так как число разрядов мало, размер алфавита — <tex>O(n)</tex>, то время работы сортировки — линейное): <tex> \langle 11 \rangle \langle 12\rangle \langle 12\rangle \langle 21\rangle \langle 21\rangle \langle22\rangle </tex>.<br />
* Удаляются копии: <tex> \langle 11\rangle \langle 12\rangle \langle 21\rangle \langle 22\rangle </tex>.<br />
* Парам даются номера (условно, в массиве они и так есть): <tex>\langle 11 \rangle -(0), \langle 12\rangle -(1), \langle 21\rangle - (2), \langle 22\rangle-(3)</tex>.<br />
* В исходной строке пары заменяются на номера: <tex>1 0 1 2 3 2</tex>.<br />
* Из полученной строки вдвое меньшего размера рекурсивно создаётся [[Сжатое суффиксное дерево | суффикcное дерево]] тем же алгоритмом.<br />
* Рекурсия не продолжается, если строка имеет длину <tex>1</tex>: суффиксное дерево строится тривиально.<br />
<br />
=== Шаг 2: построение чётного дерева ===<br />
{{Определение<br />
|definition= Четное дерево <tex>T^{even}_s</tex> является деревом суффиксов для строки <tex>s</tex>, узлы-листья <br />
которого ограничены четными позициями <tex>0,2,4,6, \dots </tex> строки <tex>s\$</tex>.}}<br />
<br />
[[Файл:Tree101232even-pre.png|thumb|300px|Раскрываем все пары в суффиксы]]<br />
[[Файл:Tree101232even.png|thumb|300px|Корректируются все развилки дерева (так как они могут совпадать в первых символах)]]<br />
<br />
Из дерева сжатой строки получаем частичное (чётное) дерево исходной строки. Частичное оно потому, что в нём будет только половина суффиксов, то есть те, которые стоят в чётных позициях.<br />
<br />
Номер каждой пары превращается в номер четного суффикса исходной строки. Раскрываем все пары в суффиксы, а номера в листьях от этого умножатся на <tex>2</tex> очевидным образом:<br />
<br />
Корректируются все развилки дерева (так как они могут совпадать в первых символах):<br />
для всех внутренних вершин <tex>u</tex>, ребра всех детей которых начинаются с одинаковых символов, мы создадим новую вершину между <tex>u</tex> и ее детьми. Это можно сделать быстро, так как все ребра, исходящие из любой вершины, лексикографически отсортированы по своим первым двум символам (так как мы сортировали номера пар на прошлом шаге). Для каждого ребра нам достаточно проверить, что его первый символ соответствует первому символу соседнего ребра, и, если так, сделать необходимые исправления. Может быть, что ребра ко всем детям <tex>u</tex> начинаются с одинакового символа, и в этом случае у вершины <tex>u</tex> будет только один ребенок. Тогда удалим <tex>u</tex>.<br />
Эта процедура требует константное время на каждое ребро и константное время на каждую вершину, а значит, на нее требуется линейное время.<br />
<br />
Итак, если <tex>T(n)</tex> {{---}} это время, которое потребуется нашему алгоритму, чтобы построить суффиксное дерево для строки <tex>S</tex>, то <tex>T_{even}</tex> может быть построено за время <tex>T(n/2) + O(n)</tex><br />
<br />
<br />
<br />
<br />
<br />
<br />
<br />
<br />
<br />
<br />
<br />
<br />
<br />
<br />
<br />
<br />
=== Шаг 3: построение нечетного по четному ===<br />
{{Определение<br />
|definition= Нечётное дерево <tex>T^{odd}_s</tex> является деревом суффиксов для строки <tex>s</tex>, узлы-листья <br />
которого ограничены нечетными позициями <tex>1,3,5, \dots </tex> строки <tex>s\$</tex>.}}<br />
<br />
[[Файл:Odd.png|thumb|450px|нечетное дерево]]<br />
<br />
Из чётного дерева нужно получить нечётное дерево (дерево из суффиксов в нечётных позициях). <br />
<br />
* [[Сжатое_суффиксное_дерево#.D0.9F.D0.BE.D1.81.D1.82.D1.80.D0.BE.D0.B5.D0.BD.D0.B8.D0.B5_.D0.B8.D0.B7_.D1.81.D1.83.D1.84.D1.84.D0.B8.D0.BA.D1.81.D0.BD.D0.BE.D0.B3.D0.BE_.D0.BC.D0.B0.D1.81.D1.81.D0.B8.D0.B2.D0.B0 | Строим по чётному дереву суффиксный массив]] — это можно сделать за <tex>О(n)</tex>. <br />
* Дописываем ко всем суффиксам (кроме того, что на нулевой позиции) символ, предшествующий ему в строке. <br />
* Заметим, что все нечетные суффиксы представляют собой один символ, за которым дальше следует четный суффикс. А чётные суффиксы у нас уже были отсортированы в суффиксном массиве. Тогда отсортируем их по первому символу за линейное время.<br />
* [[Сжатое_суффиксное_дерево#.D0.9F.D0.BE.D1.81.D1.82.D1.80.D0.BE.D0.B5.D0.BD.D0.B8.D0.B5_.D0.B8.D0.B7_.D1.81.D1.83.D1.84.D1.84.D0.B8.D0.BA.D1.81.D0.BD.D0.BE.D0.B3.D0.BE_.D0.BC.D0.B0.D1.81.D1.81.D0.B8.D0.B2.D0.B0 | Построим из нового суффиксного массива дерево]], которое будет уже нечётным, что тоже делается за линейное время.<br />
<br />
Таким образом <tex>T_{odd}</tex> может быть построено за линейное время по <tex>T_{even}</tex>.<br />
<br />
=== Шаг 4: слияние четного и нечетного дерева ===<br />
<br />
[[Файл:Tree101232merged-pre.png|thumb|450px|Слитое дерево (условно)]]<br />
[[Файл:Tree101232merged-next.png|thumb|450px|Слитое дерево (в упрощённом виде)]]<br />
<br />
Далее необходимо найти эффективный способ слияния нечетного и четного деревьев в одно дерево <tex>T_s</tex>. Слияние будем производить, начиная с корней деревьев. <br />
Предположим, что для каждого узла деревьев <tex>T_s^{odd}</tex> и <tex>T_s^{even}</tex> выходящие из них ребра занесены в специальные списки, где они '''упорядочены''' в возрастающем лексикографическом порядке подстрок, которые представляют эти ребра. Пусть каждое ребро будет дополнительно "помечено" своим первым символом. Возьмем по одному ребру из этих списков с одинаковыми метками (в одном списке не может быть ребер с одинаковыми метками, так как это сжатые суффиксные деревья), обработаем их и рекурсивно спустимся в их поддеревья. Если для ребра из одного списка не оказалось ребра с такой же меткой из другого, то в поддеревья, очевидно, не спускаемся, так как там нечего сливать.<br />
Очевидно, манипуляции со списками работают за линейное время, так как сами списки упорядочены лексикографически.<br />
<br />
Алгоритм просматривает только первые буквы подстрок, представленных ребрами деревьев <tex>T_s^{odd}</tex> и <tex>T_s^{even}</tex>, пусть это будут буквы <tex>\lambda^{odd}</tex> и <tex>\lambda^{even}</tex>. Тогда:<br />
* если <tex>\lambda^{odd}</tex> <tex>\ne</tex> <tex>\lambda^{even}</tex>, определяется поддерево, соответствующее меньшей из этих букв, и без изменений присоединяется к узлу-родителю;<br />
* если <tex>\lambda^{odd}</tex> <tex>=</tex> <tex>\lambda^{even}</tex> и длины подстрок, представленных соответствующими ребрами, равны, в дерево слияния к текущему узлу добавляются два сына: один {{---}} из четного дерева, другой {{---}} из нечетного;<br />
* если <tex>\lambda^{odd}</tex> <tex>=</tex> <tex>\lambda^{even}</tex> и длины подстрок, представленных соответствующими ребрами, различны, в дерево слияния к текущему узлу добавляются два узла, находящиеся на одном нисходящем пути, при этом ближайший узел будет соответствовать более короткой подстроке.<br />
<br />
Поскольку мы рассматриваем только первый символ каждого ребра (то есть делаем вид, что ребра равны, если первые символы у них равны), мы можем иногда слить рёбра, которые не должны были быть слиты. Однако те, которые надо было слить, точно сольем.<br />
<br />
Если начать эту процедуру для корней нечётного и чётного деревьев, она рекурсивно выполнится для корней всех поддеревьев, которые, возможно, уже содержат узлы из нечетного и четного деревьев, поскольку ранее мог быть реализован случай <tex>\lambda^{odd}</tex> <tex>=</tex> <tex>\lambda^{even}</tex>. Так как время манипулирования любым ребром этих деревьев фиксировано, то общее время слияния деревьев составит <tex>O(N)</tex>.<br />
<br />
В результате описанных действий получится дерево <tex>M_x</tex>, в котором будут присутствовать поддеревья, которые прошли процедуру слияния, и которые ее избежали (то есть были перенесены в дерево <tex>M_x</tex> без изменений).<br />
<br />
=== Шаг 5: удаление двойных дуг ===<br />
<br />
[[Файл:Tree101232merged.png|thumb|500px|откорректированное дерево]]<br />
[[Файл:Treestep5_1.jpg|thumb|550px|пример]]<br />
<br />
Разбираемся с двойными дугами (в примере их три). Для этого мы должны выяснить, сколько начальных символов у них совпадает. Совпадать может любое число символов, даже все. Проверять их все по очереди нельзя (это даст квадратичное время). <br />
Если дуги совпадают полностью, тогда ничего не делаем, удаляем одну из копий и всё. Если начало для двух дуг совпадает только частично, тогда нужно делать для них общее начало, а ветки, которые на концах, снова развести по разным деревьям (для этого можно во время слияния запомнить их начальный цвет или просто сохранить ссылки на исходные ветки). <br />
<br />
Для примера как это сделать возьмём строку <tex>10010010101000</tex>:<br />
<br />
Для того чтобы узнать общее начало двойной дуги, нужно взять одну чётную и одну нечётную вершину на дереве, для которых родителем является конец нашей двойной дуги. Например, на рисунке выше двойная дуга <tex>(1)</tex> (конец помечен зелёным) является общим родителем для вершин <tex>3</tex> и <tex>6</tex>. Чтобы узнать, на каком расстоянии будет расслаиваться двойная дуга, надо увеличить номера вершин на единицу и найти их родителя. Он будет находиться на единицу ближе к корню (и путь у вершин будет одинаковой строкой, не считая размера). Родитель вершин <tex>4</tex> и <tex>7</tex> помечен жёлтым, он находится на расстоянии <tex>1</tex> от корня, следовательно, дуга <tex>(1)</tex> должна расслаиваться в двух символах от корня, то есть обе дуги совпадают и их просто надо слить.<br />
<br />
Разберём дуги по порядку:<br />
<br />
# расслоение находится на расстоянии <tex>2</tex> от корня, то есть дуга не расслаивается.<br />
# конец является родителем вершин <tex>2</tex>, <tex>7</tex>. Родитель <tex>3</tex>, <tex>8</tex> после слияния дуги <tex>(1)</tex>, находится на глубине <tex>2</tex> символа. Значит, дуга <tex>(2)</tex> расслаивается на глубине <tex>3</tex> символа, то есть также не расслаивается. Дугу <tex>(2)</tex> нужно вычислять после обработки дуги <tex>(1)</tex>, потому что конец дуги <tex>(1)</tex> после обработки может оказаться на разной высоте, в зависимости от того на каком символе она расслоилась.<br />
# конец является родителем <tex>2</tex>, <tex>9</tex>. Родитель <tex>3</tex>, <tex>10</tex> находится на расстоянии <tex>3</tex>, а наше расслоение на расстоянии <tex>4</tex>, то есть сливается первый символ двойной дуги. Дугу <tex>(3)</tex> надо вычислять после дуги <tex>(2)</tex>. Потому что если на дуге <tex>(2)</tex> появится разветвление, то компоненты дуги <tex>(3)</tex> придётся растащить по разным веткам дерева и сравнивать их будет не нужно.<br />
# конец является родителем <tex>1</tex>, <tex>4</tex>. Расслаивается на втором символе.<br />
# конец является родителем <tex>0</tex>, <tex>3</tex>. Дугу <tex>(5)</tex> можно обрабатывать только после дуги <tex>(4)</tex>, так как от неё будет зависеть глубина расслоения. <br />
<br />
[[Файл:Treestep5_2.jpg|thumb|center|650px|итоговое дерево]]<br />
<br />
Дерево строится рекурсивно, каждый раз длина строки уменьшается вдвое, а все фазы работают линейно.<br />
В итоге получается <tex> T(n) = T(n / 2) + \Theta (n) = \Theta (n) </tex>.<br />
<br />
==Минусы алгоритма Фараха==<br />
<br />
Данный алгоритм является больше теоретическим, нежели практическим. Как можно было заметить, основная идея<br />
алгоритма довольно проста и понятна. И хоть он и является асимптотически оптимальным, на практике его используют<br />
довольно редко. Это связано с тем, что алгоритм весьма сложен для реализации, по сравнению с другими алгоритмами<br />
построения суффиксных деревьев, а также требует достаточно большой объем памяти.<br />
<br />
==См. также==<br />
* [[Сжатое суффиксное дерево]]<br />
* [[Алгоритм Укконена]]<br />
* [[Суффиксный массив]]<br />
<br />
== Источники информации ==<br />
*[http://www.cs.rutgers.edu/~farach/pubs/Suffix.pdf Optimal suffix tree construction with large alphabets ]<br />
*[http://www.proteus2001.narod.ru/gen/txt/11/farach.html Суффиксное дерево {{---}} Алгоритм Фараха]<br />
*[http://books.google.ru/books/about/Computing_Patterns_in_Strings.html?id=iKR0EewiCu4C&redir_esc=y Computing Patterns in Strings]<br />
*[https://github.com/krzysztofp/Text-Algorithms/tree/master/Farach%20suffix%20tree Chris Parjaszewski's implementation]<br />
<br />
[[Категория: Дискретная математика и алгоритмы]]<br />
<br />
[[Категория: Словарные структуры данных]]<br />
<br />
[[Категория: Суффиксное дерево]]</div>Alicehttp://neerc.ifmo.ru/wiki/index.php?title=%D0%9E%D0%B1%D1%8A%D0%B5%D0%B4%D0%B8%D0%BD%D0%B5%D0%BD%D0%B8%D0%B5_%D0%BC%D0%B0%D1%82%D1%80%D0%BE%D0%B8%D0%B4%D0%BE%D0%B2,_%D0%BF%D1%80%D0%BE%D0%B2%D0%B5%D1%80%D0%BA%D0%B0_%D0%BC%D0%BD%D0%BE%D0%B6%D0%B5%D1%81%D1%82%D0%B2%D0%B0_%D0%BD%D0%B0_%D0%BD%D0%B5%D0%B7%D0%B0%D0%B2%D0%B8%D1%81%D0%B8%D0%BC%D0%BE%D1%81%D1%82%D1%8C&diff=54117Объединение матроидов, проверка множества на независимость2016-05-21T00:49:07Z<p>Alice: </p>
<hr />
<div>{{Определение<br />
|definition = <br />
Пусть <tex>M_1 = \langle X, \mathcal{I}_1 \rangle </tex> и <tex> M_2 = \langle X, \mathcal{I}_2 \rangle </tex> {{---}} два матроида на множестве элементов <tex>X</tex> с наборами независимых множеств <tex>\mathcal{I}_1</tex> и <tex>\mathcal{I}_2</tex>. Положим <tex> \mathcal{I} = \mathcal {f} A \mid A = A_1 \cup A_2, A_1 \in \mathcal{I}_1, A_2 \in \mathcal{I}_2 \mathcal {g} </tex>. Множество <tex>\mathcal{I}</tex> удовлетворяет [[Объединение матроидов, доказательство того, что объединение является матроидом|аксиомам независимости]], следовательно, <tex>\langle X, \mathcal{I} \rangle </tex> {{---}} матроид, для которого <tex>\mathcal{I}</tex> служит независимым множеством. Этот матроид называется '''объединением матроидов''' (англ. ''matroid union'') <tex>M_1</tex> и <tex>M_2</tex>, и обозначается <tex> M_1 \cup M_2 </tex><br />
}}<br />
Обычно термин "объединение" применяется, когда носители <tex>X</tex> в обоих матроидах одинаковы, однако это не является необходимым, мы можем дополнить их до объединения, заметим, что от этого <tex>M_1</tex> и <tex>M_2</tex> не перестанут быть матроидами. Если в <tex>M_1</tex> и <tex>M_2</tex> носители непересекающиеся, тогда это будет являться [[Прямая сумма матроидов|прямой суммой матроидов]].<br />
<br />
* Операция объединения матроидов ассоциативна, следовательно, можно говорить об объединении нескольких матроидов.<br />
* В отличие от пересечения матроидов, объединение двух конечных (англ. ''finite matroid'') матроидов всегда является матроидом, однако объединение двух бесконечных матроидов (англ. ''infinite matroid'') не обязательно будет им.<br />
* Объединение применяется к независимым множествам, а не к матроидам в целом, то есть это операция на другом уровне, по сравнению с пересечение матроидов.<br />
<br />
<br />
Давайте зададим функцию <tex>P_1</tex> : <tex> X \times Y \rightarrow X</tex>: <tex>P_1((x, y)) = x</tex>, а для множества <tex>B \in X \times Y</tex> выполняется <tex>P_1(B) = \{A \subset X| \forall x \in A</tex> <tex>\exists y \in B : P_1(y) = x\}</tex>.<br />
<br />
Определим ещё несколько матроидов, которые нам понадобятся: <br />
<br />
<tex>M_{\oplus} = M_1 \oplus M_2 = \langle (X \times \{1\}) \cup (X \times \{2\}),</tex> <tex> I = \{A \mid A = A_1 \cup A_2, A_1 \in I_1, A_2 \in I_2\} \rangle</tex>.<br />
<br />
<tex>M_{P_1} = \langle (X \times \{1\}) \cup (X \times \{2\}),</tex> <tex> I_{P_1} = \{A \mid |P_1(A)| = |A|\} \rangle</tex>.<br />
<br />
Теперь перейдём к задаче. У нас есть множество и нужно проверить его независимость в объединении матроидов.<br />
Множество <tex>U</tex> - независимо, если <tex>r(U) = |U|</tex>.<br />
А можно заметить, что в матроиде <tex>M</tex> выполняется <tex>r(U) = \max\limits_{A \in I, A \in I_{P_1}, P_1(A) \subset U} |A|</tex>.<br />
Т.е. мы свели задачу о проверке множества на независимость в объединении к нахождению мощности максимального независимого множества в пересечении матроидов <tex>M_{\oplus}</tex> и <tex>M_{P_1}</tex>. Мы это уже умеем делать - [[Алгоритм построения базы в пересечении матроидов]].<br />
<br />
== См. также==<br />
* [[Пересечение матроидов, определение, примеры]]<br />
<br />
== Литература ==<br />
* Емеличев В. А., Мельников О. И., Сарванов В. И., Тышкевич Р. И. {{---}} Лекции по теории графов<br />
* Chandra Chekuri {{---}} [https://courses.engr.illinois.edu/cs598csc/sp2010/Lectures/Lecture19.pdf '''Combinatorial Optimization''']<br />
* https://en.wikipedia.org/wiki/Matroid<br />
<br />
[[Категория:Алгоритмы и структуры данных]]<br />
[[Категория:Матроиды]]</div>Alicehttp://neerc.ifmo.ru/wiki/index.php?title=%D0%9E%D0%B1%D1%8A%D0%B5%D0%B4%D0%B8%D0%BD%D0%B5%D0%BD%D0%B8%D0%B5_%D0%BC%D0%B0%D1%82%D1%80%D0%BE%D0%B8%D0%B4%D0%BE%D0%B2,_%D0%BF%D1%80%D0%BE%D0%B2%D0%B5%D1%80%D0%BA%D0%B0_%D0%BC%D0%BD%D0%BE%D0%B6%D0%B5%D1%81%D1%82%D0%B2%D0%B0_%D0%BD%D0%B0_%D0%BD%D0%B5%D0%B7%D0%B0%D0%B2%D0%B8%D1%81%D0%B8%D0%BC%D0%BE%D1%81%D1%82%D1%8C&diff=54116Объединение матроидов, проверка множества на независимость2016-05-21T00:36:06Z<p>Alice: </p>
<hr />
<div>{{Определение<br />
|definition = <br />
Пусть <tex>M_1 = \langle X, \mathcal{I}_1 \rangle </tex> и <tex> M_2 = \langle X, \mathcal{I}_2 \rangle </tex> {{---}} два матроида на множестве элементов <tex>X</tex> с наборами независимых множеств <tex>\mathcal{I}_1</tex> и <tex>\mathcal{I}_2</tex>. Положим <tex> \mathcal{I} = \mathcal {f} A \mid A = A_1 \cup A_2, A_1 \in \mathcal{I}_1, A_2 \in \mathcal{I}_2 \mathcal {g} </tex>. Множество <tex>\mathcal{I}</tex> удовлетворяет [[Объединение матроидов, доказательство того, что объединение является матроидом|аксиомам независимости]], следовательно, <tex>\langle X, \mathcal{I} \rangle </tex> {{---}} матроид, для которого <tex>\mathcal{I}</tex> служит независимым множеством. Этот матроид называется '''объединением матроидов''' (англ. ''matroid union'') <tex>M_1</tex> и <tex>M_2</tex>, и обозначается <tex> M_1 \cup M_2 </tex><br />
}}<br />
Обычно термин "объединение" применяется, когда носители <tex>X</tex> в обоих матроидах одинаковы, однако это не является необходимым, мы можем дополнить их до объединения, заметим, что от этого <tex>M_1</tex> и <tex>M_2</tex> не перестанут быть матроидами. Если в <tex>M_1</tex> и <tex>M_2</tex> носители непересекающиеся, тогда это будет являться [[Прямая сумма матроидов|прямой суммой матроидов]].<br />
<br />
* Операция объединения матроидов ассоциативна, следовательно, можно говорить об объединении нескольких матроидов.<br />
* В отличие от пересечения матроидов, объединение двух конечных (англ. ''finite matroid'') матроидов всегда является матроидом, однако объединение двух бесконечных матроидов (англ. ''infinite matroid'') не обязательно будет им.<br />
* Объединение применяется к независимым множествам, а не к матроидам в целом, то есть это операция на другом уровне, по сравнению с пересечение матроидов.<br />
<br />
<br />
Давайте зададим функцию <tex>P_1</tex> : <tex> X \times Y \rightarrow X</tex>: <tex>P_1((x, y)) = x</tex>, а для множества <tex>B \in X \times Y</tex> выполняется <tex>P_1(B) = \{A \subset X| \forall x \in A</tex> <tex>\exists y \in B : P_1(y) = x\}</tex>.<br />
<br />
Определим ещё несколько матроидов, которые нам понадобятся: <br />
<br />
<tex>M_{\oplus} = M_1 \oplus M_2 = \langle (X \times \{1\}) \cup (X \times \{2\}),</tex> <tex> I = \{A \mid A = A_1 \cup A_2, A_1 \in I_1, A_2 \in I_2\} \rangle</tex>.<br />
<br />
<tex>M_{P_1} = \langle (X \times \{1\}) \cup (X \times \{2\}),</tex> <tex> I_{P_1} = \{A \mid |P_1(A)| = |A|\} \rangle</tex>.<br />
<br />
Теперь перейдём к задаче. У нас есть множество и нужно проверить его независимость в объединении матроидов.<br />
Множество <tex>U</tex> - независимо, если <tex>r(U) = |U|</tex>.<br />
А можно заметить, что в матроиде <tex>M</tex> выполняется <tex>r(U) = \max\limits_{A \in I, A \in I_{P_1}, P_1(A) \subset U} |A|</tex>.<br />
Т.е. мы свели задачу о проверке множества на независимость в объединении к нахождению мощности максимального независимого множества в пересечении матроидов <tex>M_{\oplus}</tex> и <tex>M_{P_1}</tex>. Мы это уже умеем делать - [[Алгоритм построения базы в пересечении матроидов]].<br />
<br />
== Литература ==<br />
* Емеличев В. А., Мельников О. И., Сарванов В. И., Тышкевич Р. И. {{---}} Лекции по теории графов<br />
* Chandra Chekuri {{---}} [https://courses.engr.illinois.edu/cs598csc/sp2010/Lectures/Lecture19.pdf '''Combinatorial Optimization''']<br />
* https://en.wikipedia.org/wiki/Matroid</div>Alice