1610906281-d25a58898a45262b0b837c281ba962eb (Лекции Когабаев Соболева), страница 5

Ïîñêîëüêó íà÷àëüíîå ñîñòîÿíèå ÿâëÿåòñÿ åäèíñòâåííûì âûäåëåííûì, çàêëþ÷àåì, ÷òî L(A) = {a, aa, ab, aba}∗ . Çàìåòèì, ÷òî ñëîâà aa è aba ìîæíîâûðàçèòü ÷åðåç ñëîâà a è ab ñëåäóþùèì îáðàçîì: aa = a·a, aba = ab·a. Ïîýòîìóàâòîìàò ðàñïîçíàåò ÿçûê L(A) = {a, ab}∗ .Äëÿ ëþáîãî ÿçûêà L ñëåäóþùèå óòâåðæäåíèÿ ýêâèâàëåíòíû:(1) L ðàñïîçíàåòñÿ íåêîòîðûì äåòåðìèíèðîâàííûì êîíå÷íûì àâòîìàòîì.(2) L ðàñïîçíàåòñÿ íåêîòîðûì íåäåòåðìèíèðîâàííûì êîíå÷íûì àâòîìàòîì.(3) L ðàñïîçíàåòñÿ íåêîòîðûì íåäåòåðìèíèðîâàííûì êîíå÷íûì àâòîìàòîì ñïóñòûìè ïåðåõîäàìè.Äîêàçàòåëüñòâî.

