22
правки
Изменения
Нет описания правки
==Используемые определенияЛинейные множества==В этом разделе предполагается, что зафиксирован некоторый [[Отношение_порядка|линейный порядок ]] на алфавите <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}} ,...\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>.
}}
{{Определение
|definition =
Пусть <tex>x_{0}, x_{1},...\ldots, x_{p}</tex> при <tex>0 \leq 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>\mathbb {N}</tex> называется '''полулинейным''' (англ. ''semilinear''), если оно является объединением конечного числа линейных множеств.
}}
Полулинейное множество имеет следующие свойства:
*Любое конечное подмножество <tex>\mathbb {N}^{m}</tex> {{---}} полулинейно.
*Полулинейные множества замкнуты относительно операции объединения, пересечения, разности и проекции.
*Полулинейные множества по теореме Гинзбурга-Спаниера (англ. ''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>.
Если множество <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 ... \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> также полулинейно.
}}
Теперь перейдем к доказательству теоремы.
<br>
Пусть <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 ... \ldots \cup (\Psi_{\Sigma}(w_{q})+\Psi_{\Sigma}(W)^{*}) </tex>
|proof=
Можем заметить, пустая строка может быть удалена из множества <tex>W</tex>, так как она не влияет на суммирование. Обозначим объединение сумм в лемме как <tex>\Phi</tex>.
== См. также ==
*[[Лемма о разрастании для КС-грамматик|Лемма о разрастании для КС-грамматик]]
*[[Доказательство нерегулярности языков: лемма о разрастании|Доказательство нерегулярности языков: лемма о разрастании]]
==Примечания==
<references/>
== Источники информации==
*Гинзбург С. {{---}} Математическая теория контекстно-свободных языков
*[https://www8.cs.umu.se/kurser/TDBC92/VT06/final/3.pdf Håkan Lindqvist {{---}} Parikh’s theorem]
*[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?]
[[Категория: Теория формальных языков]]
[[Категория: Контекстно-свободные грамматики]]
[[Категория: Опровержение контекстно-свободности языка]]
