Некоторые отношения применительно к грамматикам. 


Мы поможем в написании ваших работ!



ЗНАЕТЕ ЛИ ВЫ?

Некоторые отношения применительно к грамматикам.



 

Отношения.

 

Символы "=>" и "=>+" являются примерами отношений между цепочками. Вообще говоря, (бинарным) отношением на множестве является любое свойство, которым обладают (или не обладают) любые два упорядоченных символа этого множества.

Другим примером является отношение МЕНЬШЕ ЧЕМ (<), определенное на множестве целых чисел: i<j тогда и только тогда, когда j-i является положительным ненулевым целым числом. Не математическим является отношение РЕБЕНОК, определенное на множестве людей. Некто А либо является ребенком В, либо нет.

Мы используем инфиксные обозначения для отношений: если между элементами c и d некоторого множества имеет место отношение, то мы пишем cRd. (Заметим также, что важен порядок двух объектов: из cRd автоматически не следует dRc.) Можно также рассматривать отношение как множество упорядоченных пар, для которых данное отношение справедливо: (c,d)ÎR тогда и только тогда, когда cRd.

Мы говорим, что отношение P включает другое отношение R, если из (c,d)ÎR следует (c,d)ÎP.

Отношение, обратное отношению R, записывается как R-1 и определяется следующим образом: с R-1 d тогда и только тогда, когда dRc.

Отношение, обратное отношению БОЛЬШЕ ЧЕМ, есть МЕНЬШЕ ЧЕМ. Отношение, обратное отношению РЕБЕНОК, есть РОДИТЕЛЬ.

Отношение R называется рефлексивным, если cRc справедливо для всех элементов c, принадлежащих множеству. Например, отношение МЕНЬШЕ ЧЕМ ИЛИ РАВНО (≤) являются рефлексивным (i≤i для всех действительных чисел i), тогда как отношение МЕНЬШЕ ЧЕМ таковым не являются.

Отношение R называется транзитивным, если aRb и bRc влечет за собой aRc. Отношение МЕНЬШЕ ЧЕМ над целыми числами является транзитивным. Отношение РЕБЕНОК не является транзитивным; если Джон сын Джека и Джек сын Джила, то, очевидно, Джон не является сыном Джила.

Для любого отношения R определим новое отношение R+ и назовем его транзитивным замыканием R. Оно называется так потому, что включается в любое транзитивное отношение, которое включает в себя R. Другими словами, предположим, что P - транзитивное отношение, которое включает в себя R: из (c,d)ÎR следует (c,d)ÎP. Тогда P также включает в себя R+.

Прежде всего, для двух заданных отношений R и P, определенных на одном и том же множестве, введем новое отношение RP, названное произведением R и P: cRPd тогда и только тогда, когда существует такое e, что cRe и ePd. Умножение бинарных отношений ассоциативно: (PQ)=(RP)Q для любых отношений R,P и Q.

В качестве примера рассмотрим отношения R и P над целыми числами, определенные следующим образом:

aRb тогда и только тогда, когда b=a+1,

aPb тогда и только тогда, когда b=a+2.

Очевидно, что aRPb, тогда и только тогда, когда есть такое c, что aRc и cPb, т.е. тогда и только тогда, когда b=a+3.

Используя произведение, определим теперь степени отношения R следующим образом:

R1=R, R2=RR, Rn=Rn-1R=RRn-1 для n>1. Определим R как единичное отношение:

aR0b тогда и только тогда, когда a=b.

И, наконец, транзитивное замыкание R+ отношения R определяется следующим образом:

aR+b тогда и только тогда, когда aRnb для некоторого n>0.

Очевидно, если aRb, то aR+b. Доказательство того, что R+ действительно является транзитивным, предоставляется читателю в качестве упражнения. Ясно, почему для транзитивного замыкания выбрано обозначение R+; когда отношения рассматриваются как множества упорядоченных пар, мы имеем

R+=R1ÈR2ÈR3....

Определим рефлексивное транзитивное замыкание R* отношения R как

аR*b тогда и только тогда, когда a=b или aR+b.

Таким образом, R*= R0ÈR1ÈR2È....

 

Отношения применительно к грамматикам.

 

Чем же вызван такой интерес к грамматикам? Во-первых, теперь должно быть, очевидно, что символ =>+ обозначает не что иное, как транзитивное замыкание отношения, определенного ранее. И, во-вторых, с грамматиками связано несколько важных символьных множеств, которые в дальнейшем нам придется построить. Эти множества легко определяются в терминах совсем простых отношений и их транзитивных замыканий. Единственное требование заключается в том, чтобы отношения были определены на конечном множестве элементов.

