Теорема Парика — различия между версиями

Материал из Викиконспекты
Перейти к: навигация, поиск
м (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 \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>, то есть все листья помечены терминалами, за исключением одного, который совпадает с корнем дерева.
 
# <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>.
 
Будем обозначать <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 \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^{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: Строка 110:
 
== Источники информации==
 
== Источники информации==
 
*Гинзбург С. {{---}} Математическая теория контекстно-свободных языков
 
*Гинзбург С. {{---}} Математическая теория контекстно-свободных языков
*[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?]
 
*[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

Линейные множества

В этом разделе предполагается, что зафиксирован некоторый линейный порядок на алфавите [math]\Sigma[/math]. Пусть [math]\Sigma = \{a_{1},\ldots,a_{m}\}[/math].


Определение:
Через [math]\Psi_{\Sigma}[/math] будем обозначать функцию [math]\Psi_{\Sigma} : \Sigma^{*} \rightarrow \mathbb {N}^{m}[/math], определённую следующим образом: [math]\Psi_{\Sigma}(w) = \langle |w|_{a_{1}} ,\ldots, |w|_{a_{m}} \rangle[/math], где [math]|w|_{a_{i}}[/math] — число появлений символа [math]a_{i}[/math] в слове [math]w[/math]. Аналогично, каждому языку [math]L \subset \Sigma^{*}[/math] ставится в соответствие множество [math]\Psi_{\Sigma}(L) \subset \mathbb {N}^{m}[/math], определённое так: [math]\Psi_{\Sigma}(L) = \{\Psi_{\Sigma}(w) \mid w \in L\}[/math]. Функция называется отображением Парика (англ. Parikh's mapping) соответственно слова и языка.


Пусть [math]\Sigma = \{a, b\}[/math] и [math]L = \{a, abb, bba\}[/math]. Тогда [math]\Psi_{\Sigma}(L) = \{\langle 1, 0 \rangle, \langle 1, 2 \rangle\}[/math].


Определение:
Пусть [math]x_{0}, x_{1},\ldots, x_{p}[/math] при [math]0 \leqslant p \lt \infty[/math] — вектора в множестве [math]\mathbb {N}^{m}[/math]. Множество [math]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}\}^{*}[/math] называется линейным (англ. linear) подмножеством множества [math]\mathbb {N}^{m}[/math].


Говоря проще, линейное подмножество [math]\mathbb {N}^{m}[/math] может быть построено с помощью любого m-размерного вектора [math]x_{0}[/math] добавлением к нему произвольного числа m-размерных векторов из конечного множества, например, 1 раз [math]x_{1}[/math] и 0 раз остальные вектора, 1 раз [math]x_{1}[/math], 1 раз [math]x_{2}[/math] и 0 раз остальные, и так далее.
Множество [math]L = \{(0, 0) + k_{1}(0, 2) + k_{2}(2, 0) \mid k_{1},k_{2} \in \mathbb {N}\} [/math] [math] = \{(2k_{1}, 2k_{2}) \mid k_{1},k_{2} \in \mathbb {N}\}[/math] является линейным.


Определение:
Подмножество множества [math]\mathbb {N}[/math] называется полулинейным (англ. semilinear), если оно является объединением конечного числа линейных множеств.

Полулинейное множество имеет следующие свойства:

  • Любое конечное подмножество [math]\mathbb {N}^{m}[/math] — полулинейно.
  • Полулинейные множества замкнуты относительно операции объединения, пересечения, разности и проекции.
  • Полулинейные множества по теореме Гинзбурга-Спаниера (англ. Ginsburg and Spanier theorem) — те, которые определяемы в арифметике Пресбургера (англ. Presburger arithmetic)[1].

Пусть [math]L_{1} = (1, 2) + \{(3, 5), (7, 11)\}^{*}[/math], [math]L_{2} = (1, 1) + \{(2, 3), (5, 7), (4, 0)\}^{*}[/math], [math]L_{1}[/math] и [math]L_{2}[/math] линейные подмножества [math]\mathbb {N}^{2}[/math], а [math]L = L_{1} \cup L_{2}[/math] является полулинейным подмножеством [math]\mathbb {N}^{2}[/math].

Теорема Парика

Пусть [math]\Gamma =\langle \Sigma, N, S, P\rangle[/math] — контекстно-свободная грамматика.

Далее маленькими латинскими буквами [math]s, t, \ldots[/math] будем обозначать деревья разбора. Для деревьев результатом ([math]res(s)[/math]) будем называть строку из нетерминалов и терминалов, записанных в листьях, упорядоченную слева направо, глубина дерева ([math]dep(s)[/math]) — длина наибольшего пути от листов до корня дерева, будем писать [math]N(s)[/math], чтобы обозначить множество нетерминалов в дереве, а [math]root(s)[/math] — корень дерева.

Обозначим за [math]p[/math] деревья такого вида:

  1. оно содержит хотя бы два узла.
  2. [math]res(p) = u * root(p) * v[/math], где [math]u, v \in \Sigma^{*}[/math], то есть все листья помечены терминалами, за исключением одного, который совпадает с корнем дерева.

Будем обозначать [math]s \# t[/math] если [math]t[/math] может быть получен из [math]s[/math] вставкой дерева [math]p[/math] с нетерминалом [math]A[/math] в качестве корня на место нетерминала [math]A[/math] в дереве [math]s[/math], то есть, можно увеличить [math]s[/math] с помощью некоторого дерева [math]p[/math] так, чтобы получить [math]t[/math]. В [math]s[/math] строго меньше узлов, чем в [math]t[/math].

Пусть [math]p[/math] называется базовым, если оно [math]\#[/math]-минимально среди всех [math]p[/math], то есть не содержит в себе другое [math]p[/math], которое можно вырезать. Или, иначе, [math]p[/math] является базовым, если в [math]s \# t[/math] [math]s[/math] является только тривиальным деревом с одним узлом (который же является и корнем).

Лемма:
Если [math]p[/math] является базовым, то [math]dep(p) \leqslant 2n[/math], где [math]n[/math] количество нетерминалов в N.
Доказательство:
[math]\triangleright[/math]

Обозначим за [math]\gamma[/math] путь от листа с нетерминалом [math]root(p)[/math] до корня. Пусть [math]\gamma[/math] не может быть длиннее, чем [math]n[/math], потому что если бы был, то он содержал бы повторяющийся нетерминал, и, тем самым, содержал бы в себе другое дерево [math]p'[/math], что противоречит тому, что [math]p[/math] базовое.

Для других же листов путь должен не превышать [math]n+1[/math] по тем же причинам. Таким образом, длина любого пути не больше [math]2n[/math].
[math]\triangleleft[/math]

Из леммы и из конечности нетерминалов и продукций в грамматике [math]\Gamma[/math] следует, что количество таких базовых деревьев [math]p[/math] конечно.

Лемма:
Любое дерево разбора [math]t[/math] с [math]res(t) \in \Sigma^{*}[/math] либо [math]\#[/math]-минимально, либо содержит в себе базовое [math]p[/math].
Доказательство:
[math]\triangleright[/math]
Пусть [math]t[/math] не [math]\#[/math]-минимально, тогда оно по определению содержит дерево [math]p[/math]. Пусть [math]p[/math] будет [math]\#[/math]-минимально среди всех [math]p[/math], содержащихся в [math]t[/math], тогда [math]p[/math] является базовым, так как если нет, то оно содержит в себе другое [math]p[/math], что противоречит [math]\#[/math]-минимальности.
[math]\triangleleft[/math]

Пусть [math]s \leqslant t[/math] если [math]t[/math] может быть получен из [math]s[/math] конечной последовательностью вставок базовых [math]p[/math], для которых [math]N(p) \subset N(s)[/math]. Другими словами, нам позволено выбирать любой нетерминал A в дереве и вставлять на это место базовое [math]p[/math] с корнем А в том случае, если [math]p[/math] содержит только те нетерминалы, что есть в [math]s[/math]. Если с помощью таких операций можно получить [math]t[/math], то [math]s \leqslant t[/math].

Если строка [math]\alpha = N^{*} \cup \Sigma^{*}[/math], то за [math]\Psi_{\Sigma}(\alpha)[/math] будем обозначать [math]\Psi_{\Sigma}(x)[/math], где [math]x[/math] получен из [math]\alpha[/math] удалением всех нетерминалов. За [math]\Psi_{\Sigma}(t)[/math] будем обозначать [math]\Psi_{\Sigma}(res(t))[/math].

Лемма:
Множество [math]\{\Psi_{\Sigma}(t) \mid s \leqslant t\}[/math] линейно.
Доказательство:
[math]\triangleright[/math]
[math]\{\Psi_{\Sigma}(t) | s \leqslant t\} = \Psi_{\Sigma}(s) + \langle\{\Psi_{\Sigma}(p) \mid [/math] [math]p[/math] является базовым, и его [math]N(p) \subset N(s)[/math] [math]\}\rangle[/math].
[math]\triangleleft[/math]

Будем называть [math]s[/math] [math]\leqslant[/math]-минимальным, если оно не содержит в себе повторяющихся базовых [math]p[/math].

Лемма:
Если [math]s[/math] [math]\leqslant[/math]-минимально, то его [math]dep(s) \leqslant (k+1)(n+1)[/math], где [math]n[/math] — размер [math]N[/math], а [math]k[/math] — число различных базовых [math]p[/math] в дереве.
Доказательство:
[math]\triangleright[/math]
Если путь длиннее, чем [math]dep(s) \leqslant (k+1)(n+1)[/math], то тогда он может быть поделен на [math]k+1[/math] сегмент, каждый из которых длины как минимум [math]n+1[/math], и каждый имеет повторяющийся нетерминал, а, следовательно, [math]s[/math] содержит [math]k+1[/math] непересекающееся поддерево [math]p[/math] (деревья называются непересекающимися в данном случае, если у них нет общих узлов, или если корень одного является листом другого дерева), каждое из которых, в соответствие с леммой, либо само является базовым, либо содержит базовое в себе, следовательно, в дереве [math]s[/math] содержится [math]k+1[/math] непересекающихся базовых [math]p[/math]. Но так как число различных базовых [math]p[/math] равно [math]k[/math], какое-то [math]p[/math] появляется в этом наборе дважды, что противоречит [math]\leqslant[/math]-минимальности.
[math]\triangleleft[/math]
Теорема (Парика, англ. Parikh's theorem):
Если язык [math]L \subset \Sigma^{*}[/math] является контекстно-свободным, то множество [math]\Psi_{\Sigma}(L)[/math] является полулинейным.
Доказательство:
[math]\triangleright[/math]

Воспользуемся ранее полученными результатами в доказательстве.

Зададим [math]M = \{s \mid s[/math] [math]\leqslant[/math]-минимально, [math]root(s) = S, res(s) \in \Sigma^{*}\}[/math].

Покажем, что [math]\Psi_{\Sigma}(L(\Gamma)) = \bigcup \limits_{s \in M} \{\Psi_{\Sigma}(t) \mid s \leqslant t\}[/math]. Это множество полулинейно по предпоследней и последней лемме ([math]M[/math] по ней конечно, так как число базовых [math]p[/math] конечно).

Любое такое [math]t[/math], что [math]s \leqslant t[/math] для некоторого [math]s \in M[/math] имеет корень [math]root(t) = S[/math], и его [math]res(t) \in \Sigma^{*}[/math], значит [math]t \in L(\Gamma)[/math], и значит [math]\Psi_{\Sigma}(t) \in \Psi_{\Sigma}(L(\Gamma))[/math]. В обратную сторону, любая строка [math]x \in L(\Gamma)[/math] имеет дерево разбора [math]t[/math] с корнем [math]root(t) = S[/math] и [math]res(t) = x[/math], и должно существовать [math]\leqslant[/math]-минимальное [math]s \leqslant t[/math] (в противном бы случае это означало, что [math]t[/math] не содержит базовых [math]p[/math], и значит оно само является [math]\leqslant[/math]-минимальным), и тогда [math]\Psi_{\Sigma}(x) \in \{\Psi_{\Sigma}(t) \mid s \leqslant t\}[/math].
[math]\triangleleft[/math]

Теорема Парика связывает два понятия: функцию [math]\Psi_{\Sigma}[/math] контекстно-свободного языка и полулинейное множество. Например, для языка [math]\{a(a^{2}b)^{m}(b^{3}c^{2})^{n} \mid m,n \geqslant 0\})[/math] функция [math]\Psi_{\Sigma} = (1,0,0)+\{(2,1,0), (0,3,2)\}^{*}[/math].
Эта теорема, так же, как и лемма о накачке и лемма Огдена, не является достаточной: язык [math]\{0^{n}1^{n}2^{n} \mid n \geqslant 0\}[/math] не является контекстно-свободным, однако его множество [math]\Psi_{\Sigma} = \{(n, n, n) \mid n \geqslant 0\}[/math] является полулинейным: [math]\Psi_{\Sigma} = \{(n, n, n) \mid n \geqslant 0\} = (0, 0, 0) + \{(1, 1, 1)\}^{*}[/math].

Примеры

Язык [math]\{a^{p} \mid p[/math] — простое число[math]\}[/math] не является контекстно-свободным, так как множество простых чисел не является полулинейным (в арифметике Пресбургера нельзя определить множество простых чисел).

Язык [math]\{a^{m}b^{n} \mid m \gt n[/math] или [math]m[/math] — простое и [math]m \leqslant n\}[/math] не является контекстно свободным, так как множество, порождаемое функцией [math]\Psi_{\Sigma}[/math], не является полулинейным: множество таких пар [math]\{(m, n) \mid m \gt n\} = (1, 0) + \{(1, 0), (1, 1)\}[/math] — линейно, множество таких пар [math]\{(m, n) \mid m \leqslant n\} = (0, 0) + \{(1, 1), (0, 1)\}[/math] — линейно, при этом множество простых чисел не является полулинейным, и, как следствие, множество [math]\{m[/math] — простое и [math]m \leqslant n\}[/math] не является полулинейным, [math]\Psi_{\Sigma}[/math] так же не полулинейно.

См. также

Примечания

Источники информации