Участник:Svetomsk

Базовые определения

Определение:

Пусть [math]t_0,..., t_m \in \mathbb{N}^{n}[/math], где [math]m \in \mathbb{N}[/math] и [math]n \in \mathbb{N}^{+}[/math], тогда множество [math]M = \{t_0 + l_1 t_1 + ... + l_m t_m | l_1,..., l_m \in \mathbb{N}\} = t_0 + \{t_1,..., t_m\}^{*}[/math] называется линейным подмножеством [math]\mathbb{N}^{n}[/math] (англ. linear subset)

Определение:

Полулинейное подмножество [math]\mathbb{N}^{n}[/math] (англ. semilinear subset) — объединение конечно числа линейных подмножество [math]M_1,...,M_k[/math], где [math]k \in \mathbb{N}^{+}[/math].

Определение:

Пусть [math]\Sigma = \{a_1,...,a_n\}[/math], где [math]n \in \mathbb{N}^{+}[/math] и порядок [math]a_1,...,a_n[/math] произвольный, но фиксированный (выбран определенный порядок, но не важно какой именно). Для [math]w \in \Sigma^{*}[/math] образ Париха (англ. Parikh image) — [math]\Psi(w) = (m_1,...,m_n)[/math], где [math]m_i[/math] — количество [math]a_i[/math] в [math]w[/math]

Определение:

Пусть язык [math]L \subseteq \Sigma^{*}[/math]. Тогда соответствие Париха (англ. Parikh mapping) на языке [math]L[/math] — [math]\Psi(L) = \{\Psi(w)|w \in L \} [/math]

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

Теорема (Parikh):

Для [math]\forall[/math] контекстно свободного языка [math]L[/math], [math]\Psi(L)[/math] — эффективно полулинейная. Кортежи, определяющие [math]\Psi(L)[/math] можно эффективно построить из КС грамматики, генерирующей язык [math]L[/math].

Доказательство:

[math]\triangleright[/math]

Доказательство разобьем на 3 части: Первая часть Пусть дана грамматика [math]G=(N, \Sigma, R, S)[/math]. Будем рассматривать язык [math]L^{\sim}(G)[/math], состоящий из слов, сгенерированных деревьями решений, в которых встречаются все нетерминалы из [math]N[/math]. Утверждение: [math]L^{\sim}(G)[/math] — полулинейный [math]\triangleright[/math] [math]L^{\sim}(G)[/math] — подмножество [math]L(G)[/math], который по утверждению теоремы полулинейный. [math]\triangleleft[/math] Лемма: Если [math]\Psi(L^{\sim}(G))[/math] — полулинейный для всех КС языков, тогда [math]\Psi(L(G))[/math] — полулинейный. Доказательство: [math]\triangleright[/math] Построит все грамматики [math]G_1,...,G_k[/math], где [math]k \in \mathbb{N}^{+}[/math], полученныt из [math]G[/math] удалением нетерминалов. Тогда [math]L(G) = L^{\sim}(G_1) \cup ... \cup L^{\sim}(G_k)[/math] и следовательно [math]\Psi(L(G)) = \Psi(L^{\sim}(G_1)) \cup ... \cup \Psi(L^{\sim}(G_K))[/math] — полулинейный по определению. [math]\triangleleft[/math] Заметим, что количество языков [math]k[/math] в лемме ограничено количеством нетерминалов граммитики [math]G[/math]: [math]k \le 2^{|N|} - 1[/math].

[math]\triangleleft[/math]

Вторая часть

В этой части рассмотрим деревья вывода, которые используются в генерации языка [math]L^{\sim}(G)[/math]. Определим три специальных вида деревьев с ограниченными свойствами.

Определение:

Множество терминальных деревьев вывода с корнем [math]S[/math] (англ. set of terminal derivation trees with root S) — множество деревьев, которые удовлетворяют свойствам: Все нетерминалы встречаются в дереве Ни один нетерминал не встречается более [math]k = |N|[/math] раз на любом пути в дереве Обозначим это множество [math]T[/math].

Элементы множества [math]T[/math] соответствуют деревьям вывода для языка [math]L^{\sim}(G)[/math].

Определение:

Множество всех терминальных деревьев (англ. the set of all terminal trees) — множество всех терминальных деревьев вывода, удовлетворяющих только первому пункту из определения.

Определение:

Множество промежуточных деревьев (англ. set of intermediate trees) — множество всех деревьев вывода с корнем [math]A \in N [/math], содержащих ровно один нетерминальный лист с тем же нетерминалом [math]A[/math]. Кроме того, это множество должно удовлетворять второму условию из определения. Обозначим это множество [math]I[/math]

Утверждение:

Константа [math]k[/math] из определения [math]T[/math] ограничена сверху значением [math]|N| \cdot c[/math], где [math]c[/math] — количество повторений нетерминала на пути. Следовательно и [math]T[/math], и [math]I[/math] имеют конечную высоту.

Третья часть

Определение:

Пусть [math]w_1,...,w_q[/math], где [math]q \in \mathbb{N}^{+}[/math], — множество порожденных строк (англ. set of yielded strings) из деревьев, лежащих в [math]T[/math]

