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

Определение 21(Конъюнктивные регулярные выражения) Конъюнктивные (к.) регулярные выражения над множеством E (regK(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 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*)

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