Теорема Парика - История изменений

Maintenance script: rollbackEdits.php mass rollback

2022-09-04T16:34:03Z

rollbackEdits.php mass rollback

88.208.225.209 в 04:20, 1 сентября 2022

2022-09-01T04:20:57Z

Alice в 15:44, 30 декабря 2016

2016-12-30T15:44:22Z

Alice в 01:05, 29 декабря 2016

2016-12-29T01:05:51Z

Alice в 01:00, 29 декабря 2016

2016-12-29T01:00:46Z

Alice в 00:57, 29 декабря 2016

2016-12-29T00:57:38Z

Внесённые изменения

Alice в 21:29, 27 декабря 2016

2016-12-27T21:29:37Z

Alice в 23:43, 20 декабря 2016

2016-12-20T23:43:05Z

Alice в 22:28, 20 декабря 2016

2016-12-20T22:28:30Z

Alice в 21:51, 20 декабря 2016

2016-12-20T21:51:36Z

← Предыдущая		Версия 16:34, 4 сентября 2022
Строка 1:		Строка 1:
−	~~{\| class="wikitable" align="center" style="color: red; background-color: black; font-size: 56px; width: 800px;"~~
−	\|+
−	~~\|-align="center"~~
−	~~\|'''НЕТ ВОЙНЕ'''~~
−	~~\|-style="font-size: 16px;"~~
−	\|
−	24 февраля 2022 года российское руководство во главе с Владимиром Путиным развязало агрессивную войну против Украины. В глазах всего мира это военное преступление совершено от лица всей страны, всех россиян.
−
−	Будучи гражданами Российской Федерации, мы против своей воли оказались ответственными за нарушение международного права, военное вторжение и массовую гибель людей. Чудовищность совершенного преступления не оставляет возможности промолчать или ограничиться пассивным несогласием.
−
−	Мы убеждены в абсолютной ценности человеческой жизни, в незыблемости прав и свобод личности. Режим Путина — угроза этим ценностям. Наша задача — обьединить все силы для сопротивления ей.
−
−	Эту войну начали не россияне, а обезумевший диктатор. И наш гражданский долг — сделать всё, чтобы её остановить.
−
−	~~''Антивоенный комитет России''~~
−	~~\|-style="font-size: 16px;"~~
−	\|Распространяйте правду о текущих событиях, оберегайте от пропаганды своих друзей и близких. Изменение общественного восприятия войны - ключ к её завершению.
−	~~\|-style="font-size: 16px;"~~
−	\|[https://meduza.io/ meduza.io], [https://www.youtube.com/c/popularpolitics/videos Популярная политика], [https://novayagazeta.ru/ Новая газета], [https://zona.media/ zona.media], [https://www.youtube.com/c/MackNack/videos Майкл Наки].
−	\|}
−
	==Линейные множества==		==Линейные множества==
	В этом разделе предполагается, что зафиксирован некоторый [[Отношение_порядка\|линейный порядок]] на алфавите <tex>\Sigma</tex>. Пусть <tex>\Sigma = \{a_{1},\ldots,a_{m}\}</tex>.		В этом разделе предполагается, что зафиксирован некоторый [[Отношение_порядка\|линейный порядок]] на алфавите <tex>\Sigma</tex>. Пусть <tex>\Sigma = \{a_{1},\ldots,a_{m}\}</tex>.

← Предыдущая		Версия 04:20, 1 сентября 2022
Строка 1:		Строка 1:
		+	{\| class="wikitable" align="center" style="color: red; background-color: black; font-size: 56px; width: 800px;"
		+	\|+
		+	\|-align="center"
		+	\|'''НЕТ ВОЙНЕ'''
		+	\|-style="font-size: 16px;"
		+	\|
		+	24 февраля 2022 года российское руководство во главе с Владимиром Путиным развязало агрессивную войну против Украины. В глазах всего мира это военное преступление совершено от лица всей страны, всех россиян.
		+
		+	Будучи гражданами Российской Федерации, мы против своей воли оказались ответственными за нарушение международного права, военное вторжение и массовую гибель людей. Чудовищность совершенного преступления не оставляет возможности промолчать или ограничиться пассивным несогласием.
		+
		+	Мы убеждены в абсолютной ценности человеческой жизни, в незыблемости прав и свобод личности. Режим Путина — угроза этим ценностям. Наша задача — обьединить все силы для сопротивления ей.
		+
		+	Эту войну начали не россияне, а обезумевший диктатор. И наш гражданский долг — сделать всё, чтобы её остановить.
		+
		+	''Антивоенный комитет России''
		+	\|-style="font-size: 16px;"
		+	\|Распространяйте правду о текущих событиях, оберегайте от пропаганды своих друзей и близких. Изменение общественного восприятия войны - ключ к её завершению.
		+	\|-style="font-size: 16px;"
		+	\|[https://meduza.io/ meduza.io], [https://www.youtube.com/c/popularpolitics/videos Популярная политика], [https://novayagazeta.ru/ Новая газета], [https://zona.media/ zona.media], [https://www.youtube.com/c/MackNack/videos Майкл Наки].
		+	\|}
		+
	==Линейные множества==		==Линейные множества==
	В этом разделе предполагается, что зафиксирован некоторый [[Отношение_порядка\|линейный порядок]] на алфавите <tex>\Sigma</tex>. Пусть <tex>\Sigma = \{a_{1},\ldots,a_{m}\}</tex>.		В этом разделе предполагается, что зафиксирован некоторый [[Отношение_порядка\|линейный порядок]] на алфавите <tex>\Sigma</tex>. Пусть <tex>\Sigma = \{a_{1},\ldots,a_{m}\}</tex>.

@@ Строка 89: / Строка 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>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>.
 }}

