Операции над бинарными отношениями

F Определение: Бинарным отношением R, заданным на множестве V называется подмножество множества V ´ V.

Если a ₁, a ₂Î V (a ₁, a ₂) Î R, то говорят, что для данной пары выполняется бинарное отношение R, т. е. a ₁ Ra ₂.

1. Пусть имеется два отношения R ₁ и R ₂. Объединением R ₁È R ₂ называется бинарное отношение, полученное в результате теоретико-множественного объединения R ₁ и R ₂.

2. Произведением R ₁ ´ R ₂ называется бинарное отношение со следующим свойством: a ₁ R ₁ R ₂ a ₂ в том и только том случае, если найдется такой элемент a, что a ₁ R ₁ a и aR ₂ a ₂.

3. Транзитивным замыканием R называется бинарное отношение со следующим свойством: a ₀ R a_n в том и только том случае, если найдется такая последовательность элементов a ₀, a ₁,..., a_n, n ³1, что a_iRa_{i +1}, 0 £ i £ n -1; R Í R.

4. Пусть Е – отношение равенства: a ₁ Ea ₂ в том и только том случае, если a ₁= a ₂.

5. Транзитивно-рефлексивным замыканием R * отношения R называется бинарное отношение, вычисленное по формуле R *= E È R.

6. Бинарное отношение на конечном множестве можно задать квадратной матрицей порядка n, где n – число элементов множества. Пусть элементы множества V некоторым образом пронумерованы числами от 1 до n: V = { a ₁, a ₂,..., a_n }. Тогда отношение R на V задается матрицей || s_ij ||, s_ij =1, если a_iRa_j, и s_ij =0, если для пары (a_i, a_j) отношение не выполнено.

Определим некоторые бинарные отношения на множествах нетерминальных символов КС-грамматик:

Пусть G = (V_T, V_A, I, S).

Пусть (А ₁, А ₂) – пара нетерминальных символов.

1. Будем считать, что для пары (А ₁, А ₂) в грамматике G выполняется отношение D_N, если во множестве правил S содержится правило вывода А ₁® А ₂. Если справедлива запись А ₁ D_N А ₂, то говорят, что А ₂ – непосредственно выводим из символа А ₁ без расширения.

2. Будем считать, что для пары (А ₁, А ₂) в грамматике G выполняется отношение D_W, если во множестве правил S содержится правило вывода А ₁® x ₁ А ₂ x ₂, где x ₁, x ₂Î(V_T È V_A)* и хотя бы одна из них не пустая. Если справедлива запись А ₁ D_WА ₂, то говорят, что символ А ₂ непосредственно выводим из символа А ₁ с расширением.

3. Обозначим D_N È D_W через D. Если справедлива запись А ₁ DА ₂, то говорят, что символ А ₂ непосредственно выводим из А ₁.

F Определение: 1) Нетерминальный символ КС-грамматики (контекстно-свободной) называется выводимым, если он является начальным символом или существует вывод из начального символа цепочки, содержащей вхождение данного символа.

2) Нетерминальный символ КС-грамматики называется производящим, если существует вывод из этого символа терминальной цепочки.

3) Нетерминальный символ КС-грамматики называется существенным, если он выводимый и производящий.

Лемма1: Существует эффективный алгоритм, выделяющий подмножество существенных символов из множества нетерминальных символовпроизводящей КС-грамматики.

F Определение: 1) КС – грамматика, все нетерминальные символы которой существенны, называется приведенной.

2) Нетерминальный символ КС-грамматики называется циклическим, если в этой КС-грамматике существует вывод из этого символа цепочки, содержащей вхождение этого символа. В противном случае символ – нециклический.

3) КС-грамматика называется циклической, если в ней есть хотя бы один циклический символ.

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

Лемма2: Существует эффективный алгоритм выделения подмножества символов произвольной КС-грамматики.

Лемма3: Нециклическая КС-грамматика порождает конечный язык.

F Определение: Циклический символ КС-грамматики эффективный, если в ней существует вывод из этого символа цепочки более одного элемента, содержащей данный символ, в противном случае – фиктивный.

Пример 12: Символ A в приведенной ниже грамматике - фиктивный

I ® AB B ® b

A ® C C ® A

A ® a

Лемма4: Существует эффективный алгоритм выделения эффективных циклических символов произвольной КС-грамматики.

G Теорема 2: Для того чтобы приведенная КС-грамматика порождала бесконечный язык необходимо и достаточно, чтобы она была циклической и содержала хотя бы один эффективный циклический символ.

G Теорема 3: По любой УКС-грамматике (укороченная контекстно-свободная) может быть построена почти эквивалентная ей КС-грамматика.