Если задана грамматика и нетерминальный символ U, то нам необходимо знать множество головных символов в цепочках, выводимых из U. Таким образом, если U=>+Sх, то цепочка Sх выводима из U и S принадлежит множеству. Назовем это множество голова (U) и определим его формально следующим образом:

голова (U)::={S|U=>+S...}.

(Напомним, что тремя точками "..." обозначается цепочка (возможно пустая), которая в данный момент нас не интересует.) В большинстве случаев такое определение могло бы быть удовлетворительным. Заметим, однако, что в определении используется отношение =>+, заданное на бесконечном множестве цепочек в словаре V, и хотя само множество голова (U), конечно, при его построении могут возникнуть трудности. Поэтому мы переопределим множество голова (U), используя другое отношение, заданное на конечном множестве следующим образом. Определим отношение FIRST(первый) в конечном словаре V грамматики следующим образом:

U FIRST S тогда и только тогда, когда существует правило U::=S....

Затем, согласно определению транзитивного замыкания, имеем

U FIRST+ S тогда и только тогда, когда существует непустая последовательность правил U::=S1..., S1::=S2...,..., Sn::=S.... Из этого, очевидно, вытекает, что

U FIRST+ S тогда и только тогда, когда U=>+ S....

Заметим, что если отношение FIRST+ рассматривать как множество, то оно полностью определяет множество голова (U) для всех символов U словаря V: голова (U)={S|(U, S) в FIRST+}.

П р и м е р 1.4. Чтобы проиллюстрировать оба отношения FIRST и FIRST+, выпишем несколько правил и справа от каждого из них укажем отношение FIRST, выведенное из этого правила.

Таким образом, мы имеем следующие пары в FIRST+:

(A,A) (A,B) (A,D) (B,B) (B,D) (D,B) (D,D) (C,e)

Следовательно, головными символами цепочек, выводимых из A, будут A, B и D, из B - B и D, из C – e, из D – B и D.

Есть еще три других множества, которые мы хотим здесь определить. Они могут быть определены тем же путем, что и FIRST+. Первое из них - это множество символов, которыми оканчиваются цепочки, выводимые из некоторого символа U. Оно определяется для всех символов U через отношение LAST+, являющееся транзитивным замыканием отношения LAST (последний):

U LAST S тогда и только тогда, когда существует правило U::=...S.

Второе множество - это множество внутренних символов цепочек, выводимых из нетерминала U. Оно определяется через отношение WITHIN+, являющееся транзитивным замыканием отношения WITHIN(внутри).

U WITHIN S тогда и только тогда, когда существует правило U::=...S...

И, наконец, определим множество символов S, которые выводимы из нетерминала U. Оно определяется через отношение SYMB+, являющееся транзитивным замыканием отношения SYMB(симв):

U SYMB S тогда и только тогда, когда существует правило U::=S.

 

 

Булевы матрицы и отношения.

 

Представим отношения в алфавите в виде, удобном для машинной обработки. Для такого представления больше всего подходит булева матрица B. Это матрица, элементы которой B[i, j] могут принимать только значения 0 и 1 (ложь или истина). Предположим, что отношение R определено на множестве S из n символов S1, …, Sn. Для того чтобы представить это отношение, построим булеву матрицу B n – порядка с элементами B[i, j], равными 1 тогда и только тогда, когда Si R Sj. Например возьмем отношение FIRST (пример 1.4). Матрица B для этого отношения:

  S1=A S2=B S3=C S4=D S5=e S6=d S7=f
S1=A              
S2=B              
S3=C              
S4=D              
S5=e              
S6=d              
S7=f              

 

Пусть B – булева матрица n – го порядка, представляющая отношение R, заданное в алфавите S из n символов. Тогда матрица B+, определенная как

B+ = B + BB + BBB + … + Bn,

представляет транзитивное замыкание R+ отношения R.

 

Рис.1.10. Вычисление В+ от В.

Например на рис.1.10. показаны матрицы B, B2, …, B7 и B+ для матрицы B. Из B+ вновь получаем следующие пары в FIRST+:

(A,A) (A,B) (A,D) (B,B) (B,D) (D,B) (D,D) (C,e)

 



Поделиться:


Последнее изменение этой страницы: 2016-07-14; просмотров: 444; Нарушение авторского права страницы; Мы поможем в написании вашей работы!

infopedia.su Все материалы представленные на сайте исключительно с целью ознакомления читателями и не преследуют коммерческих целей или нарушение авторских прав. Обратная связь - 44.199.225.221 (0.01 с.)