@@ Строка 12: / Строка 12: @@
 {{Определение
 |definition =
-Пусть <tex>x_{0},  x_{1},\ldots, x_{p}</tex> при <tex>0 \leqslant  p < \infty</tex> {{---}} вектора в множестве <tex>\mathbb {N}^{m}</tex>. Множество <tex>L = \{b + \sum_{i=1}^{p}k_{i} x_{i} \mid b \in B, k \geq 0, k_{1},\ldots,k_{p} \in \mathbb {N}\} = x_{0} + \{x_{1},\ldots, x_{p}\}^{*}</tex> называется '''линейным''' (англ. ''linear'') подмножеством множества <tex>\mathbb {N}^{m}</tex>.
+Пусть <tex>x_{0},  x_{1},\ldots, x_{p}</tex> при <tex>0 \leqslant  p < \infty</tex> {{---}} вектора в множестве <tex>\mathbb {N}^{m}</tex>. Множество <tex>L = \{b + \sum_{i=1}^{p}k_{i} x_{i} \mid b \in B, k \geqslant 0, k_{1},\ldots,k_{p} \in \mathbb {N}\} = x_{0} + \{x_{1},\ldots, x_{p}\}^{*}</tex> называется '''линейным''' (англ. ''linear'') подмножеством множества <tex>\mathbb {N}^{m}</tex>.
 }}
@@ Строка 38: / Строка 38: @@
 # оно содержит хотя бы два узла.
 # <tex>res(p) = u * root(p) * v</tex>, где <tex>u, v \in \Sigma^{*}</tex>, то есть все листья помечены терминалами, за исключением одного, который совпадает с корнем дерева.
-<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>.
@@ Строка 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>-минимальности.
 }}
 {{Теорема
@@ Строка 91: / Строка 90: @@
 Покажем, что  <tex>\Psi_{\Sigma}(L(\Gamma)) = \bigcup \limits_{s \in M} \{\Psi_{\Sigma}(t) \mid s \leqslant t\}</tex>. Это множество полулинейно по предпоследней и последней лемме (<tex>M</tex> по ней конечно, так как число базовых <tex>p</tex> конечно).
 Любое такое <tex>t</tex>, что <tex>s \leqslant t</tex>  для некоторого <tex>s \in M</tex> имеет корень <tex>root(t) = S</tex>, и его <tex>res(t) \in \Sigma^{*}</tex>, значит <tex>t \in L(\Gamma)</tex>, и значит <tex>\Psi_{\Sigma}(t) \in \Psi_{\Sigma}(L(\Gamma))</tex>. В обратную сторону, любая строка <tex>x \in L(\Gamma)</tex> имеет дерево разбора <tex>t</tex> с корнем <tex>root(t) = S</tex> и <tex>res(t) = x</tex>, и должно существовать <tex>leqslant</tex>-минимальное <tex>s \leqslant t</tex> (в противном бы случае это означало, что <tex>t</tex> не содержит базовых <tex>p</tex>, и значит оно само является <tex>\leqslant</tex>-минимальным), и тогда <tex>\Psi_{\Sigma}(x) \in \{\Psi_{\Sigma}(t) \mid s \leqslant t\}</tex>.
 }}
