2.10. Вероятности на ...

После определения возникает проблема, предполагает ли оно одинаковое «отношение» ко всем регулярным конфигурациям или некоторым них должен быть приписан вес, больший, чем остальным. Как, другими словами, следует вводить меру на пространстве конфигураций?

Для того чтобы сделать это, необходимо тем или иным способом определить распределение вероятностей или, по меньшей мере, аппроксимировать его. Если у нас нет сведений о случайном механизме, порождающем меру, то нам остается лишь действовать эмпирически и подсчитывать частоты встречаемости наблюдаемых конфигураций и затем классифицировать их на основе какого-либо признака. Более привлекательной, однако, является попытка промоделировать вероятностную меру исходя из соответствующих принципов. Как обычно, при вероятностном моделировании следует попытаться представить случайные элементы с помощью переменных, подчиняющихся «хорошим» распределениям, т. е. обладающих статистической независимостью или одинаковым распределением или и тем и другим одновременно.

В результате мы приходим к метрической теории образов - комбинаторные свойства теории естественно приводят к определенным вероятностным следствиям, к изучению которых мы приступим в данном разделе.

Рассмотрим пространство и простой случайный источник образующих (см. разд. 1.4), так что на задано априорное распределение Пусть произведение мер на прямом произведении пространств причем безусловное распределение по каждой координате.

Если то распределение вероятностей определяется на совокупности регулярных конфигураций как условная мера

Здесь для образующих входящих в допустимые -элементные конфигурации, вводится фиксированная индексация, которая выбирается в зависимости от используемого типа соединения. Пользуясь такой индексацией, мы рассматриваем в качестве точки в пространстве в качестве подмножества

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

Случай 2.10.1 (разделенные объемы). Пусть X является пространством и образующие представляют собой сферы, удовлетворяющие ограничениям случая 2.9.2 и принадлежащие определяется на основе допущения о независимости непрерывности распределения на и положительности плотности распределения на (0,1). В таком случае и соотношение (2.10.1) справедливо.

В тех частных случаях, когда конфигурации не имеют внутренней структуры и, следовательно, какие-либо ограничения отсутствуют, приходим просто к т. е.

Допустим, что счетное и содержит образующие причем Последнее не представляет собой существенного ограничения, поскольку в случае, если некоторая соответствующая просто изымается из пространства образующих. Пусть, кроме того, имеется по крайней мере одна допустимая конфигурация длины Допустим, что рассматриваются конфигурации, составленные из образующих и обладающие фиксированной внутренней структурой, заданной соединениями а, и будем говорить, что структура связей требует если о соединяет — некоторая заданная функция согласования определяется для любой заданной из соотношения (2.10.1). Числитель этого выражения равен если , и 0 — в остальных случаях. Однако в том и только том случае, если для всех соединенных пар. Это означает, что доказано следующее утверждение.

Для пространств конфигураций с ограничениями вероятности определяются выражением

где произведение берется по всем соединениям в конфигурации, нормировочная константа, обеспечивающая . В частном случае, когда А — «истинное», приведенное выражение сводится к

где количества образующих в разбиении образующие, входящие в разбиение.

Рассмотрим теперь случай, когда непрерывная мера на (бесконечном более чем счетном). При этом возникает та трудность, что может оказаться равным нулю и соотношение (2.10.1) теряет смысл. Для того чтобы разобраться в этой ситуации, начнем рассмотрение с частного случая, иллюстрирующего, что может происходить в принципе. Пусть Б — «полный» и для всех

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

Естественно потребовать, чтобы множества были монотонно убывающими при стремлении к нулю и имели в качестве предела диагональное множество

Этого, однако, недостаточно. Необходимо допустить также наличие некоего свойства подобия; для этого вводится условие: принадлежит если принадлежит Обоснование подобного выбора выглядит следующим образом. Пусть значения представляют

результаты измерений, скажем таких, как местоположение, при отсутствии приоритетного начала координат. В таком случае вполне естественно рассматривать переносы в как преобразования подобия и естественно, как и выше, будет требоваться инвариантность относительно переносов.

