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