-Теорема Парика связывает два понятия: функцию <tex>\Psi_{\Sigma}</tex> контекстно-свободного языка и полулинейное множество. Например, для языка <tex>\{a(a^{2}b)^{m}(b^{3}c^{2})^{n} \mid m,n \geq 0\})</tex> функция <tex>\Psi_{\Sigma} = (1,0,0)+\{(2,1,0), (0,3,2)\}^{*}</tex>.
+Теорема Парика связывает два понятия: функцию <tex>\Psi_{\Sigma}</tex> контекстно-свободного языка и полулинейное множество. Например, для языка <tex>\{a(a^{2}b)^{m}(b^{3}c^{2})^{n} \mid m,n \geqslant 0\})</tex> функция <tex>\Psi_{\Sigma} = (1,0,0)+\{(2,1,0), (0,3,2)\}^{*}</tex>.
-<br>Эта теорема, так же, как и лемма о накачке и лемма Огдена, не является достаточной: язык <tex>\{0^{n}1^{n}2^{n} \mid n \geq 0\}</tex> [[Лемма о разрастании для КС-грамматик#Пример доказательства неконтекстно-свободности языка с использованием леммы|не является контекстно-свободным]], однако его множество <tex>\Psi_{\Sigma} = \{(n, n, n) \mid n \geqslant 0\}</tex> является полулинейным: <tex>\Psi_{\Sigma} = \{(n, n, n) \mid n \geqslant 0\} = (0, 0, 0) + \{(1, 1, 1)\}^{*}</tex>.
+<br>Эта теорема, так же, как и лемма о накачке и лемма Огдена, не является достаточной: язык <tex>\{0^{n}1^{n}2^{n} \mid n \geqslant 0\}</tex> [[Лемма о разрастании для КС-грамматик#Пример доказательства неконтекстно-свободности языка с использованием леммы|не является контекстно-свободным]], однако его множество <tex>\Psi_{\Sigma} = \{(n, n, n) \mid n \geqslant 0\}</tex> является полулинейным: <tex>\Psi_{\Sigma} = \{(n, n, n) \mid n \geqslant 0\} = (0, 0, 0) + \{(1, 1, 1)\}^{*}</tex>.
 ==Примеры==
@@ Строка 102: / Строка 99: @@
 Язык <tex>\{a^{p} \mid p</tex> {{---}} простое число<tex>\}</tex> не является контекстно-свободным, так как множество простых чисел не является полулинейным (в арифметике Пресбургера нельзя определить множество простых чисел).
-Язык <tex>\{a^{m}b^{n} \mid m > n</tex> или <tex>m</tex> {{---}} простое и <tex>m \leq n\}</tex> не является контекстно свободным, так как множество, порождаемое функцией <tex>\Psi_{\Sigma}</tex>, не является полулинейным: множество таких пар <tex>\{(m, n) \mid m > n\} = (1, 0) + \{(1, 0), (1, 1)\}</tex> {{---}} линейно, множество таких пар <tex>\{(m, n) \mid m \leqslant n\} = (0, 0) + \{(1, 1), (0, 1)\}</tex> {{---}} линейно, при этом множество простых чисел не является полулинейным, и, как следствие, множество <tex>\{m</tex> {{---}} простое и <tex>m \leqslant n\}</tex> не является полулинейным, <tex>\Psi_{\Sigma}</tex> так же не полулинейно.
+Язык <tex>\{a^{m}b^{n} \mid m > n</tex> или <tex>m</tex> {{---}} простое и <tex>m \leqslant n\}</tex> не является контекстно свободным, так как множество, порождаемое функцией <tex>\Psi_{\Sigma}</tex>, не является полулинейным: множество таких пар <tex>\{(m, n) \mid m > n\} = (1, 0) + \{(1, 0), (1, 1)\}</tex> {{---}} линейно, множество таких пар <tex>\{(m, n) \mid m \leqslant n\} = (0, 0) + \{(1, 1), (0, 1)\}</tex> {{---}} линейно, при этом множество простых чисел не является полулинейным, и, как следствие, множество <tex>\{m</tex> {{---}} простое и <tex>m \leqslant n\}</tex> не является полулинейным, <tex>\Psi_{\Sigma}</tex> так же не полулинейно.
 == См. также ==

@@ Строка 113: / Строка 113: @@
 == Источники информации==
 *Гинзбург С. {{---}} Математическая теория контекстно-свободных языков
-*[https://www8.cs.umu.se/kurser/TDBC92/VT06/final/3.pdf Håkan Lindqvist {{---}} Parikh’s theorem]
+*Dexter C. Kozen {{---}} Automata and Computability
 *[http://cs.stackexchange.com/questions/265/how-to-prove-that-a-language-is-not-context-free Stack Exchange {{---}} How to prove that a language is not context-free?]

@@ Строка 49: / Строка 49: @@
 <br>
-Теперь определим три множества деревьев разбора.
+Теперь же сосредоточимся на языке <tex>L^{\sim}(\Gamma)</tex>. Определим три множества деревьев разбора.
 {{Определение
 |definition =
@@ Строка 64: / Строка 64: @@
 }}
-Последнее множество относится к тем правилам грамматики, которые делают строку больше в процессе вывода, то есть <tex>A \Rightarrow uAv</tex>, где <tex>u, v \in \Sigma</tex>. Эти деревья могут быть использованы, чтобы увеличить дерево разбора в множестве <tex>T'</tex> замещением нетерминала <tex>A</tex> в некотором дереве <tex>t'</tex> на дерево из множества <tex>I</tex>, определение которого написано ниже.
+Последнее множество соотносится с теми правилами грамматики, которые делают строку больше в процессе вывода, то есть <tex>A \Rightarrow uAv</tex>, где <tex>u, v \in \Sigma</tex>. Эти деревья могут быть использованы, чтобы увеличить дерево разбора в множестве <tex>T'</tex> замещением нетерминала <tex>A</tex> в некотором дереве <tex>t'</tex> на дерево из множества <tex>I</tex>, определение которого написано ниже.
 {{Определение
 |definition =
-Пусть <tex>I</tex> {{---}} множество всех деревьев разбора с корнем <tex>A \in N</tex>, содержащих только один нетерминальный лист, который также помечен как <tex>A</tex>.
+Пусть <tex>I</tex> {{---}} множество всех деревьев разбора с корнем <tex>A \in N</tex>, содержащих только один нетерминальный лист, который также помечен как <tex>A</tex>. В дополнение, деревья разбора множества <tex>I</tex> должны удовлетворять условию 2 в определении <tex>T</tex>.
 }}
-В дополнение, деревья разбора множества <tex>I</tex> должны удовлетворять условию 2 в определении <tex>T</tex>. Еще можно заметить, что деревья из <tex>T</tex> и <tex>I</tex> имеют конечную высоту.
+В деревьях из этого множества могут содержаться другие нетерминалы, но главное, чтобы среди листов содержался только корневой.
 <br>
@@ Строка 80: / Строка 82: @@
 |proof=
 Можем заметить, пустая строка может быть удалена из множества <tex>W</tex>, так как она не влияет на суммирование. Обозначим объединение сумм в лемме как <tex>\Phi</tex>.
-Также заметим, что <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>.
+Также заметим, что <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>.
 Доказывать лемму будем в две стадии по индукции.
-<tex>\Longrightarrow</tex>
+<tex>\Longrightarrow</tex> <tex>\Phi \subset L^{\sim}(\Gamma)</tex>.
-<tex>\Phi \subset L^{\sim}(\Gamma)</tex>.
+В этой части доказательства будет рассмотрен случай <tex>m = (m_{1},\ldots,m_{m}) \in \Phi \rightarrow m \in \Psi_{\Sigma}(L^{\sim}(\Gamma)</tex>.
-В этой части доказательства будет рассмотрен случай <tex>m = (m_{1},\ldots,m_{m}) \in \Phi \rightarrow m \in \Psi_{\Sigma}(L^{\sim}(\Gamma)</tex>.
+'''База индукции''':
 <tex>\Longleftarrow</tex> <tex>L^{\sim}(\Gamma) \subset \Phi</tex>.
 }}

@@ Строка 4: / Строка 4: @@
 {{Определение
 |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>.
+Через <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'') соответственно слова и языка.
 }}
@@ Строка 54: / Строка 54: @@
 Пусть <tex>T</tex> {{---}} множество всех терминальных деревьев разбора с корнем <tex>S</tex>, которые удовлетворяют двум условиям:
 . Каждый нетерминал <tex>N</tex> встречается в в дереве.
-. Каждый нетерминал <tex>N</tex> встречается не более чем <tex>k = |N|</tex> раз в дереве.
+. Каждый нетерминал <tex>N</tex> встречается не более чем <tex>k = |N|</tex> раз в любом пути.
 }}
-Деревья из этого множества соотносятся с деревьями разбора языка <tex>L^{\sim}(\Gamma)</tex>, так как при выводе каждого слова из этого языка также используются все нетерминалы грамматики.
+Деревья из этого множества соотносятся с деревьями разбора языка <tex>L^{\sim}(\Gamma)</tex>, так как при выводе каждого слова из этого языка также используются все нетерминалы грамматики. В дальнейшем доказательстве <tex>T</tex> используется для определения отображения Парика языка <tex>L^{\sim}(\Gamma)</tex> как объединение индивидуальных отображений.
 В отличие от предыдущего определения, для следующего множества число <tex>k</tex> для любого нетерминала не ограничено.
@@ Строка 80: / Строка 80: @@
 |proof=
 Можем заметить, пустая строка может быть удалена из множества <tex>W</tex>, так как она не влияет на суммирование. Обозначим объединение сумм в лемме как <tex>\Phi</tex>.
 Доказывать лемму будем в две стадии по индукции.
-<tex>\Longrightarrow</tex> <tex>\Phi \subset L^{\sim}(\Gamma)</tex>.
+<tex>\Longrightarrow</tex>
 <tex>\Longleftarrow</tex> <tex>L^{\sim}(\Gamma) \subset \Phi</tex>.

@@ Строка 1: / Строка 1: @@
-==Используемые определения==
+==Линейные множества==
-В этом разделе предполагается, что зафиксирован некоторый линейный порядок на алфавите <tex>\Sigma</tex>. Пусть <tex>\Sigma = \{a_{1},...,a_{m}\}</tex>.
+В этом разделе предполагается, что зафиксирован некоторый [[Отношение_порядка|линейный порядок]] на алфавите <tex>\Sigma</tex>. Пусть <tex>\Sigma = \{a_{1},\ldots,a_{m}\}</tex>.
 {{Определение
 |definition =
-Через <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>.
+Через <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>.
 }}
@@ Строка 12: / Строка 12: @@
 {{Определение
 |definition =
-Пусть <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>.
+Пусть <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>.
 }}
@@ Строка 22: / Строка 22: @@
 Подмножество множества <tex>\mathbb {N}</tex> называется '''полулинейным''' (англ. ''semilinear''), если оно является объединением конечного числа линейных множеств.
 }}
 *Любое конечное подмножество <tex>\mathbb {N}^{m}</tex> {{---}} полулинейно.
 *Полулинейные множества замкнуты относительно операции объединения, пересечения, разности и проекции.
-*Полулинейные множества по теореме Гинзбурга-Спаниера (англ. ''Ginsburg and Spanier theorem'') {{---}} те, которые определяемы в арифметика Пресбургера (англ. ''Presburger arithmetic'').
+*Полулинейные множества по теореме Гинзбурга-Спаниера (англ. ''Ginsburg and Spanier theorem'') {{---}} те, которые определяемы в арифметике Пресбургера (англ. ''Presburger arithmetic'')<ref>[https://en.wikipedia.org/wiki/Presburger_arithmetic Wikipedia {{---}} Presburger arithmetic]</ref>.
 Пусть <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>.
@@ Строка 42: / Строка 43: @@
 Если множество <tex>\Psi_{\Sigma}(L^{\sim}(\Gamma))</tex> полулинейно для всех контекстно-свободных языков, тогда множество <tex>\Psi_{\Sigma}(L(\Gamma))</tex> также полулинейно.
 |proof=
-Построим грамматики <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> также полулинейно.
+Построим грамматики <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> также полулинейно.
 }}
