22
правки
Изменения
Нет описания правки
{{Определение
|definition =
Через <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'') соответственно слова и языка.
}}
{{Определение
|definition =
Пусть <tex>x_{0}, x_{1},\ldots, x_{p}</tex> при <tex>0 \leqslant p < \infty</tex> {{---}} вектора в множестве <tex>\mathbb {N}^{m}</tex>. Множество <tex>L = \{b + \sum_{i=1}^{p}k_{i} x_{i} \mid b \in B, k \geq geqslant 0, k_{1},\ldots,k_{p} \in \mathbb {N}\} = x_{0} + \{x_{1},\ldots, x_{p}\}^{*}</tex> называется '''линейным''' (англ. ''linear'') подмножеством множества <tex>\mathbb {N}^{m}</tex>.
}}
==Теорема Парика==
Пусть <tex>\Gamma =\langle \Sigma, N, S, P\rangle</tex> {{Теорема---}} контекстно-свободная грамматика. |about=ПарикаДалее маленькими латинскими буквами <tex>s, англt, \ldots</tex> будем обозначать деревья разбора. ''Parikh'Для деревьев результатом (<tex>res(s)</tex>) будем называть строку из нетерминалов и терминалов, записанных в листьях, упорядоченную слева направо, глубина дерева (<tex>dep(s)</tex>) {{---}} длина наибольшего пути от листов до корня дерева, будем писать <tex>N(s)</tex>, чтобы обозначить множество нетерминалов в дереве, а <tex>root(s theorem'')</tex> {{---}} корень дерева. Обозначим за <tex>p</tex> деревья такого вида:# оно содержит хотя бы два узла.|statement# <tex>res(p) =Если язык u * root(p) * v</tex>, где <tex>L u, v \subset in \Sigma^{*}</tex> является [[Контекстно-свободные грамматики, выводто есть все листья помечены терминалами, за исключением одного, который совпадает с корнем дерева. Будем обозначать <tex>s \# t</tex> если <tex>t</tex> может быть получен из <tex>s</tex> вставкой дерева <tex>p</tex> с нетерминалом <tex>A</tex> в качестве корня на место нетерминала <tex>A</tex> в дереве <tex>s</tex>, то есть, можно увеличить <tex>s</tex> с помощью некоторого дерева <tex>p</tex> так, чтобы получить <tex>t</tex>. В <tex>s</tex> строго меньше узлов, лево- и правосторонний выводчем в <tex>t</tex>. Пусть <tex>p</tex> называется ''базовым'', дерево разбора|контекстноесли оно <tex>\#</tex>-свободным]]минимально среди всех <tex>p</tex>, то множество есть не содержит в себе другое <tex>p</tex>, которое можно вырезать. Или, иначе, <tex>p</tex> является базовым, если в <tex>s \Psi_# t</tex> <tex>s</tex> является только тривиальным деревом с одним узлом (который же является и корнем). {{\Sigma}Лемма|statement=Если <tex>p</tex> является базовым, то <tex>dep(Lp)\leqslant 2n</tex>, где <tex>n</tex> является полулинейнымколичество нетерминалов в N.
|proof=
{{Лемма
|statement=
|proof=
}}
Если строка <brtex>Теперь определим три множества деревьев разбора. \alpha = N^{*} \cup \Sigma^{Определение|definition = Пусть *}</tex>T, то за </tex> \Psi_{{---\Sigma}} множество всех терминальных деревьев разбора с корнем (\alpha)</tex>Sбудем обозначать <tex>\Psi_{\Sigma}(x)</tex>, которые удовлетворяют двум условиям:1. Каждый нетерминал где <tex>Nx</tex> встречается в в дереве.2. Каждый нетерминал получен из <tex>N\alpha</tex> встречается не более чем удалением всех нетерминалов. За <tex>k = |N|\Psi_{\Sigma}(t)</tex> раз в дереве.}}Деревья из этого множества соотносятся с деревьями разбора языка будем обозначать <tex>L^\Psi_{\simSigma}(\Gammares(t))</tex>, так как при выводе каждого слова из этого языка также используются все нетерминалы грамматики.
}}
{{Лемма
|statement=
|proof=
{{Теорема
|about=
Парика, англ. ''Parikh's theorem''
|statement=Если язык <tex>L \subset \Sigma^{*}</tex> является [[Контекстно-свободные грамматики, вывод, лево- и правосторонний вывод, дерево разбора|контекстно-свободным]], то множество <tex>\Psi_{\Sigma}(L)</tex> является полулинейным.
|proof=
Зададим <tex>M = \{s \mid s</tex> <tex>\leqslant</tex>-минимально, <tex>root(s) = S, res(s) \in \Sigma^{*}\}</tex>.
Покажем, что <tex>\Psi_{\Sigma}(L(\Gamma)) = \bigcup \limits_{s \in M} \{\Psi_{\Sigma}(t) \mid s \leqslant t\}</tex>. Это множество полулинейно по предпоследней и последней лемме (<tex>M</tex> по ней конечно, так как число базовых <tex>p</tex> конечно).
Любое такое <tex>t</tex>, что <tex>s \leqslant t</tex> для некоторого <tex>s \in M</tex> имеет корень <tex>root(t) = S</tex>, и его <tex>res(t) \in \Sigma^{*}</tex>, значит <tex>t \in L(\Gamma)</tex>, и значит <tex>\Psi_{\Sigma}(t) \in \Psi_{\Sigma}(L(\Gamma))</tex>. В обратную сторону, любая строка <tex>x \in L(\Gamma)</tex> имеет дерево разбора <tex>t</tex> с корнем <tex>root(t) = S</tex> и <tex>res(t) = x</tex>, и должно существовать <tex>\leqslant</tex>-минимальное <tex>s \leqslant t</tex> (в противном бы случае это означало, что <tex>t</tex> не содержит базовых <tex>p</tex>, и значит оно само является <tex>\leqslant</tex>-минимальным), и тогда <tex>\Psi_{\Sigma}(x) \in \{\Psi_{\Sigma}(t) \mid s \leqslant t\}</tex>.
}}
Теорема Парика связывает два понятия: функцию <tex>\Psi_{\Sigma}</tex> контекстно-свободного языка и полулинейное множество. Например, для языка <tex>\{a(a^{2}b)^{m}(b^{3}c^{2})^{n} \mid m,n \geq geqslant 0\})</tex> функция <tex>\Psi_{\Sigma} = (1,0,0)+\{(2,1,0), (0,3,2)\}^{*}</tex>.<br>Эта теорема, так же, как и лемма о накачке и лемма Огдена, не является достаточной: язык <tex>\{0^{n}1^{n}2^{n} \mid n \geq geqslant 0\}</tex> [[Лемма о разрастании для КС-грамматик#Пример доказательства неконтекстно-свободности языка с использованием леммы|не является контекстно-свободным]], однако его множество <tex>\Psi_{\Sigma} = \{(n, n, n) \mid n \geq geqslant 0\}</tex> является полулинейным: <tex>\Psi_{\Sigma} = \{(n, n, n) \mid n \geq geqslant 0\} = (0, 0, 0) + \{(1, 1, 1)\}^{*}</tex>.
==Примеры==
Язык <tex>\{a^{p} \mid p</tex> {{---}} простое число<tex>\}</tex> не является контекстно-свободным, так как множество простых чисел не является полулинейным (в арифметике Пресбургера нельзя определить множество простых чисел).
Язык <tex>\{a^{m}b^{n} \mid m > n</tex> или <tex>m</tex> {{---}} простое и <tex>m \leq 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 \leq leqslant n\} = (0, 0) + \{(1, 1), (0, 1)\}</tex> {{---}} линейно, при этом множество простых чисел не является полулинейным, и, как следствие, множество <tex>\{m</tex> {{---}} простое и <tex>m \leq leqslant n\}</tex> не является полулинейным, <tex>\Psi_{\Sigma}</tex> так же не полулинейно.
== См. также ==
== Источники информации==
*Гинзбург С. {{---}} Математическая теория контекстно-свободных языков
*[https://www8Dexter C.cs.umu.se/kurser/TDBC92/VT06/final/3.pdf Håkan Lindqvist Kozen {{---}} Parikh’s theorem]Automata and Computability
*[http://cs.stackexchange.com/questions/265/how-to-prove-that-a-language-is-not-context-free Stack Exchange {{---}} How to prove that a language is not context-free?]