XML - статьи

Первая нормальная форма.


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

  • ?- к.-м. регулярное выражение, где ? обозначает "пустой список"
  • e
    E: e- к.-м. регулярное выражение
  • Если r1- к.-м. регулярное выражение, то (r1), r1*- к.-м. регулярные выражения
  • Если r1 и r2- к.-м. регулярные выражения, то r1, r2 - к.-м. регулярные выражения

    • Определение 20 (Первая нормальная форма) Схема S=(T,E,A,p,a,r) представлена в первой нормальной форме (эквивалентная форма), если :

    e
    E p(e)=r0|..|rn , где
    i ri regKM({id(E),T})

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

    Для доказательства этой теоремы следует воспользоваться следствием 1 из теоремы 3. Пусть e - некий элемент схемы S=(T,E,A,p,a,r). Соответственно p(e) - регулярное выражение. Используя эквивалентные преобразования регулярных выражений r?

    r|? (3.1.2) и r+
    r*,r (3.1.3) мы приходим к регулярному выражению, соответствующему исходному, но не содержащему операций ? и +. После чего следует воспользоваться преобразованиями (r1| r2),r3
    ( r1, r3)|( r1, r2) (3.1.6) и (r1| r2)*
    ( r1*, r2*)* (3.1.8) , после которых операция конкатенации ("|") "поднимается". Таким образом, для любого типа элемента e, p(e) преобразуется в выражение p'(e) вида r0|..|rn , где
    i ri
    regKM({id(E),T}). В силу следствия 1 новая схема S'=(T,E,A,p',a,r) , представленная в первой нормальной форме, эквивалентна схеме S

    Следует заметить, что для регулярных выражений с использованием операции позитивного замыкания ("+") вместо операции Клини ("*")теорема о существовании нормальной формы также верна.

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

  • ? - к.-м. регулярное выражение, где обозначает "пустой список"
  • e
    E: e- к.-м. регулярное выражение
  • Если r1 - к.-м. регулярное выражение, то (r1), r1+- к.-м. регулярные выражения


    • Если r1 и r2- к.-м. регулярные выражения, то r1, r2 - к.-м. регулярные выражения

    Принимая альтернативное определение конъюнктивно-множественных регулярных выражений, доказательство теоремы 5 частично меняется. Так, вместо преобразования r+
    r*,r     используется r*
    r+|?     (3.1.9). А вместо преобразования (r1| r2)*
    ( r1*, r2*)*     для поднятия конкатенации применяется (r1|r2)+
    ( r1+,r2+)+|( r2+, r1+)+| r1+| r2+|( r1+, r2+)+,r1+|( r2+, r1+),r2+     (3.1.17)

    Пример 6

    Приведем к первой форме r0|..|rn , где
    i ri
    regKM({id(E),T}) следующее регулярное выражение: ((b|c)?,(f?,b*)*), используя эквивалентные преобразования

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

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


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