XML - статьи

         

Вторая нормальная форма.


Определение 21(Конъюнктивные регулярные выражения) Конъюнктивные (к.) регулярные выражения над множеством E (regK(E))определяются следующим образом:

  • ?- регулярное выражение, где обозначает "пустой список"
  • e
    E: e- к. регулярное выражение
  • Если r1 - к. регулярное выражение, то (r1)-к. регулярные выражения
  • Если r1 и r2- к. регулярные выражения, то r1, r2 - тоже к. регулярное выражение
  • Если r =(e0,..,en) , где >
    i : ei
    E, то r* и r+ - к. регулярные выражения
  • Определение 22 (Вторая нормальная форма) Схема S=(T,E,A,p,a,r) представлена во второй нормальной форме (слабо-эквивалентная нормальная форма), если:

    e
    E p(e)=r0|..|rn , где
    i ri
    regK(E)

    Teoрема 6 (Существование второй нормальной формы) Для любой схемы S=(T,E,A,p,a,r) существует схема слабо-эквивалентная ей, представленная во второй нормальной форме.

    Для доказательства этой теоремы, необходимо воспользоваться результатами Теоремы 5. Для исходной схемы S существует эквивалентная схема S', структурные ограничения которой имеют вид r0|..|rn , где

    i ri
    regKM(E). Далее, для каждого ri мы воспользуемся преобразованием (r1*, r2)* ? ? | r1*, r2+ (3.2.2) для уменьшения вложенных операторов * и +. После чего, если выражение r2 содержит операцию *, то воспользуемся преобразованием (3.1.3) для замены оператора r2+ на r2*,r Таким образом, используя индукцию по длине регулярного выражения и по глубине "вложенности" операций * и +, приходим к доказательству теоремы. Используя преобразования (3.2.1) и (3.1.11)-(3.1.16) можно добиться существенного упрощения выходной формы

    Пример 7 Приведем регулярное выражение из предыдущего примера ко второй нормальной форме.

    (b|c)?,(f?,b*)*

    b,(f,b*)*| c,(f,b*)*| (f,b*)*? (b|c|? )(b*f+|? )? b+f+|b|cb*f+|c|b*f+|?? b|cb*f+|c|b*f+|? (в последнем переходе использовалось эквивалентное преобразование r*|r+
    r*)



    Содержание раздела