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

Материал из Викиконспекты
Перейти к: навигация, поиск
Строка 34: Строка 34:
 
|statement=Если язык <tex>L \subset \Sigma^{*}</tex> является  [[Контекстно-свободные грамматики, вывод, лево- и правосторонний вывод, дерево разбора|контекстно-свободным]], то множество <tex>\Psi_{\Sigma}(L)</tex> является полулинейным.
 
|statement=Если язык <tex>L \subset \Sigma^{*}</tex> является  [[Контекстно-свободные грамматики, вывод, лево- и правосторонний вывод, дерево разбора|контекстно-свободным]], то множество <tex>\Psi_{\Sigma}(L)</tex> является полулинейным.
 
|proof=
 
|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>,  
+
 
 +
<br>
 +
{{Лемма
 +
|statement=
 +
Если множество <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>k = 2^{|N|} - 1</tex>. Вычитание происходит из-за того, что начальный нетерминал <tex>S</tex> не должен быть удален.
 +
 
 +
<br>
 +
Теперь определим три множества деревьев разбора.
 +
{{Определение
 +
|definition =
 +
Пусть <tex>T</tex> {{---}} множество всех терминальных деревьев разбора с корнем <tex>S</tex>, которые удовлетворяют двум условиям:
 +
1. Каждый нетерминал <tex>N</tex> встречается в в дереве.
 +
2. Каждый нетерминал <tex>N</tex> встречается не более чем <tex>k = |N|</tex> раз в дереве.
 +
}}
 +
Деревья из этого множества соотносятся с деревьями разбора языка <tex>L^{\sim}(\Gamma)</tex>, так как при выводе каждого слова из этого языка также используются все нетерминалы грамматики.
 +
 
 +
В отличие от предыдущего определения, для следующего множества число <tex>k</tex> для любого нетерминала не ограничено.
 +
{{Определение
 +
|definition =
 +
Пусть <tex>T'</tex> {{---}} множество всех терминальных деревьев разбора с корнем <tex>S</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> должны удовлетворять условию 2 в определении <tex>T</tex>. Еще можно заметить, что деревья из <tex>T</tex> и <tex>I</tex> имеют конечную высоту.
 +
 
 +
<br>
 +
Теперь перейдем к доказательству теоремы.
 +
<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> представляют возможные поддеревья, которые могут быть использованы для того, чтобы увеличить длину пути в некотором дереве.
 +
{{Лемма
 +
|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>
 +
|proof=
 +
Можем заметить, пустая строка может быть удалена из множества <tex>W</tex>, так как она не влияет на суммирование. Обозначим объединение сумм в лемме как <tex>\Phi</tex>.
 +
 
 +
Доказывать лемму будем в две стадии по индукции.
 +
 
 +
<tex>\Longrightarrow</tex> <tex>\Phi \subset L^{\sim}(\Gamma)</tex>.
 +
 
 +
 
 +
<tex>\Longleftarrow</tex> <tex>L^{\sim}(\Gamma) \subset \Phi</tex>.
 +
 
 +
}}
 +
 
 
}}
 
}}
  
Строка 50: Строка 102:
 
== См. также ==
 
== См. также ==
 
*[[Лемма о разрастании для КС-грамматик|Лемма о разрастании для КС-грамматик]]
 
*[[Лемма о разрастании для КС-грамматик|Лемма о разрастании для КС-грамматик]]
 +
  
 
== Источники ==
 
== Источники ==
 
*Гинзбург С. {{---}} Математическая теория контекстно-свободных языков
 
*Гинзбург С. {{---}} Математическая теория контекстно-свободных языков
 +
*[https://www8.cs.umu.se/kurser/TDBC92/VT06/final/3.pdf Håkan Lindqvist {{---}} Parikh’s theorem]
  
 
[[Категория: Теория формальных языков]]
 
[[Категория: Теория формальных языков]]
 
[[Категория: Контекстно-свободные грамматики]]
 
[[Категория: Контекстно-свободные грамматики]]
 
[[Категория: Опровержение контекстно-свободности языка]]
 
[[Категория: Опровержение контекстно-свободности языка]]

Версия 00:51, 21 декабря 2016

Используемые определения

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


Определение:
Через [math]\Psi_{\Sigma}[/math] будем обозначать функцию [math]\Psi_{\Sigma} : \Sigma^{*} \rightarrow \mathbb {N}^{m}[/math], определённую следующим образом: [math]\Psi_{\Sigma}(w) = \langle |w|_{a_{1}} ,..., |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].


Пусть [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},..., x_{p}[/math] при [math]0 \leq 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 \geq 0, k_{1},...,k_{p} \in \mathbb {N}\} = x_{0} + \{x_{1},..., 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).

Пусть [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].

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