Èìïëèêàöèè (1) ⇒ (2) è (2) ⇒ (3) î÷åâèäíû. Äîêàæåì ñïðàâåäÒåîðåìà 9.ëèâîñòü èìïëèêàöèè (3) ⇒ (1).Ïóñòü A = hQ, A, ∆, q0 , F i ïðîèçâîëüíûé Λ-í.ê.à., ðàñïîçíàþùèé ÿçûê L. Äëÿëþáîãî ñîñòîÿíèÿ q ∈ Q ââåä¼ì â ðàññìîòðåíèå ìíîæåñòâîΛΛΛΛE(q) = {q} ∪ {p ∈ Q | â A ñóùåñòâóåò ïóòü âèäà q −→ q1 −→ ... −→ qk −→ p}.Îïðåäåëèì ä.ê.à. A0 = hQ0 , A, δ, q00 , F 0 i ñëåäóþùèì îáðàçîì:a) Q0 = P (Q);á) q00 = E(q0 );â) F 0 = {q 0 ⊆ Q | q 0 ∩ F 6= ∅};ã) äëÿ ëþáîãî q 0 ⊆ Q è êàæäîãî a ∈ A ïîëîæèì (ñì.

ïîÿñíåíèå íà ðèñóíêå)δ(q 0 , a) =[[E(p).q∈q 0 p∈∆(q,a)20Ãëàâà II. Êîíå÷íûå àâòîìàòû è ôîðìàëüíûå ãðàììàòèêèi1a pq0iPP aPq1q21PPq iΛ - ip4p2i3p5p3p6Λ - ip7ΛiPaPPP Λ - iq iPq 0 = {q1 , q2 }∆(q1 , a) = {p1 , p2 }∆(q2 , a) = {p3 }E(p1 ) = {p1 , p4 , p7 }E(p2 ) = {p2 }E(p3 ) = {p3 , p5 , p6 }δ(q 0 , a) = {p1 , .

. . , p7 }Äîêàæåì, ÷òî äëÿ ëþáîãî ñëîâà w ∈ A∗ è ëþáûõ ñîñòîÿíèé p, q ∈ Q ñëåäóþùèåóñëîâèÿ ýêâèâàëåíòíû:(à)  Λ-í.ê.à. A ñóùåñòâóåò ïóòü, êîòîðûé íà÷èíàåòñÿ â q , çàêàí÷èâàåòñÿ â p, èâäîëü äóã êîòîðîãî ÷èòàåòñÿ ñëîâî w.(á)  ä.ê.à. A0 ñóùåñòâóåò ïóòü, êîòîðûé íà÷èíàåòñÿ â E(q), çàêàí÷èâàåòñÿ â íåêîòîðîì p0 3 p, è âäîëü äóã êîòîðîãî ÷èòàåòñÿ ñëîâî w.Çàìåòèì, ÷òî åñëè q íà÷àëüíîå ñîñòîÿíèå A è p âûäåëåííîå ñîñòîÿíèå A, òîóñëîâèå (à) ýêâèâàëåíòíî óñëîâèþ w ∈ L(A), à óñëîâèå (á) ýêâèâàëåíòíî óñëîâèþw ∈ L(A0 ).

Òàêèì îáðàçîì, L(A) = L(A0 ).Äîêàæåì èíäóêöèåé ïî äëèíå ñëîâà w ýêâèâàëåíòíîñòü óñëîâèé (à) è (á).10 . Ïóñòü |w| = 0, ò.å. w = Λ. Òîãäà óñëîâèå (à) ýêâèâàëåíòíî òîìó, ÷òî â Añóùåñòâóåò ïóòü âèäàΛΛΛΛq−→ q1 −→ ... −→ qk −→p(âêëþ÷àÿ ñëó÷àé, êîãäà ïóòü íå ñîäåðæèò äóã), ÷òî â ñâîþ î÷åðåäü ýêâèâàëåíòíîóñëîâèþ p ∈ E(q). Ïîêàæåì, ÷òî óñëîâèå p ∈ E(q) ýêâèâàëåíòíî (á). Äåéñòâèòåëüíî,åñëè p ∈ E(q), òî âçÿâ p0 = E(q), î÷åâèäíî ïîëó÷èì óñëîâèå (á). Åñëè æå â ä.ê.à.

A0ñóùåñòâóåò ïóòü, íà÷èíàþùèéñÿ â E(q), çàêàí÷èâàþùèéñÿ â íåêîòîðîì p0 3 p, âäîëüäóã êîòîðîãî ÷èòàåòñÿ ïóñòîå ñëîâî, òî ñ íåîáõîäèìîñòüþ p0 = E(q). Ñëåäîâàòåëüíîp ∈ E(q).20 . Äîïóñòèì, ýêâèâàëåíòíîñòü (à) è (á) óæå äîêàçàíà äëÿ ïðîèçâîëüíûõ ñëîâ wäëèíû k . Äîêàæåì ýêâèâàëåíòíîñòü (à) è (á) äëÿ ïðîèçâîëüíîãî ñëîâà w äëèíû k +1.Ïóñòü w = s1 .

. . sk sk+1 , ãäå si ∈ A.Ïóñòü äëÿ ñëîâà w âûïîëíÿåòñÿ óñëîâèå (à). Ñëåäîâàòåëüíî, ñóùåñòâóþò ñîñòîÿíèÿ r1 , r2 ∈ Q òàêèå, ÷òî â Λ-í.ê.à. A ñóùåñòâóåò ïóòüsk+1t1tmΛΛq −→. . . −−→ r1 −−−→ r2 −→ ... −→ p,ãäå t1 . . . tm = s1 . . . sk è m > k .  ÷àñòíîñòè, ñëîâî v = s1 . . . sk ÷èòàåòñÿ âäîëü äóãïóòè â A, êîòîðûé íà÷èíàåòñÿ â q è çàêàí÷èâàåòñÿ â r1 , ò.å. äëÿ ñëîâà v è ñîñòîÿíèéq è r1 âûïîëíÿåòñÿ óñëîâèå (à).  ñèëó èíäóêöèîííîãî ïðåäïîëîæåíèÿ, äëÿ v , q èr1 âûïîëíÿåòñÿ óñëîâèå (á), ò.å. â ä.ê.à.

A0 ñóùåñòâóåò ïóòü, êîòîðûé íà÷èíàåòñÿ âE(q), çàêàí÷èâàåòñÿ â íåêîòîðîì r10 3 r1 , è âäîëü äóã êîòîðîãî ÷èòàåòñÿ ñëîâî v :s1sk 0E(q) −→. . . −→r1 3 r1 .Òàê êàê r2 ∈ ∆(r1 , sk+1 ) è r1 ∈ r10 , òî E(r2 ) ⊆ δ(r10 , sk+1 ). Ïîñêîëüêó p ∈ E(r2 ),sk+1çàêëþ÷àåì, ÷òî p ∈ δ(r10 , sk+1 ). Ñëåäîâàòåëüíî â ä.ê.à. A0 ñóùåñòâóåò äóãà r10 −−−→ p0 ,ãäå p0 = δ(r10 , sk+1 ) è p0 3 p.Ÿ 6. Íåäåòåðìèíèðîâàííûå êîíå÷íûå àâòîìàòû ñ ïóñòûìè ïåðåõîäàìè21Òàêèì îáðàçîì, â A0 ñóùåñòâóåò ïóòü âèäàs1sk 0 sk+1 0E(q) −→. .

. −→r1 −−−→ p 3 p.Îòñþäà çàêëþ÷àåì, ÷òî ñëîâî w óäîâëåòâîðÿåò óñëîâèþ (á).Ïóñòü òåïåðü äëÿ ñëîâà w âûïîëíÿåòñÿ óñëîâèå (á). Ñëåäîâàòåëüíî, ñóùåñòâóåòñîñòîÿíèå r10 ∈ Q0 òàêîå, ÷òî â ä.ê.à. A0 ñóùåñòâóåò ïóòü âèäàs1sk 0 sk+1 0E(q) −→. . . −→r1 −−−→ p 3 p.SSÒàê êàê p0 = δ(r10 , sk+1 ) =E(r2 ) è p ∈ p0 , òî ñóùåñòâóþò ñîñòîÿíèÿr1 ∈r10 r2 ∈∆(r1 ,sk+1 )r1 ∈ è r2 ∈ ∆(r1 , sk+1 ) òàêèå, ÷òî p ∈ E(r2 ).Ïîñêîëüêó r1 ∈ r10 è â ä.ê.à.

A0 ñóùåñòâóåò ïóòür10s1sk 0E(q) −→. . . −→r1 ,òî äëÿ ñëîâà v = s1 . . . sk âûïîëíÿåòñÿ óñëîâèå (á). Ñëåäîâàòåëüíî, â ñèëó èíäóêöèîííîãî ïðåäïîëîæåíèÿ, äëÿ v è ñîñòîÿíèé q , r1 âûïîëíÿåòñÿ óñëîâèå (à), ò.å. â Λ-í.ê.à.A ñóùåñòâóåò ïóòüt1tmq −→. . .

−−→ r1 ,âäîëü äóã êîòîðîãî ÷èòàåòñÿ ñëîâî t1 . . . tm = s1 . . . sk = v (m > k ).Òàê êàê r2 ∈ ∆(r1 , sk+1 ), òî â A èìååòñÿ äóãàsk+1r1 −−−→ r2 .Òàê êàê p ∈ E(r2 ), òî â A íàéäåòñÿ ïóòüΛΛr2 −→ ... −→ p.Îêîí÷àòåëüíî ïîëó÷àåì ñóùåñòâîâàíèå â A ñëåäóþùåãî ïóòèsk+1t1tmΛΛq −→. . . −−→ r1 −−−→ r2 −→ ... −→ p,âäîëü äóã êîòîðîãî ÷èòàåòñÿ ñëîâî t1 . .

. tm sk+1 = w, ò.å. ñïðàâåäëèâî óñëîâèå (à).Òàêèì îáðàçîì, ïîñòðîåííûé ä.ê.à. A0 ðàñïîçíàåò ÿçûê L.(ïðîäîëæåíèå). Ïðèìåíèì àëãîðèòì èç äîêàçàòåëüñòâà òåîðåìû 9 ê Λ-í.ê.à.A èç ïðåäûäóùåãî ïðèìåðà ïîëó÷èì ñëåäóþùèé ä.ê.à. A0 , ýêâèâàëåíòíûé èñõîäíîìó A:Ïðèìåð{q }{q2 }{q ,q ,q }00 1 2aH di- id a3 QkkQQ6QQ aQ aaQQQ {q1 ,q2 }QQ iQ diia{q0 ,q1 }bbQQQQbQbQQQ bQs ?Qs iQ+Qd?a,b - iQk3Qb∅ Q {q0 ,q2 }QaQbQ i{q1 }22Ãëàâà II.

Êîíå÷íûå àâòîìàòû è ôîðìàëüíûå ãðàììàòèêèÇàìåòèì, ÷òî â ïîëó÷åííîì àâòîìàòå ñîñòîÿíèÿ {q1 }, {q2 }, {q0 , q1 } è {q1 , q2 } ÿâëÿþòñÿ íåäîñòèæèìûìè, ò.å. â íèõ íåâîçìîæíî ïîïàñòü èç íà÷àëüíîãî ñîñòîÿíèÿ.Íåäîñòèæèìûå ñîñòîÿíèÿ ìîæíî óäàëèòü èç àâòîìàòà, ïðè ýòîì ðàñïîçíàâàåìûéàâòîìàòîì ÿçûê íå èçìåíèòñÿ.{q0 }H ida{q0 ,q1 ,q2 }- id a6a bba,b - i∅Ÿ 7.?di?b{q0 ,q2 }Ñâîéñòâà àâòîìàòíûõ ÿçûêîâ äàííîì ïàðàãðàôå ìû äîêàæåì âàæíûå òåîðåòèêî-ìíîæåñòâåííûå ñâîéñòâà àâòîìàòíûõ ÿçûêîâ, à òàêæå ïîêàæåì, ÷òî ñóùåñòâóþò íåàâòîìàòíûå ÿçûêè.çàìêíóòî îòíîñèòåëüíîÃîâîðÿò, ÷òî ïîäìíîæåñòâî X ìíîæåñòâà Af : A → A, åñëè äëÿ ëþáûõ x1 , . . . , xn ∈ X èìååò ìåñòî f (x1 , .

. . , xn ) ∈ X .Îïðåäåëåíèå.îïåðàöèènÀâòîìàòíûå ÿçûêè çàìêíóòû îòíîñèòåëüíî îáúåäèíåíèÿ, ïåðåñå÷åíèÿ, äîïîëíåíèÿ, êîíêàòåíàöèè è çâ¼çäî÷êè Êëèíè.Äîêàçàòåëüñòâî. Äëÿ êàæäîé èç ïÿòè îïåðàöèé ìû íåôîðìàëüíî îïèøåì, êàê ïîÒåîðåìà 10.çàäàíûì àâòîìàòàì, ðàñïîçíàþùèì èñõîäíûå ÿçûêè, ïîñòðîèòü àâòîìàò, ðàñïîçíàþùèé ðåçóëüòàò ïðèìåíåíèÿ äàííîé îïåðàöèè ê èñõîäíûì ÿçûêàì. Çàìåòèì, ÷òî âñèëó òåîðåìû 9 äëÿ êàæäîãî èç ñëó÷àåâ äîñòàòî÷íî ñòðîèòü íåäåòåðìèíèðîâàííûéàâòîìàò ñ ïóñòûìè ïåðåõîäàìè.. Ïóñòü A1 , A2 äåòåðìèíèðîâàííûå êîíå÷íûå àâòîìàòû íàä àëôàâèòîì A.

Íàì íåîáõîäèìî îïðåäåëèòü àâòîìàò A òàêîé, ÷òî L(A) = L(A1 ) ∪ L(A2 ).Ìîæíî ñ÷èòàòü, ÷òî ìíîæåñòâà ñîñòîÿíèé A1 è A2 íå ïåðåñåêàþòñÿ, â ïðîòèâíîìñëó÷àå ñëåäóåò ïåðåèìåíîâàòü ñîñòîÿíèÿ.Àâòîìàò A ñòðîèòñÿ ñëåäóþùèì îáðàçîì (ñì. ñõåìó ïîñòðîåíèÿ íà ðèñóíêå):à) Ñîåäèíèì ãðàôè÷åñêèå äèàãðàììû àâòîìàòîâ A1 è A2 â îäíó, ââåäÿ íîâîåíà÷àëüíîå ñîñòîÿíèå q00 , è äîáàâèâ äâå äóãè, âûõîäÿùèå èç q00 , âõîäÿùèå â ñòàðûåíà÷àëüíûå ñîñòîÿíèÿ, è ïîìå÷åííûå ñèìâîëîì Λ. (Ñ÷èòàåì, ÷òî íà÷àëüíûå ñîñòîÿíèÿèñõîäíûõ àâòîìàòîâ ïåðåñòàþò áûòü òàêîâûì.)á) Ìíîæåñòâîì âûäåëåííûõ ñîñòîÿíèé A áóäåò îáúåäèíåíèå ìíîæåñòâ âûäåëåííûõ ñîñòîÿíèé àâòîìàòîâ A1 è A2 .ÎáúåäèíåíèåH iH iA1A2didiHHq00iA1dij iHΛHA2di*ΛH iHH23Ÿ 7.