@@ Строка 73: / Строка 74: @@
 Теперь перейдем к доказательству теоремы.
 <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> представляют возможные поддеревья, которые могут быть использованы для того, чтобы увеличить длину пути в некотором дереве.
+Пусть <tex>w_{1},\ldots,w_{q}</tex> при <tex>q \in \mathbb {N}^{+}</tex> будут множеством строк, порожденных деревьями из <tex>T</tex>, и множество <tex>W</tex> {{---}} набором всех строк <tex>uv</tex>, для которых <tex>uAv</tex> будет результатом, полученным с помощью дерева разбора из <tex>I</tex> с вершиной <tex>A \in N</tex>. Элементы множества <tex>W</tex> представляют возможные поддеревья, которые могут быть использованы для того, чтобы увеличить длину пути в некотором дереве.
 {{Лемма
 |statement=
-Для языка <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>
+Для языка <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>
 |proof=
 Можем заметить, пустая строка может быть удалена из множества <tex>W</tex>, так как она не влияет на суммирование. Обозначим объединение сумм в лемме как <tex>\Phi</tex>.
@@ Строка 102: / Строка 103: @@
 == См. также ==
 *[[Лемма о разрастании для КС-грамматик|Лемма о разрастании для КС-грамматик]]
-== Источники ==
+== Источники информации==
 *Гинзбург С. {{---}} Математическая теория контекстно-свободных языков
 *[https://www8.cs.umu.se/kurser/TDBC92/VT06/final/3.pdf Håkan Lindqvist {{---}} Parikh’s theorem]
 [[Категория: Теория формальных языков]]
 [[Категория: Контекстно-свободные грамматики]]
 [[Категория: Опровержение контекстно-свободности языка]]

@@ Строка 34: / Строка 34: @@
 |statement=Если язык <tex>L \subset \Sigma^{*}</tex> является  [[Контекстно-свободные грамматики, вывод, лево- и правосторонний вывод, дерево разбора|контекстно-свободным]], то множество <tex>\Psi_{\Sigma}(L)</tex> является полулинейным.
 |proof=
-Для доказательства будем пользоваться  [[Лемма о разрастании для КС-грамматик|леммой о накачке для контекстно-свободных языков]].
+Пусть <tex>\Gamma =\langle \Sigma, N, S, P\rangle</tex> {{---}} контекстно-свободная грамматика. Вместо того, чтобы рассматривать <tex>L(\Gamma)</tex>, рассмотрим язык <tex>L^{\sim}(\Gamma)</tex>, содержащий только строки, порожденные выводами, в которых встречаются все нетерминалы грамматики.
-//Пусть <tex>\Gamma =\langle \Sigma, N, S, P\rangle</tex> {{---}} неукорачивающая контекстно-свободная грамматика, порождающая множество <tex>L</tex>, и пусть <tex>n</tex> {{---}} константа из леммы о накачке.
+Так как теорема Парика говорит о том, что для <tex>L(\Gamma)</tex> множество <tex>\Psi_{\Sigma}(L)</tex> полулинейно, то же самое должно сохраняться и для <tex>L^{\sim}(\Gamma)</tex>.
-//Для каждого набора нетерминалов <tex>U</tex>, содержащих <tex>S</tex>,
 }}
@@ Строка 50: / Строка 102: @@
 == См. также ==
 *[[Лемма о разрастании для КС-грамматик|Лемма о разрастании для КС-грамматик]]
 == Источники ==
 *Гинзбург С. {{---}} Математическая теория контекстно-свободных языков
 [[Категория: Теория формальных языков]]
 [[Категория: Контекстно-свободные грамматики]]
 [[Категория: Опровержение контекстно-свободности языка]]