Теорема Парика — различия между версиями
Alice (обсуждение | вклад) |
м (rollbackEdits.php mass rollback) |
||
(не показаны 4 промежуточные версии 2 участников) | |||
Строка 12: | Строка 12: | ||
{{Определение | {{Определение | ||
|definition = | |definition = | ||
− | Пусть <tex>x_{0}, x_{1},\ldots, x_{p}</tex> при <tex>0 \leqslant p < \infty</tex> {{---}} вектора в множестве <tex>\mathbb {N}^{m}</tex>. Множество <tex>L = \{b + \sum_{i=1}^{p}k_{i} x_{i} \mid b \in B, k \ | + | Пусть <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>. |
}} | }} | ||
Строка 38: | Строка 38: | ||
# оно содержит хотя бы два узла. | # оно содержит хотя бы два узла. | ||
# <tex>res(p) = u * root(p) * v</tex>, где <tex>u, v \in \Sigma^{*}</tex>, то есть все листья помечены терминалами, за исключением одного, который совпадает с корнем дерева. | # <tex>res(p) = u * root(p) * v</tex>, где <tex>u, v \in \Sigma^{*}</tex>, то есть все листья помечены терминалами, за исключением одного, который совпадает с корнем дерева. | ||
− | + | ||
Будем обозначать <tex>s \# t</tex> если <tex>t</tex> может быть получен из <tex>s</tex> вставкой дерева <tex>p</tex> с нетерминалом <tex>A</tex> в качестве корня на место нетерминала <tex>A</tex> в дереве <tex>s</tex>, то есть, можно увеличить <tex>s</tex> с помощью некоторого дерева <tex>p</tex> так, чтобы получить <tex>t</tex>. В <tex>s</tex> строго меньше узлов, чем в <tex>t</tex>. | Будем обозначать <tex>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>. | ||
Строка 77: | Строка 77: | ||
Если путь длиннее, чем <tex>dep(s) \leqslant (k+1)(n+1)</tex>, то тогда он может быть поделен на <tex>k+1</tex> сегмент, каждый из которых длины как минимум <tex>n+1</tex>, и каждый имеет повторяющийся нетерминал, а, следовательно, <tex>s</tex> содержит <tex>k+1</tex> непересекающееся поддерево <tex>p</tex> (деревья называются непересекающимися в данном случае, если у них нет общих узлов, или если корень одного является листом другого дерева), каждое из которых, в соответствие с леммой, либо само является базовым, либо содержит базовое в себе, следовательно, в дереве <tex>s</tex> содержится <tex>k+1</tex> непересекающихся базовых <tex>p</tex>. Но так как число различных базовых <tex>p</tex> равно <tex>k</tex>, какое-то <tex>p</tex> появляется в этом наборе дважды, что противоречит <tex>\leqslant</tex>-минимальности. | Если путь длиннее, чем <tex>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>-минимальности. | ||
}} | }} | ||
− | |||
{{Теорема | {{Теорема | ||
Строка 90: | Строка 89: | ||
Покажем, что <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>\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>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 \ | + | Теорема Парика связывает два понятия: функцию <tex>\Psi_{\Sigma}</tex> контекстно-свободного языка и полулинейное множество. Например, для языка <tex>\{a(a^{2}b)^{m}(b^{3}c^{2})^{n} \mid m,n \geqslant 0\})</tex> функция <tex>\Psi_{\Sigma} = (1,0,0)+\{(2,1,0), (0,3,2)\}^{*}</tex>. |
− | <br>Эта теорема, так же, как и лемма о накачке и лемма Огдена, не является достаточной: язык <tex>\{0^{n}1^{n}2^{n} \mid n \ | + | <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>. |
==Примеры== | ==Примеры== | ||
Строка 102: | Строка 99: | ||
Язык <tex>\{a^{p} \mid p</tex> {{---}} простое число<tex>\}</tex> не является контекстно-свободным, так как множество простых чисел не является полулинейным (в арифметике Пресбургера нельзя определить множество простых чисел). | Язык <tex>\{a^{p} \mid p</tex> {{---}} простое число<tex>\}</tex> не является контекстно-свободным, так как множество простых чисел не является полулинейным (в арифметике Пресбургера нельзя определить множество простых чисел). | ||
− | Язык <tex>\{a^{m}b^{n} \mid m > n</tex> или <tex>m</tex> {{---}} простое и <tex>m \ | + | Язык <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> так же не полулинейно. |
== См. также == | == См. также == | ||
Строка 113: | Строка 110: | ||
== Источники информации== | == Источники информации== | ||
*Гинзбург С. {{---}} Математическая теория контекстно-свободных языков | *Гинзбург С. {{---}} Математическая теория контекстно-свободных языков | ||
− | * | + | *Dexter C. Kozen {{---}} Automata and Computability |
*[http://cs.stackexchange.com/questions/265/how-to-prove-that-a-language-is-not-context-free Stack Exchange {{---}} How to prove that a language is not context-free?] | *[http://cs.stackexchange.com/questions/265/how-to-prove-that-a-language-is-not-context-free Stack Exchange {{---}} How to prove that a language is not context-free?] | ||
Текущая версия на 19:34, 4 сентября 2022
Линейные множества
В этом разделе предполагается, что зафиксирован некоторый линейный порядок на алфавите . Пусть .
Определение: |
Через | будем обозначать функцию , определённую следующим образом: , где — число появлений символа в слове . Аналогично, каждому языку ставится в соответствие множество , определённое так: . Функция называется отображением Парика (англ. Parikh's mapping) соответственно слова и языка.
Пусть и . Тогда .
Определение: |
Пусть | при — вектора в множестве . Множество называется линейным (англ. linear) подмножеством множества .
Говоря проще, линейное подмножество может быть построено с помощью любого m-размерного вектора добавлением к нему произвольного числа m-размерных векторов из конечного множества, например, 1 раз и 0 раз остальные вектора, 1 раз , 1 раз и 0 раз остальные, и так далее.
Множество является линейным.
Определение: |
Подмножество множества | называется полулинейным (англ. semilinear), если оно является объединением конечного числа линейных множеств.
Полулинейное множество имеет следующие свойства:
- Любое конечное подмножество — полулинейно.
- Полулинейные множества замкнуты относительно операции объединения, пересечения, разности и проекции.
- Полулинейные множества по теореме Гинзбурга-Спаниера (англ. Ginsburg and Spanier theorem) — те, которые определяемы в арифметике Пресбургера (англ. Presburger arithmetic)[1].
Пусть
, , и линейные подмножества , а является полулинейным подмножеством .Теорема Парика
Пусть
— контекстно-свободная грамматика.Далее маленькими латинскими буквами
будем обозначать деревья разбора. Для деревьев результатом ( ) будем называть строку из нетерминалов и терминалов, записанных в листьях, упорядоченную слева направо, глубина дерева ( ) — длина наибольшего пути от листов до корня дерева, будем писать , чтобы обозначить множество нетерминалов в дереве, а — корень дерева.Обозначим за
деревья такого вида:- оно содержит хотя бы два узла.
- , где , то есть все листья помечены терминалами, за исключением одного, который совпадает с корнем дерева.
Будем обозначать
если может быть получен из вставкой дерева с нетерминалом в качестве корня на место нетерминала в дереве , то есть, можно увеличить с помощью некоторого дерева так, чтобы получить . В строго меньше узлов, чем в .Пусть
называется базовым, если оно -минимально среди всех , то есть не содержит в себе другое , которое можно вырезать. Или, иначе, является базовым, если в является только тривиальным деревом с одним узлом (который же является и корнем).Лемма: |
Если является базовым, то , где количество нетерминалов в N. |
Доказательство: |
Обозначим за Для других же листов путь должен не превышать путь от листа с нетерминалом до корня. Пусть не может быть длиннее, чем , потому что если бы был, то он содержал бы повторяющийся нетерминал, и, тем самым, содержал бы в себе другое дерево , что противоречит тому, что базовое. по тем же причинам. Таким образом, длина любого пути не больше . |
Из леммы и из конечности нетерминалов и продукций в грамматике
следует, что количество таких базовых деревьев конечно.Лемма: |
Любое дерево разбора с либо -минимально, либо содержит в себе базовое . |
Доказательство: |
Пусть | не -минимально, тогда оно по определению содержит дерево . Пусть будет -минимально среди всех , содержащихся в , тогда является базовым, так как если нет, то оно содержит в себе другое , что противоречит -минимальности.
Пусть
если может быть получен из конечной последовательностью вставок базовых , для которых . Другими словами, нам позволено выбирать любой нетерминал A в дереве и вставлять на это место базовое с корнем А в том случае, если содержит только те нетерминалы, что есть в . Если с помощью таких операций можно получить , то .Если строка
, то за будем обозначать , где получен из удалением всех нетерминалов. За будем обозначать .Лемма: |
Множество линейно. |
Доказательство: |
является базовым, и его . |
Будем называть
-минимальным, если оно не содержит в себе повторяющихся базовых .Лемма: |
Если -минимально, то его , где — размер , а — число различных базовых в дереве. |
Доказательство: |
Если путь длиннее, чем | , то тогда он может быть поделен на сегмент, каждый из которых длины как минимум , и каждый имеет повторяющийся нетерминал, а, следовательно, содержит непересекающееся поддерево (деревья называются непересекающимися в данном случае, если у них нет общих узлов, или если корень одного является листом другого дерева), каждое из которых, в соответствие с леммой, либо само является базовым, либо содержит базовое в себе, следовательно, в дереве содержится непересекающихся базовых . Но так как число различных базовых равно , какое-то появляется в этом наборе дважды, что противоречит -минимальности.
Теорема (Парика, англ. Parikh's theorem): |
Если язык контекстно-свободным, то множество является полулинейным. является |
Доказательство: |
Воспользуемся ранее полученными результатами в доказательстве. Зададим -минимально, .Покажем, что Любое такое . Это множество полулинейно по предпоследней и последней лемме ( по ней конечно, так как число базовых конечно). , что для некоторого имеет корень , и его , значит , и значит . В обратную сторону, любая строка имеет дерево разбора с корнем и , и должно существовать -минимальное (в противном бы случае это означало, что не содержит базовых , и значит оно само является -минимальным), и тогда . |
Теорема Парика связывает два понятия: функцию
Эта теорема, так же, как и лемма о накачке и лемма Огдена, не является достаточной: язык не является контекстно-свободным, однако его множество является полулинейным: .
Примеры
Язык
— простое число не является контекстно-свободным, так как множество простых чисел не является полулинейным (в арифметике Пресбургера нельзя определить множество простых чисел).Язык
или — простое и не является контекстно свободным, так как множество, порождаемое функцией , не является полулинейным: множество таких пар — линейно, множество таких пар — линейно, при этом множество простых чисел не является полулинейным, и, как следствие, множество — простое и не является полулинейным, так же не полулинейно.См. также
Примечания
Источники информации
- Гинзбург С. — Математическая теория контекстно-свободных языков
- Dexter C. Kozen — Automata and Computability
- Stack Exchange — How to prove that a language is not context-free?