В этом выборе, с другой стороны, нет ничего необычного. Пусть результаты измерений характеризуют не местоположение, а, скажем, размер, так что . В данном случае имеется предпочтительное начало координат, и наиболее естественным условием подобия окажется группа масштабных изменений при . В таком случае будет утверждаться, что если то и должно принадлежать т. е. последнее образовано лучами, исходящими из начала координат, а не прямыми, параллельными днагонали, как в предыдущем случае. Случай переносов рассматривается здесь в связи с тем, что он отчетливо выявляет основную трудность. Геометрическая интерпретация данного условия состоит в том, что образует относительно упоминавшейся днагонали цилиндрическое множество с постоянным поперечным сечением. В противном случае следовало бы требовать разной точности в разных точках диагонали, и результат оказался бы другим. Для того чтобы воспользоваться соотношением (2.10.1), следует рассмотреть условную вероятность

где числитель, и знаменатель выражения (2.10.6) можно записать в виде

где интервал для числителя равен , а для знаменателя — Введем обозначение для подмножества

Внутренний интеграл в (2.10.7) можно ограничить сверху и снизу с помощью

где мера Лебега в может быть выбрано произвольно малым, если достаточно мало. Наличие таких ограничений

для числителя и знаменателя показывает, что выражение (2.10.6) имеет предел при , а именно

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

Теорема 2.10.1. Для конфигураций длины с заданной внутренней структурой при выполнении указанных условий распределение вероятностей, индуцированное на определяется безусловными распределениями на образующих, на которые наложены ограничения,

Если классы соответствующих «ограниченных» образующих велики, , то распределение (2.10.11) становится все более сконцентрированным.

Следствие. Если в дополнение к условиям теоремы 2.10.1 функция имеет единственный максимум при то индуцированная вероятностная мера слабо сходится к единице со всей массой вероятности, сконцентрированной на элементе

Это утверждение следует из известных свойств обобщенных средних (см., например, монографию Харди, Литлвуда и Пойа (1934), стр. 173).

Это означает, что рост алгебраической зависимости ведет к увеличению концентрации вероятностей.

В связи с этим в нашем случае возникает еще одна проблема: при каких обстоятельствах алгебраическое ограничение не влияет на безусловные распределения? Ответ получить нетрудно.

Следствие. При выполнении условий теоремы 2.10.1 безусловные распределения остаются неизменными в том и только

том случае, если функция принимает лишь значения 0 и К, где К — некоторая постоянная.

Доказательство. Безусловное распределение остается неизменным в том и только том случае, если (см. (2.10.11))

где К — интеграл в знаменателе. Следовательно,

что означает либо либо

Вероятностную меру, индуцированную посредством на будем обозначать через

Теперь можно существенно ослабить условия теоремы 2.10.1. В частности, можно допустить, чтобы носителем образующих являлась вся действительная ось, или, что более интересно, конечное евклидово пространство или его часть. В последнем случае функция согласования может включать только некоторые координаты вектора. Условием, которое нельзя ослабить так, чтобы это не отразилось на результате, является инвариантность относительно переносов в области толерантности Можно использовать области типа

или

поскольку они инвариантны относительно переносов. Если же используются инвариантности других типов, то (2.10.11) не выполняется. В качестве соответствующего примера можно привести случай изменения масштаба, однако здесь мы не будем ни продолжать обсуждение этой темы, пытаться получить обобщение результатов для случая распределений более общего вида.

Возвращаясь к инвариантным относительно переносов, в качестве примера рассмотрим нормальные распределения.

Случай 2.10.2 (связанные нормальные распределения). Пусть действительные с и принадлежат к одному классу разбиения. В таком случае безусловное распределение на допустимой конфигурации также нормально.

Доказательство. Применим (2.10.11), но расширенное на бесконечную область и с различными безусловными распределениями для образующих. Это приведет при проведении точно такого же доказательства, дополненного требованием однородности, к получению аналогичного выражения, в котором степень заменяется произведением. Поэтому применительно к данному случаю получаем

Это выражение можно записать в стандартной форме плотности нормального распределения с параметрами

Отметим, что полученная в результате дисперсия не больше любой исходной дисперсии

Рис. 2.10.1.

