Iv_task5 (1178896), страница 2

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

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

Ïîìåíÿåì íàïðàâëåíèå ñòðåëîê. Áûâøåå íà÷àëüíîå ñîñòîÿíèå ñòàíîâèòñÿ ïðèíèìàþùèì, áûâøèå ïðèíèìàþùèå ïåðåñòàþò èìè áûòü. Äîáàâëÿåòñÿ íà÷àëüíàÿ âåðøèíà,ε-ïåðåõîäû èç êîòîðîé âåäóò ê áûâøèì ïðèíèìàþùèì âåðøèíàì.62a3aaab1b4bbb bbb85aaa7a6εεεε9Òåïåðü ïîñòðîèì ïî íåìó ÄÊÀ.7ε{9, 8, 7, 6, 5, 4}ab{6, 5, 4, 3, 2, 1}{5, 4, 3, 2, 1}a{8, 7, 6, 5, 4, 3}bbbabb{7, 6, 5, 4, 3, 2, 1}ba{8, 7, 6, 5, 4}{8, 7, 6, 5, 4, 3, 2}aa{8, 7, 6, 5, 4, 3, 2, 1}a, bÎáîçíà÷èì âåðøèíû ïî-íîâîìó8a0ab31abab bb4b6a b2a7aa5a, bÌèíèìèçèðóåì äàííûé ïîëíûé àâòîìàò:a{1, 3, 4, 5|0, 2, 6, 7} −→ {1, 3, 4, 5|0, 2|6|7}b{1, 3, 4, 5|0, 2|6|7} →− {1, 3, 4|5|0, 2|6|7}b{1, 3, 4|5|0, 2|6|7} →− {1, 3|4|5|0, 2|6|7}b{1, 3|4|5|0, 2|6|7} →− {1|3|4|5|0, 2|6|7}a,b{1|3|4|5|0, 2|6|7} −−→ {1|3|4|5|0, 2|6|7}Òîãäà ìèíèìèçèðîâàííûé ïîëíûé àâòîìàò:9(5)0bb31aa4abb6aba5a7a, b äàííîì àâòîìàòå íåò òóïèêîâ, òî åñòü îí ÿâëÿåòñÿ ìèíèìàëüíûì.Çàäà÷à 5Íå âåðíî, êîíòðïðèìåð:Σ = {0}2L = {0n |n > 1}L̄ · L̄ = L0 ≡ 0∗(6)L íåðåãóëÿðåí, ïî äîêàçàííîé çàäà÷å èç ïðåäûäóùåé äîìàøíåé ðàáîòû.

Äîïîëíåíèå íåðåãóëÿðíîãî ÿçûêà íåðåãóëÿðíûé ÿçûê, òàê êàê â ïðîòèâíîì ñëó÷àå äîïîëíåíèå äîïîëíåíèÿáûë áû ðåãóëÿðíûì, ÷òî íåâåðíî.Äîêàæåì, ÷òî êîíêîòåíàöèÿ äîïîëíåíèé ñîâïàäàåò ñî âñåì ìíîæåñòâîì ñëîâ ÿçûêà.Èìååì, ÷òî {ε, 0, 00} ⊂ L, òàê êàê èõ ñòåïåíè íóëÿ, ñîîòâåòñòâåííî 0 è 1, íå ÿâëÿþòñÿêâàäðàòàìè íàòóðàëüíîãî ÷èñëà áîëüøåãî åäèíèöû.

Èìååì, ÷òî {ε, 0, 00} ⊂ L0 .∀n > 2∃n = a + b : a, b íå êâàäðàòû íàòóðàëüíûõ ÷èñåë áîëüøèõ åäèíèöû. Ýòî ñëåäóåò èçòîãî, ÷òî n = 1 + (n − 1) = 2 + (n − 2), ãäå 1,2 êâàäðàòû è îäíî èç ÷èñåë n − 1 èëè n − 2íå ÿâëÿåòñÿ êâàäðàòîì, òàê êàê ∀x2 , y 2 : x, y > 1, |x2 − y 2 | > 1.Èç ïðåäûäóùèõ äâóõ ïàðàãðàôîâ ñëåäóåò, ÷òî ∀n > 0∃0a 0b : a, b > 0, a, b íå êâàäðàòûíàòóðàëüíûõ ÷èñåë áîëüøå åäèíèöû.

Èç ýòîãî ñëåäóåò, ÷òî 0∗ ñîäåðæèòñÿ â êîíêàòåíàöèèäîïîëíåíèé. Îáðàòíîå óòâåðæäåíèå òàêæå âåðíî, òàê êàê 0∗ ìíîæåñòâî âñåõ ñëîâ äàííîãîàëôàâèòà.10Òàêèì îáðàçîì, ìû ïðèâåëè êîíòðïðèìåð, òî åñòü óòâåðæäåíèå çàäà÷è íå âåðíî.Çàäà÷à 6Íåâåðíî, òàê êàê R, êîòîðûé ÿâëÿåòñÿ êîíå÷íûì ÿçûêîì, ÿâëÿåòñÿ ðåãóëÿðíûì, ÷òî ñëåäóåò èç òîãî, ÷òî îí ìîæåò áûòü ïîñòðîåí êîíå÷íûì îáúåäèíåíèåì ñëîâ, êàæäîå èç êîòîðûõÿâëÿåòñÿ êîíå÷íîé êîíêàòåíàöèåé áóêâ, ÷òî ïðÿìî îçíà÷àåò, ÷òî ÿçûê R ìîæåò áûòü ïîñòðîåí ïî îïðåäåëåíèþ ðåãóëÿðíûõ ÿçûêîâ, òî åñòü ÿâëÿåòñÿ ðåãóëÿðíûì.Ïóñòü L1 ðåãóëÿðåí, òîãäà L1 ∪ R ðåãóëÿðíî, ÷òî áûëî äîêàçàíî ðàíåå.

Îäíàêî L íåðåãóëÿðåí, èç ÷åãî ñëåäóåò íåðåãëÿðíîñòü L1 .11.

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

Список файлов курсовой работы