Дискретно-непрерывная математика (стр. 86 )

Пример грамматики.

1. V.

2. U.

3. В.

4. P=BF.

5. Q = P U,

6.R=QF.

7.F=V R.

Пусть α, β и γ — типы вершин, соответствующие трем типам категорий. Приведенную выше грамматику можно представить графом (рис. 5.65).

Рис.5.65.

Заметим, что по­именованными в графе оказываются только вершины ти­па α и рекурсивно используемая вершина. Используя распределительное свойство и подстановки, имеем

Результаты можно интерпретировать как граммати­ку некоторого простого префиксного языка, в котором F обозначает формулу, V—переменную, В — двоичный оператор и U — единичный оператор. Рекурсивное опре­деление формулы имеет вид:

1. Переменная.

2. Двоичный оператор, за которым следуют две фор­мулы.

3. Единичный оператор, за которым следует одна формула.

Соответствующий граф показан на рис. 5.66.

Рис. 5.66.

Граф грамматики называется Г-графом языка и используется для получения всех цепочек и опознавания любых про­извольно заданных цепочек. Цепочки префиксного язы­ка имеют вид;

Заметим, что

1. Г-граф языка конечен.

2. Множество всех цепочек ∑ конечно.

3. Множество всех цепочек ∑ неречислимо.

4. Произвольная цепочка ∑k может быть представле­на деревом. Например, на рис. 5.67 показано дерево, соответствующее цепочке ∑6, приведенной выше.

Pис. 5.67

∑-графы представляют собой ориентированные расту­щие из корня деревья, каждая вершина которых по­именована соответствую­щим названием категории. Обычно требуется, чтобы ∑-графы формальных язы­ков были связны и пред­ставляли собой деревья, а не леса (в терминологии теории графов). Кроме того, обычно предполагает - ся, что цепочки языка определены однозначно, т. е. каждой цепочке соответству­ет единственный ∑-граф. Можно опре­делить, является ли заданная цепочка неоднозначной при заданной грамматике. Задача определения неоднознач­ной грамматики или вообще языка (который может иметь много различных грамматик) оказывается более слож­ной. Действительно, было показано, что задача опре­деления однозначности (или неоднозначности) формаль­ной грамматики рассматриваемого типа неразрешима. С другой стороны, если цепочки языка перечислимы, то можно проверить на однозначность достаточно большое их число.

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

Полезно найти особые ограничения или обобщения Г-графов языка. Одно из интересных обобщений связано с заданием некоторых функций длины на дугах графа. В начальный момент длины всех дуг одинаковы. По мере последовательного использования дуг значения их функции длины возрастают. Альтернативные варианты путей выбираются всегда с учетом длины. Таким обра­зом, накапливая «опыт», машина улучшает качество своей работы. Если такую взвешивающую схему встро­ить, например, в транслятор с ФОРТРАНа, то трансля­тор сможет в некотором смысле обучиться распознава­нию стиля и почерка отдельных программистов.

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

Цель одного разработанного проекта состоит в том, чтобы найти структурную характеристи­ку больших массивов табличных данных. В этом случае алфавит состоит из элементов таблицы — множеств взаимосвязанных свойств — которые можно распознать. Категории информации определяются структурно из элементов таблиц.

ДОПОЛНИТЕЛЬНЫЕ ПРИЛОЖЕНИЯ

5.29. Математические машины и цепи Маркова

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

системы проявляется в форме перехода из одного состоя­ния в другое и формирования соответствующего выход­ного сигнала. Формализация предыдущей идеи приво­дит к понятию математической машины.

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

Определение. Машина есть математическая система, которая состоит из

1) конечного множества S={s1,..., sm} элементов, называемых состояниями,

2) конечного множества Х={х1,.,., хп} элементов, называемых входами,

3) конечного множества Y={y1,..., уk} элементов, называемых выходами,

4) функции перехода Т, которая отображает S×Х нa S,

5) функции выхода Ω, которая отображает S ×Х на Y.

Если sS и хХ, то s'=T(s, x) интерпретируется как следующее состояние, в которое попадает машина из текущего состояния s при воздействии входного сигна­ла х. Аналогично, y=Ω(s, x) есть выходной сигнал машины, находящейся в состоянии s при воздействии входного сигнала х. Множества X и Y называются соот­ветственно входным и выходным алфавитом (хотя при­рода их элементов существенно изменяется в зависимо­сти от рассматримаемых задач).

Машины, соответствующие данному определению, можно классифицировать по нескольким признакам. Во-первых, они являются детерминированными, так как их выходной сигнал и следующее состояние полностью определяются входным сигналом и текущим состоянием. Далее, такие машины являются последовательностными, так как входные сигналы подаются в дискретные момен­ты времени

t1, t2, t3, а не непрерывно. Они являются полными, т. е. каждая комбинация состояния и входного сигнала (входа) имеет смысл и дает известный выход­ной сигнал (выход) и новое состояние. Они не имеют памяти в том смысле, что текущий выход и следующее состояние не зависят от прошлых входов, состояний или выходов. Наконец, они стационарны в том смысле, что функция переходов Т и функция выхода Ω не зави­сят от рассматриваемого момента времени. Изменив не­которые или все из названных предположений, можно получить определение машины более общего вида.

Иногда машину удобно изображать ориентирован­ным графом, вершины которого соответствуют состояни­ям, а дуги характеризуют X, Y, Т и Ω.

Сказанное проще всего пояснить на примере. Рассмотрим машину, для которой

S={s1,s2, s3, s4}, Х={0,1} и Y={a, b, с}.

Одна из возможных машин с множеством состояний S и алфавитами X и Y представлена в виде графа рис. 5.68.

Рис. 5.68.

Каждая вершина соответствует одному состоянию. На­чальная вершина инцидентна точно двум дугам (в об­щем случае, k дугам, где k — число различных входов). Если некоторая дуга идет из вершины s в вершину s' и ей соответствует упорядоченная пара (х, у), то T(s, x) = s', Ω(s, x)=y. Например, если текущее состояние системы s3, то вход 0 даст выход b и переведет систему в состояние s4. С другой стороны, вход 1 дает выход а и система останется в состоянии s3. (Практически число дуг можно уменьшить, помечая некоторые дуги несколь­кими упорядоченными парами, если несколько входов дают одно и то же следующее состояние.) Отдельные состояния и множества можно классифи­цировать по структурным признакам соответствующего графа. Например, машина называется сильно связной, если ей соответствует сильно связный граф. Независимо от начального состояния s такую машину можно всегда перевести в любое другое состояние s' с помощью соот­ветствующей последовательности входов (не обязатель­но за один шаг). Состояние s называется переходным, если из соответствующей ему вершины выходит, по крайней мере, одна дуга (s, t), где t≠s, и если эта вер­шина не является конечной ни для одной дуги (и, s), где и≠s. Например, s1 — переходное состояние. Состоя­ние s1, которому соответствует вершина, являющаяся конечной, по крайней мере, для одной дуги (t, s), где t≠s, и не являющаяся начальной ни для одной дуги (s, и) где s≠и, называется устойчивым. (Рассматривае­мая машина не имеет отдельных устойчивых состояний. Однако состояние s2, s3 и s4 совместно образует в соответствующем смысле устойчивое множество сос­тояний).