1610906281-ae38486ec859a3a9dcd398b8f34f26aa (824377), страница 3
Текст из файла (страница 3)
Âûäåëåííûìè ñîñòîÿíèÿìè áóäóò 1 è 2.Ôóíêöèÿ ïåðåõîäîâ áóäåò çàäàâàòüñÿ ñëåäóþùåé òàáëèöåé:ñîñòîÿíèå/ñèìâîëab010121202Ðèñ. 2.6: Ôóíêöèÿ ïåðåõîäîâÝòîò àâòîìàò èçîáðàæ¼í íà Ðèñ. 2.7.ÓïðàæíåíèÿÃëàâà 2. Àâòîìàòíûå ÿçûêè20EDEDDEÐèñ. 2.7: Ïîëó÷åííûé àâòîìàò.1. Ïîñòðîéòå è èçîáðàçèòå ãðàôè÷åñêè êîíå÷íûé àâòîìàò A, ðàñïîçíàþùèéà) ÿçûê L = ∅ íàä àëôàâèòîì A = {0};á) ÿçûê L = {Λ} íàä àëôàâèòîì A = {0};â) ÿçûê L = {0} íàä àëôàâèòîì A = {0, 1};ã) ÿçûê L = A (ò.å., ìíîæåñòâî îäíîýëåìåíòíûõ ñëîâ) íàä àëôàâèòîìA = {0, 1, 2};ä) ÿçûê L = {0}∗ íàä àëôàâèòîì A = {0, 1};å) ÿçûê L = {0, 1}∗ íàä àëôàâèòîì A = {0, 1, 2};æ) ÿçûê, ñîñòîÿùèé èç ñëîâ, íà÷èíàþùèõñÿ íà 00 íàä àëôàâèòîì A ={0, 1};ç) ÿçûê, ñîñòîÿùèé èç ñëîâ, íå íà÷èíàþùèõñÿ íà 00 íàä àëôàâèòîìA = {0, 1};è) ÿçûê, ñîñòîÿùèé èç ñëîâ, íà÷èíàþùèõñÿ íà 01 íàä àëôàâèòîì A ={0, 1, 2};ê) ÿçûê, ñîñòîÿùèé èç ñëîâ, îêàí÷èâàþùèõñÿ íà 00 íàä àëôàâèòîì A ={0, 1};ë) ÿçûê, ñîñòîÿùèé èç ñëîâ, îêàí÷èâàþùèõñÿ íà 01 íàä àëôàâèòîì A ={0, 1, 2};ì) ÿçûê, ñîñòîÿùèé èç ñëîâ, ñîäåðæàùèõ ðîâíî îäèí ñèìâîë 1 è ðîâíîäâà ñèìâîëà 0 íàä àëôàâèòîì A = {0, 1, 2};í) ÿçûê, ñîñòîÿùèé èç ñëîâ, ñîäåðæàùèõ ÷åòíîå ÷èñëî ñèìâîëîâ 1 èíå÷åòíîå ÷èñëî ñèìâîëîâ 2 íàä àëôàâèòîì A = {0, 1, 2};î) ÿçûê L = {1| .{z.
. 1} 6= Λ | n ∈ N} íàä àëôàâèòîì A = {0, 1};2nï) ÿçûê L = {s ∈ A | â ñëîâå s ðàçíîñòü ÷èñëà ñèìâîëîâ 0 è ÷èñëà ñèìâîëîâ 1 ÷åòíà} íàä àëôàâèòîì A = {0, 1};ð) ÿçûê L = {s ∈ A | â ñëîâå s ðàçíîñòü ÷èñëà ñèìâîëîâ 0 è ÷èñëà ñèìâîëîâ 1 äåëèòñÿ íà 5} íàä àëôàâèòîì A = {0, 1};2.2. Ëåììà î íàêà÷èâàíèèñ) ÿçûê L = {f|. . .
f (0) | n ∈ N}{z }21íàä àëôàâèòîì A = {f, 0, (, )};ò) ÿçûê L = {s ∈ {a, b}∗ | â s íå âñòðå÷àåòñÿ ïîäðÿä äâå áóêâû b};ó) ÿçûê L = {s ∈ {a, b}∗ | â s âñòðå÷àåòñÿ äâå áóêâû b ïîäðÿä};ô) ÿçûê L = {s ∈ {a, b}∗ | â s åñòü ïîäñëîâî abab};õ) ÿçûê L = {s ∈ {a, b}∗ | â s íå ñîäåðæèòñÿ ïîäñëîâî abab};ö) ÿçûê L = {s ∈ {a, b}∗ | â s âñòðå÷àåòñÿ äâå áóêâû a ïîäðÿä è äâåáóêâû b ïîäðÿä};÷) ÿçûê L = {s ∈ {+, −, 0, . . . , 9}∗ | s çàïèñü öåëîãî ÷èñëà};ø) ÿçûê L = {s ∈ {0, . . . , 9}∗ | s çàïèñü ÷¼òíîãî íàòóðàëüíîãî ÷èñëà};ù) ÿçûê L = {s ∈ {0, . .
. , 9}∗ | s çàïèñü íàòóðàëüíîãî ÷èñëà, äåëÿùåãîñÿ íà 3}.2.2nËåììà î íàêà÷èâàíèèÇäåñü ìû îïèøåì îäíî ïðîñòîå íî âàæíîå ñâîéñòâî àâòîìàòíûõ ÿçûêîâ,îòñóòñòâèå êîòîðîãî â áîëüøèíñòâå ñëó÷àåâ ëåãêî ïðîâåðÿåìî, è ïîýòîìóäàííîå ñâîéñòâî îáû÷íî ïîçâîëÿåò áåç îñîáûõ óñèëèé äîêàçûâàòü íåàâòîìàòíîñòü ÿçûêîâ. Îíî îñíîâàíî íà ïðîñòîì íàáëþäåíèè, ñîñòîÿùåì âòîì, ÷òî åñëè íåêîòîðîå ñëîâî ïðèíèìàåòñÿ êîíå÷íûì àâòîìàòîì.
ò.å.,ïðî÷èòûâàåòñÿ âäîëü ïóòè ïî íåìó, êîòîðûé âåä¼ò èç íà÷àëüíîãî ñîñòîÿíèÿ â âûäåëåííîå è ïðè ýòîì ñîäåðæèò ïåòëþ, òî ìû ìîæåì äîéòè äîýòîé ïåòëè âäîëü äàííîãî ïóòè, ïðîéòè å¼ ñêîëüêî óãîäíî (â òîì ÷èñëå è íîëü) ðàç è ïîòîì, íàêîíåö, ïðîéòè îñòàòîê ïóòè. Ïðè ýòîì ïðîéäåííûé ïóòü ñíîâà áóäåò ïóò¼ì èç íà÷àëüíîãî ñîñòîÿíèÿ â âûäåëåííîå.Ñîîòâåòñòâåííî, âñå ñëîâà, ÷èòàåìûå âäîëü òàêèõ ïóòåé, òîæå äîëæíûïðèíèìàòüñÿ ýòèì àâòîìàòîì!Áóäåì ãîâîðèòü, ÷òî ÿçûê L îáëàäàåò ñâîéñòâîìíàêà÷èâàíèÿ, åñëè ñóùåñòâóåò íàòóðàëüíîå ÷èñëî p òàêîå, ÷òî äëÿ ëþáîãî ñëîâà âèäà uvw èç L òàêîãî, ÷òî |v| > p, ñóùåñòâóåò ïðåäñòàâëåíèå v â âèäå v = αβγ òàêîå, ÷òî β 6= Λ, è äëÿ ëþáîãî k ∈ N ñïðàâåäëèâîuαβ k γw ∈ L.Îïðåäåëåíèå 2.2.1Òåîðåìà 2.2.1 (Ëåììà î íàêà÷èâàíèè)ëàäàåò ñâîéñòâîì íàêà÷èâàíèÿ.Ëþáîé àâòîìàòíûé ÿçûê îá-Ãëàâà 2.
Àâòîìàòíûå ÿçûêè22Äîêàçàòåëüñòâî òåîðåìû. Ïóñòü ÿçûêèpLðàñïîçíà¼òñÿ àâòîìàòîì ÷èñëî åãî ñîñòîÿíèé. Âîçüì¼ì ïðîèçâîëüíîå ñëîâî÷òî|v| > p.òàêîå,Òîãäà ïóòü èç íà÷àëüíîãî ñîñòîÿíèÿ, âäîëü êîòîðîãî ïðî÷è-òûâàåòñÿ ñëîâî|v| > p,uvw ∈ LA,uvw,çàêàí÷èâàåòñÿ â âûäåëåííîì ñîñòîÿíèè. ÏîñêîëüêóΓ, ñîîòâåòñòâóþùèé ôðàãìåíòó v , ïðîõîäèò ÷åðåçs àâòîìàòà A êàê ìèíèìóì äâàæäû.
Òàêèì îáðàçîì,ñëîâî v ìîæíî ïðåäñòàâèòü â âèäå v = αβγ , ãäå α, β , γ ïðî÷èòûâàþòñÿñîîòâåòñòâåííî âäîëü îòðåçêîâ ïóòè Γ äî s, ïåòëå îò s äî s è îñòàâøåéñÿ÷àñòè. Ïðè ýòîì |β| 6= Λ, è ó÷àñòîê β íà÷èíàåòñÿ è çàêàí÷èâàåòñÿ â îäíîì è òîì æå ñîñòîÿíèè s. Ðàññìîòðèì ïóòü ïî àâòîìàòó, âûõîäÿùèé èçíà÷àëüíîãî ñîñòîÿíèÿ, ïðîõîäÿùèé ïîñëåäîâàòåëüíî ó÷àñòêè u, α, ïîòîìïðîõîäÿùèé k ðàç ó÷àñòîê β (ïî ïåòëå), ïîòîì ïî ó÷àñòêó γ , è ïîòîì ïîw.
Ëþáîé òàêîé ïóòü íà÷èíàåòñÿ â íà÷àëüíîì ñîñòîÿíèè è çàêàí÷èâàåòkñÿ â âûäåëåííîì ñîñòîÿíèè. Âäîëü íåãî áóäåò ÷èòàòüñÿ ñëîâî vαβ γw ,kîòêóäà vαβ γw ∈ L(A) = L, ÷òî è òðåáîâàëîñü. ó÷àñòîê ïóòèíåêîòîðîå ñîñòîÿíèåÄîêàæåì ñ ïîìîùüþ Ëåììû î íàêà÷èâàíèè, ÷òî ÿçûêN}L = {ai bi | i ∈íå àâòîìàòåí. Ïðåäïîëîæèâ, ÷òî îí àâòîìàòåí, ìû ïî ýòîé ëåììåïîëó÷èì, ÷òî îí îáëàäàåò ñâîéñòâîì íàêà÷èâàíèÿ. Çàôèêñèðóåìpêàêâ îïðåäåëåíèè íàêà÷èâàíèÿ. Âîçüì¼ì ïðîèçâîëüíîå íàòóðàëüíîå ÷èñëîm > p. Òîãäà ïî ëåììå î íàêà÷èâàíèè ñëîâî am bm ∈ L ìîæíî ïðåäñòàâèòüâ âèäåam b m = al an ar b m ,ãäåm=l+n+rèn>0al ank ar bm = al+nk+r bm ∈ L.íî ïîñëåäíåå íåâîçìîæíî, ïîñêîëüêó èççà n > 0 ïðè k = 0 ïîëó÷èìl + n · 0 + r < l + n + r = m, è, ñòàëî áûòü, al+n·0+r bm ∈/ L.òàê, ÷òîáû äëÿ ëþáîãîk ∈ NâûïîëíÿëîñüÑåé÷àñ ìû ïîêàæåì, ÷òî ñâîéñòâî íàêà÷èâàíèÿ íåëüçÿ ðàññìàòðèâàòü, êàê êðèòåðèé àâòîìàòíîñòè, ïîñêîëüêó ñóùåñòâóþò íåàâòîìàòíûåÿçûêè, óäîâëåòâîðÿþùèå ýòîìó ñâîéñòâó.
Âïðî÷åì, ýòî íå âëèÿåò íà îáùóþ óñïåøíîñòü ïðèìåíåíèÿ ýòîé ëåììû ïðè äîêàçàòåëüñòâàõ íåàâòîìàòíîñòè ÿçûêîâ.Òåîðåìà 2.2.2÷èâàíèÿ.Ñóùåñòâóåò íåàâòîìàòíûé ÿçûê ñî ñâîéñòâîì íàêà-Ýòà òåîðåìà áóäåò ïîëó÷åíà êàê ñëåäñòâèå èç äðóãîãî áîëåå îáùåãî ðåçóëüòàòà, äëÿ ïîíèìàíèÿ äîêàçàòåëüñòâà êîòîðîãî òðåáóåòñÿ çíàêîìñòâî ñ òåîðåòèêîìíîæåñòâåííûì ïîíÿòèåì ìîùíîñòè. Ìàòåðèàë äîêîíöà ýòîãî ïàðàãðàôà ìîæíî îïóñòèòü.2.2. Ëåììà î íàêà÷èâàíèè23Íàä ëþáûì òð¼õýëåìåíòíûì àëôàâèòîì ÷èñëî ÿçûêîâ,îáëàäàþùèõ ñâîéñòâîì íàêà÷èâàíèÿ, íåñ÷¼òíî.Òåîðåìà 2.2.3A ñîñòîèò èç ñèìâîëîâ 0, 1, 4. Áóäåì ãîâîðèòü, ÷òî ñëîâî w ∈ A ñîäåðæèò ïîñëåäîâàòåëüíîñòü ε =ε0 ε1 .
. . εk−1 ∈ {0, 1}∗ , åñëè ñëîâî 4ε0 4ε1 4 . . . 4εk−1 4 ÿâëÿåòñÿ íà÷àëüíûì ñåãìåíòîì w . Íà÷àëüíûå ñåãìåíòû ñëîâà âèäà 4ε0 4ε1 4 . . . 4εk−1 4,ε0 , ε1 , . . . , εk−1 ∈ {0, 1}, áóäåì íàçûâàòü ïðàâèëüíûìè ñåãìåíòàìè. ÎòìåÄîêàçàòåëüñòâî. Ïóñòü àëôàâèò∗òèì ñëåäóþùèå ñâîéñòâà ââåä¼ííûõ ïîíÿòèé:•Åñëèwñîäåðæèòñîäåðæèò•ε,èγÿâëÿåòñÿ íà÷àëüíûì ñåãìåíòîìε,òîwγ.Ó ëþáîãî ñëîâà åñòü ìàêñèìàëüíûé ïðàâèëüíûé ñåãìåíò îòíîñèòåëüíî îòíîøåíèÿ ¾áûòü íà÷àëüíûì ñåãìåíòîì¿.•Ó ëþáîãî ñëîâà åñòü ìàêñèìàëüíàÿ ïîñëåäîâàòåëüíîñòü, êîòîðóþîíî ñîäåðæèò.Áóäåì îáîçíà÷àòü ìàêñèìàëüíûé ïðàâèëüíûé ñåãìåíò ñëîâàè ìàêñèìàëüíîå ñëîâî, êîòîðîå îíî ñîäåðæèò ÷åðåç∗Ïîäìíîæåñòâî T â {0, 1} íàçîâ¼ì äåðåâîì, åñëèâíèç, ò.å., äëÿ ëþáûõ ñëîâ÷àëüíûé ñåãìåíòβèβ ∈ T,αw ÷åðåç µ(w)s(w).Λ∈Tè T çàìêíóòîβ ñïðàâåäëèâî ñâîéñòâî: åñëè α íàα ∈ T .
Íåòðóäíî âèäåòü, ÷òî ñóùåñòâóåòèòîêîíòèíóóì ðàçëè÷íûõ äåðåâüåâ.ÅñëèT äåðåâî, òî îïðåäåëèìLT = {w ∈ A∗ | s(w) ∈ T }.T0 6= T1 ñëåäóåò íåðàâåíñòâî ÿçûLT0 6= LT1 .  ñàìîì äåëå, ïóñòü, íàïðèìåð, ε0 ε1 . . . εk−1 ∈ T0 \T1 . Òîãäàñëîâî 4ε0 4ε1 4 . . . 4εk−1 4 ïðèíàäëåæèò LT0 \ LT1 . Îòñþäà ñëåäóåò, ÷òîñóùåñòâóåò êîíòèíóóì ðàçëè÷íûõ ÿçûêîâ âèäà LT .Çàìåòèì, ÷òî èç íåðàâåíñòâà äåðåâüåâêîâÒåîðåìà áóäåò ñëåäîâàòü èç ñëåäóþùåé ëåììû:Ëåììà 2.2.1 Ëþáîé ÿçûê âèäà LT îáëàäàåò ñâîéñòâîì íàêà÷èâàíèÿ ñïàðàìåòðîì p ðàâíûì 2.Ðàññìîòðèì ïðîèçâîëüíûé ÿçûê âèäàèçâîëüíîå ïîäñëîâî ñëîâàwäëèíû2.LT .Ïóñòüw ∈ LTèβ ïðî-Ðàññìîòðèì ñëåäóþùèå ñëó÷àè:Ãëàâà 2.
Àâòîìàòíûå ÿçûêè24Ñëó÷àé 1. Ñëîâî β íàõîäèòñÿ âíóòðè ñåãìåíòà µ(w). ýòîì ñëó÷àå β ñîäåðæèò ñèìâîë a, ðàâíûé 0 èëè 1. Çàìåíÿÿ â ñëîâåw ñèìâîë a íà ëþáîå ñëîâî ai (i ∈ N), ò.å., íàêà÷èâàÿ ýòîò ñèìâîë, ìûñíîâà ïîëó÷èì ñëîâî èç LT .Ñëó÷àé 2. Ñëîâî β íå íàõîäèòñÿ âíóòðè ñåãìåíòà µ(w), íî èìååò ñ íèìíåïóñòîå ïåðåñå÷åíèå.  ýòîì ñëó÷àå β îáÿçàòåëüíî ñîäåðæèò ïîñëåäíèéiñèìâîë 4 èç µ(w). Çàìåíÿÿ åãî íà ëþáîå ñëîâî âèäà 4 (i ∈ N), ò.å.,íàêà÷èâàÿ ïîñëåäíèé ñèìâîë, ìû ñíîâà ïîëó÷èì ñëîâî èç LT .Ñëó÷àé 3. Ñëîâî β íå ïåðåñåêàåòñÿ ñ µ(w), è µ(w) 6= Λ.Çäåñü ìû ðàññìîòðèì äâà ïîäñëó÷àÿ:Ïîäñëó÷àé 3.1. Ñëåâà ê β ïðèìûêàåò ñèìâîë 4.Åñëè õîòÿ áû îäèí èç ñèìâîëîâ ñëîâà β ðàâåí 4, òî, íàêà÷èâàÿ âñëîâå w îñòàâøèéñÿ ñèìâîë, ìû ñíîâà ïîëó÷èì ñëîâà èç LT .Åñëè íè îäèí èç ñèìâîëîâ ñëîâà β íå ðàâåí 4, è ñïðàâà ê íåìó ïðèìûêàåò ñèìâîë 4, òî ìû ìîæåì íàêà÷àòü âñ¼ ñëîâî β , îñòàâàÿñü ïðèýòîì â LT ; åñëè ïðè ýòîì ñïðàâà ê íåìó ïðèìûêàåò ñèìâîë 0 èëè 1, òîìîæíî íàêà÷àòü ëþáîé èç ñèìâîëîâ ñëîâà β , îñòàâàÿñü â LT .Ïîäñëó÷àé 3.2.
Ñëåâà ê β ïðèìûêàåò ñèìâîë 0 èëè 1. ýòîì ñëó÷àå ìû ìîæåì íàêà÷àòü âòîðîé ñèìâîë ñëîâàâβ,îñòàâàÿñüLT .Ñëó÷àé 4. µ(w) = Λ. ýòîì ñëó÷àå ïåðâàÿ áóêâà ñëîâàáóêâû ñëîâàβw íå ðàâíà 4, è íàêà÷èâàíèå âòîðîéñîõðàíèò ýòî ñâîéñòâî, ïîýòîìó âñå ïîëó÷èâøèåñÿ òàêèìñïîñîáîì ñëîâà áóäóò ëåæàòü âLT .Äîêàçàòü íåàâòîìàòíîñòü ñëåäóþùèõ ÿçûêîâ:1. {ap | p ïðîñòîå}2. {w ∈ {a, b}∗ | ÷èñëî áóêâ a â ñëîâå w ðàâíî ÷èñëó áóêâ b}3.
{w ∈ {a, b}∗ | ÷èñëî áóêâ a â ñëîâå w ðàâíî óäâîåííîìó ÷èñëó áóêâ b}4. {am | m ∈ N}5. {w ∈ {a, b}∗ | ÷èñëî áóêâ a â ñëîâå w íà 2 áîëüøå ÷èñëà áóêâ b â í¼ì}Óïðàæíåíèÿ22.3. Íåäåòåðìèíèðîâàííûå àâòîìàòû2.325Íåäåòåðìèíèðîâàííûå àâòîìàòûÇäåñü áóäóò ðàññìîòðåíû òàê íàçûâàåìûå íåäåòåðìèíèðîâàííûå àâòîìàòû ñî ñêà÷êàìè è êàê ÷àñòíûé ñëó÷àé íåäåòåðìèíèðîâàííûå àâòîìàòû. Êàê âûÿñíèòñÿ, ýòè àâòîìàòû îïðåäåëÿþò òîò æå ñàìûé êëàññÿçûêîâ, ÷òî è îáû÷íûå êîíå÷íûå àâòîìàòû. Ïîëüçà îò íèõ ñîñòîèò â òîì,÷òî îíè ïðåäîñòàâëÿþò ãîðàçäî áîëüøå óäîáñòâ äëÿ äîêàçàòåëüñòâà àâòîìàòíîñòè òîãî èëè èíîãî ÿçûêà: êàê ïðàâèëî, íåäåòåðìèíèðîâàííûéàâòîìàò äëÿ ðàñïîçíàâàíèÿ ÿçûêà áûâàåò ãîðàçäî ëåã÷å ïîñòðîèòü, ÷åìïðîñòî êîíå÷íûé àâòîìàò.Ñíà÷àëà ìû íåôîðìàëüíî îõàðàêòåðèçóåì íåäåòåðìèíèðîâàííûå àâòîìàòû. Îòëè÷èå íåäåòåðìèíèðîâàííûõ àâòîìàòîâ îò îáû÷íûõ ñîñòîèò âòîì, ÷òî â ýòèõ àâòîìàòàõ âìåñòî îäíîçíà÷íî çàäàííîãî ñîñòîÿíèÿt(s, a),s ïðè ïîñòóïëåíèè íàâõîä ñèìâîëà a, îïðåäåëÿåòñÿ íåêîòîðîå ìíîæåñòâî âîçìîæíûõ ñîñòîÿíèé T (s, a) äëÿ òàêîãî ïåðåõîäà.
 ÷àñòíîñòè, ýòî ìíîæåñòâî ìîæåòâ êîòîðîå ñëåäóåò ïåðåéòè èç òåêóùåãî ñîñòîÿíèÿñîäåðæàòü âñåãî îäèí ýëåìåíò (è òîãäà ñëåäóþùåå ñîñòîÿíèå, êàê è ðàíåå, çàäàíî îäíîçíà÷íî), ìîæåò áûòü ïóñòûì (è òîãäà íèêàêîé ïåðåõîäâîîáùå íåâîçìîæåí), íó è, êîíå÷íî, îíî ìîæåò ñîäåðæàòü áîëåå îäíîãîýëåìåíòà, è òîãäà ó íàñ åñòü âîçìîæíîñòü ïåðåéòè â ëþáîå èç ñîñòîÿíèéèç ìíîæåñòâàT (s, a)!Ìû òàêæå äîïóñêàåì, ÷òîáû ó íåäåòåðìèíèðîâàí-íîãî àâòîìàòà áûëî áîëåå îäíîãî íà÷àëüíîãî ñîñòîÿíèÿ ëèáî âîîáùå íåáûëî íè îäíîãî.Ìû ïîéä¼ì, îäíàêî, åù¼ äàëüøå ïî ïóòè îáîáùåíèÿ ïîíÿòèÿ êîíå÷íîãî àâòîìàòà, à èìåííî, ðàçðåøèì â îòäåëüíûõ ñëó÷àÿõ ïåðåõîäû â ñëåäóþùèå ñîñòîÿíèÿ âîîáùå áåç ïîñòóïëåíèÿ íà âõîä êàêèõëèáî ñèìâîëîâ,ñêà÷êè.
![](https://s.studizba.com/z.php?f=/templates/si/i/noavatar.png&w=100&h=100&t=1"){kind=avatar}
