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

Òàêèì îáðàçîì, âäîëü îäíèõ âåòâåé âû÷èñëåíèé àâòîìàò ìîæåò ïðî÷èòàòü âñå âõîäíûå ñèìâîëû è îñòàíîâèòñÿ â âûäåëåííîì ñîñòîÿíèè, âäîëüäðóãèõ ìîæåò ïðî÷èòàòü âñå ñèìâîëû, íî îñòàíîâèòñÿ â íåâûäåëåííîì ñîñòîÿíèè,âäîëü òðåòüèõ âåòâåé ðàáîòà àâòîìàòà ¾îáðûâàåòñÿ íà ïîëóñëîâå¿.Ïåðåéäåì ê ôîðìàëüíûì îïðåäåëåíèÿì, ñâÿçàííûì ñ íåäåòåðìèíèðîâàííûìè àâòîìàòàìè.Íåäåòåðìèíèðîâàííûì êîíå÷íûì àâòîìàòîì (ñîêðàùåííî í.ê.à.)íàçûâàåòñÿ óïîðÿäî÷åííàÿ ïÿòåðêà A = hQ, A, ∆, q0 , F i, â êîòîðîé Q, A, q0 , F îïðåäåëÿþòñÿ è íàçûâàþòñÿ òàê æå, êàê â äåòåðìèíèðîâàííîì ñëó÷àå, à ôóíêöèÿ ïåðåõîäîâÎïðåäåëåíèå.∆ ÿâëÿåòñÿ ôóíêöèåé âèäà ∆ : Q × A → P (Q), ãäå P (Q) ìíîæåñòâî âñåõ ïîäìíîæåñòâ Q (ñì.

àêñèîìó ñòåïåíè èç Ÿ 1).Ãðàôè÷åñêîå èçîáðàæåíèå íåäåòåðìèíèðîâàííûõ àâòîìàòîâÏðè ãðàôè÷åñêîì èçîáðàæåíèè íåäåòåðìèíèðîâàííûõ àâòîìàòîâ èñïîëüçóþòñÿòå æå îáîçíà÷åíèÿ, ÷òî è â äåòåðìèíèðîâàííîì ñëó÷àå. Ïðè ýòîì èç îäíîãî ñîñòîÿíèÿ àâòîìàòà ìîãóò âûõîäèòü ñðàçó íåñêîëüêî (èëè íèñêîëüêî) ñòðåëîê, ïîìå÷åííûõîäíîé è òîé æå áóêâîé àëôàâèòà. Äóãà, âûõîäÿùàÿ èç ñîñòîÿíèÿ q , âõîäÿùàÿ â ñîñòîÿíèå q 0 , ïîìå÷åííàÿ ñèìâîëîì a, ïðèñóòñòâóåò â ñõåìå àâòîìàòà òîãäà è òîëüêîòîãäà, êîãäà q 0 ∈ ∆(q, a).Íàïðèìåð, àâòîìàò A = hQ, A, ∆, q0 , F i, ãäå A = {a, b}, Q = {q0 , q1 , q2 },F = {q2 }, à ôóíêöèÿ ïåðåõîäîâ çàäàåòñÿ ñîîòíîøåíèÿìèÏðèìåð.∆(q0 , a) = {q0 },∆(q0 , b) = {q0 , q1 },∆(q1 , a) = ∅,∆(q1 , b) = {q2 },∆(q2 , a) = ∅,∆(q2 , b) = ∅,èìååò ñëåäóþùåå ãðàôè÷åñêîå èçîáðàæåíèå:a,b?H iq0Îïðåäåëåíèå.b - iq1b - diq2Ïóòü â íåäåòåðìèíèðîâàííîì êîíå÷íîì àâòîìàòå A=hQ, A, ∆, q0, F iîïðåäåëÿåòñÿ è îáîçíà÷àåòñÿ òàê æå, êàê â äåòåðìèíèðîâàííîì ñëó÷àå, íóæíî ëèøüóñëîâèå δ(ri , si+1 ) = ri+1 çàìåíèòü íà óñëîâèå ri+1 ∈ ∆(ri , si+1 ).ðàñïîçíà¼òÃîâîðÿò, ÷òî í.ê.à.

