Третья нормальная форма.

Определение 23 (Простые регулярные выражения) Простые (п.) регулярные выражения над множеством E (regS(E))определяются следующим образом:

?-п. регулярное выражение, где обозначает "пустой список"

E: e- п. регулярное выражение

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

Если r =e , где e

E, то r* ,r? r+ - п. регулярные выражения

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

E p(e)=r , где r

regS(E)

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

Для доказательства этой теоремы следует воспользоваться упрощающими преобразованиями для построения новой структурной схемы, являющейся упрощением исходной схемы и представленной в третьей нормальной форме. Для доказательства того, что такая схема существует необходимо воспользоваться индукцией по длине регулярного выражения.

Пример 8 Рассмотрим регулярное выражение из примера 7.

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

В отличие от первой и второй нормальных форм, для третьей нормальной формы можно сформулировать и доказать теорему единственности. Пусть на множестве E введено отношение порядка. Тогда, определим простые упорядоченные регулярные выражения следующим образом:

Определение 25 (Простые упорядоченные регулярные выражения) Простые упорядоченные (п. у.) регулярные выражения над множеством E (regSO(E))определяются следующим образом:

? -п. у. регулярное выражение, где обозначает "пустой список"

E: e- п. у. регулярное выражение

Если r =e , где e

E, то r* ,r? r+ - п. у. регулярные выражения

Если r1 и r1- п. регулярные выражения, и

a1,a2

E, таких, что

s1= [e0,..,ei-1,a1,ei+1,..,en], s2= [e'0,..,e'i-1,a2,e'i+1,..,e'n] s1|=r1, и s2|=r2 верно, что e1e2, то r1, r2 - тоже п. у. регулярное выражение

Определение 24 (Третья нормальная форма) Схема S=(T,E,A,p,a,r) с заданным отношением порядка на множестве E представлена в третьей нормальной форме (простая нормальная форма), если:

E p(e)=r , где r

regSO(E)

Если не существует двух типов элементов с одинаковым именем, то отношение порядка на множестве E может соответствовать лексикографическому порядку на множестве имен элементов.

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