fl_task1 (1178876), страница 2

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

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

Çäåñü åñòü òîíêàÿ ëèíãâèñòè÷åñêàÿ ðàçL(A).Àâòîìàòíèöà, ñëîâà ïðèíèìàåò è ðàñïîçíà¼ò, êîíå÷íî ñõîæè, íî çà íèìè ñòîÿòðàçíûå îïðåäåëåíèÿ.5Î ðåøåíèè çàäà÷ß õî÷ó îòìåòèòü, ÷òî ïîäðåøåíèåì çàäà÷è ïîíèìàåòñÿ íå ïîëó÷å-íèå êîíå÷íîãî îòâåòà áåç ïîÿñíåíèé, à ïîñëåäîâàòåëüíîñòüîáîñíîâàííûõäåéñòâèé, ïðèâîäÿùèõ ê ïðàâèëüíîìó îòâåòó. Âñå äåéñòâèÿ è ïîñòðîåíèÿäîëæíû áûòü îáîñíîâàííûâñåãäà. ×àñòî ÿ áóäó àêöåíòèðîâàòü â óñëî-âèè âíèìàíèå íà òîì, ÷òî èìåííî íóæíî äîêàçàòü, íî ýòî íå îçíà÷àåò,÷òî åñëè â çàäà÷å íåò ôðàçû â äóõå ¾äîêàçàòü, ÷òî A = B¿, òî ìîæíîïèñàòü íå ïîäêðåïë¼ííûé äîâîäàìè ïîòîê ñîçíàíèÿ.Íå îáÿçàòåëüíî ðåøèòü âñå çàäà÷è, ïîýòîìó åñëè íå ïîëó÷àåòñÿ ÷òîòî ðåøèòü ñàìîñòîÿòåëüíî, íå íàäî ýòî ñóäîðîæíî ñïèñûâàòü.

Ëó÷øå ðåøèòü òî, ÷òî ïîëó÷àåòñÿ. Íå ñòðàøíî íå ðåøèòü ñòðàøíî ïîïàñòüñÿ íàñïèñûâàíèè. ß áóäó êëàñòåðèçîâàòü ðàáîòû ïî ãëóïîñòÿì. Ýòî íå îçíà÷àåò, ÷òî çàäà÷è íåëüçÿ îáñóæäàòü äðóã ñ äðóãîì. Åñëè êòî-òî ðàññêàçàëâàì èäåþ ðåøåíèÿ è âû äóìàåòå, ÷òî å¼ ïîíÿëè è ðåøèëè çàïèñàòü, òîóêàæèòå ññûëêó íà àâòîðà èäåè.6Çàäà÷è ïðåäáàçîâîãî óðîâíÿÇàäà÷à 1.1.{a, aa} · {b, bb} =?2.{a, aa} + {b, bb} =?3.{a, aa} × {b, bb} =?64.((aa|b)∗ (a|bb)∗ )∗ =?5.{a3n | n > 0} ∩ {a5n+1 |n > 0}∗ =?6.∅ ∩ {ε} =?7Çàäà÷è áàçîâîãî óðîâíÿÅñëè â çàäà÷å ÿâíî íå óêàçàí àëôàâèò, íî â òåêñòå óïîìÿíóòû ñèì-âîëûa, b (0, 1),òî àëôàâèò â ýòîé çàäà÷å ñîñòîèò èç ñèìâîëîâÇàäà÷à 2.

Çàïèñàòü ðåãóëÿðíîå âûðàæåíèå äëÿ ÿçûêàa, b (0, 1).L = Σ∗ \{(a|b)∗ ab(a|b)∗ }.Äîêàçàòü, ÷òî ÿçûê ïîðîæä¼ííûé ðåãóëÿðíûì âûðàæåíèåì ñîâïàäàåò ñL.Çàäà÷à 3.Àâòîìàò1q0A:q11 00Àâòîìàò01q2q010B:q10 00q21Äëÿ êàæäîãî àâòîìàòà îòâåòüòå íà ñëåäóþùèå âîïðîñû (1-2):1. Àâòîìàò çàäàí ÷åðåç ãðàô ïåðåõîäîâ. Çàïèøèòå îïðåäåëåíèå àâòîìàòàâ âèäå2.3.(Q, Σ, δ, q0 , F ).ßâëåòñÿ ëè àâòîìàò äåòåðìèíèðîâàííûì?Îïèøèòå ïîñëåäîâàòåëüíîñòü êîíôèãóðàöèé àâòîìàòàáîòêå ñëîâà4.Îïèøèòå ýëåìåíòû êàæäîãî ìíîæåñòâàw = 1101010.Âåðíî ëè, ÷òîÏðèíèìàåò ëè àâòîìàòBñëîâîïðè îáðà-v = 10001?5.

Óêàæèòå ïî îäíîìó ñëîâó, ïðèíàäëåæàùåìóñëîâó, íå ïðèíàäëåæàùååAw ∈ L(A)?L(A), L(B).íûìè.7Âñå4L(A), L(B)è ïî îäíîìóñëîâà äîëæíû áûòü ðàçëè÷-Çàäà÷à 4.Îïðåäåëèì ÿçûê(1)L ⊆ {a, b}∗èíäóêòèâíûìè ïðàâèëàìè:ε ∈ L;(2) âìåñòå ñ ëþáûì ñëîâîìx∈LâLòàêæå âõîäÿò ñëîâà(3) íèêàêèõ äðóãèõ ñëîâ â L íåò.∗ ÿçûê T ⊆ {a, b} âõîäèò ïóñòîå ñëîâîçàêàí÷èâàþùèåñÿ áóêâîéεxa, xaa, xabba;è ÂÑÅ íà÷èíàþùèåñÿ èa ñëîâà, â êîòîðûõ íåò ïîäñëîâ abaL = T.èëè bbb.Äîêàæèòå èëè îïðîâåðãíèòå, ÷òî1. Äîêàæèòå èëè îïðîâåðãíèòå, ÷òîL = T.Åñëè ðàâåíñòâî íåâåðíî, òîíóæíî ÿâíî óêàçàòü ñëîâî, ïðèíàäëåæàùåå îäíîìó ÿçûêó è íå ïðèíàäëåæàùåå äðóãîìó.

Åñëè ðàâåíñòâî âåðíî, òî íóæíî ïðîâåñòè äîêàçàòåëüñòâî ÏÎ ÈÍÄÓÊÖÈÈ:1)2)L ⊆ T;T ⊆ L.T . Äîêàæèòå (ïî èíäóêÿçûê T .2. Ïîñòðîéòå êîíå÷íûé àâòîìàò, ðàñïîçíàþùèéöèè), ÷òî ïîñòðîåííûé àâòîìàò ðàñïîçíà¼ò8Áëàãîäàðíîñòèß õîòåë áû ïîáëàãîäàðèòü Ñåðãåÿ Òàðàñîâà çà ïðåäîñòàâëåíèå ñâîèõìàòåðèàëîâ è çàäà÷, ÷àñòü èç êîòîðûõ ÿ èñïîëüçîâàë ïðè ïîäãîòîâêå ýòèõçàäàíèé.

Òàêæå ÿ õî÷ó ïîáëàãîäàðèòü Äìèòðèÿ Ãîí÷àðà çà èñïðàâëåíèåîïå÷àòîê è ðåêîìåíäàöèè ïî ïðàâêå ïðåäûäóùåé âåðñèè ýòîãî çàäàíèÿ.8.

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

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