A=hQ, A, ∆, q0 , F iñëîâî s1 s2 . . . sk ∈A , åñëè ñóùåñòâóåò ïîñëåäîâàòåëüíîñòü ñîñòîÿíèé q0 = r0 , r1 , . . . , rk òàêàÿ, ÷òîÎïðåäåëåíèå.∗r1 ∈ ∆(r0 , s1 ),r2 ∈ ∆(r1 , s2 ),......rk ∈ ∆(rk−1 , sk ),è ïðè ýòîì rk ∈ F .16Ãëàâà II. Êîíå÷íûå àâòîìàòû è ôîðìàëüíûå ãðàììàòèêèÄðóãèìè ñëîâàìè, ñëîâî w = s1 s2 . . .

sk ðàñïîçíà¼òñÿ àâòîìàòîì, åñëè â í¼ì ñóùåñòâóåò õîòÿ áû îäèí ïóòüs1s2skq0 = r0 −→r1 −→. . . −→rk ∈ Fòàêîé, ÷òî îí íà÷èíàåòñÿ â íà÷àëüíîì ñîñòîÿíèè q0 , âäîëü åãî äóã ÷èòàåòñÿ ñëîâîs1 s2 . . . sk (â íåäåòåðìèíèðîâàííîì àâòîìàòå òàêîé ïóòü îïðåäåëÿåòñÿ íåîäíîçíà÷íîïî ñëîâó w) è çàêàí÷èâàåòñÿ â íåêîòîðîì âûäåëåííîì ñîñòîÿíèè.Îïðåäåëåíèå.Êàê è ðàíüøå, ÷åðåç L(A) îáîçíà÷àåòñÿA.åìûõ àâòîìàòîìÿçûê âñåõ ñëîâ, ðàñïîçíàâà-(ïðîäîëæåíèå). Àâòîìàò èç ïðåäûäóùåãî ïðèìåðà ðàñïîçíà¼ò â òî÷íîñòèâñå ñëîâà â àëôàâèòå {a, b}, êîòîðûå èìåþò ñóôôèêñ bb, ò. å. L(A) = {w ∈ {a, b}∗ |∃v ∈ {a, b}∗ (w = vbb)}. Äåéñòâèòåëüíî, ëþáîé ïóòü, çàêàí÷èâàþùèéñÿ â âûäåëåíbbíîì ñîñòîÿíèè äàííîãî àâòîìàòà, îáÿçàí ñîäåðæàòü ó÷àñòîê q0 →− q1 →− q2 .

Îòñþäàñëåäóåò, ÷òî ñëîâà, ðàñïîçíàâàåìûå A, äîëæíû ñîäåðæàòü õîòÿ áû îäíî âõîæäåíèåïîäñëîâà bb. Ïîñêîëüêó èç âûäåëåííîãî ñîñòîÿíèÿ íåò âûõîäÿùèõ ñòðåëîê, òî ëþáîéïóòü, ñîäåðæàùèé îïèñàííûé âûøå ó÷àñòîê, îáðûâàåòñÿ êàê ðàç ïîñëå ïðîõîæäåíèÿäàííîãî ó÷àñòêà. Îòñþäà ñëåäóåò, ÷òî â ñëîâàõ, ðàñïîçíàâàåìûõ àâòîìàòîì, ïîñëåêðàéíåãî ñïðàâà âõîæäåíèÿ ïîäñëîâà bb íåò áóêâ.ÏðèìåðÄëÿ ëþáîãî íåäåòåðìèíèðîâàííîãî êîíå÷íîãî àâòîìàòà A ñóùåñòâóåò äåòåðìèíèðîâàííûé êîíå÷íûé àâòîìàò A0 òàêîé, ÷òî L(A) =L(A0 ).Äîêàçàòåëüñòâî.