Теорема (Парика, англ. Parikh's theorem):
Если язык [math]L \subset \Sigma^{*}[/math] является контекстно-свободным, то множество [math]\Psi_{\Sigma}(L)[/math] является полулинейным.
Доказательство:
[math]\triangleright[/math]

Пусть [math]\Gamma =\langle \Sigma, N, S, P\rangle[/math] — контекстно-свободная грамматика. Вместо того, чтобы рассматривать [math]L(\Gamma)[/math], рассмотрим язык [math]L^{\sim}(\Gamma)[/math], содержащий только строки, порожденные выводами, в которых встречаются все нетерминалы грамматики. Так как теорема Парика говорит о том, что для [math]L(\Gamma)[/math] множество [math]\Psi_{\Sigma}(L)[/math] полулинейно, то же самое должно сохраняться и для [math]L^{\sim}(\Gamma)[/math].


Лемма:
Если множество [math]\Psi_{\Sigma}(L^{\sim}(\Gamma))[/math] полулинейно для всех контекстно-свободных языков, тогда множество [math]\Psi_{\Sigma}(L(\Gamma))[/math] также полулинейно.
Доказательство:
[math]\triangleright[/math]
Построим грамматики [math]\Gamma_{1},...\Gamma_{k}[/math] для какого-то [math]k \in \mathbb {N}^{+}[/math] путем удаления из грамматики [math]\Gamma[/math] нетерминалов. Тогда [math]L(\Gamma) = L^{\sim}(\Gamma_{1}) \cup ... \cup L^{\sim}(\Gamma_{k})[/math]. Так как для каждого из языков [math]L^{\sim}(\Gamma_{p})[/math] множество [math]\Psi_{\Sigma}[/math] полулинейно, то, по свойствам полулинейных множеств, для [math]L(\Gamma)[/math] [math]\Psi_{\Sigma}[/math] также полулинейно.
[math]\triangleleft[/math]

Стоит заметить, что число таких языков в лемме ограничено числом нетерминалов в грамматике: [math]k = 2^{|N|} - 1[/math]. Вычитание происходит из-за того, что начальный нетерминал [math]S[/math] не должен быть удален.


Теперь определим три множества деревьев разбора.

Определение:
Пусть [math]T[/math] — множество всех терминальных деревьев разбора с корнем [math]S[/math], которые удовлетворяют двум условиям:

1. Каждый нетерминал [math]N[/math] встречается в в дереве.

2. Каждый нетерминал [math]N[/math] встречается не более чем [math]k = |N|[/math] раз в дереве.

Деревья из этого множества соотносятся с деревьями разбора языка [math]L^{\sim}(\Gamma)[/math], так как при выводе каждого слова из этого языка также используются все нетерминалы грамматики.

В отличие от предыдущего определения, для следующего множества число [math]k[/math] для любого нетерминала не ограничено.

Определение:
Пусть [math]T'[/math] — множество всех терминальных деревьев разбора с корнем [math]S[/math], которые удовлетворяют первому условию из предыдущего определения.


Последнее множество относится к тем правилам грамматики, которые делают строку больше в процессе вывода, то есть [math]A \Rightarrow uAv[/math], где [math]u, v \in \Sigma[/math]. Эти деревья могут быть использованы, чтобы увеличить дерево разбора в множестве [math]T'[/math] замещением нетерминала [math]A[/math] в некотором дереве [math]t'[/math] на дерево из множества [math]I[/math], определение которого написано ниже.

Определение:
Пусть [math]I[/math] — множество всех деревьев разбора с корнем [math]A \in N[/math], содержащих только один нетерминальный лист, который также помечен как [math]A[/math].

В дополнение, деревья разбора множества [math]I[/math] должны удовлетворять условию 2 в определении [math]T[/math]. Еще можно заметить, что деревья из [math]T[/math] и [math]I[/math] имеют конечную высоту.


Теперь перейдем к доказательству теоремы.
Пусть [math]w_{1},...,w_{q}[/math] при [math]q \in \mathbb {N}^{+}[/math] будут множеством строк, порожденных деревьями из [math]T[/math], и множество [math]W[/math] — набором всех строк [math]uv[/math], для которых [math]uAv[/math] будет результатом, полученным с помощью дерева разбора из [math]I[/math] с вершиной [math]A \in N[/math]. Элементы множества [math]W[/math] представляют возможные поддеревья, которые могут быть использованы для того, чтобы увеличить длину пути в некотором дереве.

Лемма:
Для языка [math]L^{\sim}(\Gamma)[/math] выполняется равенство [math]\Psi_{\Sigma}(L^{\sim}(\Gamma)) = (\Psi_{\Sigma}(w_{1})+\Psi_{\Sigma}(W)^{*}) \cup ... \cup (\Psi_{\Sigma}(w_{q})+\Psi_{\Sigma}(W)^{*}) [/math]
Доказательство:
[math]\triangleright[/math]

Можем заметить, пустая строка может быть удалена из множества [math]W[/math], так как она не влияет на суммирование. Обозначим объединение сумм в лемме как [math]\Phi[/math].

Доказывать лемму будем в две стадии по индукции.

[math]\Longrightarrow[/math] [math]\Phi \subset L^{\sim}(\Gamma)[/math].


[math]\Longleftarrow[/math] [math]L^{\sim}(\Gamma) \subset \Phi[/math].
[math]\triangleleft[/math]
[math]\triangleleft[/math]

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

См. также


Источники