А.Б. Угольников - Лекции по дискретной математике (1083729), страница 12

Просмтор этого файла доступен только зарегистрированным пользователям. Но у нас супер быстрая регистрация: достаточно только электронной почты!

Текст из файла (страница 12)

 ÷àñòíîñòè R1 = {Q}, R2 6= {Q}. Ò.å. ëþáûå äâà ñîñòîÿíèÿ 1-ýêâèâàëåíòíû,Rk ,òîíî ñóùåñòâóþò 2 ñîñòîÿíèÿ íå 2-ýêâèâàëåíòíûõ. 1-ýêâèâàëåíòíîñòü ëþáûõ äâóõ ñîñòîÿíèé îçíà÷àåò,÷òî ðàáîòà àâòîìàòà íå çàâèñèò îò òîãî, â êàêîì ñîñòîÿíèè îí íàõîäèòñÿ (F (a, qi )ëþáûõqi , qj ∈ Q, a ∈ A).= F (a, qj )äëÿÍî ýòî îçíà÷àåò, ÷òî ëþáûå äâà ñîñòîÿíèÿ ïðîñòî ýêâèâàëåíòíû ïðîòèâîðå÷èå ñ ñóùåñòâîâàíèåì 2-íåýêâèâàëåíòíûõ ñîñòîÿíèé.Òåîðåìà äîêàçàíà.Èçâëå÷¼ì èç ïðåäûäóùåé òåîðåìû êðèòåðèé ýêâèâàëåíòíîñòè äâóõ àâòîìàòîâ.Òåîðåìà.

Ïóñòü äàíû äâà êîíå÷íûõ àâòîìàòà:V = (A, B, Q, F, G)V 0 = (A, B, Q0 , F 0 , G0 )|Q| = n, |Q0 | = n0Òîãäà äëÿ ëþáûõ q ∈ Q, q 0 ∈ Q0 ñïðàâåäëèâî ñëåäóþùåå óòâåðæäåíèå:q ∼ q0 ⇔ qÄîêàçàòåëüñòâî.n+n0 −1∼q0Ïîñòðîèì "îáúåäèí¼ííûé" êîíå÷íûé àâòîìàò:V̂ = (A, B, Q̂, F̂ , Ĝ)ãäåQ̂ = Q ∪ Q0F (a, q̂), q̂ ∈ QF̂ (a, q̂) =F 0 (a, q̂), q̂ ∈ Q0G(a, q̂), q̂ ∈ QĜ(a, q̂) =G0 (a, q̂), q̂ ∈ Q0Äëÿ àâòîìàòàV̂óòâåðæäåíèå òåîðåìû ñîâïàäàåò ñ óòâåðæäåíèåì òåîðåìû Ìóðà.Ñîêðàù¼ííûì àâòîìàòîì äëÿ äàííîãî àâòîìàòà V = (A, B, Q, F, G) íàçûâàåòñÿ òàêîé àâòîìàòV̂ = (A, B, Q̂, F̂ , Ĝ), ÷òî V̂ ∼ V è ñðåäè âñåõ àâòîìàòîâ ýêâèâàëåíòíûõ V V̂ èìååò íàèìåíüøåå00êîëè÷åñòâî ñîñòîÿíèé, ò.å. äëÿ ëþáûõ q, q ∈ Q̂ âûïîëíåíî q 6∼ q .Äëÿ ïîñòðîåíèÿ ñîêðàù¼ííîãî àâòîìàòà íåîáõîäèìî ïîñòðîèòü ïîñëåäîâàòåëüíîñòü ìíîæåñòâRk = {Qk1 , ..., Qkrk } (ñì. äîêàçàòåëüñòâî òåîðåìû Ìóðà) è íàéòè íàèìåíüøåå k, òàêîå ÷òî Rk = Rk+1 .0k0 äîêàçàòåëüñòâå òåîðåìû Ìóðà îòìå÷àëîñü, ÷òî äëÿ òàêîãî k q, q ∈ Qi âëå÷¼ò q ∼ q .

ÇàòåìâûáèðàåìQ̂ = {q1 , ..., qrk }ãäåqi ïðîèçâîëüíîå èçQki .ÏîëîæèìF̂ (a, qi ) = F (a, qi )Ĝ(a, qi ) = qjãäåqj ∈ Q̂èqj ∼ G(a, qi ).63.

Характеристики

Список файлов лекций