Ïóñòü A = hQ, A, ∆, q0, F i èñõîäíûé í.ê.à. Îïðåäåëèì ñëåäóþÒåîðåìà 8(î äåòåðìèíèçàöèè).ùèé ä.ê.à. A0 = hQ0 , A, δ, q00 , F 0 i (ñì. ïðèìåð íà ðèñóíêå):à) Q0 = P (Q);Sá) δ(q 0 , a) =∆(r, a), ãäå q 0 ∈ Q0 è a ∈ A;r∈q 0â) = {q0 };ã) F = {q 0 ∈ Q0 | q 0 ∩ F 6= ∅}.q000A:a? a, b - iH idq0q1A0 :HHH i{q }Z0aa- id?{q0 , q1 }ZbbZZ~ ?Zdia, b - ia,b{q1 }∅Äîêàæåì, ÷òî äëÿ ëþáîãî ñëîâà w ∈ A∗ è ëþáûõ ñîñòîÿíèé p, q ∈ Q ñëåäóþùèåóñëîâèÿ ýêâèâàëåíòíû:(à) Â í.ê.à.

A ñóùåñòâóåò ïóòü, êîòîðûé íà÷èíàåòñÿ â q , çàêàí÷èâàåòñÿ â p, è âäîëüäóã êîòîðîãî ÷èòàåòñÿ ñëîâî w.(á)  ä.ê.à. A0 ñóùåñòâóåò ïóòü, êîòîðûé íà÷èíàåòñÿ â {q}, çàêàí÷èâàåòñÿ â íåêîòîðîì p0 3 p, è âäîëü äóã êîòîðîãî ÷èòàåòñÿ ñëîâî w.Ÿ 5. Íåäåòåðìèíèðîâàííûå êîíå÷íûå àâòîìàòû17Çàìåòèì, ÷òî åñëè q íà÷àëüíîå ñîñòîÿíèå A è p âûäåëåííîå ñîñòîÿíèå A, òîóñëîâèå (à) ýêâèâàëåíòíî óñëîâèþ w ∈ L(A), à óñëîâèå (á) ýêâèâàëåíòíî óñëîâèþw ∈ L(A0 ).

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

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

Ñëåäîâàòåëüíî, ñóùåñòâóåò ñîñòîÿíèår ∈ Q òàêîå, ÷òî â í.ê.à. A ñóùåñòâóåò ïóòüsk+1s1skq −→. . . −→r −−−→ p. ÷àñòíîñòè, ñëîâî v = s1 . . . sk ÷èòàåòñÿ âäîëü äóã ïóòè â A, êîòîðûé íà÷èíàåòñÿ âq è çàêàí÷èâàåòñÿ â r, ò.å. äëÿ ñëîâà v è ñîñòîÿíèé q è r âûïîëíÿåòñÿ óñëîâèå (à). ñèëó èíäóêöèîííîãî ïðåäïîëîæåíèÿ, äëÿ v , q è r âûïîëíÿåòñÿ óñëîâèå (á), ò.å.â ä.ê.à. A0 ñóùåñòâóåò ïóòü, êîòîðûé íà÷èíàåòñÿ â {q}, çàêàí÷èâàåòñÿ â íåêîòîðîìr0 3 r, è âäîëü äóã êîòîðîãî ÷èòàåòñÿ ñëîâî v :s1sk 0{q} −→.

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

. −→r −−−→ p 3 p.SÒàê êàê p0 = δ(r0 , sk+1 ) =∆(r, sk+1 ) è p ∈ p0 , òî ñóùåñòâóåò ñîñòîÿíèå r ∈ r0r∈r0òàêîå, ÷òî p ∈ ∆(r, sk+1 ).Ïîñêîëüêó r ∈ r0 è â ä.ê.à. A0 ñóùåñòâóåò ïóòüs1sk 0{q} −→. . . −→r,òî äëÿ ñëîâà v = s1 . . . sk âûïîëíÿåòñÿ óñëîâèå (á). Ñëåäîâàòåëüíî, â ñèëó èíäóêöèîííîãî ïðåäïîëîæåíèÿ, äëÿ v è ñîñòîÿíèé q , r âûïîëíÿåòñÿ óñëîâèå (à), ò.å. â í.ê.à.A ñóùåñòâóåò ïóòüs1skq −→.