Ñâîéñòâà àâòîìàòíûõ ÿçûêîâÒàêîå îïèñàíèå îäíîçíà÷íî çàäà¼ò àâòîìàò A. Ðàññìîòðèì ïðîèçâîëüíûé ïóòü ïîäóãàì àâòîìàòà A, êîòîðûé íà÷èíàåòñÿ â q00 è çàêàí÷èâàåòñÿ â âûäåëåííîì ñîñòîÿíèè. Ïåðâûì ïåðåõîäîì òàêîãî ïóòè îáÿçàí áûòü Λ-ïåðåõîä, à îñòàëüíûå ïåðåõîäûëèáî ïîëíîñòüþ ñîäåðæàòñÿ âíóòðè àâòîìàòà A1 , ëèáî ïîëíîñòüþ ñîäåðæàòñÿ âíóòðè àâòîìàòà A2 . Ñëåäîâàòåëüíî, ëþáîå ñëîâî, ðàñïîçíàâàåìîå A, ýòî ñëîâî, ðàñïîçíàâàåìîå A1 èëè A2 .

Ñ äðóãîé ñòîðîíû, ëþáîå ñëîâî, ðàñïîçíàâàåìîå A1 èëè A2 ,î÷åâèäíî, ðàñïîçíàåòñÿ àâòîìàòîì A. Òàêèì îáðàçîì, àâòîìàò A èñêîìûé.. Ïóñòü ä.ê.à. A = hQ, A, δ, q0 , F i ðàñïîçíàåò ÿçûê L, ò. å. äëÿ ëþáîãîñëîâà w ∈ A∗ èìååò ìåñòî ýêâèâàëåíòíîñòü w ∈ L ⇐⇒ δ ∗ (q0 , w) ∈ F . Îòñþäàâûòåêàåò ýêâèâàëåíòíîñòü w ∈/ L ⇐⇒ δ ∗ (q0 , w) ∈/ F . Äðóãèìè ñëîâàìè, èìååò∗∗ìåñòî óñëîâèå w ∈ A \ L ⇐⇒ δ (q0 , w) ∈ Q \ F . Îòñþäà ñëåäóåò, ÷òî ä.ê.à A0 =hQ, A, δ, q0 , Q \ F i ðàñïîçíàåò äîïîëíåíèå L = A∗ \ L.. Çàìêíóòîñòü àâòîìàòíûõ ÿçûêîâ îòíîñèòåëüíî ïåðåñå÷åíèÿ ñëåäóåò èç çàìêíóòîñòè îòíîñèòåëüíî îáúåäèíåíèÿ è äîïîëíåíèÿ, à òàêæå èç òåîðåòèêîìíîæåñòâåííîãî òîæäåñòâà A ∩ B = A ∪ B ..

