Структурные ограничения XML

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

Определение 1 (Регулярные выражения над множеством символов E) Множество регулярных выражений над множеством E (reg(E))определяется следующим образом:

Определение 2 (Порождаемые последовательности) Пусть r- регулярное выражение над множеством E. Тогда конечная (м.б. пустая) последовательность s=[e0,..,en] символов, где

, порождается выражением r (s|=r), тогда и только тогда, когда выполняется одно из следующих соотношений:

Множество всех порождаемых последовательностей регулярного выражения r над множеством Е называется регулярным множеством и обозначается так:

Пример 1

Пусть E={0,1}.
Множество последовательностей, порождаемых регулярным выражением (0|1)(0|1) состоит из множества последовательностей длины 2, содержащих элементы 0 и 1:

[0,0];[0,1];[1,0];[1,1].

Регулярное выражение (0|1)* порождает множество последовательностей произвольной длины, состоящих из 0 и 1, то есть полное множество всех последовательностей над множеством E.

Определение 3 (Эквивалентность регулярных выражений) Пусть r1,r2

reg(E) . Тогда

Определение 3' (Эквивалентность регулярных выражений)Пусть r1,r2

reg(E) . Тогда

Пример 2

Регулярные выражения r*,r и r+ эквивалентны, где r - произвольное регулярное выражение над множеством r. Покажем это. Пусть s|= r+ . Тогда по определению 2 s ? [s1,..,sn], где

i: si |=r. Тогда s1|=r и [s2,..,sn]|=r* и, значит, s|= r*,r . В обратную сторону утверждение доказывается аналогично.

Teoрема 1 (Замена выражений) Пусть

1 и

2 - есть идентичные регулярные выражения над множеством {E,r1} и {E,r2}, соответственно ,где r1 и r2- обозначения регулярных выражений над множеством E (f1 получается из f2 путем замены символа r2 на r1 и наоборот). Пусть

1 и

2 - это два регулярных выражения над множеством E, получаемые, соответственно, из

1 и

2, с помощью замены символов r1 и r2 на регулярные выражения над множеством E. Тогда r2

r1 ==>

Содержание Назад Вперед

Forekc.ru
Рефераты, дипломы, курсовые, выпускные и квалификационные работы, диссертации, учебники, учебные пособия, лекции, методические пособия и рекомендации, программы и курсы обучения, публикации из профильных изданий