Для того чтобы выяснить, как структура связей влияет на стохастическую зависимость, рассмотрим случай, в котором 2 — «линейный порядок», «равенство» и входные и выходные связи образующей — действительные (они обозначены у и 2 соответственно). задано двумерными нормальными распределениями с нулевыми средними, единичными средними квадратичными отклонениями и коэффициентом корреляции .

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

с квадратичной формой

из которой моменты второго порядка могут быть вычислены непосредственно.

Прежде чем приступить к этим вычислениям, рассмотрим Р, определенную в естественно, она будет задаваться выражениями (2.10.18) и (2.10.19), за исключением того, что будет заменено Пусть нас не интересует последний показатель связи . В таком случае следует проинтегрировать плотность совместного распределения по этой переменной, что приведет к получению выражения типа в котором, однако, коэффициент 1 при заменяется некоторой постоянной . Эту процедуру можно повторить; чтобы получить рекуррентное соотношение для постоянных записываем следующее:

Интегрирование по приводит к рекурсии

Все будут принадлежать интервалу [1,2], и, поскольку правая часть (2.10.21) есть возрастающая функция эти постоянные образуют ограниченную возрастающую последовательность. Нетрудно показать, что где удовлетворяет уравнению

Следовательно, поскольку возможен корень только больше единицы,

Точно таким же образом при рассмотрении конфигурации, которая предполагается продолжающейся на шагов влево, можно в связи с симметричностью задачи использовать эти же аргументы. Это действительно так, поскольку зависимость между входной и выходной связями симметрична, хотя тип соединения 2 в данном случае не симметричен.

Объединение этих результатов позволяет получить следующую теорему,

Теорема 2.10.3. Мера, введенная на обладает тем свойством, что для регулярной конфигурации плотность совместного распределения определяется выражением (2.10.18), в котором заменяется на

где определяется выражением (2.10.21). В пределе при значение стремится к

В данном случае с рассматривается как конкатенация

Выполнив ряд алгебраических преобразований, основанных на использовании (2.10.21), переписываем (2.10.24) в следующем виде:

последнее приводит к интересным следствиям.

Во-первых, это означает, что Р в нашем случае обладает марковским свойством: линейный тип соединения в сочетании с отношением связи «равенство» приводит к марковской зависимости.

Во-вторых, можно воспользоваться стохастической независимостью

с дисперсиями

В частности, с помощью (2.10.22) для предельного случая получаем следующий простой результат:

Это означает, что -структура обеспечивает уменьшение дисперсии от 1 до Кроме того, коэффициент корреляции между двумя соседними показателями связей при равен он также уменьшается.

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

Для иллюстрации возможностей, открывающихся в этом направлении, рассмотрим более сложный тип соединения. Пусть образующие перенумерованы с помощью пар целых чисел, так что их можно было бы представить как узлы решетки на плоскости. Вместо того чтобы, как в предыдущем случае, начинать с конечных конфигураций и использовать ограниченную область определения, будем с самого начала считать конфигурацию бесконечной, т. е. считать, что в конфигурации встречаются все целые значения и Пусть образующие имеют одни и те же связи, хотя показатели связей могут, естественно, быть разными. В качестве как и выше, выбирается «равенство». Допустим также, что соединения инвариантны относительно переносов. Арность образующих будем обозначать через (учитываются реверсивные стрелки).

Образующая может иметь вид, как на рис. 2.10.2а, а соединения — как на рис. 2.10.26; на последнем рисунке связи удалены, с тем чтобы не загромождать его.

Допустим, что показатели связей некоторой образующей подчиняются нормальному распределению с нулевыми средними, единичными средними квадратичными отклонениями и полностью симметричными корреляциями. Последнее означает, что все коэффициенты корреляции имеют одно и то же значение . В таком случае корреляционная матрица имеет вид

т. е. является матрицей и ее обратная матрица равна

где

Рис. 2.10.2а.

Рис. 2.10.2б.

Известно, что для положительной определенности матрицы (а это здесь необходимо) требуется выполнение неравенства

Обозначим показатели связей образующей через где индекс, указанный на рис. 2.10.2а. Перенумерации требует лишь половина связей (симметрия!),

