fl_task1 (1178876)
Текст из файла
Çàäàíèå 1Ðåãóëÿðíûå ÿçûêè è àâòîìàòûËèòåðàòóðà:1.Õîïêðîôò Ä., Ìîòâàíè Ð., Óëüìàí Ä.Ââåäåíèå â òåîðèþ àâòîìàòîâ, ÿçûêîâ è âû÷èñëåíèé.Ì.: Âèëüÿìñ, 2002.2.Àõî À., Óëüìàí Ä.Òåîðèÿ ñèíòàêñè÷åñêîãî àíàëèçà, ïåðåâîäà è êîìïèëÿöèèÌ.: Ìèð, 1978. Ãë. 0, 2.3.Ñåðåáðÿêîâ Â.À., Ãàëî÷êèí Ì.Ï., Ãîí÷àð Ä.Ð., Ôóðóãÿí Ì.Ã.Òåîðèÿ è ðåàëèçàöèÿ ÿçûêîâ ïðîãðàììèðîâàíèÿ.Ì.: ÌÇ-ïðåññ, 2006.Êëþ÷åâûå ñëîâà1:ïðèíöèïìàò.
èíäóêöèè, ÿçûê, ðåãóëÿðíûå âû-ðàæåíèÿ, êîíêàòåíàöèÿ, îáúåäèíåíèå, èòåðàöèÿ, êîíå÷íûå àâòîìàòû(ÊÀ), äåòåðìèíèðîâàííûå è íåäåòåðìèíèðîâàííûå ÊÀ, ðåãóëÿðíûå ÿçûêè.1TEX ýòîì ãîäó âñå çàäàíèÿ ïðèíèìàþòñÿ òîëüêî â ôîðìàòåTEX.Âî-ïåðâûõ, ÷åðåç ïàðó ëåò âàì óæå ïðåäñòîèò íàïèñàíèå äèïëîìà è áîëüøèíñòâî äèïëîìîâ òàê èëè èíà÷å ñâÿçàíû ñ ìàòåìàòèêîé, è óæ òî÷íîâ ïîäàâëÿþùåì áîëüøèíñòâå èç íèõ ïðèñóòñòâóþò ôîðìóëû.TEX äî-âîëüíî ãèáêèé èíñòðóìåíò äëÿ ðàáîòû ñ ìàòåìàòè÷åñêèìè òåêñòàìè, îíÿâëÿåòñÿ ñòàíäàðòîì äëÿ ïóáëèêàöèé â êðóïíûõ æóðíàëàõ, íå çàâèñèòîò ïëàòôîðìû è ñ íèì äîâîëüíî óäîáíî ðàáîòàòü. Äàæå â ïåðåïèñêàõâ ñåòè, óæå ïðèíÿòî çàïèñûâàòü ìàòåìàòè÷åñêèå ôîðìóëû â ñòèëå òåõàè áîëüøèíñòâî ïðîôèëüíûõ ñàéòîâ ïîääåðæèâàþò êîíâåðòàöèþ íà ëåòó èç òåõà â ôîðìóëû.
ß áóäó ïðåäîñòàâëÿòü òåõîâñêèå èñõîäíèêè êîâñåì çàäàíèÿì. Âî-âòîðûõ, â ýòîì ãîäó ÿ ïëàíèðóþ ÷àñòè÷íî àâòîìàòèçèðîâàòü ïðîöåññ ïðè¼ìà çàäàíèÿ, ïîýòîìó, åñëè ïëàíû ñáóäóòñÿ, òî ñ1 ìèíèìàëüíûé íåîáõîäèìûé îáú¼ì ïîíÿòèé è íàâûêîâ ïî ýòîìó ðàçäåëó)1îïðåäåë¼ííîãî ìîìåíòà ñäàâàòü çàäàíèÿ â òåõå ïðèä¼òñÿ ïî òåõíè÷åñêèìïðè÷èíàì. êà÷åñòâå ëèòåðàòóðû ïî òåõó, ÿ ðåêîìåíäóþ êíèãó Ëüâîâñêîãî èñòàòüþ ñ íàáîðîì ïðèìåðîâ Âîðîíöîâà è wiki-ó÷åáíèê. Òàê æå ÿ íàø¼ëâèäåîóðîêè, âîçìîæíî îíè îêàæóòñÿ ïîëåçíû.Òåõîì ïîëüçóåòñÿ ñòîëüêî ëþäåé, ÷òî ïðàêòè÷åñêè âñå ïîòðåáíîñòè,êîòîðûå âîçíèêàþò â ïðîöåññå íàïèñàíèÿ íàó÷íûõ òåêñòîâ, óæå óäîâëåòâîðåíû. Íàïðèìåð, äëÿ ïîñòðîåíèÿ ãðàôîâ àâòîìàòîâ åñòü ìíîæåñòâîïàêåòîâ.
ß ïðåäïî÷èòàþ ïàêåòtikz. Äîêóìåíòàöèÿ ê ýòîìó ïàêåòó íàõî-äèòñÿ çäåñü. êà÷åñòâå ðåäàêòîðà, ÿ ðåêîìåíäóþ èñïîëüçîâàòü Texmaker. Ýòî äîâîëüíî óäîáíûé êðîññïëàòôîðìåííûé ðåäàêòîð.2Î çàäàíèÿõÇàäàíèÿ ñäàþòñÿ åæåíåäåëüíî, ñäàòü çàäàíèå íàäî äî 22:59 ñðåäû. Èñ-õîäíèêè òåõà è pdf ñ çàäàíèåì íóæíî ïðèñûëàòü ïî àäðåñó homework@rubtsov.su,åñëè íà ñàéòå íå ïîÿâÿòñÿ èíûå óêàçàíèÿ, äëÿ ïèñåì ïî äðóãîìó ïîâîäóñòîèò èñïîëüçîâàòü àäðåñ alex@rubtsov.su.  ñàìîì çàäàíèè îáÿçàòåëüíîóêàæèòå ôàìèëèþ, èìÿ è íîìåð ãðóïïû.Çàäà÷è äåëÿòñÿ íà ñëåäóþùèå êàòåãîðèè: ïðåäáàçîâûå, áàçîâûå, óñèëåííûå è äîïîëíèòåëüíûå. Åñëè âû íå ìîæåòå ðåøèòü çàäà÷è ïðåäáàçîâîãî óðîâíÿ, òî ñêîðåå âñåãî âàì ñòîèò åù¼ ðàç ðàçîáðàòüñÿ ñ ìàòåðèàëîì.Ñäàâàòü ýòè çàäà÷è êðàéíå æåëàòåëüíî, áëàãî îíè íå áîëüøèå ïî îáú¼ìó,÷òîáû â ñëó÷àå êðèòè÷åñêîé îøèáêè ÿ ìîã äàòü îáðàòíóþ ñâÿçü.
Çàäà÷èáàçîâîãî óðîâíÿ ýòî îáÿçàòåëüíûå çàäà÷è. Îíè íå ïðåäñòàâëÿþò îñîáîéòðóäíîñòè, íî èõ óæå íåîáõîäèìî ñäàâàòü â îáÿçàòåëüíîì ïîðÿäêå. Óñèëåííûå çàäà÷è ýòî çàäà÷è â ðàìêàõ êóðñà è áëèçêèå ê êóðñó, êîòîðûåêðàéíå æåëàòåëüíî ðåøàòü, åñëè âû õîòèòå àâòîìàò: óñïåøíîå ðåøåíèåýòèõ çàäà÷ îáëåã÷èò ïîëó÷åíèå àâòîìàòà è òåì áîëåå ñäà÷ó çàäàíèÿ.Êàæäóþ íåäåëþ áóäóò ïðîâîäèòüñÿ êîíòðîëüíûå íà 10-15 ìèíóò. Ôîðìàò openbook: âû ìîæåòå ïîëüçîâàòüñÿ ëþáîé ëèòåðàòóðîé, íî÷èòåëüíî â áóìàæíîì âèäå ! Îöåíêè çà êîíòðîëüíûå0è îò3èñêëþ-äî7.Áåçäîïîëíèòåëüíîãî îáùåíèÿ, ÿ ãîòîâ â êà÷åñòâå àâòîìàòà âûñòàâèòü ñðåäíþþ îöåíêó çà êîíòðîëüíûå, åñëè ó âàñ íåò øòðàôíûõ î÷êîâ.
Íî îáû÷íî, òå êòî íå èìåþò øòðàôíûõ î÷êîâ æåëàþò ïîâûñèòü îöåíêó, ïîýòîìóñðåäíþþ îöåíêó ïî êîíòðîëüíûì ñëåäóåò ðàññìàòðèâàòü êàê îöåíêó ñ2êîòîðîé íà÷èíàåòñÿ ðàçãîâîð. Àâòîìàò ìîæíî ïîëó÷èòü òîëüêî åñëè ïðîìåæóòî÷íûå îáùèå êîíòðîëüíûå äëÿ âñåãî êóðñà íàïèñàíû íå íà äâà.Çà íåñäàííûå çàäàíèÿ è ïëîõî íàïèñàííûå êîíòðîëüíûå íà÷èñëÿþòñÿøòðàôíûå î÷êè, êîòîðûå íà î÷íûõ ñäà÷àõ ïðåîáðàçóþòñÿ â äîïîëíèòåëüíûå çàäà÷è.Íå ñäàííîå â ñðîê çàäàíèå èëè íå íàïèñàííóþ â ñðîê ñåìèíàðñêóþêîíòðîëüíóþ íåëüçÿ ïåðåñäàòü ïîòîì, âíå çàâèñèìîñòè îò ïðè÷èíû. Âñåíàáðàííûå äîëãè ìîæíî áóäåò çàêðûòü íà î÷íîé ñäà÷å, ïîýòîìó äîïîëíèòåëüíûå ìåðû äëÿ óâåëè÷åíèÿ ìèðîâîé ñïðàâåäëèâîñòè ïðèìåíÿòüñÿíå áóäóò.3Òåîðåòèêî-ìíîæåñòâåííîå îòñòóïëåíèåÄëÿ ïîëíîöåííîãî ïðîõîæäåíèÿ äàííîãî êóðñà, âû äîëæíû ïîìíèòüàçû òåîðèè ìíîæåñòâ. Âû äîëæíû çíàòü ÷òî òàêîå ìíîæåñòâî, ïóñòîåìíîæåñòâî, ýëåìåíò ìíîæåñòâà, îñíîâíûå îïåðàöèè íàä ìíîæåñòâàìè:îáúåäèíåíèå, ïåðåñå÷åíèå, äîïîëíåíèå, èñêëþ÷åíèå.
Îäíàêî, êàê ïîêàçûâàåò ïðàêòèêà, îáÿçàòåëüíî íàéäóòñÿ ëþäè, êîòîðûå íå ïîìíÿò ÷òîòàêîå äåêàðòîâî (ïðÿìîå) ïðîèçâåäåíèå.Îïðåäåëåíèå 1. Äåêàðòîâûì ïðîèçâåäåíèåì äâóõ ìíîæåñòâçûâàþò ìíîæåñòâîXèYíà-X × Y = {(x, y) | x ∈ X, y ∈ Y }.Òàêæå íåðåäêî çàáûâàþò, ÷òî ìíîæåñòâî âñåõ ïîäìíîæåñòâ ìíîæåXñòâà X , îáîçíà÷àþò 2 .Âîñïîëíèòü ïðîáåëû â òåîðèè ìíîæåñòâ è äèñêðåòíîì àíàëèçå, à òàêæå óçíàòü ìíîãî íîâîãî è èíòåðåñíîãî ìîæíî èç êíèãè Í.Ê. Âåðåùàãèíàè À. ØåíÿËåêöèè ïî ìàòåìàòè÷åñêîé ëîãèêå è òåîðèè àëãîðèòìîâ.Ýòà êíèãà, à òàêæå ìíîãî äðóãèõ èíòåðåñíûõ è ïîëåçíûõ êíèã, íàõîäÿòñÿâ ñâîáîäíîì äîñòóïå ïî àäðåñó4http://www.mccme.ru/free-books/.Ðåãóëÿðíûå ÿçûêè è êîíå÷íûå àâòîìàòûÏîäàëôàâèòîì ïîíèìàåòñÿ êîíå÷íîå ìíîæåñòâî. Ìû áóäåì îáîçíà-Σ, Γ. Îáû÷Σ = {a, b} èëè÷àòü àëôàâèòû çàãëàâíûìè ãðå÷åñêèìè áóêâàìè, òàêèìè êàêíî ìû áóäåì èñïîëüçîâàòü äâóõáóêâåííûå àëôàâèòûΣ = {0, 1}.Ìíîæåñòâà ìû áóäåì îáîçíà÷àòü çàãëàâíûìè áóêâàìè, à èõýëåìåíòû ñòðî÷íûìè.3Äëÿáóêâ ýëåìåíòîâ àëôàâèòà îïðåäåëåíà îïåðàöèÿ êîíêàòåíà-öèè :a · b = ab.
Ñëîâî w = w1 w2 . . . wn êîíêàòåíàöèÿ áóêâ. Äëèíó ñëîw, ìû áóäåì îáîçíà÷àòü |w|. Äëÿ ñëîâà w = w1 w2 . . . wn , äëèíà |w|ðàâíà n, i-ûé ñèìâîë ñëîâà ìû áóäåì îáîçíà÷àòü w[i] = wi , ïîäñëîâîwi wi+1 . . . wj áóäåì îáîçíà÷àòü w[i, j]. Ìû íå áóäåì ðàçëè÷àòü ñëîâà äëèíû 1 è áóêâû, à òàêæå îäíîýëåìåíòíûå ìíîæåñòâà ñëîâ è ñëîâà. Ïóñòîåñëîâî ìû áóäåì îáîçíà÷àòü ε. Ïóñòîå ñëîâî îáëàäàåò ñëåäóþùèìè ñâîéñòâàìè: Äëÿ ëþáîãî ñëîâà w , ε · w = w · ε = w , |ε| = 0. Äëÿ ìíîæåñòââàñëîâ îïðåäåëåíû ñëåäóþùèå îïåðàöèè:•Êîíêàòåíàöèÿ:X · Y = {x · y | x ∈ X, y ∈ Y }.•Âîçâåäåíèå â ñòåïåíü:X n = |X · X{z· . .
. X}n•Îáúåäèíåíèå:•Èòåðàöèÿ2X|Y = X + Y = X ∪ Y = {w | w ∈ Xèëèw ∈ Y }.X∗ = ε + X + X2 + X3 + . . . Xn + . . . ïåðâîé ÷àñòè êóðñà ìû áóäåì èçó÷àòü êëàññ ðåãóëÿðíûõ ÿçûêîâREG.Ðåãóëÿðíûå ÿçûêè îïðåäåëÿþòñÿ ñëåäóþùèì îáðàçîì:• ∅ ∈ REG.• ∀σ ∈ Σ : {σ} ∈ REG.• ∀X, Y ∈ REG : X · Y, X|Y, X ∗ ∈ REG.•Áîëüøå íåò ðåãóëÿðíûõ ÿçûêîâ.Òàê, ìíîæåñòâî âñåõ ñëîâ íàä àëôàâèòîìΣîáîçíà÷àþòΣ∗ .Çàïèñü ðåãóëÿðíûõ ÿçûêîâ ñ èñïîëüçîâàíèåì ñêîáîê è îïðåäåë¼ííûõâûøå îïåðàöèé, íàçûâàþòðåãóëÿðíûì âûðàæåíèåì. Ñàìè ïî ñåáå ñêîá-êè ÿâëÿþòñÿ ðàçäåëèòåëåì è íå íåñóò ñìûñëîâîé íàãðóçêè: Ðåãóëÿðíîå∗∗∗âûðàæåíèå (a) çàäà¼ò ÿçûê {a}, (a|b) = {a, b}, (a|b) = {a, b} = Σ .Óïðàæíåíèå 1.Ïîêàçàòü, ÷òîε ∈ REG. òåîðèè ôîðìàëüíûõ ÿçûêîâ, êàæäîìó êëàññó ÿçûêîâ ñîîòâåòñòâóåò ìîäåëü âû÷èñëåíèé, êîòîðàÿ ðàñïîçíà¼ò äàííûé êëàññ ÿçûêîâ.
Äëÿêëàññà ðåãóëÿðíûõ ÿçûêîâ òàêîé ìîäåëüþ ÿâëÿåòñÿÊîíå÷íûé Àâòîìàò(ÊÀ).2 Ýòà îïåðàöèÿ òàêæå íîñèò íàçâàíèå çâ¼çäî÷êà Êëèíè, â ÷åñòü âûäàþùåãîñÿ ìàòåìàòèêà Ñòèâåíà Êëèíè.4Îïðåäåëåíèå 2. Êîíå÷íûé àâòîìàòíàáîðîì(Q, Σ, q0 , δ, F ),A ýòî óñòðîéñòâî, îïèñûâàåìîåãäå• Q êîíå÷íîå ìíîæåñòâî ñîñòîÿíèé àâòîìàòà;• Σ àëôàâèò, ñëîâà íàä êîòîðûì îáðàáàòûâàåò àâòîìàò;• q0 íà÷àëüíîå ñîñòîÿíèå àâòîìàòà;• δ : Q × Σ → 2Q• F ⊂Q ôóíêöèÿ ïåðåõîäîâ; ìíîæåñòâî ïðèíèìàþùèõ ñîñòîÿíèé.Àâòîìàò ÿâëÿåòñÿäåòåðìèíèðîâàííûì (ÄÊÀ), åñëè ôóíêöèÿ ïåðå-õîäîâ îïðåäåëåíà îäíîçíà÷íî, òî åñòü äëÿ êàæäîãî ñîñòîÿíèÿ q è äëÿ0êàæäîãî ñèìâîëà σ , ñóùåñòâóåò íå áîëüøå îäíîãî ñîñòîÿíèÿ q ∈ δ(q, σ). ïðîòèâíîì ñëó÷àå, àâòîìàò ÿâëÿåòñÿÍà âõîä àâòîìàòà ïîäà¼òñÿ ñëîâîíåäåòåðìèíèðîâàííûì (ÍÊÀ).w = w1 . .
. wn . Àâòîìàò îáðàáàòûâà-åò ñëîâî ñëåâà íàïðàâî ïî òàêòàì. äåòåðìèíèðîâàííîì ñëó÷àå, çà òàêò ðàáîòû àâòîìàò íàõîäèòñÿ âq , ñ÷èòûâàåò ñèìâîë σ è âû÷èñëÿåò ôóíêöèþ ïåðåõîäà δ(q, σ).00Åñëè δ(q, σ) = q , òî àâòîìàò ïåðåõîäèò â ñîñòîÿíèå q , åñëè æå δ(q, σ) = ∅,ñîñòîÿíèèòî àâòîìàò ïðåêðàùàåò ðàáîòó. íåäåòåðìèíèðîâàííîì ñëó÷àå, çà òàêò ðàáîòû, àâòîìàò íåäåòåðq 0 èç ìíîæåñòâà δ(q, σ) è ïåðåõîäèò â0ñîñòîÿíèè q .  ñëó÷àå, åñëè δ(q, σ) = ∅, àâòîìàò ïðåêðàùàåò ðàáîòó. Ïîäìèíèðîâàííî âûáèðàåò ñîñòîÿíèåíåäåòåðìèíèðîâàííîì âûáîðîì, ìû ïîíèìàåì, ñëåäóþùóþ ñèòóàöèþ.Ñëîâîïðèíèìàåòñÿ àâòîìàòîì, åñëè ïîñëå îáðàáîòêè ñëîâà, àâòî-ìàò îêàçàëñÿ â ïðèíèìàþùåì ñîñòîÿíèè.
Íåäåòåðìèíèðîâàííûé àâòîìàòâñåãäà îêàçûâàåòñÿ â ïðèíèìàþùåì, ñîñòîÿíèè, åñëè îí ìîæåò â íåãîïîïàñòü. Òàêèì îáðàçîì, äåòåðìèíèðîâàííûé àâòîìàò ïðèíèìàåò ñëîâî,åñëè ïîñëå îáðàáîòêè ñëîâà îí îêàçàëñÿ â ïðèíèìàþùåì ñîñòîÿíèè, àíåäåòåðìèíèðîâàííûé àâòîìàò ïðèíèìàåò ñëîâî, åñëè ñóùåñòâóåò òàêàÿïîñëåäîâàòåëüíîñòü âûáîðîâ ñîñòîÿíèé, ÷òî ïîñëå îáðàáîòêè ñëîâà îíîêàçûâàåòñÿ â ïðèíèìàþùåì ñîñòîÿíèè.Íàçîâ¼ìêîíôèãóðàöèåé ïàðó(q, w) ∈ Q × Σ∗ .Íà ìíîæåñòâå êîí-ôèãóðàöèé ââåä¼ì ñîîòâåòñòâóþùåå òàêòàì ðàáîòû àâòîìàòà áèíàðíîå0∗0îòíîøåíèå `: äëÿ âñåõ q ∈ δ(q, a) è äëÿ âñåõ w ∈ Σ (q, aw) ` (q , w). Ðå∗ôëåêñèâíîå è òðàíçèòèâíîå çàìûêàíèå îòíîøåíèÿ ` îáîçíà÷èì ` .
Òàêèì îáðàçîì, àâòîìàò ïðèíèìàåò ñëîâî, åñëè ñóùåñòâóåò òàêàÿ öåïî÷êà5êîíôèãóðàöèé0(q0 , w1 w[2, n]) ` (q10 , w[2, n]), (q10 , w2 w[3, n]) ` (q20 , w[3, n]), . . . , (qn−1, wn ) ` (qn0 , ε),∗00÷òî qn ∈ F . Èëè â òåðìèíàõ òðàíçèòèâíîãî çàìûêàíèÿ ∃qn : (q0 , w) `(qn0 , ε).Ìíîæåñòâî âñåõ ñëîâ, ïðèíèìàåìûõ àâòîìàòîì A áóäåì îáîçíà÷àòüA ïðèíèìàåò ÿçûê L, åñëè ∀w ∈ L : w ∈ L(A), äðóãèìèñëîâàìè L ⊆ L(A). Åñëè ïðè ýòîì, L(A) ⊆ L, òî áóäåì ãîâîðèòü, ÷òîàâòîìàò A ðàñïîçíà¼ò ÿçûê L.
Характеристики
Тип файла PDF
PDF-формат наиболее широко используется для просмотра любого типа файлов на любом устройстве. В него можно сохранить документ, таблицы, презентацию, текст, чертежи, вычисления, графики и всё остальное, что можно показать на экране любого устройства. Именно его лучше всего использовать для печати.
Например, если Вам нужно распечатать чертёж из автокада, Вы сохраните чертёж на флешку, но будет ли автокад в пункте печати? А если будет, то нужная версия с нужными библиотеками? Именно для этого и нужен формат PDF - в нём точно будет показано верно вне зависимости от того, в какой программе создали PDF-файл и есть ли нужная программа для его просмотра.















