Задачи по теме Конечные автоматы без выхода (1124123)
Текст из файла
ÇÀÄÀ×È ÏÎ ÀÂÒÎÌÀÒÀÌ-ÐÀÑÏÎÇÍÀÂÀÒÅËßÌ1. Ïîñòðîèòü äèàãðàììû Ìóðà äëÿ àâòîìàòîâ â àëôàâèòå{0, 1},êî-òîðûå äîïóñêàþò ñëåäóþùèå ìíîæåñòâà:∗a) âñå ñëîâà èç ìíîæåñòâà {0, 1} \ {0, 1, Λ},b){0, 10},c) âñå ñëîâà äëèíû 3,d) âñå ñëîâà, êîòîðûå íà÷èíàþòñÿ ñëîâîì 01,e) âñå ñëîâà, êîòîðûå îêàí÷èâàþòñÿ ñëîâîì 00,f ) âñå ñëîâà, êîòîðûå ñîäåðæàò ñëîâî 110.2. Äîêàçàòü êîíå÷íóþ àâòîìàòíîñòü ñëåäóþùèõ ìíîæåñòâ:a) ëþáîå êîíå÷íîå ìíîæåñòâî â àëôàâèòå A = {a1 , . . . , am };∗b) ëþáîå ìíîæåñòâî âèäà A \ X , ãäå X êîíå÷íîå ìíîæåñòâî ñëîââ àëôàâèòåA;d) ìíîæåñòâî âñåõ ñëîâ âani ,1 ≤ i ≤ m;àëôàâèòå {0, 1}, êîòîðûåc) ìíîæåñòâî âñåõ ñëîâ âèäàãäåèìåþò ÷åòíóþäëèíó, íà÷èíàþòñÿ áóêâîé 0 è â êîòîðûõ áóêâû 0 è 1 ÷åðåäóþòñÿ;e) ìíîæåñòâî âñåõ ñëîâ â àëôàâèòå{0, 1}, êîòîðûå ñîñòàâëåíû èç ½áëî-êîâ 010 è 001.3. Ïîñòðîèâ íà ìíîæåñòâå{0, 1}∗ïîäõîäÿùèå ïðàâîèíâàðèàíòíûå îò-íîøåíèÿ ýêâèâàëåíòíîñòè êîíå÷íîãî èíäåêñà, äîêàçàòü êîíå÷íóþ àâòîìàòíîñòü ñëåäóþùèõ ìíîæåñòâ:{Λ};{0};c) {Λ, 0, 1};nd) {0 1 : n = 0, 1, .
. .}.a)b)4. Äëÿ ëþáîãîn≥2îïðåäåëèòü íà ìíîæåñòâåàíòíóþ ýêâèâàëåíòíîñòü èíäåêñà{0, 1}∗ïðàâîèíâàðè-n.5. Ïî àíàëîãèè ñ ïðàâîèíâàðèàíòíîé ýêâèâàëåíòíîñòüþ îïðåäåëèì∗íà ìíîæåñòâå A ëåâîèíâàðèàíòíóþ ýêâèâàëåíòíîñòü: åñëè ā ∼ b̄ è c̄ ∗ïðîèçâîëüíîå ñëîâî èç A , òî c̄ā ∼ c̄b̄.Áóäåò ëè äëÿ ëåâîèíâàðèàíòíîé ýêâèâàëåíòíîñòè ñïðàâåäëèâ àíàëîãòåîðåìû 2 èç ëåêöèé (î ïðåäñòàâëåíèè ïðîèçâîëüíîãî êîíå÷íî-àâòîìàòíîãî ìíîæåñòâà â âèäå îáúåäèíåíèÿ íåêîòîðîãî êîëè÷åñòâà êëàññîâ ëåâîèíâàðèàíòíîãî îòíîøåíèÿ ýêâèâàëåíòíîñòè êîíå÷íîãî èíäåêñà)?16. Îïðåäåëèì îïåðàöèþ2Xãðàäóèðîâàííîãî âîçâåäåíèÿ â êâàäðàò.2Äëÿ ïðîèçâîëüíîãî ìíîæåñòâà ñëîâ X ìíîæåñòâî X ñîñòîèò èç âñåõñëîâ âèäàāā,ãäåā ∈ X .Ñîõðàíÿåò ëè ââåäåííàÿ îïåðàöèþ êîíå÷íóþ àâòîìàòíîñòü ìíîæåñòâ?7.
Äîêàçàòü çàìêíóòîñòü êëàññà êîíå÷íî-àâòîìàòíûõ ìíîæåñòâ îòíîñèòåëüíî îïåðàöèé îáúåäèíåíèÿ è ïåðåñå÷åíèÿ, èñïîëüçóÿ îïåðàöèþïðÿìîãî ïðîèçâåäåíèÿ àâòîìàòîâ.8. Êàêèå ìíîæåñòâà äîïóñêàþò ñëåäóþùèå íåäåòåðìèíèðîâàííûå àâòîìàòû (ïðåäâàðèòåëüíî ïîñòðîèòü äëÿ íèõ äèàãðàììû Ìóðà):Q = {q1 , q2 }, f (0, q1 ) = {q1 , q2 }, f (1, q1 ) = {q2 }, f (0, q2 ) = {q2 },f (1, q2 ) = {q1 , q2 }, F = {q2 } è F = {q1 }.b) Q = {q1 , q2 , q3 }, f (0, q1 ) = {q2 }, f (1, q1 ) = {q1 , q2 }, f (0, q2 ) = {q3 },f (1, q2 ) = {q3 }, f (0, q3 ) = {q3 }, f (1, q3 ) = {q2 , q3 }, F = {q3 }.c) Q = {q1 , q2 , q3 }, f (0, q1 ) = {q1 , q2 }, f (1, q1 ) = {q1 }, f (0, q2 ) = {q2 },f (1, q2 ) = {q2 , q3 }, f (0, q3 ) = {q1 , q3 }, f (1, q3 ) = {q1 , q3 }, F = {q3 }.a)9.
Äëÿ çàäàííûõ íåäåòåðìèíèðîâàííûõ àâòîìàòîâ ìåòîäîì äåòåðìèíèçàöèè ïîñòðîèòü ýêâèâàëåíòíûé äåòåðìèíèðîâàííûé àâòîìàò (äîïóñêàþùèé òî æå ñàìîå ìíîæåñòâî ñëîâ):a) çàäà÷à 8à, îáà ñëó÷àÿ;b) Q = {q1 , q2 }, f (0, q1 ) = {q1 }, f (1, q1 ) = {q1 , q2 }, f (0, q2 ) = {q1 , q2 },f (1, q2 ) = {q1 }, F = {q2 }.c) çàäà÷à 8b.10. Îòïðàâëÿÿñü îò ìíîæåñòâ{0}è{1},ïîñòðîèòü ñ ïîìîùüþ îïå-ðàöèé îáúåäèíåíèÿ, ïðîèçâåäåíèÿ è èòåðàöèè ìíîæåñòâî âñåõ ñëîâ â àëôàâèòå{0, 1},êîòîðûå ñîäåðæàò ïîäñëîâî 0001.ā ñëîâî â àëôàâèòå A = {a1 , . .
. , am }. Ñêîëüêî ðàç íóæíî∗ïðèìåíèòü îïåðàöèþ èòåðàöèè, ÷òîáû ïîëó÷èòü ìíîæåñòâî A \ {ā} èçìíîæåñòâ {a1 }, . . . , {am } ñ ïîìîùüþ îïåðàöèé îáúåäèíåíèÿ, ïðîèçâåäå11. Ïóñòüíèÿ è èòåðàöèè?12. Ïóñòü ìíîæåñòâî X ñîñòîèò èç n ñëîâ. Ìîæåò ëè ìíîæåñòâî X · X22ñîäåðæàòü n ñëîâ? ìåíüøå, ÷åì n ñëîâ? ìåíüøå, ÷åì n ñëîâ? Ïðèâåñòèïðèìåðû.13. Äîêàçàòü ðåãóëÿðíîñòü ñëåäóþùèõ ìíîæåñòâ ñëîâ â àëôàâèòå{0, 1}:2a) ëþáîå êîíå÷íîå ìíîæåñòâî ñëîâ;∗b) äîïîëíåíèå (äî ìíîæåñòâà {0, 1} ) ê ëþáîìó êîíå÷íîìó ìíîæåñòâóñëîâ;c) ìíîæåñòâî âñåõ ñëîâ, ïðåäñòàâèìûõ â âèäå ïðîèçâåäåíèÿ çàäàííûõñëîâā1 , .
. . , ān ;d) ìíîæåñòâî âñåõ ñëîâ, ñîäåðæàùèõ â êà÷åñòâå ïîäñëîâà îäíî èç ñëîâā1 , . . . , ān ;e) ìíîæåñòâî âñåõ ñëîâ, êîòîðûå íå ñîäåðæàò íè îäíî èç çàäàííûõñëîâā1 , . . . , ān ;f ) ìíîæåñòâî âñåõ ñëîâ, äëèíû êîòîðûõ èìåþò âèä14. Äëÿ àâòîìàòîâAèB5k + 1 èëè 5k + 3.ïîñòðîèòü (íåäåòåðìèíèðîâàííûé) àâòîìàò,D(A) · D(B):a) àâòîìàò A:Q = {q1 , q2 , q3 }, f (0, q1 ) = q2 , f (1, q1 ) = q1 , f (0, q2 ) = q2 ,f (1, q2 ) = q3 , f (0, q3 ) = q1 , f (1, q3 ) = q3 , F = {q1 , q3 },àâòîìàò B :Q = {q1 , q2 }, f (0, q1 ) = q1 , f (1, q1 ) = q2 , f (0, q2 ) = q2 ,f (1, q2 ) = q2 , F = {q2 };b) àâòîìàò A:Q = {q1 , q2 }, f (0, q1 ) = q1 , f (1, q1 ) = q2 , f (0, q2 ) = q1 ,f (1, q2 ) = q2 , F = {q2 };àâòîìàò B :Q = {q1 , q2 , q3 }, f (0, q1 ) = q2 , f (1, q1 ) = q3 , f (0, q2 ) = q2 ,f (1, q2 ) = q2 , f (0, q3 ) = q3 , f (1, q3 ) = q1 , F = {q2 , q3 }.êîòîðûé äîïóñêàåò ìíîæåñòâîA ïîñòðîèòü∗êîòîðîãî D(C) = D(A) :a) àâòîìàò A èç çàäà÷è 14a;b) àâòîìàò B èç çàäà÷è 14b.15.
Äëÿ àâòîìàòàX . . . , am }, ā1 , . . . , ām16. Ïóñòü(íåäåòåðìèíèðîâàííûé) àâòîìàòêîíå÷íî-àâòîìàòíîå ìíîæåñòâî â àëôàâèòå ïðîèçâîëüíûå ñëîâà â àëôàâèòåðåçóëüòàòå îäíîâðåìåííîé çàìåíû áóêââñåõ ñëîâàõ ìíîæåñòâà17. ÏóñòüXXa1 , . . . , a mC,óA = {a1 ,A. Äîêàçàòü, ÷òî âā1 , . .
. , ām âîñëîâàìèîáðàçóåòñÿ êîíå÷íî-àâòîìàòíîå ìíîæåñòâî. êîíå÷íî-àâòîìàòíîå ìíîæåñòâî â àëôàâèòåA, Yêîíå÷íî-àâòîìàòíîå ìíîæåñòâî â îäíîáóêâåííîì àëôàâèòå. Îáîçíà÷èì÷åðåçX/Yìíîæåñòâî âñåõ òåõ ñëîâ èçäëèíàìè ñëîâ èç18. ÏóñòüXY.X,Äîêàçàòü, ÷òî ìíîæåñòâîäëèíû êîòîðûõ ÿâëÿþòñÿX/Yêîíå÷íî-àâòîìàòíî. êîíå÷íî-àâòîìàòíîå ìíîæåñòâî, Rev(X) ìíîæåñòâîâñåõ ñëîâ, îáðàòíûõ ê ñëîâàì èçX(ò.å. ñëîâ, ïðî÷èòàííûõ ñïðàâà íàëå-âî). Äîêàçàòü, ÷òî ìíîæåñòâî Rev(X) êîíå÷íî-àâòîìàòíî.3.
Характеристики
Тип файла PDF
PDF-формат наиболее широко используется для просмотра любого типа файлов на любом устройстве. В него можно сохранить документ, таблицы, презентацию, текст, чертежи, вычисления, графики и всё остальное, что можно показать на экране любого устройства. Именно его лучше всего использовать для печати.
Например, если Вам нужно распечатать чертёж из автокада, Вы сохраните чертёж на флешку, но будет ли автокад в пункте печати? А если будет, то нужная версия с нужными библиотеками? Именно для этого и нужен формат PDF - в нём точно будет показано верно вне зависимости от того, в какой программе создали PDF-файл и есть ли нужная программа для его просмотра.
![](https://s.studizba.com/z.php?f=/templates/si/i/noavatar.png&w=100&h=100&t=1"){kind=avatar}
