22
правки
Изменения
Новая страница: «==Используемые определения== В этом разделе предполагается, что зафиксирован некоторый л...»
==Используемые определения==
В этом разделе предполагается, что зафиксирован некоторый линейный порядок на алфавите <tex>\Sigma</tex>. Пусть <tex>\Sigma = \{a_{1},...,a_{n}\}</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>\Sigma = \{a, b\}</tex> и <tex>L = \{a, abb, bba\}</tex>. Тогда <tex>\Psi_{\Sigma}(L) = \{\langle 1, 0 \rangle, \langle 1, 2 \rangle\}</tex>.
{{Определение
|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>\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>Множество <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> является линейным.
{{Определение
|definition =
Подмножество множества <tex>\mathbb {N}</tex> называется '''полулинейным''' (англ. ''semilinear''), если оно является объединением конечного числа линейных множеств.
}}
*Любое конечное подмножество <tex>\mathbb {N}^{m}</tex> {{---}} полулинейно.
*Полулинейные множества замкнуты относительно операции объединения, пересечения, разности и проекции.
*Полулинейные множества по теореме Гинзбурга-Спаниера (англ. ''Ginsburg and Spanier theorem'') {{---}} те, которые определяемы в арифметика Пресбургера (англ. ''Presburger arithmetic'').
Пусть <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>.
С помощью линейного множества можно представить функцию <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>.
==Теорема Парика==
{{Теорема
|about=
Парика, англ. ''Parikh's theorem''
|statement=Если язык <tex>L \subset \Sigma^{*}</tex> является [[Контекстно-свободные грамматики, вывод, лево- и правосторонний вывод, дерево разбора|контекстно-свободным]], то множество <tex>\Psi_{\Sigma}(L)</tex> является полулинейным.
|proof=
Для доказательства будем пользоваться [[Лемма о разрастании для КС-грамматик|леммой о накачке для контекстно-свободных языков]].
Пусть <tex>\Gamma =\langle \Sigma, N, S, P\rangle</tex> {{---}} неукорачивающая контекстно-свободная грамматика, порождающая множество <tex>L</tex>, и пусть <tex>n</tex> {{---}} константа из леммы о накачке.
Для каждого набора нетерминалов <tex>U</tex>, содержащих <tex>S</tex>,
}}
Эта теорема, так же, как и лемма о накачке и лемма Огдена, не является достаточной: язык <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>.
==Примеры==
Язык <tex>\{a^{p} \mid p</tex> {{---}} простое число<tex>\}</tex> не является контекстно-свободным, так как множество простых чисел не является полулинейным (в арифметике Пресбургера нельзя определить множество простых чисел).
Язык <tex>\{a^{m}b^{n} \mid m > n</tex> или <tex>m</tex> {{---}} простое и <tex>m \leq n\}</tex> не является контекстно свободным, так как множество, порождаемое функцией <tex>\Psi_{\Sigma}</tex>, не является полулинейным: множество таких пар <tex>\{(m, n) \mid m > n\} = (1, 0) + \{(1, 0), (1, 1)\}</tex> {{---}} линейно, множество таких пар <tex>\{(m, n) \mid m \leq n\} = (0, 0) + \{(1, 1), (0, 1)\}</tex> {{---}} линейно, при этом множество простых чисел не является полулинейным, и, как следствие, множество <tex>\{m</tex> {{---}} простое и <tex>m \leq n\}</tex> не является полулинейным, <tex>\Psi_{\Sigma}</tex> так же не полулинейно.
== См. также ==
*[[Лемма о разрастании для КС-грамматик|Лемма о разрастании для КС-грамматик]]
== Источники ==
*Гинзбург С. {{---}} Математическая теория контекстно-свободных языков
[[Категория: Теория формальных языков]]
[[Категория: Контекстно-свободные грамматики]]
[[Категория: Опровержение контекстно-свободности языка]]
В этом разделе предполагается, что зафиксирован некоторый линейный порядок на алфавите <tex>\Sigma</tex>. Пусть <tex>\Sigma = \{a_{1},...,a_{n}\}</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>\Sigma = \{a, b\}</tex> и <tex>L = \{a, abb, bba\}</tex>. Тогда <tex>\Psi_{\Sigma}(L) = \{\langle 1, 0 \rangle, \langle 1, 2 \rangle\}</tex>.
{{Определение
|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>\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>Множество <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> является линейным.
{{Определение
|definition =
Подмножество множества <tex>\mathbb {N}</tex> называется '''полулинейным''' (англ. ''semilinear''), если оно является объединением конечного числа линейных множеств.
}}
*Любое конечное подмножество <tex>\mathbb {N}^{m}</tex> {{---}} полулинейно.
*Полулинейные множества замкнуты относительно операции объединения, пересечения, разности и проекции.
*Полулинейные множества по теореме Гинзбурга-Спаниера (англ. ''Ginsburg and Spanier theorem'') {{---}} те, которые определяемы в арифметика Пресбургера (англ. ''Presburger arithmetic'').
Пусть <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>.
С помощью линейного множества можно представить функцию <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>.
==Теорема Парика==
{{Теорема
|about=
Парика, англ. ''Parikh's theorem''
|statement=Если язык <tex>L \subset \Sigma^{*}</tex> является [[Контекстно-свободные грамматики, вывод, лево- и правосторонний вывод, дерево разбора|контекстно-свободным]], то множество <tex>\Psi_{\Sigma}(L)</tex> является полулинейным.
|proof=
Для доказательства будем пользоваться [[Лемма о разрастании для КС-грамматик|леммой о накачке для контекстно-свободных языков]].
Пусть <tex>\Gamma =\langle \Sigma, N, S, P\rangle</tex> {{---}} неукорачивающая контекстно-свободная грамматика, порождающая множество <tex>L</tex>, и пусть <tex>n</tex> {{---}} константа из леммы о накачке.
Для каждого набора нетерминалов <tex>U</tex>, содержащих <tex>S</tex>,
}}
Эта теорема, так же, как и лемма о накачке и лемма Огдена, не является достаточной: язык <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>.
==Примеры==
Язык <tex>\{a^{p} \mid p</tex> {{---}} простое число<tex>\}</tex> не является контекстно-свободным, так как множество простых чисел не является полулинейным (в арифметике Пресбургера нельзя определить множество простых чисел).
Язык <tex>\{a^{m}b^{n} \mid m > n</tex> или <tex>m</tex> {{---}} простое и <tex>m \leq n\}</tex> не является контекстно свободным, так как множество, порождаемое функцией <tex>\Psi_{\Sigma}</tex>, не является полулинейным: множество таких пар <tex>\{(m, n) \mid m > n\} = (1, 0) + \{(1, 0), (1, 1)\}</tex> {{---}} линейно, множество таких пар <tex>\{(m, n) \mid m \leq n\} = (0, 0) + \{(1, 1), (0, 1)\}</tex> {{---}} линейно, при этом множество простых чисел не является полулинейным, и, как следствие, множество <tex>\{m</tex> {{---}} простое и <tex>m \leq n\}</tex> не является полулинейным, <tex>\Psi_{\Sigma}</tex> так же не полулинейно.
== См. также ==
*[[Лемма о разрастании для КС-грамматик|Лемма о разрастании для КС-грамматик]]
== Источники ==
*Гинзбург С. {{---}} Математическая теория контекстно-свободных языков
[[Категория: Теория формальных языков]]
[[Категория: Контекстно-свободные грамматики]]
[[Категория: Опровержение контекстно-свободности языка]]
