close

Вход

Забыли?

вход по аккаунту

?

О матрице первых моментов разложимой стохастической КС-грамматики.

код для вставкиСкачать
УЧЕНЫЕ ЗАПИСКИ КАЗАНСКОО ОСУДАСТВЕННОО УНИВЕСИТЕТА
Физико-математические науки
2009
Том 151, кн. 2
УДК 519.713
О МАТИЦЕ ПЕВЫХ МОМЕНТОВ
АЗЛОЖИМОЙ СТОХАСТИЧЕСКОЙ
КС-АММАТИКИ
Л.П. Жильцова
Аннотация
ассматривается стохастическая контекстно-свободная грамматика с произвольным
числом классов нетерминальных символов без ограничений на порядок следования классов. Соответствующая ей матрица A первых моментов является разложимой. Для случая,
когда перронов корень r матрицы A строго меньше единицы, исследуются свойства матрицы At при t ? ?.
Ключевые слова: алгоритм, кодирование, сжатие, контекстно-свободный язык,
грамматика, оптимизация, автомат, вероятность.
Введение
В работах [1, 2? нами рассматривались вопросы, связанные с кодированием сообщений, являющихся словами стохастического контекстно-свободного языка (стохастического КС-языка), при условии, что матрица первых моментов грамматики
неразложима, непериодична и ее максимальный по модулю собственный корень
(перронов корень) строго меньше единицы (докритический случай). При неразложимой матрице первых моментов нетерминальные символы грамматики образуют
один класс.
При изучении вопросов кодирования важную роль играет строение матрицы A
первых моментов и асимптотическое поведение элементов матрицы At при t ? ?.
Свойства неразложимой матрицы At изучены в [3?. Для докритического случая
в [4? проведено исследование грамматик с двумя классами нетерминальных символов, при этом установлено асимптотическое поведение матрицы At .
В настоящей работе свойства матриц A и At исследуются для стохастических
КС-грамматик с произвольным числом классов нетерминальных символов грамматики без ограничений на порядок следования классов.
1.
Основные определения
Для изложения результатов о контекстно-свободных языках будем использовать определения КС-языка и стохастического КС-языка из [5, 6?. Стохастической
КС-грамматикой называется система G = hVT , VN , R, si, где VT и VN конечные
множества терминальных и нетерминальных символов (терминалов и нетерминалов) соответственно; s ? VN аксиома, R множество правил. Множество R
k
[
можно представить в виде R =
Ri , где k мощность алавита VN и Ri =
i=1
= {ri1 , . . . , rini }. Каждое правило rij из Ri имеет вид
pij
rij : Ai ? ?ij ,
j = 1, . . . , ni ,
О МАТИЦЕ ПЕВЫХ МОМЕНТОВ
81
где Ai ? VN , ?ij ? (VT ? VN )? и pij вероятность применения правила rij (вероятность правила rij ), которая удовлетворяет следующим условиям:
0 < pij ? 1 и
ni
X
pij = 1,
i = 1, 2, . . . , k.
j=1
Для слов ? и ? из (VT ?VN )? будем говорить, что ? непосредственно выводимо
из ? (и записывать ? ? ? ), если ? = ?1 Ai ?2 , ? = ?1 ?ij ?2 для некоторых ?1 , ?2 ?
pij
? (VT ? VN )? , и в грамматике G имеется правило Ai ? ?ij .
Обозначим через ?? релексивное транзитивное замыкание отношения ? .
КС-язык, порождаемый грамматикой G, определяется как множество слов
LG = {? : s ?? ?, ? ? VT? }.
Каждому слову ? КС-языка соответствует последовательность правил грамматики (вывод), с помощью которой ? выводится из аксиомы s. Вероятность вывода
определяется как произведение вероятностей правил, образующих вывод. Вероятность слова ? определяется как сумма вероятностей всех различных левых выводов слова ? (при левом выводе очередное правило применяется к самому левому
нетерминалу в слове).
рамматика G называется согласованной, если
X
lim
p(?) = 1
N ??
??L,|?|?N
(здесь |x| длина слова x ). В работе рассматриваются согласованные KCграмматики. Согласованная КС-грамматика G индуцирует распределение вероятностей P на множестве слов порождаемого КС-языка L и определяет стохастический КС-язык L = (L, P ).
Важное значение имеет понятие дерева вывода. Дерево строится следующим
образом.
Корень дерева помечается аксиомой s. Пусть при выводе слова ? на очередpij
ном шаге в процессе левого вывода применяется правило A ? bi1 bi2 · · · bim , где
bil ? VN ? VT (l = 1, . . . , m). Тогда из самой левой вершины-листа дерева, помеченной символом A (при обходе листьев дерева слева направо), проводится m
дуг в вершины следующего яруса, которые помечаются слева направо символами
bi1 , bi2 , . . . , bim соответственно. После построения дуг и вершин для всех правил
грамматики в выводе слова языка все листья дерева помечены терминальными
символами и само слово получается при обходе листьев дерева слева направо.
Ярусы дерева будем нумеровать следующим образом. Корень дерева расположен в нулевом ярусе. Вершины дерева, смежные с корнем, образуют первый ярус,
и т. д. Дуги, выходящие из вершин j -го яруса, ведут к вершинам (j + 1) -го яруса.
ассмотрим многомерные производящие ункции Fi (s1 , s2 , . . . , sk ), i =
= 1, . . . , k, где переменная si соответствует нетерминальному символу Ai . Функция Fi (s1 , s2 , . . . , sk ) строится по множеству правил Ri с одинаковой левой частью
Ai следующим образом.
pij
Для каждого правила Ai ? ?ij выписывается слагаемое
qij= pij · sl11 · sl22 · . . . · slkk ,
где lm число вхождений нетерминального символа Am в правую часть правила
(m = 1, . . . , k). Тогда
ni
X
Fi (s1 , s2 , . . . , sk ) =
qij .
j=1
82
Л.П. ЖИЛЬЦОВА
Пусть
aij
?Fi (s1 , . . . , sk ) =
?sj
.
s1 =s2 =···=sk =1
Квадратная матрица A порядка k, образованная элементами aij , называется
матрицей первых моментов грамматики G.
Так как матрица A неотрицательна, существует максимальный по модулю действительный неотрицательный собственный корень (перронов корень) [7?. Обозначим этот корень через r .
Известно необходимое и достаточное условие согласованности стохастической
КС-грамматики [6?: стохастическая КС-грамматика при отсутствии бесполезных
нетерминалов (то есть не участвующих в порождении слов языка) является согласованной тогда и только тогда, когда перронов корень матрицы первых моментов
не превосходит единицы.
В работе рассматривается случай, когда r < 1.
Введем некоторые обозначения. Будем говорить, что нетерминал Aj непосредственно следует за нетерминалом Ai (и обозначать Ai ? Aj ), если в грамматике
pil
существует правило вида Ai ?
?1 Aj ?2 , где ?1 , ?2 ? (VT ? VN )? . Транзитивное
замыкание отношения ? обозначим ?? .
Пусть Ai ? VN . Через I1 (Ai ) обозначим множество нетерминалов таких, что
Ai ?? Aj для любого Aj ? I1 (Ai ). Через I2 (Ai ) обозначим множество нетерминалов таких, что Aj ? Ai для любого Aj ? I2 (Ai ). Через I0 (Ai ) обозначим пересечение этих множеств, то есть I0 (Ai ) = I1 (Ai ) ? I2 (Ai ). Множество нетерминалов
K = {Ai1 , . . . , Aiq }, для которых I0 (Aij ) совпадают и I0 (Aij ) 6= ?, j = 1, . . . , q, назовем классом. Если I0 (Ai ) = ?, то будем считать, что Ai образует особый класс
{Ai }.
рамматика G называется неразложимой, если все нетерминалы из VN образуют один класс. В противном случае G называется разложимой. азложимой
грамматике соответствует разложимая матрица [7? первых моментов.
Для различных классов нетерминалов K1 и K2 будем говорить, что класс K2
непосредственно следует за классом K1 (и обозначать K1 ? K2 ), если существуют
A1 ? K1 и A2 ? K2 такие, что A1 ? A2 . елексивное транзитивное замыкание
отношения ? обозначим через ?? и назовем отношением следования.
Пусть {K1 , K2 , . . . , Km } множество классов нетерминалов грамматики,
m ? 2 . Без ограничения общности можно считать, что в грамматике нет особых классов.
Будем полагать, что классы нетерминалов перенумерованы таким образом, что
Ki ? Kj тогда и только тогда, когда i < j (это всегда можно сделать). Соответствующая разложимой грамматике матрица первых моментов A имеет следующий
вид:
?
?
A11 A12 . . .
A1m?1
A1m
? 0
A22 . . .
A2m?1
A2m ?
?
?
.
.
.
.
.
.
.
.
.
.
.
.
... ?
A=?
(1)
?
?.
? 0
0
. . . Am?1m?1 Am?1m ?
0
0
...
0
Amm
Один класс нетерминалов в матрице первых моментов представлен множеством
подряд идущих строк и соответствующим множеством столбцов с теми же номерами. Для класса Ki квадратная подматрица, образованная соответствующими
строками и столбцами, обозначается через Aii . Подматрица Aij является нулевой,
если Ki ? Kj . Блоки, расположенные ниже главной диагонали, нулевые в силу
упорядоченности классов нетерминалов.
О МАТИЦЕ ПЕВЫХ МОМЕНТОВ
83
Для каждого класса Ki матрица Aii неразложима. Без ограничения общности
будем считать, что она строго положительна и непериодична. Этого всегда можно
добиться, применяя метод укрупнения правил грамматики, описанный в [2?.
Обозначим через ri перронов корень матрицы Aii . Для неразложимой матрицы перронов корень является действительным и простым [7?. Очевидно, в силу
структуры матрицы первых моментов, r = maxi {ri } и r > 0.
Пусть J = {i1 , i2 , . . . , il } множество всех номеров ij классов, для которых
rij = r.
Введем некоторые соглашения. ассматривая вектор, будем считать, что мы
имеем дело с вектором-столбцом, если противное не оговорено специально. В дальнейшем для вектора или матрицы X будем писать X = c (X ? c), где c скаляр,
если все компоненты вектора или матрицы X равны (соответственно меньше или
равны) c. Через X T обозначим транспонирование вектора или матрицы X. Через (v1 , v2 ), где v1 , v2 векторы-столбцы, будем обозначать объединенный векторстолбец (v1T , v2T )T .
2.
Асимптотика для матрицы
At
Заиксируем пару (l, h), l, h ? {1, 2, . . . , m}, и рассмотрим всевозможные последовательности классов Ki1 ? Ki2 ? . . . ? Kis , где i1 = l, is = h. Среди всех таких
последовательностей выберем ту, которая содержит наибольшее число классов с
номерами из J . Это число обозначим через slh .
Дополнительно переупорядочим классы по неубыванию величины s1l , причем
при одинаковых значениях s1l сначала поставим классы с номерами из J.
азобьем последовательность классов на группы классов M1 , M2 , . . . , Mw , при
этом класс Kl отнесем к группе M1 при s1l ? 1 и к группе Mj при s1l = j (l =
= 2, . . . , m). Для краткости далее будем называть группу классов просто группой.
Для групп Mi и Mj определим s?ij как maxKl ?Mi ,Kh ?Mj {slh } .
Матрицу первых моментов будем также представлять в виде
?
?
B11 B12 . . . B1w
? 0
B22 . . . B2w ?
?
A=?
? ... ... ... ... ?,
0
0
. . . Bww
где Bij подматрица на пересечении строк для классов из группы Mi и столбцов
для классов из Mj . Очевидно, каждая матрица Bii имеет перронов корень r.
(t)
ассмотрим подматрицу Blh матрицы первых моментов A. Запись Blh будем
t
применять для обозначения соответствующей подматрицы матрицы A . Изучим
поведение матрицы At при t ? ?.
Теорема 1.
При t ? ?
(t)
?
Blh = Hlh · tslh ?1 rt (1 + o(1)),
где Hlh матрица, не зависящая от t.
Доказательство проведем индукцией по числу групп.
Пусть A = (B11 ). руппу M1 разобьем на три подгруппы. К первой подгруппе
M11 отнесем классы нетерминалов с s1l = 0, ко второй подгруппе M12 классы
с номерами из множества J, к третьей подгруппе M13 все остальные классы.
В соответствии с этим разбиением B11 представим в виде
?
?
C11 C12 C13
C22 C23 ? ,
B11 = ? 0
0
0
C33
Доказательство.
84
Л.П. ЖИЛЬЦОВА
где Cij подматрица со строками для классов из M1i и столбцами для классов
из M1j .
t
Исследуем строение подматриц матрицы B11
при t ? ?. Заметим, что подгруппа M11 может быть пустой, тогда в B11 присутствуют только подматрицы
C22 , C23 и C33 .
Известно следующее представление для степени произвольной матрицы C [7?:
t
C =
s X
?tl Zl1 + ?tl
l=1
?
· Zl2 + . . . + ?tl
(ml ?1)
Zlml ,
(2)
где ?l корни минимального многочлена ?(?) матрицы C (l = 1, . . . , s), ml кратность корня ?l для минимального многочлена, (?tl )(n) n -я производная по
?l от ?tl , матрицы Zlj вполне определяются заданием матрицы C и не зависят от
t.
Так как каждому классу Ki из M11 или из M13 соответствует перронов корень
t
t
t
t
ri < r, то для C11
и C33
из (2) следуют оценки C11
= o(rt ) и C33
= o(rt ).
Пусть M1l содержит jl классов (l = 1, 2, 3). Любому классу Ki из M12 соответствует неразложимая подматрица Aii в представлении (1), и классы из M12
попарно несравнимы.
Для неразложимой положительной матрицы Atii применим представление,
установленное в [3?:
Atii = Ui Vi · rt (1 + o(1)),
где Ui правый собственный вектор (вектор-столбец), Vi левый собственный
вектор (вектор-строка), соответствующие r, Ui > 0, Vi > 0 и Vi Ui = 1.
t
Поэтому матрицу C22
можно представить в следующем виде:
?
?
Uj1 +1 Vj1 +1
0
... 0
0
?
? t
0
Uj1 +2 Vj1 +2 . . . 0
0
t
? · r (1 + o(1)).
C22
=?
(3)
?
?
...
...
... ...
...
0
0
. . . 0 Uj1 +j2 Vj1 +j2
Обозначим через D матрицу
?
Uj1 +1 Vj1 +1
0
?
0
U
Vj1 +2
j
+2
1
?
?
...
...
0
0
?
... 0
0
?
... 0
0
?.
?
... ...
...
. . . 0 Uj1 +j2 Vj1 +j2
Очевидно, что D можно представить в виде
j2
X
(2)
(2)
Ui Vi
(2)
, где Ui
=
i=j1 +1
(2)
= (0, . . . , 0, Ui , 0, . . . , 0), Vi
= (0, . . . , 0, Vi , 0, . . . , 0) и Ui и Vi расположены на
местах, соответствующих классу Ki .
Непосредственной проверкой устанавливается, что
(t)
C12 =
t?1
X
t??log log t?
j
t?j?1
C11
C12 C22
=
j=0
X
j
t?j?1
C11
C12 C22
+
j=0
t??log log t?
Обозначим
X
j=0
рез ?2 .
j
t?j?1
C11
C12 C22
через ?1 и
t?1
X
j
t?j?1
C11
C12 C22
.
j=t??log log t?+1
t?1
X
j=t??log log t?+1
j
t?j?1
C11
C12 C22
че-
85
О МАТИЦЕ ПЕВЫХ МОМЕНТОВ
t
Оценим сначала ?2 . Для этого применим представление (2) для C11
. Отметим,
t
что для C11 все собственные корни строго меньше r, а элементы матрицы C22
ограничены некоторой константой, не зависящей от t. Поэтому
t?1
X
?2 ? c1 · (r? )t??log log t?+1
t?j?1
C12 C22
?
j=t??log log t?+1
c2 · (r? )t??log log t?+1 · ?log log t? = O log log t · (log t)c3 · (r? )t = o rt
для некоторых констант c1 , c2 и c3 , и r? , удовлетворяющего неравенству r? < r.
t?j?1
Учитывая представление (3) для C22
, получим:
?1 = rt?1 (1 + o(1))
t??log log t? X
j=0
C11
r
j
C12 D.
Нетрудно проверить, что
?
1X
r j=0
C11
r
j
= (rE ? C11 )?1 ,
поскольку перронов корень матрицы C11 строго меньше r, и, следовательно, обратная матрица для (rE ? C11 ) существует. Поэтому
?1 = rt (rE ? C11 )?1 C12 D · (1 + o(1)).
Найдем правый собственный вектор матрицы B11 для перронова корня r. Компоненты вектора представим в виде U = (U (1) , U (2) , U (3) ), где U (1) соответствует
M11 , U (2) M12 , и U (3) M13 . Вектор U удовлетворяет системе уравнений
?
?
C U (1) + C12 U (2) + C13 U (3) = rU (1) ,
?
? 11
C22 U (2) + C23 U (3) = rU (2) ,
?
?
?
C33 U (3) = rU (3) .
Отсюда U (3) = 0, так как перронов корень матрицы C33 строго меньше r ,
U (2) является правым собственным вектором для матрицы C22 и U (1) = (rE ?
? C11 )?1 C12 U (2) .
Таким образом,
(t)
C12 = rt (rE ? C11 )?1 C12
j2
X
(2)
(2)
Ui Vi
· (1 + o(1)) = rt
i=j1 +1
j2
X
(1)
(2)
Ui Vi
· (1 + o(1)),
i=j1 +1
(1)
(2)
где Ui соответствует правому собственному вектору Ui матрицы C22 .
(t)
ассмотрим матрицу C23 . Непосредственной проверкой устанавливается, что
(t)
C23 =
t?1
X
j
t?j?1
C22
C23 C33
.
j=0
Представим эту сумму в виде ?1 + ?2 , где
?1 =
t?1
X
j=?log log t?+1
?log log t?
j
t?j?1
C22
C23 C33
,
?2 =
X
j=0
j
t?j?1
C22
C23 C33
.
86
Л.П. ЖИЛЬЦОВА
t
Аналогично тому, как это сделано для C12
, доказывается оценка ?2 = o(rt ).
Для ?1 справедливы соотношения
t?1
X
?1 = D ·
r
i
t?j?1
C23 C33
t
· (1 + o(1)) = r · (1 + o(1))
t??log log t??2 X
j=0
j=?log log t?+1
C33
r
j
.
Найдем левый собственный вектор матрицы B11 для перронова корня r. Компоненты вектора представим в виде V = (V (1) , V (2) , V (3) ). Вектор V удовлетворяет
системе уравнений
?
?
V (1) C11 = rV (1) ,
?
?
V (1) C12 + V (2) C22 = rV (2) ,
?
?
? (1)
V C13 + V (2) C23 + V (3) C33 = rV (3) .
Отсюда V (1) = 0, так как перронов корень матрицы C11 строго меньше r , V (2)
является левым собственным вектором для матрицы C22 , и V (3) = V (2) C23 (rE ?
? C33 )?1 . Поэтому
(t)
C23 = rt
j2
X
(2)
(2)
Ui Vi
C23 (rE ? C33 )?1 · (1 + o(1)) = rt
i=j1 +1
j2
X
(2)
(3)
Ui Vi
· (1 + o(1)).
i=j1 +1
(t)
Наконец, рассмотрим матрицу C13 . Нетрудно проверить, что
(t)
C13
=
t?1
X
j
t?j?1
C11
C13 C33
j=0
+
t?1
X
j
t?j?1
C12
C23 C33
.
j=0
Так как перроновы корни матриц C11 и C33 строго меньше r , то справедлива
оценка
t?1
X
j
t?j?1
C11
C13 C33
= o(rt ).
j=0
Поэтому
(t)
C13 =
t?1
X
(j)
t?j?1
C12 C23 C33
+ o(rt ).
j=0
(j)
Применяя полученную оценку для C12 , после несложных преобразований получим, что
(t)
C13
t
=r ·
j2
X
(1) (2)
Ui Vi C23 (rE
?1
? C33 )
i=j1 +1
Таким образом,
?
t
B11
0
?
= ?0
0
· (1 + o(1)) = r
t
j2
X
(1)
(3)
Ui Vi
· (1 + o(1)).
i=j1 +1
Pj2
(1) (2)
Ui Vi
1 +1
Pji=j
(2) (2)
2
i=j1 +1 Ui Vi
0
?
Pj2
(1) (3)
i=j1 +1 Ui Vi
Pj2
(2) (3) ? · rt + o(rt ).
?
i=j1 +1 Ui Vi
0
(4)
Отметим, что строки матрицы B11 , соответствующие классам Ki ? M12 , то
есть классам, для которых i ? J, пропорциональны компонентам правого соб(2)
ственного вектора Ui , а столбцы, соответствующие классам Kj ? M12 , пропор(2)
циональны компонентам левого собственного вектора Vj .
87
О МАТИЦЕ ПЕВЫХ МОМЕНТОВ
ассмотрим случай w = 2. В этом случае матрица At имеет вид
(t)
t
B11
B12
At =
.
t
0
B22
t
Строение матрицы B22
аналогично строению исследованной ранее подматрицы
(t)
t
для B11 , соответствующей подклассам M12 и M13 . Для B12 справедлива ормула
t?1
X
(t)
j
t?j?1
B12 =
B11
B12 B22
.
j=0
t
t
Для того чтобы различать собственные вектора матриц B11
и B22
, введем втоt
рой верхний индекс, равный 1, в случае матрицы B11 , и равный 2, в случае матриt
цы B22
. Для группы M2 отсутствует подгруппа M21 , поэтому M2 = (M22 , M23 ) .
В результате преобразований, учитывающих вид (4), получим, что
(t)
B12
?
0
?
= ?0
0
P (11) (21)
U
V
Pi i(21) i(21)
U
V
i
i i
0
P (11) (31) ?
U
V
Pi i(21) i(31) ?
? · B12 Ч
U
V
i
i i
0
Ч
P
(22)
j Uj
(22)
Vj
0
P
(22)
j Uj
0
(32)
Vj
!
· trt + o(trt ).
Представим матрицу B12 в виде
B12
?
D11
= ?D21
D31
?
D12
D22 ? ,
D32
(5)
где разбиение по строкам сделано в соответствии с подгруппами группы M1 , а по
столбцам в соответствии с подгруппами группы M2 . Тогда
?P
?
P
(11) (22)
(11) (32)
c
U
V
c
U
V
ij
ij
i
j
i
j
?Pi,j
Pi,j
(t)
(21) (32) ? · trt + o(trt ),
B12 = ? i,j cij Ui(21) Vj(22)
Vj ?
i,j cij Ui
0
0
(21)
(31)
(22)
где cij = Vi D21 + Vi D31 Uj . Коэициент cij > 0 в случае, когда
Ki ? Kj .
(t)
Блоки матрицы B12 можно также представить в виде, аналогичном (4), сменив
порядок суммирования и проведя суммирование по i :
?P
P ?(11) (32) ?
?(11) (22)
U
V
U
V
j
?Pj j
Pj j?(21) j(32) ?
(t)
t
t
B12 = ? j Uj?(21) Vj(22)
Vj ? · tr + o(tr ),
j Uj
0
0
P
?(l1)
(l1)
где Uj
= i cij Ui , l = 1, 2.
В силу строения собственных векторов, соответствующих подгруппам M12 и
M22 , строки для класса Ki ? M12 пропорциональны компонентам правого собственного вектора матрицы Aii , а столбцы для Kj ? M22 компонентам левого
собственного вектора матрицы Ajj .
Таким образом, доказана справедливость теоремы для w = 2.
88
Л.П. ЖИЛЬЦОВА
(t)
t
Заметим, что D32 = O(rt ) и D33
= O(rt ), для получения этих оценок достаточно в качестве матрицы первых моментов рассмотреть матрицу без строк и
столбцов, соответствующих подгруппам M11 и M12 . При этом D32 перейдет в
подматрицу C12 , а D33 в подматрицу C13 .
Предположим, что утверждение теоремы справедливо для w ? 1 групп. Докажем его для w групп.
Обозначим через D1 подматрицу матрицы A, соответствующую первым w ?
? 1 группам, и через D2 подматрицу, соответствующую группам с номерами
2, 3, . . . , w . Тогда матрицу первых моментов A можно представить в виде
?
?
B1w
D1 E1
A=
, где E1 = ? . . . ? ,
0 Bww
Bw?1,w
и в виде
A=
Очевидно, что
At =
(t)
E2
,
D2
B11
0
где E2 = B12
(t)
D1t
0
E1
t
Bww
=
t
B11
0
. . . B1w .
(t)
E2
D2t
,
(t)
где E1 , E2 подматрицы в At , соответствующие подматрицам E1 и E2 в A.
Для матриц D1 и D2 утверждение теоремы справедливо по предположению ин(t)
дукции. Поэтому достаточно доказать теорему для подматрицы B1w .
Непосредственной проверкой устанавливается, что
(t)
B1w =
w?1
t?1
X X
(j)
t?j?1
B1l Blw Bww
.
l=1 j=0
?
(j)
По предположению индукции B1l = O ts1l ?1 rt . Так как группы упорядочены по
(j)
возрастанию s?1l , то определяющим в сумме является слагаемое B1,w?1 . Поэтому
(t)
B1w =
t?1
X
(j)
t?j?1
B1w?1 Bw?1w Bww
· (1 + o(1)).
j=0
(j)
аскрывая B1w?1 , после несложных преобразований получим:
?P ?(11) (2w) P ?(11) (3w) ?
U
Vj
U
V
?
Pj j?(21) j(3w) ? s?1w ?1 t
?Pj j
(t)
B1w = ? j Uj?(21) Vj(2w)
r + o(ts1w ?1 rt ),
?·t
Vj
j Uj
0
0
где
?(l1)
Uj
=
X (21)
1
(31)
(2w) (l1)
Vi D21 + Vi D31 Uj Ui
?1 i
s?1w
и Dl1 блоки матрицы Bw?1,w (l = 1, 2).
Теорема доказана.
Из доказательства теоремы вытекает
Следствие 1.
При t ? ?
(t)
Blh = Hlh · tslh ?1 rt (1 + o(1)) для l 6= h,
?
89
О МАТИЦЕ ПЕВЫХ МОМЕНТОВ
где
?P
?(1l)
Hlh
(2h)
U
Vj
?P j
= ? j Uj?(2l) Vj(2h)
0
j
P ?(1l) (3h) ?
U
V
Pj j?(2l) j(3h) ?
Vj ? .
j Uj
0
Проинтерпретируем результаты теоремы 1, используя деревья вывода. Обозначим через D множество деревьев вывода, корень которых помечен аксиомой грамматики A1 , и через Mi (t) математическое ожидание числа вершин на ярусе t
дерева вывода из D, помеченных нетерминальным символом Ai .
Следствие 2.
Пусть Ai ? Kj . Тогда при t ? ?
Mi (t) ? ci · ts1j ?1 rt ,
где ci некоторая неотрицательная константа.
абота выполнена при инансовой поддержке ФФИ (проект ќ 07-01-00739).
Summary
L.P. Zhiltsova.
On a Matrix of First Moments for Deomposable Stohasti CF-Grammar.
Stohasti ontext-free grammar is onsidered whih ontains arbitrary number of lasses
of non-terminal symbols without restritions on the suession order of lasses. Corresponding
matrix A of rst moments is deomposable. For the ase when Perron's root of the matrix A
is stritly less than one, properties of the matrix At are investigated under t ? ?.
Key
words:
algorithm, oding,
optimization, automaton, probability.
ompression,
ontext-free
language,
grammar,
Литература
1.
Закономерности применения правил грамматики в выводах слов
стохастического контекстно-свободного языка // Матем. вопр. кибернетики. 2000. Вып. 9. С. 101126.
2.
Жильцова Л.П. О нижней оценке стоимости кодирования и асимптотически оптимальном кодировании стохастического контекстно-свободного языка // Дискр. анализ и исслед. операций. Сер. 1. 2001. Т. 8, ќ 3. С. 2645.
3.
Жильцова Л.П.
Севастьянов Б.А.
Ветвящиеся процессы. М.: Наука, 1971. 436 .
4.
Борисов А.Е. О свойствах стохастического КС-языка, порожденного грамматикой
с двумя классами нетерминальных символов // Дискр. анализ и исслед. операций.
Сер. 1. 2005. Т. 12, ќ 3. С. 331.
5.
Ахо А., Ульман Дж. Теория синтаксического анализа, перевода и компиляции. Т. 1. М.: Мир, 1978. 616 с.
6.
Фу К.
Структурные методы в распознавании образов. М.: Мир, 1977. 320 с.
7.
антмахер Ф..
Теория матриц. М.: Наука, 1966. 576 с.
Поступила в редакцию
30.03.09
Жильцова Лариса Павловна доктор изико-математических наук, проессор
каедры математической логики и высшей алгебры Нижегородского государственного
университета им. Н.И. Лобачевского.
E-mail: larzhilrambler.ru
Документ
Категория
Без категории
Просмотров
4
Размер файла
214 Кб
Теги
грамматике, первые, моментов, матрица, стохастических, разложимой
1/--страниц
Пожаловаться на содержимое документа