Регулярные языки.Индуктивная процедура порождения регулярных языков.Регулярные выражения.Полукольцо регулярных языков.Незамкнутость полукольца регулярных языков.

П/к РЯ-R(v) п/к с итерацией состоит из пустого языка языка ,всех языков ,аÎÚ(каждый из которых содержит единственную однобуквенную цепочку а),и замкнутую относительно итерации.

Теор. Язык в алфавите V регуляренÛон является элементом п/к R(v).Алгебраические операции над регулярными языками представляют с помощью регулярных выражений. Каждый р.в. представляет некоторой р.я., причем языки Æ, и ,где аÎÚ,обозначаются выражениями Æ,  и ,соответственно, и если рег. Выражение р обозначает р.я. Р, а рег. выражениями q обоз. р.я. Q, то (р+q),pq или p* обозначает множества pÚq, PQ и P*.

Приоритет.

¯:*,.,+.

V= -р.я.

1)Æ, , ,аÎÚ

2)L₁ иL_2-р.я. L₁ÚL₂-р.я.

3)            L₁0L₂-р.я.

4)L-р.я. L*= =р.я.

Теорема Лагранжа

Пусть G=(G, . , II) – группа ,а H=(H, . , II) – её подгруппа. Левым смежным классом подгруппы Н по эл-ту а э Gназ м-во аН={y: y=ah, h э H}. Cоот-но правый смеж класс подгруппы Н по эл-ту а э G это м-во На={y: y=hа, h э H}

Теор 1: БО ~н есть эквивалентность на G, причём класс эквивалентности произвольного эл-та а э G совпадает с левым смежным классом аН.

Д-во: Докажем, что ~н является эквивалентностью на G. Посколько аН=На для люб а э G, т.е. а~н а, то БО ~н рефлексивно. Если а~нb, то аН=Нb, =>bH=Ha =>b~н a => БО симметрично. Наконец, из того, что а ~н b и b~н с следует, что аН=bH и bН=Нc =>aH=Hc =>a ~н c => БО транзитивно. Итак ~н – эквивалентность.

Докажем, что класс эквивалентности произвольного эл-та а = аН. Воспользуемся методом двух включений. Пусть х э [a]~н, т.е. х~н а, тогда хН=аН. Последнее означает, что любой эл-т вида аh, h э H, может быть представлен в виде хh1, где h1 э Н, т.е. аh=xh1. Отсюда получаем х=ahh1^-1. Поскольку Н – подгруппа, h, h1 э Н, то h2=hh1^-1 э Н. Следовательно, х=аh2 э аН и [a]~н =с аН.

Покажем второе включение, т.е. докажем, что аН =с [a]~н.

Пусть х э аН, тогда х=аh для некоторого h э Н. Отсюда получаем, что хН=аhH. Поскольку для всякого h э Н, как доказано выше hH=H, справедливо рав-во хН=аН, откуда х~н а и х э [a]~н.

Теор 2: Всякий левый смежный класс подгруппы Н равномощен Н.

Для произвольного фиксированного а э G зададим отображение Fa: H->aH. след образом Fa(h)=ah. Во-первых, отображение Fa есть сюръекция, т.к. если х э аН, то х = аh для некоторогоh э Н, откуда х=Fa(h). Во-вторых, Fa – инъекция, поскольку из равенства ah1=ah2 в силу законов сокращения в группе G следует h1=h2. =>Fa – биекция и |аН|=|Н|.

Теорема Лагранжа: Порядок конечной группы делится нацело на порядок любой её подгруппы.

Согласно вышеизложенным теоремам все левые смежные классы образуют разбиение множества G на подмножества, равномощные (в силу теор) подгруппе Н. Т.к. группа G – конечна, то число элементов разбиения конечно. Обозначив это число через K ,заключаем , что |G|=K|H|. Следовательно, порядок группы |G| делится нацело на порядок группы |H|.

Следствия: 1)любая группа простого порядка является циклической; 2) конечная группа неразложима ó она является циклич группой, порядок которой есть простое число. В конечной группе G для любого эл-та а э G имеет место равенство а^|G|=1.

.Классы Поста Примеры.Теерема о замкнутости классов Поста.

Пять функциональных классов,называемые классами Поста.

1)Т₀=ífÎP₂:f(0,….0)=0ý-класс функций, сохраняющих нуль.

2)Т₁=ífÎP₂:f(1,….1)=1 класс функций, сохраняющих 1.

3)L=ífÎP₂:f(x₁,….x_n)=a₀+a₁x₁+a_nx_n-класс линейных функциий,полином жигалкина которых не содержит ни одной коньюкции материалов.

4)Класс самодвойственности ф-ий S-ífÎP₂:f( )=f( )

5)

-класс монотонных функций

Теор.Каждый класс Поста замкнут.

Д-во:Нужно для каждого класса Поста           ,доказать что замыкание  множества бф С совпадает с С.Пусть f(g_1….g_n)-какая –то суперпозиция над С, обозначим ее через .Без ограничения обязоности можно считать,что все функции f,g_1….g_nÎP_2n.Рассуждаем,используя индукцию по определению суперпозиции ,если для каждого функция g_ix_i,где x_i-переменное,то =f(x,…x_n)ÎC.предположим,что в суперпозиции  все функции g_i есть эл-ты класса Поста C.Докажем, что и =f(g,…g_n)ÎC

1)Если С=Т_0,то

2)При С=  аналогино

3)Пусть с= .Фиксируем произвольно набор           Вычислим:

4)С=М.Берем произвольные наборы так,что Докажем ÎМ.Имеем:                                  т.к. все функции     монотонные и тем сильнее вектор                 не больше вектора               ,а функция f так же монотоннаÞ ÎМ

. Естественный порядок идемпотентного полукольца

На носителе идемп п/к S=(S,+, . , O, II) с помощью операции сложения п/к может быть введено отношение порядка, называемое естественным порядком идемп п/к: a<=bóa+b=b

Проверим, что таким образом действительно определено отношение порядка. Для этого нужно показать, что данное отношение рефлексивно, антисимметрично и транзитивно:

· Поскольку для любого х в силу идемпотентности сложения имеет место рав-во х+х=х, то имеем х<=x, т.е. введено отношение рефлексивно.

· Соотношения х<=y и y<=x означают х+у=у и у+х=х. Поскольку сложение коммутативно , то из этих равенств следует, что х=у =>антисим.

· x<=y и y<=z означают х+у=у и у+z=z =>x+z=x+(y+z) = (x+y)+z = y+z = z =>x<=zтранзитивно.

Значит отношение <= есть отношение порядка.

Теорема о точной верхней грани конечного подмножества идемпотентного п/к

Тео: Если А - конечное подмножество носителя идемпотентного п/к-ца, то supA относительно естественного порядка этого п/к равен сумме всех элементов м-ва А.

Д-во: Пусть А={a1…an}, и а=а1+…+аn. Для произвольного эл-та ai, i=1,n в силу коммут и идемп-ти сложения имеем: ai+a = ai+(а1+…+ai+…+аn) = a1+…+ai+ai+…an=a1+…+ai+…+an=a, т.е. ai<=a, т.е. a – есть верхняя грань множества А. Покажем, что это ТВГ.

Возьмём произвольную ВГ b м-ва А и рассмотрим сумму b+a. Т.к. для каждого i=1,n имеет место ai<=b, т.е. ai+b=b, то b+a = b + (а1+…+аn) = (b+a1) + (a2+…+an)=b+ a2+…+an=b =>a<=b и поэтому а – ТВГ м-ва А.