Определение 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)+
