1610906281-ae38486ec859a3a9dcd398b8f34f26aa (824377), страница 2
Текст из файла (страница 2)
Ïîýòîìó ñîñòîÿíèå11èã-ðàåò äëÿ íàñ îñîáóþ ðîëü (äâåðü îòêðûòà, öåëü äîñòèãíóòà!), è òîãäà ìûíàçîâ¼ì ýòî ñîñòîÿíèåâûäåëåííûì.Ñòîèò ñðàçó çàìåòèòü, ÷òî âûäåëåí-íûå ñîñòîÿíèÿ ìîãóò îêàçàòüñÿ è äðóãèìè â ñëó÷àå, åñëè ìû ïðåñëåäóåìäðóãóþ öåëü, íàïðèìåð, åñëè íàøà çàäà÷à ñîñòîèò â òîì, ÷òîáû äâåðüîñòàâàëàñü çàêðûòîé, òî âûäåëåííûõ ñîñòîÿíèé áóäåò óæå íå îäíî à òðè:00, 01è10.Ìû òàêæå ìîæåì ñ÷èòàòü, ÷òî â ñàìîì íà÷àëå îáà íàøèçàìêà çàêðûòû.
Òîãäà ñîñòîÿíèå00ìîæíî íàçâàòüíà÷àëüíûì.âñ¼òàêè íàøåé öåëüþ áóäåò îòêðûòü äâåðü èç ñîñòîÿíèÿ00,Åñëè æå11.â íà÷àëå îáà çàìêà îòêðûòû, òî íà÷àëüíûì ñîñòîÿíèåì áóäåòÅñëèòî ïîñëå-AB , ABAA, AABABB ïðèâåäóò ê óñïåõó, à âîòΛ (íè÷åãî íå äåëàåì), ABBA è BBB òàêîãî óæåäîâàòåëüíîñòè äåéñòâèéî ïîñëåäîâàòåëüíîñòÿõñêàçàòü íåëüçÿ. Òàêèì îáðàçîì, äàííûé êîíå÷íûé àâòîìàò ìîæíî èñïîëüçîâàòü äëÿ êëàññèôèêàöèè ñëîâ àëôàâèòà{A, B}.Ìîæíî ñêàçàòü,÷òî ñëîâî ïðèíèìàåòñÿ, åñëè îíî ïðèâîäèò ê äîñòèæåíèþ öåëè.Ðàññìîòðèì åù¼ îäèí ïðèìåð. Ïðåäïîëîæèì, ÷òî Îñòðîâ Ñîêðîâèùèìååò ôîðìó êâàäðàòà è, â ñâîþ î÷åðåäü, ðàçáèò íà 16 êâàäðàòîâ:$$Ðèñ.
2.1: Êëàäû íà Îñòðîâå ÑîêðîâèùÊâàäðàòû, ïîìå÷åííûå ñèìâîëàìè,íåäîñòóïíû èççà íåïðîõîäè-ìûõ äæóíãëåé.  êâàäðàòàõ, ïîìå÷åííûõ ñèìâîëîì$,íàõîäÿòñÿ êëàäû.Ìû ìîæåì â êàæäûé ìîìåíò âðåìåíè íàõîäèòñÿ â îäíîì èç êâàäðàòîâè ïåðåìåùàòüñÿ ïî îñòðîâó, ïåðåõîäÿ èç êâàäðàòà â êâàäðàò, äâèãàÿñü2.1. Îñíîâíûå îïðåäåëåíèÿ15íà ñåâåð, þã, çàïàä èëè âîñòîê. Ýòè ïåðåìåùåíèÿ áóäóò îáîçíà÷àòüñÿ ñîîòâåòñòâåííî ñèìâîëàìèñ, þ, â, ç.Çäåñü ìû ìîæåì ñ÷èòàòü, ÷òî ñîñòî-ÿíèÿìè ñèñòåìû ÿâëÿþòñÿ ñàìè ýòè êâàäðàòû (ò.å., ñèñòåìà íàõîäèòñÿâ ñîñòîÿíèès,åñëè ìû íàõîäèìñÿ â êâàäðàòås.),à âîçäåéñòâèÿìè íàñèñòåìó áóäóò ïåðåäâèæåíèÿ íà îäèí êâàäðàò íà ñåâåð, þã, çàïàä èëèâîñòîê. Ìû ñ÷èòàåì, ÷òî ïðè ïåðåäâèæåíèè â êâàäðàò, ïîìå÷åííûé ñèìâîëîì,äîñòóï â êîòîðûé íåâîçìîæåí, ìû îñòà¼ìñÿ íà òîì æå ñàìîììåñòå, ò.å., ñîñòîÿíèå íå ìåíÿåòñÿ.
Åñëè ìû ñòàâèì ñâîåé öåëüþ äîáû÷óêëàäîâ, òî èìååò ñìûñë ñ÷èòàòü âûäåëåííûìè ñîñòîÿíèÿìè êâàäðàòû,ïîìå÷åííûå ñèìâîëîì$.Åñëè ìû íà÷èíàåì äâèæåíèå èç ëåâîãî íèæíå-ãî óãëà, òî èìååò ñìûñë ñ÷èòàòü ñîîòâåòñòâóþùèé êâàäðàò íà÷àëüíûìñîñòîÿíèåì ñèñòåìû. Ïèðàòû, îñòàâèâøèå êëàäû, ìîãóò îñòàâèòü îïèñàíèå ïóòè ê ýòèì êëàäàì èç ëåâîãî íèæíåãî óãëà â âèäå èíñòðóêöèè òèïà:ñíà÷àëà ïîéòè íà ñåâåð, ïîòîì îïÿòü íà ñåâåð, ïîòîì íà âîñòîê . . . Ïîäîáíûå èíñòðóêöèè ìîæíî ïðåäñòàâèòü â âèäå ñëîâ â àëôàâèòå{ñ,þ,â,ç}(ñðåäè òàêèõ ñëîâ èìååò ñìûñë òàêæå ðàññìàòðèâàòü è ïóñòîå ñëîâî, ñîîòâåòñòâóþùåå îòñóòñòâèþ ïåðåìåùåíèÿ).
Îïÿòüòàêè, íåêîòîðûå òàêèåñëîâàèíñòðóêöèè ìîãóò ïðèâåñòè ê êëàäó, à íåêîòîðûå íåò. Òàê ñëåäî-ññâââ è ññââþþñþññçâ íåò.âàíèå èíñòðóêöèÿìèíñòðóêöèÿìΛèïðèâîäèò ê êëàäó, à ñëåäîâàíèå îáîèõ íàøèõ ïðèìåðàõ ìû ïðèøëè ê òîìó, ÷òî âîçäåéñòâèÿ, ìåíÿþùèå ñîñòîÿíèÿ ñèñòåìû, ìîæíî ïðåäñòàâëÿòü â âèäå ñèìâîëîâ íåêîòîðîãîàëôàâèòà, à ïîñëåäîâàòåëüíî îñóùåñòâëÿþùèå äðóã çà äðóãîì âîçäåéñòâèÿ â âèäå ñëîâ íàä ýòèì àëôàâèòîì. Ìîæíî òàêæå ñ÷èòàòü, ÷òî íàâõîä àâòîìàòà ïîñëåäîâàòåëüíî ïîäàþòñÿ ñèìâîëû íåêîòîðîãî ñëîâà, ïîäâîçäåéñòâèåì êîòîðûõ îí èçìåíÿåò ñâî¼ ñîñòîÿíèå. Êðîìå òîãî, â îáîèõýòèõ ïðèìåðàõ óìåñòíî ãîâîðèòü î ðàçäåëåíèè ñëîâ íà äâà ìíîæåñòâà ïðèâîäÿùèõ èëè íå ïðèâîäÿùèõ ê öåëè.Òåïåðü ìîæíî ñôîðìóëèðîâàòü ôîðìàëüíîå îïðåäåëåíèå êîíå÷íîãîàâòîìàòà.Êîíå÷íûì àâòîìàòîì íàçûâàåòñÿ óïîðÿäî÷åííàÿïÿòåðêà hS, A, i, t, F i, ãäåÎïðåäåëåíèå 2.1.1• S êîíå÷íîå ìíîæåñòâî, íàçûâàåìîå ìíîæåñòâîì ñîñòîÿíèé;• A êîíå÷íûé àëôàâèò;• i ∈ S íà÷àëüíîå ñîñòîÿíèå;Ãëàâà 2.
Àâòîìàòíûå ÿçûêè16• t : S × A → S ôóíêöèÿ ïåðåõîäà;• F ⊆ S ìíîæåñòâî âûäåëåííûõ (çàêëþ÷èòåëüíûõ) ñîñòîÿíèé. íàøèõ ïðèìåðàõ ïðèñóòñòâîâàëè íåêîòîðûå êëàññèôèêàöèè ñëîâ ïîïðèçíàêó äîñòèæåíèÿ öåëè (îòêðûâàåò ëè ñëîâî äâåðü, ïîìîãàåò ëè íàéòè êëàä).
Îòðàçèì ýòè êëàññèôèêàöèè â ôîðìàëüíîì îïðåäåëåíèè. Ìûíàçîâ¼ì ýòîðàñïîçíàâàåìîñòüþ èëè ïðèíèìàåìîñòüþñëîâ àâòîìàòîì.∗∗Ñíà÷àëà îïðåäåëèì èíäóêöèåé ïî äëèíå ñëîâà ôóíêöèþ t : S × A → S ,∗âûäàþùóþ ñîñòîÿíèå t (s, w), â êîòîðîì îêàæåòñÿ àâòîìàò, íàõîäèâøèéñÿ â ñîñòîÿíèèñëîâàs,íà âõîä êîòîðîãî ïîñëåäîâàòåëüíî ïîñòóïèëè ñèìâîëûw:t∗ (s, Λ) = s,t∗ (s, wa) = t(t∗ (s, w), a),Çíà÷åíèåt∗ (s, w)åñëèw ∈ A∗ , a ∈ A.ðàâíî ñîñòîÿíèþ, â êîòîðîì îêàæåòñÿ àâòîìàò ïîñëåïîñëåäîâàòåëüíîãî ïåðåõîäà èç íà÷àëüíîãî ñîñòîÿíèÿ â ñîîòâåòñòâèè ñtèä¼òðå÷ü, ìû ÷àñòî áóäåì èñïîëüçîâàòü òàêæå è áîëåå óäîáíóþ çàïèñüt∗ (s, w).
Ñëåäóþùèå ñâîéñòâà î÷åâèäíû:s·wñèìâîëàìè ñëîâàw. ñëó÷àå. êîãäà êîãäà ÿñíî, î êàêîé ôóíêöèèâìåñòîs · Λ = s,(s · w0 ) · w1 = s · w0 w1 ,äëÿ âñåõw0 , w1 ∈ A∗ .Îïðåäåëåíèå 2.1.2 Ïóñòü A = hS, A, i, t, F i êîíå÷íûé àâòîìàò. Åñëè i · w ∈ F , òî ìû áóäåì ãîâîðèòü, ÷òî àâòîìàò A ðàñïîçíà¼ò ñëîâîw. Óïîòðåáëÿåòñÿ òàêæå âûðàæåíèå ¾àâòîìàò A ïðèíèìàåò ñëîâîw¿.ßçûê, ðàñïîçíàâàåìûé àâòîìàòîì A = hS, A, i, t, F i, îïðåäåëÿåòñÿ,êàêL(A) = {w ∈ A∗ | i · w ∈ F }.Óïîòðåáëÿåòñÿ òàêæå âûðàæåíèå ¾ÿçûê àâòîìàòà A¿.ßçûê âèäà L(A), ãäå L(A) íåêîòîðûé êîíå÷íûé àâòîìàò, íàçûâàåòñÿ àâòîìàòíûì ÿçûêîì.Çàìåòèì, ÷òîΛ ∈ L(A)âûïîëíåíî òîãäà è òîëüêî òîãäà, êîãäà íà-÷àëüíîå ñîñòîÿíèå ÿâëÿåòñÿ âûäåëåííûì.2.1.
Îñíîâíûå îïðåäåëåíèÿ17Íàèáîëåå óäîáíûì è áûñòðûì ñïîñîáîì îïèñàíèÿ êîíå÷íîãî àâòîìàòà ÿâëÿåòñÿ åãî ãðàôè÷åñêîå èçîáðàæåíèå,â êîòîðîì ñîñòîÿíèÿ èçîáðàæàþòñÿ íåáîëüøèìè êðóæêàìè (èëè îâàëàìè), âûäåëåííûå ñîñòîÿíèÿ äâîéíûìè êðóæêàìè, íà÷àëüíîå ñîñòîÿíèå êðóæêîì ñî âõîäÿùåéâ íåãî ñòðåëêîé ñî ñâîáîäíûì íà÷àëîì, ïåðåõîäû ìåæäó ñîñòîÿíèÿìèèçîáðàæàþòñÿ äóãàìè, ïîìå÷åííûìè ñèìâîëàìè àëôàâèòàA.Òàê íàëè-÷èå â ðèñóíêå ôðàãìåíòàDîçíà÷àåò, ÷òî èç ñîñòîÿíèÿ 1 àâòîìàò ïðè ïîëó÷åíèè ñèìâîëàaïåðåé-ä¼ò â ñîñòîÿíèå 2.
Íàïðèìåð, àâòîìàò èç ïåðâîãî ïðèìåðà, îïèñûâàþùèéîòêðûâàíèå äâåðè ñ äâóìÿ çàìêàìè, èçîáðàæ¼í íà Ðèñ 2.2.$$%%%%$$Ðèñ. 2.2: Îòêðûâàíèå äâåðè ñ äâóìÿ çàìêàìè.Àâòîìàò, ñîîòâåòñòâóþùèé ïîèñêó êëàäîâ íà Îñòðîâå Ñîêðîâèù, ìîæíî èçîáðàçèòü òàê, êàê ýòî ñäåëàíî íà Ðèñ. 2.3:ɫɡɜɫɸɫ ɸɜɡɸɡɜɡɫ ɸɫɡɜɸɫɜɡɫ ɸɜɜɡ ɫɡɸɸɜɡɫɸɜÐèñ.
2.3: Ïîèñê êëàäîâ íà Îñòðîâå Ñîêðîâèù.Ãëàâà 2. Àâòîìàòíûå ÿçûêè18Ñåé÷àñ áóäåò ïðåäñòàâëåí îäèí íåôîðìàëüíûé ìåòîä ðåøåíèÿ çàäà÷íà ïîñòðîåíèå êîíå÷íûõ àâòîìàòîâ ñ çàäàííûìè ñâîéñòâàìè.Ðàññìîòðèì çàäà÷ó: ïîñòðîèòü êîíå÷íûé àâòîìàò íàä àëôàâèòîì{a, b},a.ðàñïîçíàþùèé âñå ñëîâà, â êîòîðûõ ñîäåðæèòñÿ ðîâíî îäíà áóêâàÊàê ìû ñàìè ìîãëè áû ðàñïîçíàâàòü òàêèå ñëîâà, êîòîðûå ïîñòóïàþòíàì â âèäå ïîñëåäîâàòåëüíîñòè ñèìâîëîâ, îñíîâûâàÿñü òîëüêî íà æèòåéñêîì îïûòå? Ïîïûòàåìñÿ îïèñàòü îäèí èç âîçìîæíûõ ïðîöåññîâ. (Ìîæåòáûòü, ñåé÷àñ ñòîèò íà ìèíóòó çàáûòü îá óæå èìåþùåìñÿ ó íàñ ìàòåìàòè÷åñêîì îáðàçîâàíèè!) Ïðîöåññ ñîñòîèò â òîì, ÷òî ïåðåä íà÷àëîì ðàáîòûìû êàê áû íà÷èíàåì ïîñòîÿííî ïðîèçíîñèòü ïðî ñåáÿ ôðàçó: ¾ïîêà ÷òîa íå áûëî¿ (ïðè ýòîì ìîæíî ñêàçàòü, ÷òî ìû íàõîäèìñÿñîñòîÿíèè , ñîîòâåòñòâóþùåì ýòîé ôðàçå!) è ïîñëåäîâàòåëü-íè îäíîé áóêâûâ íåêîòîðîìíî ïðîñìàòðèâàåì ñèìâîëû âõîäíîãî ñëîâà, áóêâó çà áóêâîé.
Ìû áóäåìïðîèçíîñèòü ýòó ôðàçó äî òåõ ïîð, ïîêà íå ïîñòóïèò ñèìâîëa.Ïîñëåýòîãî ìû èçìåíÿåì ôðàçó íà ¾â ïîëó÷åííîì ñëîâå ðîâíî îäíà áóêâàa,èñëîâî, êîòîðîå ìû ñåé÷àñ ïðî÷èòàëè, íàì ïîäõîäèò¿ (çàìåòüòå, ÷òî ìûèçìåíèëè ñîñòîÿíèå !);ìû ïðîäîëæàåì ïðîèçíîñèòü ýòó ôðàçó äî òåõïîð, ïîêà íà âõîä íå ïîñòóïèò áóêâàa.Ïîñëå ýòîãî ìû èçìåíÿåì ôðàçóíà ¾ýòî ñëîâî òî÷íî íå ãîäèòñÿ¿ (òåì ñàìûì îïÿòüèçìåíèâ ñîñòîÿíèå) èïðîäîëæàåì ïðîèçíîñèòü å¼, óæå íèêîãäà íå èçìåíÿÿ. Åñëè ñëîâî çàêîí÷èòñÿ, êîãäà ìû íàõîäèìñÿ â ñîñòîÿíèè ¾â ïîëó÷åííîì ñëîâå ðîâíî îäíàáóêâàa,è ñëîâî, êîòîðîå ìû ñåé÷àñ ïðî÷èòàëè, íàì ïîäõîäèò¿, òî îíîñîäåðæèò ðîâíî îäíó áóêâóa;â îñòàëüíûõ ñëó÷àÿõ îíî ëèáî ñîäåðæèòêàê ìèíèìóì äâå òàêèõ áóêâû ëèáî íè îäíîé.Ýòîò ïðîöåññ êàê ðàç åñòåñòâåííûì îáðàçîì äà¼ò íàì èñêîìûé êîíå÷íûé àâòîìàò.
Äåéñòâèòåëüíî, â ïðîöåññå ðàñïîçíàâàíèÿ ñëîâ ìû âêàæäûé ìîìåíò âðåìåíè íàõîäèìñÿ â îäíîì èç òð¼õ ñîñòîÿíèé, îïðåäåëÿåìûõ ôðàçàìè:Ñîñòîÿíèå 1:ïîêà ÷òî íè îäíîé áóêâûÑîñòîÿíèå 2:â ïîëó÷åííîì ê íàñòîÿùåìó ìîìåíòó ñëîâå åñòü ðîâíîîäíà áóêâàa,aíå áûëîè ñëîâî, êîòîðîå ìû ïðî÷èòàëè ê äàííîìó ìîìåíòóâðåìåíè, íàì ïîäõîäèòÑîñòîÿíèå 3:ýòî ñëîâî òî÷íî íå ãîäèòñÿ.Ñîñòîÿíèå 1 ÿâëÿåòñÿ íà÷àëüíûì, à ñîñòîÿíèå 2 âûäåëåííûì. Ôóíêöèÿïåðåõîäîâ çàäà¼òñÿ î÷åâèäíûì îáðàçîì (ñì.
òàáëèöó):2.1. Îñíîâíûå îïðåäåëåíèÿ19ñîñòîÿíèå/ñèìâîëab121232333Ðèñ. 2.4: Ôóíêöèÿ ïåðåõîäîâÒåïåðü îñòà¼òñÿ ãðàôè÷åñêè èçîáðàçèòü ïîëó÷åííûé àâòîìàò (Ñì.Ðèñ 2.5): DE DEDEÐèñ. 2.5: Ïîëó÷åííûé àâòîìàò.Ðàññìîòðèì åù¼ îäíó çàäà÷ó: ïîñòðîèòü êîíå÷íûé àâòîìàò, êîòîðûéðàñïîçíàåò ñëîâà íàä àëôàâèòîì{a, b},÷èñëî áóêâaâ êîòîðûõ íå äå-ëèòñÿ íà 3.Äåéñòâóÿ êàê è ðàíüøå, ìû ìîæåì â êà÷åñòâå ñîñòîÿíèé âçÿòü îñòàòêèîò äåëåíèÿ íà 3 ÷èñëà ñèìâîëîâa, ïîñòóïèâøèõ íà âõîä â äàííûé ìîìåíò.Íà÷àëüíûì ñîñòîÿíèåì áóäåò 0.
![](https://s.studizba.com/z.php?f=/templates/si/i/noavatar.png&w=100&h=100&t=1"){kind=avatar}
