Теорема о связи между отношением эквивалентности и разбиением множества.

Фор-ка:для любого класса эквивалентости на мн-ве А множество классов эквивалентности образует разбиение множества А.Обратно,любое разбиение мн-ва А задает на нем отношение эквив совпадают с эл-ми разбиения.До-во:покажем.что отношение эквив. Р на мн-ве определяет некоторое разбиение этого мн-ва.Убедимся вначале,что любые 2 класса эквив. По отношению р либо пересек,либо совпад.Пусть 2 класа эквиви. р и р имеют общий элемент zpx ,zpy.В силу симметричности отношения р имеем xpz, и тогда xpz ,ypz.В силу транзитивности отн-ния р получим xpy.Пусть hÎ р, тогда hpx т.к.xpy,то hpyÞhÎ р. Обратно,если hÎ р,то в силу сим-ти рполучим hpy,ypx и в силу транз-ти- hpx,т.е hÎ р. Таким образом р= р.Итак, любые два не совпадающих класса эквив-ти не пересек. Т.к. для "xÎA справедливо х Î р(поскольку хрх) ,т.е. каждый элемент мн-ва АÎ некоторому классу экв-ти по отн. ,то мно-во всех классов экв-ти по отношению р образует разьиение исходного мн-ва А.Таким образом,любое отношение экв-ти однозначно определяет некоторое разбиение.Теперь -некоторое разбиение мн-ва А.Рассмотрим отношение р,такое ,что xpy имеет местоÛ,когда хи уÎодному и тому же эл-ту ,данного разбиения: xpyÛ($iÎI) (xÎBi) Ù(yÎBi)/.Очевидно, что введенное отношение рефл. и симм..Если для "х,у,z имеет место xpy и ypz, то x,y,z в силу отношения p принадлежат одному и тому же эл-ту Bi разбиенияÞ,хpz и отношение pтранзитивно.Таким образом,р- эквив-ть А.Терема позволяет отождествлять отношения эквивалентности и разбиения: любая эквивалентность опр. Единственное разбиение и наоборот.

Транзитивность-БО р на мн-ве А наз. транз-тью,если для " х,у,zÎА из того,что хру и урzÞxpz.

Симметричность-,если для " х,у,zÎА из xpyÞ урх

Эквивалентность-рефликсивно,сим-но,тран-но.

Рефликсивность-если на мн-ве А содержится в p:idyÍp,т.е xpx для "x

мн-ваА."xÎA(x,x)Îp.

Пусть А- произ. мн-во.Сем-во  непустых и папарно не пересек. Мн-в назыв разбиением мн-ва А,если объединение мн-в см-ва Bi равно равно АÈiÎIВ=А

Детерминизация конечных автоматов. Теорема о детерминизации. Алгоритм детерминизации.

Т-ма: для любого КА мб построен эквивалентный ему детерминированный КА.

Алгоритм: 1) удаление дуг с меткой Л, 2) собственно детерминизация

Удаление Л-переходов: чтобы перейти от исходного КА М=(V,Q,q0,F,б) к эквивалентному ему М’=(V,Q’,q0,F’,б’) без Л-переходов достаточно в исходном графе М проделать следующие преобразования:

А) все состояния кроме начального, в которые входят дуги с меткой Л, удаляются. Тем самым определяется множество Q’ конечного автомата М’. Понятно, что Q’ входит в Q. При этом, полагаем, что начальное состояние остаётся прежним.

Б) Множество дуг КА М’ и их меток опред так: для любых двух состояний p,r э Q’ ->ar имеет место титт, когда a э V, а в графе М имеет место одно из двух: либо существует дуга из р в r, метка которой содержит а, либо существует такое состояние q, что р=>+л q и q->ar. При этом вершина q может и не принадлежать множеству Q’, т.е. она может и исчезнуть при переходе к автомату М’. Если же q э Q’, то, естественно, в М’ сохранится дуга (p,r), и символ а будет одним из символов, принадлежащих метке этой дуги.