. . −→r.18Ãëàâà II. Êîíå÷íûå àâòîìàòû è ôîðìàëüíûå ãðàììàòèêèÒàê êàê p ∈ ∆(r, sk+1 ), òî â A èìååòñÿ äóãàsk+1r −−−→ p.Îêîí÷àòåëüíî ïîëó÷àåì ñóùåñòâîâàíèå â A ñëåäóþùåãî ïóòèsk+1s1skq −→. . . −→r −−−→ p,âäîëü äóã êîòîðîãî ÷èòàåòñÿ ñëîâî s1 . . . sk sk+1 = w, ò.å. ñïðàâåäëèâî óñëîâèå (à).Òàêèì îáðàçîì, ïîñòðîåííûé ä.ê.à. A0 ðàñïîçíà¼ò ÿçûê L(A).Ÿ 6.Íåäåòåðìèíèðîâàííûå êîíå÷íûå àâòîìàòû ñ ïóñòûìè ïåðåõîäàìè íåêîòîðûõ èñòî÷íèêàõ (ñì., íàïðèìåð, [4],[13]) èñïîëüçóåòñÿ áîëåå øèðîêèé êëàññíåäåòåðìèíèðîâàííûõ êîíå÷íûõ àâòîìàòîâ, êîòîðûé îòëè÷àåòñÿ îò ââåäåííîãî âûøå òåì, ÷òî ôóíêöèÿ ïåðåõîäîâ ∆ èìååò âèä ∆ : Q × (A ∪ {Λ}) → P (Q).

Àâòîìàòûäàííîãî òèïà íàçûâàþò, ïîñêîëüêó â íèõ äîïóñêàþòñÿ äóãè, ïîìå÷åííûå ïóñòûì ñëîâîì Λ. Íàëè÷èå äóãè, ïîìå÷åííîé Λ, âûõîäÿùåéèç ñîñòîÿíèå q è âõîäÿùåé â ñîñòîÿíèå q 0 , îçíà÷àåò, ÷òî àâòîìàò, íàõîäÿñü â ñîñòîÿíèèq , ìîæåò ïåðåéòè â ñîñòîÿíèå q 0 , íå ñ÷èòûâàÿ ñèìâîëà ñ ëåíòû. Ïîëüçóÿñü òåðìèíàìèèç ïðîãðàììèðîâàíèÿ, ìîæíî ñêàçàòü, ÷òî â òàêîé ñèòóàöèè àâòîìàò îñóùåñòâëÿåòèç q â q 0 .Òàêîé âèä àâòîìàòîâ óäîáíî èñïîëüçîâàòü ïðè äîêàçàòåëüñòâå íåêîòîðûõ ñâîéñòâ.Îäíàêî äîáàâëåíèå Λ-ïåðåõîäîâ â îïðåäåëåíèå íåäåòåðìèíèðîâàííîãî àâòîìàòà íåèçìåíÿåò êëàññ àâòîìàòíûõ ÿçûêîâ, ò. å. ÿçûê ðàñïîçíàåòñÿ íåêîòîðûì íåäåòåðìèíèðîâàííûì êîíå÷íûì àâòîìàòîì (ñîãëàñíî íàøåìó îïðåäåëåíèþ) òîãäà è òîëüêîòîãäà, êîãäà îí ðàñïîçíàåòñÿ íåêîòîðûì íåäåòåðìèíèðîâàííûì êîíå÷íûì àâòîìàòîì ñ Λ-ïåðåõîäàìè.àâòîìàòàìè ñ ïóñòûìè ïåðåõîäàìèáåçóñëîâíûé ïåðåõîäÍåäåòåðìèíèðîâàííûì êîíå÷íûì àâòîìàòîì ñ ïóñòûìè ïåðåõîäàìè (ñîêðàùåííî Λ-í.ê.à.) íàçûâàåòñÿ óïîðÿäî÷åííàÿ ïÿò¼ðêà A = hQ, A, ∆, q0, F i,â êîòîðîé Q, A, q0 , F îïðåäåëÿþòñÿ è íàçûâàþòñÿ òàê æå êàê ðàíüøå, à ôóíêöèÿïåðåõîäîâ ∆ ÿâëÿåòñÿ ôóíêöèåé âèäà ∆ : Q × (A ∪ {Λ}) → P (Q).Ïóòü â Λ-í.ê.à.