Ïóñòü A1 , A2 äåòåðìèíèðîâàííûå êîíå÷íûå àâòîìàòû íàä àëôàâèòîì A, ìíîæåñòâà ñîñòîÿíèé êîòîðûõ íå ïåðåñåêàþòñÿ. Ïîñòðîèì àâòîìàò A,ðàñïîçíàþùèé ÿçûê L(A1 )L(A2 ), ñëåäóþùèì îáðàçîì (ñì. ñõåìó ïîñòðîåíèÿ íà ðèñóíêå):à) Ñîåäèíèì ãðàôè÷åñêèå äèàãðàììû àâòîìàòîâ A1 è A2 , äîáàâèâ íîâûå äóãè,âûõîäÿùèå èç âñåõ âûäåëåííûõ ñîñòîÿíèé àâòîìàòà A1 , âõîäÿùèå â íà÷àëüíîå ñîñòîÿíèå àâòîìàòà A2 , è ïîìå÷åííûå ñèìâîëîì Λ.á) Íà÷àëüíûì ñîñòîÿíèåì ïîëó÷åííîãî àâòîìàòà îáúÿâëÿåòñÿ íà÷àëüíîå ñîñòîÿíèå A1 .â) Âûäåëåííûìè ñîñòîÿíèÿìè ïîëó÷åííîãî àâòîìàòà îáúÿâëÿþòñÿ âñå âûäåëåííûå ñîñòîÿíèÿ àâòîìàòà A2 .