Будем считать, что показатели связей образуют р-мерный стационарный гауссов случайный векторный процесс с нулевыми средними и взаимными ковариациями которые ниже будут вычисляться.

Наше доказательство в данном случае является отчасти эвристическим в том смысле, что мы не используем в качестве исходных конечные конфигурации с последующим предельным переходом; этот дефект следует устранить путем строгого вывода.

В квадратичной форме (появляющейся в экспоненте) коэффициенты будут следующими:

Итак, необходимо решить дифференциальное уравнение в частных производных

Взаимные ковариации могут, однако, быть записаны как

где матричнозначная ограниченная мера на квадрате, используемом в качестве области интегрирования в (2.10.34), причем матричные значения — это неотрицательные симметрические матрицы (см. монографию Дуба (1953), стр. 536).

С другой стороны, функцию, стоящую в левой части (2.10.33), также можно записать аналогичным образом, но при специальном выборе

Следовательно, определив спектральные меры, получаем

где коэффициенты задаются следующим образом:

Введя фурье-преобразование типа соединения с помощью функции матрицы

где это те у которых связь соединена с образующей , можно решить уравнение (2.10.36) относительно спектральной меры

где обозначает функцию матрицы с элементом . Это дает нам спектральную меру и, следовательно, искомую взаимную ковариацию.

Мы нуждаемся в ограничениях нормы матриц и находим их из стандартного матричного неравенства

Однако

Если

Если, с другой стороны, то, используя (2.10.31а), получаем

Следовательно, можно записать

где Так как , то при можно определить

с помощью формального разложения в ряд Тейлора для квадратного корня, выбрав, например, положительную ветвь при Этот степенной ряд матриц равномерно сходится при действительных и можно записать, что

из последнего следует, что

где все е-векторы и их компоненты некоррелированны и имеют дисперсию

Важной частью доказательства является вывод (2.10.44), и его можно резюмировать следующим образом.

Теорема 2.10.4. Для конфигураций описанного типа структура ковариаций показателей связей задается спектральной мерой

где фурье-преобразование внутренней структуры, определяемой типом соединения;

Следует подчеркнуть, что в отличие от предыдущего случая данное доказательство является чисто эвристическим, поскольку мы не показали сходимость к предельному распределению.

Применим этот же способ анализа к структурам связей, возникающим в конечно-автоматных и бесконтекстных языках, начав с первых.

Обозначим безусловные вероятности на через где состояния, терминальный символ. В таком случае Р-мера, индуцированная на определяется как

где обозначения очевидны. Аналогичным образом, если с вложена в , как и выше, получаем выражение, аналогичное (2.10.49), с связями, и приходится «просуммировать» первых и последних, а также соответствующие терминальные символы. Введя матрицу

можно для соответствующих вероятностей записать

где вектор-столбец имеет единичные координаты, а вектор-столбец нулевые, за исключением координаты, которая равна единице,

В таком случае в (52) получаем

зависящую лишь от последнего показателя связи где с обозначает подконфигурацию с, не включающую последнюю образующую. Соединение Е — «линейный порядок» индуцирует марковское свойство в данном случае так же, как и в предыдущем случае.

Аналогичным образом в случае бесконтекстных языков такое же рассуждение показывает, что индуцированные вероятности можно рассматривать как результат последовательного выбора правил подстановки, причем акты выбора условно независимы — каждый зависит только от предшествующей образующей конфигурации. Итак, полученная в результате мера принадлежит ветвящемуся процессу, основанному на типе соединения 2 — «древовидный» и отношении согласования «равенство». Теперь приступим к более подробному анализу этого случая.

Для обозначения синтаксических переменных, элементов будем пользоваться греческими буквами, а иногда — цифрами. Перенумеруем множество правил подстановки с помощью индекса изменяющегося в диапазоне от 1 до Множество правил подстановку, применяемых к будем обозначать через

Как обычно, два вывода будут считаться идентичными, если они имеют одно и то же дерево вывода.

Случай 2.10.3 (синтаксически управляемые вероятности). Если заданы числа такие, что

всякому дереву вывода Т ставится в соответствие вероятность

где - множество правил, использованных в узлах Т, с учетом многократного применения правил.