A = hQ, A, ∆, q0, F i îïðåäåëÿåòñÿ è îáîçíà÷àåòñÿ òàêÎïðåäåëåíèå.Îïðåäåëåíèå.æå, êàê â ñëó÷àå íåäåòåðìèíèðîâàííîãî êîíå÷íîãî àâòîìàòà. Çàìåòèì ëèøü, ÷òî âóñëîâèè ri+1 ∈ ∆(ri , si+1 ) äîïóñêàåòñÿ si+1 = Λ.ðàñïîçíà¼òÃîâîðÿò, ÷òî Λ-í.ê.à. A = hQ, A, ∆, q0 , F iñëîâî w =s1 s2 . . . sk , ãäå si áóêâû àëôàâèòà A, åñëè â A ñóùåñòâóåò õîòÿ áû îäèí ïóòüÎïðåäåëåíèå.t1t2tmr0 −→r1 −→.

. . −−→ rmòàêîé, ÷òî îí íà÷èíàåòñÿ â íà÷àëüíîì ñîñòîÿíèè r0 , çàêàí÷èâàåòñÿ â íåêîòîðîì âûäåëåííîì ñîñòîÿíèè rm ∈ F , è âäîëü åãî äóã ÷èòàåòñÿ ñëîâî t1 t2 . . . tm = s1 s2 . . . sk ,ïðè÷¼ì m > k , ò. å. íåêîòîðûå èç ñèìâîëîâ t1 , . . . , tm ìîãóò áûòü ïóñòûìè.Ÿ 6.

Íåäåòåðìèíèðîâàííûå êîíå÷íûå àâòîìàòû ñ ïóñòûìè ïåðåõîäàìèÎïðåäåëåíèå.ðàñïîçíàâàåìûõÄëÿ ïðîèçâîëüíîãî Λ-í.ê.à. A ÷åðåç L(A) îáîçíà÷èìA.19ÿçûê âñåõ ñëîâ,Àâòîìàò A = hQ, A, ∆, q0 , F i, ãäå A = {a, b}, Q = {q0 , q1 , q2 }, F = {q0 }, àôóíêöèÿ ïåðåõîäîâ çàäàåòñÿ ñîîòíîøåíèÿìèÏðèìåð.∆(q0 , a) = {q1 , q2 },∆(q0 , b) = ∅,∆(q0 , Λ) = ∅,∆(q1 , a) = ∅,∆(q1 , b) = {q2 },∆(q1 , Λ) = ∅,∆(q2 , a) = {q0 },∆(q2 , b) = ∅,∆(q2 , Λ) = {q0 },èìååò ñëåäóþùåå ãðàôè÷åñêîå èçîáðàæåíèå:q0Hiy dO@@aq1a- iΛa@b@R i@q2Äàííûé àâòîìàò ñîäåðæèò ÷åòûðå ïóòè, êîòîðûå íà÷èíàþòñÿ è çàêàí÷èâàþòñÿ âñîñòîÿíèè q0 , íî â ïðîìåæóòêàõ íå ïîïàäàþò â q0 . Âäîëü ýòèõ ïóòåé ðàñïîçíàþòñÿñëîâà a, aa, ab è aba.