1
правка
Изменения
Новая страница: «==Базовые определения== {{Определение |id=def11 |definition= Пусть <tex>t_0,..., t_m \in \mathbb{N}^{n}</tex>, где <tex>m \i...»
==Базовые определения==
{{Определение
|id=def11
|definition=
Пусть <tex>t_0,..., t_m \in \mathbb{N}^{n}</tex>, где <tex>m \in \mathbb{N}</tex> и <tex>n \in \mathbb{N}^{+}</tex>, тогда множество <tex>M = \{t_0 + l_1 t_1 + ... + l_m t_m | l_1,..., l_m \in \mathbb{N}\} = t_0 + \{t_1,..., t_m\}^{*}</tex> называется '''линейным подмножеством''' <tex>\mathbb{N}^{n}</tex> (англ. ''linear subset'')
}}
{{Определение
|id=def12
|definition=
'''Полулинейное подмножество''' <tex>\mathbb{N}^{n}</tex> (англ. ''semilinear subset'') {{---}} объединение конечно числа линейных подмножество <tex>M_1,...,M_k</tex>, где <tex>k \in \mathbb{N}^{+}</tex>.
}}
{{Определение
|id=def13
|definition=
Пусть <tex>\Sigma = \{a_1,...,a_n\}</tex>, где <tex>n \in \mathbb{N}^{+}</tex> и порядок <tex>a_1,...,a_n</tex> произвольный, но фиксированный (выбран определенный порядок, но не важно какой именно).
Для <tex>w \in \Sigma^{*}</tex> '''образ Париха''' (англ. ''Parikh image'') {{---}} <tex>\Psi(w) = (m_1,...,m_n)</tex>, где <tex>m_i</tex> {{---}} количество <tex>a_i</tex> в <tex>w</tex>
}}
{{Определение
|id=def14
|definition=
Пусть язык <tex>L \subseteq \Sigma^{*}</tex>. Тогда '''соответствие Париха''' (англ. ''Parikh mapping'') на языке <tex>L</tex> {{---}} <tex>\Psi(L) = \{\Psi(w)|w \in L \} </tex>
}}
==Теорема Париха==
{{Теорема
|id=th1
|author=
Parikh
|statement=
Для <tex>\forall</tex> контекстно свободного языка <tex>L</tex>, <tex>\Psi(L)</tex> {{---}} эффективно полулинейная. Кортежи, определяющие <tex>\Psi(L)</tex> можно эффективно построить из КС грамматики, генерирующей язык <tex>L</tex>.
|proof=
Доказательство разобьем на 3 части:
===Первая часть===
Пусть дана грамматика <tex>G=(N, \Sigma, R, S)</tex>. Будем рассматривать язык <tex>L^{\sim}(G)</tex>, состоящий из слов, сгенерированных деревьями решений, в которых встречаются ''все'' нетерминалы из <tex>N</tex>.
{{Утверждение
|id=proposal1
|statement=
<tex>L^{\sim}(G)</tex> {{---}} полулинейный
|proof=
<tex>L^{\sim}(G)</tex> {{---}} подмножество <tex>L(G)</tex>, который по утверждению теоремы полулинейный.
}}
{{Лемма
|id=lemma1
|statement=
Если <tex>\Psi(L^{\sim}(G))</tex> {{---}} полулинейный для всех КС языков, тогда <tex>\Psi(L(G))</tex> {{---}} полулинейный.
|proof=
Построит все грамматики <tex>G_1,...,G_k</tex>, где <tex>k \in \mathbb{N}^{+}</tex>, полученныt из <tex>G</tex> удалением нетерминалов. Тогда <tex>L(G) = L^{\sim}(G_1) \cup ... \cup L^{\sim}(G_k)</tex> и следовательно <tex>\Psi(L(G)) = \Psi(L^{\sim}(G_1)) \cup ... \cup \Psi(L^{\sim}(G_K))</tex> {{---}} полулинейный по определению.
}}
Заметим, что количество языков <tex>k</tex> в лемме ограничено количеством нетерминалов граммитики <tex>G</tex>: <tex>k \le 2^{|N|} - 1</tex>.
}}
===Вторая часть===
В этой части рассмотрим деревья вывода, которые используются в генерации языка <tex>L^{\sim}(G)</tex>. Определим три специальных вида деревьев с ограниченными свойствами.
{{Определение
|id=def21
|definition=
'''Множество терминальных деревьев вывода с корнем <tex>S</tex>''' (англ. ''set of terminal derivation trees with root S'') {{---}} множество деревьев, которые удовлетворяют свойствам:
# Все нетерминалы встречаются в дереве
# Ни один нетерминал не встречается более <tex>k = |N|</tex> раз на любом пути в дереве
Обозначим это множество <tex>T</tex>.
}}
Элементы множества <tex>T</tex> соответствуют деревьям вывода для языка <tex>L^{\sim}(G)</tex>.
{{Определение
|id=def22
|definition=
'''Множество всех терминальных деревьев''' (англ. ''the set of all terminal trees'') {{---}} множество всех терминальных деревьев вывода, удовлетворяющих только первому пункту из [[#def21|определения]].
}}
{{Определение
|id=def23
|definition=
'''Множество промежуточных деревьев''' (англ. ''set of intermediate trees'') {{---}} множество всех деревьев вывода с корнем <tex>A \in N </tex>, содержащих ровно один нетерминальный лист с тем же нетерминалом <tex>A</tex>. Кроме того, это множество должно удовлетворять второму условию из [[#def21|определения]].
Обозначим это множество <tex>I</tex>
}}
{{Утверждение
|id=proposal2
|statement=
Константа <tex>k</tex> из [[#def21|определения]] <tex>T</tex> ограничена сверху значением <tex>|N| \cdot c</tex>, где <tex>c</tex> {{---}} количество повторений нетерминала на пути. Следовательно и <tex>T</tex>, и <tex>I</tex> имеют конечную высоту.
}}
=== Третья часть ===
{{Определение
|id=def31
|definition=
Пусть <tex>w_1,...,w_q</tex>, где <tex>q \in \mathbb{N}^{+}</tex>, {{---}} '''множество порожденных строк''' (англ. ''set of yielded strings'') из деревьев, лежащих в [[#def21|<tex>T</tex>]]
}}
{{Определение
|id=def32
|definition=
Пусть <tex>W</tex> {{---}} множество все строк вида <tex>uv</tex> таких, что <tex>uAv</tex> {{---}} результат какого-то дерева вывода из <tex>I</tex> для некоторого терминала <tex>A \in N</tex>
}}
Внимательно посмотрев на последнее определение, очевидно можно заметить, что элементы <tex>W</tex> представляют собой возможные поддеревья, который могут быть использованы для того, чтобы сделать дерево вывода больше.
Другими словами, элементы <tex>W</tex> соответствуют правилу в КС грамматике, которое делает строку длиннее, вводя нетерминал между двумя терминалами.
{{Лемма
|id=lemma2
|statement=
<tex>
\Psi(L^{\sim}(G)) =
\left.
\begin{matrix}
& \Psi(w_1) + \Psi(W)* \\
& \cup \\
& . \\
& . \\
& . \\
& \cup \\
& \Psi(w_q) + \Psi(W)* \\
\end{matrix}
\right\}
\Phi
</tex>
|proof=
(по индукции)
'''Вправо'''
<tex>\Phi \subseteq L^{\sim}(G)</tex>
''База индукции'': Пусть <tex>m = \Psi(w_i)</tex> для некоторого <tex>i \in \mathbb{N}^{+} </tex>, тогда <tex>w_i \in L^{\sim}(G)</tex>. Следовательно <tex>\Psi(w_i) \in \Psi(L^{\sim}(G))</tex>. По [[#def22|определению]] <tex>\widetilde{T}</tex> <tex>w_i</tex> соответствует строке, формирующей язык <tex>L^{\sim}(G)</tex>.
''Переход'': Пусть <tex>m = m' + \Psi(u)</tex>, где <tex>u \in W</tex>
Есть дерево <tex>t \in \widetilde{T}</tex> с результатом <tex>w</tex> такое, что <tex>\Psi(w) = m'</tex>. Также есть дерево <tex>t' \in I </tex> выводящее <tex>u_0 A v_0 </tex> такое, что <tex>u = u_0 v_0</tex>
Теперь построим дерево вывода, полученное заменой всех вершин <tex>p</tex> с нетерминалом <tex>A</tex> в дереве <tex>t</tex> на деревья полученные заменой листов с нетерминалом <tex>A</tex> в дереве <tex>t'</tex> на поддерево <tex>t</tex> с корнем в вершине <tex>p</tex>. Получившееся дерево принадлежит множеству <tex>\widetilde{T}</tex> и его результат <tex>z</tex> удовлетворяет равенству <tex>\Psi(z) = \Psi(w) + \Psi(u) = m </tex>.
Полученное равенство доказывает шаг индукции.
'''Влево'''
<tex>L^{\sim}(G) \subseteq \Phi </tex>
''База индукции'': Если <tex>t \in T </tex>, тогда <tex>w = w_i </tex> для некотого <tex>i \in \mathbb{N}^{+} </tex>. Таким образом <tex> \Psi(w) \in \Phi </tex>.
''Шаг индукции'': Пусть <tex>p_1,...,p_n, где <tex>n \in \mathbb{N}^{+}</tex>, {{---}} вершины на некотором пути и пусть индексы обозначают позицию вершины на этом пути. Более того, пусть все вершины будут помечены одним и тем же нетерминалом <tex>A</tex> таким, что все ''хорошие'' поддеревья дерева с корнем в <tex>p_1</tex> удовлетворяют условию 2 из [[#def21|определения]].
Пусть <tex>t_i</tex> будет дерево, полученное из дерева <tex>t</tex> удалением вершин в <tex>p_i</tex> и <tex>p_{i+1}</tex>. Наоборот, пусть дерево <tex>\bar{t_i}</tex> получено удалением вершин между <tex>p_i</tex> и <tex>p_{i+1}</tex>. Тогда <tex>t_i \in I </tex> и <tex>\Psi(w) = \Psi(\bar{u_i}) + \Psi(u_i)</tex>, где <tex>u_i</tex> и <tex>\bar{u_i}</tex> являются результатом вывода деревьев <tex>t_i</tex> и <tex>\bar{t_i}</tex> соответственно.
Осталось показать, что <tex>\bar{t_i}</tex> может быть выбрано так, чтобы <tex>\bar{t_i} \in \widetilde{T}</tex>
Пусть <tex>N\backslash{A} = \{B_1,...,B_{n-1}\}</tex>, где <tex>n \in \mathbb{N}^{+}</tex>. Тогда <tex>\bar{t_i} \in \widetilde{T}</tex>, если <tex>t_i</tex> содержит все <tex>B_j</tex> в <tex>t</tex> для некоторого <tex> j \notin \{1,...,n - 1\}</tex>. Но так как есть <tex>n</tex> выборов для <tex>i</tex>, должно быть хотя бы одно <tex>i \in \{0,...,n - 1\}</tex>, для которого это не выполняется. Следовательно <tex>\bar{t_i} \in \widetilde{T}</tex> и шаг индукции доказан.
}}
Доказательство показывает, что соответствие Париха КС языка равносильно тому, что получено из терминальных деревьев выхода, которые имеют самые короткие из возможных пути и их результат вывода и добавление добавлений от поддеревьев, которые могут быть подкачаны произвольное количество раз в соответствующее линейное подмножество.
{{Определение
|id=def11
|definition=
Пусть <tex>t_0,..., t_m \in \mathbb{N}^{n}</tex>, где <tex>m \in \mathbb{N}</tex> и <tex>n \in \mathbb{N}^{+}</tex>, тогда множество <tex>M = \{t_0 + l_1 t_1 + ... + l_m t_m | l_1,..., l_m \in \mathbb{N}\} = t_0 + \{t_1,..., t_m\}^{*}</tex> называется '''линейным подмножеством''' <tex>\mathbb{N}^{n}</tex> (англ. ''linear subset'')
}}
{{Определение
|id=def12
|definition=
'''Полулинейное подмножество''' <tex>\mathbb{N}^{n}</tex> (англ. ''semilinear subset'') {{---}} объединение конечно числа линейных подмножество <tex>M_1,...,M_k</tex>, где <tex>k \in \mathbb{N}^{+}</tex>.
}}
{{Определение
|id=def13
|definition=
Пусть <tex>\Sigma = \{a_1,...,a_n\}</tex>, где <tex>n \in \mathbb{N}^{+}</tex> и порядок <tex>a_1,...,a_n</tex> произвольный, но фиксированный (выбран определенный порядок, но не важно какой именно).
Для <tex>w \in \Sigma^{*}</tex> '''образ Париха''' (англ. ''Parikh image'') {{---}} <tex>\Psi(w) = (m_1,...,m_n)</tex>, где <tex>m_i</tex> {{---}} количество <tex>a_i</tex> в <tex>w</tex>
}}
{{Определение
|id=def14
|definition=
Пусть язык <tex>L \subseteq \Sigma^{*}</tex>. Тогда '''соответствие Париха''' (англ. ''Parikh mapping'') на языке <tex>L</tex> {{---}} <tex>\Psi(L) = \{\Psi(w)|w \in L \} </tex>
}}
==Теорема Париха==
{{Теорема
|id=th1
|author=
Parikh
|statement=
Для <tex>\forall</tex> контекстно свободного языка <tex>L</tex>, <tex>\Psi(L)</tex> {{---}} эффективно полулинейная. Кортежи, определяющие <tex>\Psi(L)</tex> можно эффективно построить из КС грамматики, генерирующей язык <tex>L</tex>.
|proof=
Доказательство разобьем на 3 части:
===Первая часть===
Пусть дана грамматика <tex>G=(N, \Sigma, R, S)</tex>. Будем рассматривать язык <tex>L^{\sim}(G)</tex>, состоящий из слов, сгенерированных деревьями решений, в которых встречаются ''все'' нетерминалы из <tex>N</tex>.
{{Утверждение
|id=proposal1
|statement=
<tex>L^{\sim}(G)</tex> {{---}} полулинейный
|proof=
<tex>L^{\sim}(G)</tex> {{---}} подмножество <tex>L(G)</tex>, который по утверждению теоремы полулинейный.
}}
{{Лемма
|id=lemma1
|statement=
Если <tex>\Psi(L^{\sim}(G))</tex> {{---}} полулинейный для всех КС языков, тогда <tex>\Psi(L(G))</tex> {{---}} полулинейный.
|proof=
Построит все грамматики <tex>G_1,...,G_k</tex>, где <tex>k \in \mathbb{N}^{+}</tex>, полученныt из <tex>G</tex> удалением нетерминалов. Тогда <tex>L(G) = L^{\sim}(G_1) \cup ... \cup L^{\sim}(G_k)</tex> и следовательно <tex>\Psi(L(G)) = \Psi(L^{\sim}(G_1)) \cup ... \cup \Psi(L^{\sim}(G_K))</tex> {{---}} полулинейный по определению.
}}
Заметим, что количество языков <tex>k</tex> в лемме ограничено количеством нетерминалов граммитики <tex>G</tex>: <tex>k \le 2^{|N|} - 1</tex>.
}}
===Вторая часть===
В этой части рассмотрим деревья вывода, которые используются в генерации языка <tex>L^{\sim}(G)</tex>. Определим три специальных вида деревьев с ограниченными свойствами.
{{Определение
|id=def21
|definition=
'''Множество терминальных деревьев вывода с корнем <tex>S</tex>''' (англ. ''set of terminal derivation trees with root S'') {{---}} множество деревьев, которые удовлетворяют свойствам:
# Все нетерминалы встречаются в дереве
# Ни один нетерминал не встречается более <tex>k = |N|</tex> раз на любом пути в дереве
Обозначим это множество <tex>T</tex>.
}}
Элементы множества <tex>T</tex> соответствуют деревьям вывода для языка <tex>L^{\sim}(G)</tex>.
{{Определение
|id=def22
|definition=
'''Множество всех терминальных деревьев''' (англ. ''the set of all terminal trees'') {{---}} множество всех терминальных деревьев вывода, удовлетворяющих только первому пункту из [[#def21|определения]].
}}
{{Определение
|id=def23
|definition=
'''Множество промежуточных деревьев''' (англ. ''set of intermediate trees'') {{---}} множество всех деревьев вывода с корнем <tex>A \in N </tex>, содержащих ровно один нетерминальный лист с тем же нетерминалом <tex>A</tex>. Кроме того, это множество должно удовлетворять второму условию из [[#def21|определения]].
Обозначим это множество <tex>I</tex>
}}
{{Утверждение
|id=proposal2
|statement=
Константа <tex>k</tex> из [[#def21|определения]] <tex>T</tex> ограничена сверху значением <tex>|N| \cdot c</tex>, где <tex>c</tex> {{---}} количество повторений нетерминала на пути. Следовательно и <tex>T</tex>, и <tex>I</tex> имеют конечную высоту.
}}
=== Третья часть ===
{{Определение
|id=def31
|definition=
Пусть <tex>w_1,...,w_q</tex>, где <tex>q \in \mathbb{N}^{+}</tex>, {{---}} '''множество порожденных строк''' (англ. ''set of yielded strings'') из деревьев, лежащих в [[#def21|<tex>T</tex>]]
}}
{{Определение
|id=def32
|definition=
Пусть <tex>W</tex> {{---}} множество все строк вида <tex>uv</tex> таких, что <tex>uAv</tex> {{---}} результат какого-то дерева вывода из <tex>I</tex> для некоторого терминала <tex>A \in N</tex>
}}
Внимательно посмотрев на последнее определение, очевидно можно заметить, что элементы <tex>W</tex> представляют собой возможные поддеревья, который могут быть использованы для того, чтобы сделать дерево вывода больше.
Другими словами, элементы <tex>W</tex> соответствуют правилу в КС грамматике, которое делает строку длиннее, вводя нетерминал между двумя терминалами.
{{Лемма
|id=lemma2
|statement=
<tex>
\Psi(L^{\sim}(G)) =
\left.
\begin{matrix}
& \Psi(w_1) + \Psi(W)* \\
& \cup \\
& . \\
& . \\
& . \\
& \cup \\
& \Psi(w_q) + \Psi(W)* \\
\end{matrix}
\right\}
\Phi
</tex>
|proof=
(по индукции)
'''Вправо'''
<tex>\Phi \subseteq L^{\sim}(G)</tex>
''База индукции'': Пусть <tex>m = \Psi(w_i)</tex> для некоторого <tex>i \in \mathbb{N}^{+} </tex>, тогда <tex>w_i \in L^{\sim}(G)</tex>. Следовательно <tex>\Psi(w_i) \in \Psi(L^{\sim}(G))</tex>. По [[#def22|определению]] <tex>\widetilde{T}</tex> <tex>w_i</tex> соответствует строке, формирующей язык <tex>L^{\sim}(G)</tex>.
''Переход'': Пусть <tex>m = m' + \Psi(u)</tex>, где <tex>u \in W</tex>
Есть дерево <tex>t \in \widetilde{T}</tex> с результатом <tex>w</tex> такое, что <tex>\Psi(w) = m'</tex>. Также есть дерево <tex>t' \in I </tex> выводящее <tex>u_0 A v_0 </tex> такое, что <tex>u = u_0 v_0</tex>
Теперь построим дерево вывода, полученное заменой всех вершин <tex>p</tex> с нетерминалом <tex>A</tex> в дереве <tex>t</tex> на деревья полученные заменой листов с нетерминалом <tex>A</tex> в дереве <tex>t'</tex> на поддерево <tex>t</tex> с корнем в вершине <tex>p</tex>. Получившееся дерево принадлежит множеству <tex>\widetilde{T}</tex> и его результат <tex>z</tex> удовлетворяет равенству <tex>\Psi(z) = \Psi(w) + \Psi(u) = m </tex>.
Полученное равенство доказывает шаг индукции.
'''Влево'''
<tex>L^{\sim}(G) \subseteq \Phi </tex>
''База индукции'': Если <tex>t \in T </tex>, тогда <tex>w = w_i </tex> для некотого <tex>i \in \mathbb{N}^{+} </tex>. Таким образом <tex> \Psi(w) \in \Phi </tex>.
''Шаг индукции'': Пусть <tex>p_1,...,p_n, где <tex>n \in \mathbb{N}^{+}</tex>, {{---}} вершины на некотором пути и пусть индексы обозначают позицию вершины на этом пути. Более того, пусть все вершины будут помечены одним и тем же нетерминалом <tex>A</tex> таким, что все ''хорошие'' поддеревья дерева с корнем в <tex>p_1</tex> удовлетворяют условию 2 из [[#def21|определения]].
Пусть <tex>t_i</tex> будет дерево, полученное из дерева <tex>t</tex> удалением вершин в <tex>p_i</tex> и <tex>p_{i+1}</tex>. Наоборот, пусть дерево <tex>\bar{t_i}</tex> получено удалением вершин между <tex>p_i</tex> и <tex>p_{i+1}</tex>. Тогда <tex>t_i \in I </tex> и <tex>\Psi(w) = \Psi(\bar{u_i}) + \Psi(u_i)</tex>, где <tex>u_i</tex> и <tex>\bar{u_i}</tex> являются результатом вывода деревьев <tex>t_i</tex> и <tex>\bar{t_i}</tex> соответственно.
Осталось показать, что <tex>\bar{t_i}</tex> может быть выбрано так, чтобы <tex>\bar{t_i} \in \widetilde{T}</tex>
Пусть <tex>N\backslash{A} = \{B_1,...,B_{n-1}\}</tex>, где <tex>n \in \mathbb{N}^{+}</tex>. Тогда <tex>\bar{t_i} \in \widetilde{T}</tex>, если <tex>t_i</tex> содержит все <tex>B_j</tex> в <tex>t</tex> для некоторого <tex> j \notin \{1,...,n - 1\}</tex>. Но так как есть <tex>n</tex> выборов для <tex>i</tex>, должно быть хотя бы одно <tex>i \in \{0,...,n - 1\}</tex>, для которого это не выполняется. Следовательно <tex>\bar{t_i} \in \widetilde{T}</tex> и шаг индукции доказан.
}}
Доказательство показывает, что соответствие Париха КС языка равносильно тому, что получено из терминальных деревьев выхода, которые имеют самые короткие из возможных пути и их результат вывода и добавление добавлений от поддеревьев, которые могут быть подкачаны произвольное количество раз в соответствующее линейное подмножество.