В этом определении подразумевается, что если некоторое правило имеет в вероятность, равную нулю, то оно удалено из . Итак, Аналогичным образом, если существует только один вывод, начинающийся с о и имеющий положительную вероятность (эта вероятность должна быть в таком случае равна единице), то исключается посредством подстановки в правых частях всех правил ее значения. Это означает, что быть может, за исключением тех правил, которые изменяют а.

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

Пример 1. Пусть задан только один терминальный символ а, единственная синтаксическая переменная и правила

так что Правилу 1 ставится в соответствие вероятность В таком случае Общая схема завершенного вывода включает применений правила 2, за которыми следует одно применение правила Обозначив соответствующее дерево через на основе (2.10.56) получаем

Так как множество всех деревьев вывода равно — то

Итак, получено истинное распределение вероятностей, определенное на множестве полных деревьев вывода.

Это, однако, не всегда так. Действительно, достаточно взять то же, что и в примере 1, тривиальное множество грамматически допустимых цепочек но порожденных некоторой другой грамматикой.

Пример 2. Все то же, что и в примере 1, за исключением правил, имеющих теперь вид

с вероятностями соответственно. Рассмотрим, например, это множество состоит из двух деревьев, представленных на рис. 2.10.3; каждому из них приписывается вероятность .

Рис. 2.10.3.

В общем случае вывод включает применений правила применение правила 2. Следовательно, соответствующая вероятность равна Суммируя все эти вероятности, получаем