Определение:

Пусть [math]W[/math] — множество все строк вида [math]uv[/math] таких, что [math]uAv[/math] — результат какого-то дерева вывода из [math]I[/math] для некоторого терминала [math]A \in N[/math]

Внимательно посмотрев на последнее определение, очевидно можно заметить, что элементы [math]W[/math] представляют собой возможные поддеревья, который могут быть использованы для того, чтобы сделать дерево вывода больше.

Другими словами, элементы [math]W[/math] соответствуют правилу в КС грамматике, которое делает строку длиннее, вводя нетерминал между двумя терминалами.

Лемма:

[math] \Psi(L^{\sim}(G)) = \left. \begin{matrix} & \Psi(w_1) + \Psi(W)* \\ & \cup \\ & . \\ & . \\ & . \\ & \cup \\ & \Psi(w_q) + \Psi(W)* \\ \end{matrix} \right\} \Phi [/math]

Доказательство:

[math]\triangleright[/math]

(по индукции) Вправо [math]\Phi \subseteq L^{\sim}(G)[/math] База индукции: Пусть [math]m = \Psi(w_i)[/math] для некоторого [math]i \in \mathbb{N}^{+} [/math], тогда [math]w_i \in L^{\sim}(G)[/math]. Следовательно [math]\Psi(w_i) \in \Psi(L^{\sim}(G))[/math]. По определению [math]\widetilde{T}[/math] [math]w_i[/math] соответствует строке, формирующей язык [math]L^{\sim}(G)[/math]. Переход: Пусть [math]m = m' + \Psi(u)[/math], где [math]u \in W[/math] Есть дерево [math]t \in \widetilde{T}[/math] с результатом [math]w[/math] такое, что [math]\Psi(w) = m'[/math]. Также есть дерево [math]t' \in I [/math] выводящее [math]u_0 A v_0 [/math] такое, что [math]u = u_0 v_0[/math] Теперь построим дерево вывода, полученное заменой всех вершин [math]p[/math] с нетерминалом [math]A[/math] в дереве [math]t[/math] на деревья полученные заменой листов с нетерминалом [math]A[/math] в дереве [math]t'[/math] на поддерево [math]t[/math] с корнем в вершине [math]p[/math]. Получившееся дерево принадлежит множеству [math]\widetilde{T}[/math] и его результат [math]z[/math] удовлетворяет равенству [math]\Psi(z) = \Psi(w) + \Psi(u) = m [/math]. Полученное равенство доказывает шаг индукции. Влево [math]L^{\sim}(G) \subseteq \Phi [/math] База индукции: Если [math]t \in T [/math], тогда [math]w = w_i [/math] для некотого [math]i \in \mathbb{N}^{+} [/math]. Таким образом [math] \Psi(w) \in \Phi [/math]. Шаг индукции: Пусть [math]p_1,...,p_n, где \lt tex\gt n \in \mathbb{N}^{+}[/math], — вершины на некотором пути и пусть индексы обозначают позицию вершины на этом пути. Более того, пусть все вершины будут помечены одним и тем же нетерминалом [math]A[/math] таким, что все хорошие поддеревья дерева с корнем в [math]p_1[/math] удовлетворяют условию 2 из определения. Пусть [math]t_i[/math] будет дерево, полученное из дерева [math]t[/math] удалением вершин в [math]p_i[/math] и [math]p_{i+1}[/math]. Наоборот, пусть дерево [math]\bar{t_i}[/math] получено удалением вершин между [math]p_i[/math] и [math]p_{i+1}[/math]. Тогда [math]t_i \in I [/math] и [math]\Psi(w) = \Psi(\bar{u_i}) + \Psi(u_i)[/math], где [math]u_i[/math] и [math]\bar{u_i}[/math] являются результатом вывода деревьев [math]t_i[/math] и [math]\bar{t_i}[/math] соответственно. Осталось показать, что [math]\bar{t_i}[/math] может быть выбрано так, чтобы [math]\bar{t_i} \in \widetilde{T}[/math] Пусть [math]N\backslash{A} = \{B_1,...,B_{n-1}\}[/math], где [math]n \in \mathbb{N}^{+}[/math]. Тогда [math]\bar{t_i} \in \widetilde{T}[/math], если [math]t_i[/math] содержит все [math]B_j[/math] в [math]t[/math] для некоторого [math] j \notin \{1,...,n - 1\}[/math]. Но так как есть [math]n[/math] выборов для [math]i[/math], должно быть хотя бы одно [math]i \in \{0,...,n - 1\}[/math], для которого это не выполняется. Следовательно [math]\bar{t_i} \in \widetilde{T}[/math] и шаг индукции доказан.

[math]\triangleleft[/math]

Доказательство показывает, что соответствие Париха КС языка равносильно тому, что получено из терминальных деревьев выхода, которые имеют самые короткие из возможных пути и их результат вывода и добавление добавлений от поддеревьев, которые могут быть подкачаны произвольное количество раз в соответствующее линейное подмножество.