В) множество заключительных состояний F’ KAM’ содержит все состояния q э Q’, т.е. состояния КА М, не удаляемые согласну п. А), для которых имеет место q->*л qf для некоторого qf, принадлежащего f (т.е. либо состояние q само является заключительным состоянием КА М, либо из него ведёт путь ненулевой длины по дугам с меткой Л в одно из заключительных состояний КА М.

2. Детерминизация: Пусть М=(V,Q,q0,F,б) – КА без Л-переходов. Построим эквивалентный М детерминированный КА М1. Этот КА определяется таким образом, что его множество состояний есть множество всех подмножеств множества состояний КА М. Это значит, что каждое отдельное состояние КА М1 определено как некоторое подмножество множества состояний КА М. При этом, начальным состоянием нового КА является одноэлементное подмножество, содержащее нач сос старого КА. А заключительными состояниями нового КА являются все такие подмножества Q, которые содержат хотя бы одну заключительную вершину исходного КА М.

Функция переходов нового КА определяется так, что из состояния множества S по входному символу а КА М1 переходит в состояние-множество, представляющее собой объединение всех множеств состояний старого КА, в которые этот старый КА переходит по символу а из каждого состояния множества S. Таким образом, КА М1 является детерминизированным по построению.

Теор: Дополнение регулярного языка есть регулярный язык.

Д-во: Пусть L-ря в алфавите v.Тогда дополнение языка L(как мн-ва слов) есть язык I=V*/L.

Согласно торемы о детерминизации для L может быть построен детерминизированным КА М, допускаемый L.Поскольку в детерминизированном автомате из каждой вершины по каждому входному символу определен переход в точности в одну вершину, то какова бы не была цепочка х в алфавите V для нее найдется единственный путь в М,нач. в начальном состоянии,на которой читается цепочка Х. Ясно ,что цепочка Х допускается автоматом М, т.е. хÎL(M),Ûпоследнее состояние указанного пути явл. заключительным. ОтсюдаÞ,что цепочка хÏL(M)Ûкогда последнее состояние указанного пути не заключ.

Но наш как раз и нужен КА М,который допускает исходный исходный КА МÞ превращая каждое заключительное состояние М в незаключетельное и наоборот, получим детерминизированный автомат,допускаемый дополнение языка L.

Замкнутое полукольцо.Непрерывность операции сложения в замнкутом полукольце.Теорема о наименьшем решении линейного уравнения х=ах+b в замкнутом п/к.

Замкнутое п/к-$=(S,+,.,0,1I):

1)оно идемпотентно

2)любая посл-ть эл-тов мн-ва S имеет т.в.г.относительно естественного порядка £ этого идемпотентного п/к. ,x_iÎSsup £)

3)операция «.» сохраняет т.в.г. последовательности

" nÎN

a sup = sup

sup = sup

Теорема:" конечное идемпотентное п/к замкнуто

Док-во: поскольку носитель S идемп. п/к S=(S,+,.,0,1I) есть конечное множество,то множество эл-ов " последовательности в этом п/к конечно.Для нахождения точной верхней грани такой последовательности нужно найти точную верхнюю грань мн-ва р=  ее членов,т.е. согласно теор.,вычислить некоторую конечную сумму, которая всегда $.Таким образом, в кот.

идемпотентном п/к " последовательность имеет т.в.г.

Условия хранения точных верхних граней имеют вид

a(p₁+…p_n)=ap₁ +…+ap_n

(p₁+…+p_n)*a=p₁a+…+p_na ýÞS-п/кзамкнуто

Полное множество булевых функций. Теорема о доказательстве полноты множества

путем представления его элементов формулами над полным множеством.

М-во БФ назполным, если любая БФ в нём мб представлена ф-лой над ним.

Т-ма: Пусть F – полн м-во БФ. Если любая функция из F мб представлена формулой над м-вом G, то м-воG также полное.

Д-во: Пусть для люб f э Ff(x1…xn)=псиG(x1…xn) (мб предст как)

1. Пусть фи – некот ф-ла над F. Фи=х =>y будет формулой и над G.

2. Фи=с э F (пусть фи – некоторая константа из множества F, если она нам существует)

Тогда по предположению существует G.

3. Пусть над м-вом F построена f(Ф1…Фn), где Фi – некоторая ф-ла над F.

Согласно индуктивному предположению над каждой Фi существует эквивалентная ей ф-ла тетаi над множеством G. Тогда f(Ф1…Фn)=f(тета1…тетаn)=псиG. Поскольку в силу полноты любая БФ может быть представлена формулой над F, то эта же БФ мб представлена ф-лой над G.