где -число различных деревьев вывода, приводящих к получению цепочки Эта функция обращается в нуль при а при Можно показать, что она непрерывна на отрезке [0, 1] (однако она не является аналитической в точке ; поэтому будет принимать значения, строго большие нуля и меньшие единицы при Для того чтобы получить допустимое распределение вероятностей на разумеется, необходимо требовать выполнение условия . Данный пример показывает, что оно не выполняется автоматически. Необходимо найти условия, гарантирующие выполнение этого требования. Для этого необходимо воспользоваться более сложным методом.

Нам будет удобнее работать с бесконечными деревьями вывода. Ко множеству правил добавим тривиальные правила для каждого терминального символа. Всем таким правилам приписывается вероятность, равная единице. В результате

при продолжении дерева вывода до бесконечности терминальный символ при подстановке может быть заменен только таким же терминальным символом (с вероятностью 1). Введем понятие уровня, для чего воспользуемся рис. 2.10.4, не требующим дополнительных пояснений.

Рис. 21.10.4.

Обозначим через множество всех возможных продолженных до бесконечности деревьев. Для заданного конечного дерева Т, завершенного или не завершенного, но доведенного до уровня I, введем подмножество множества включающее все бесконечно продолженные деревья вывода, совпадающие с деревом Т вплоть до уровня Подмножество называется цилиндрическим множеством с базой Т уровня Введем вероятности на цилиндрических множествах, приписывая вероятности их базе в соответствии с (2.10.56), и распространим меру на -алгебру подмножеств образованную всеми цилиндрическими множествами. Хотя полученная таким образом мера и является вполне корректной вероятностной мерой, это не совсем то, что мы хотели получить, поскольку нас интересуют лишь завершающиеся выводы. В они соответствуют цилиндрическим множествам, в которых, начиная с некоторого уровня, все символы являются терминальными; все это множество обозначим через Требуется найти критерии выполнения условия

Рассмотрим произвольное дерево вывода и обратимся к его уровню Определим число появлений на этом уровне первой синтаксической переменной, -второй синтаксической переменной и т. д. В результате получим вектор

где число синтаксических переменных. Следует установить, сходится ли вектор (с вероятностью единица) к нулевому; это означало бы, что вывод заканчивается.

В данном случае наша задача сведена к задаче, решение которой известно. Действительно, вектор образует ветвящийся процесс несколькими типами частиц (см. монографию Харриса (1963), стр. 58—80). Обозначим синтаксические переменные

индексами где 1 соответствует начальному символу. Рассмотрим для переменной множество пра причем пусть

где — число синтаксических переменных, входящих в правую часть правила Пусть матрица М имеет вид

Будем считать, что матрица М не имеет финальных классов (см. монографию Харриса (1963), стр. 75). В таком случае из теоремы о вырождении ветвящихся процессов следует, что вывод, начинающийся с произвольной синтаксической переменной, с вероятностью единица будет завершен в том и только том случае, если где положительное собственное значение матрицы М, большее по абсолютной величине всех остальных собственных значений. Следовательно, доказана следующая теорема.

Теорема 2.10.5. При описанных условиях синтаксически управляемая вероятностная модель порождает допустимую вероятностную меру на множестве завершающихся деревьев вывода в том и только том случае, если и матрица М не имеет финальных классов.

В примере 2 данного раздела присутствует единственная синтаксическая переменная а, так что и матрица М превращается в действительное число

Следовательно, «ели , то вероятностная мера, индуцированная на множестве деревьев вывода, корректна.

Далее будем считать, что условия теоремы 2.10.5 выполняются, и поэтому можно говорить о вероятностной мере на множестве всех деревьев вывода, причем индуцирована синтаксически управляемыми вероятностями.

Мы воспользуемся вероятностной мерой для определения вероятностной меры на множестве регулярных конфигураций, порожденных множеством

Определение 2.10.1. Для произвольной грамматически допустимой цепочки (52) зададим

Эта вероятностная мера обозначается через обозначает множество всех деревьев вывода для

Из определения 2.10.1 следует, что цепочке ставится в соответствие положительная вероятность в том и только том случае, если она грамматически правильна. В гл. 3 цепочки будут рассматриваться как изображения.

Замечание 1. Если грамматика однозначна, то вероятностная мера Р вводится посредством простого просмотра единственного вывода Т заданной цепочки и вероятность данного предложения Р определяется как .

Замечание 2. Один и тот же бесконтекстный язык иногда можно получить с помощью множества различных грамматик Эти грамматики вместе с вероятностями используемых правил подстановки порождают различные меры При заданном языке существует широкий выбор допустимых распределений вероятностей, обладающих не только различными параметрами, но и различными аналитическими формами. Возвращаясь к замечаниям 1 и 2, отметим, что в первом случае форма имеет вид

а во втором —

Грамматика определяет синтаксис, вероятностная мера определяет узус или стиль.

Нетрудно определить энтропию, что мы теперь и сделаем.

Теорема 2.10.6. Если энтропии определены как

и если собственное значение строго меньше 1, то энтропия Н вероятностной меры является первым компонентом вектора

где .

Доказательство. Для всех синтаксических переменных построим множества деревьев вывода с корнем в Как и выше, на каждом индуцируем синтаксически управляемые вероятности, что приводит к получению мер

. Для каждой из этих мер вычислим энтропию

Чтобы продемонстрировать, что они конечны, обратимся сначала к энтропиям соответствующим цилиндрическим множествам на уровне и запишем рекуррентное соотношение, связывающее энтропии воспользовавшись известной зависимостью

Наконец, устремим I к бесконечности, обратив внимание на монотонность зависимости от Сходимость следует из Для нас в первую очередь представляет интерес форма полученного в результате соотношения:

где — синтаксические переменные, входящие в заменяемую часть правила с учетом кратности. Воспользовавшись числами (см. выше), выражение (2.10.73) можно записать как

С учетом из последнего следует, что

или в матричном виде

т.е.

причем матрица неособенная, так как Нас интересует энтропия и, так как результат устанавливает приведенная ниже теорема.

С помощью этой теоремы можно вычислить энтропию, не прибегая к оценке вероятностей в явном виде. Вернемся еще раз к примеру 2. Так как то, если , из (2.10.77) непосредственно следует, что

При рассмотрении конечных автоматов возникает проблема приложения этих результатов к более конкретным задачам.

Теорема 2.10.7. Рассмотрим правостороннюю линейную грамматику и допустим, что всякой синтаксической переменной соответствует по меньшей мере один вывод с положительной вероятностью . В таком случае индуцированная вероятностная мера корректна.

Доказательство. В правосторонних линейных грамматиках все правила имеют вид или где

Это означает, что упоминавшиеся уже числа принимают значения 0 и 1, поэтому

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