1610906281-ae38486ec859a3a9dcd398b8f34f26aa (824377), страница 4
Текст из файла (страница 4)
 ýòîì ñëó÷àå ìû ïîëó÷èì òàê íàçûâàåìûå íåäåòåðìèíèðîâàííûå àâòîìàòû ñî ñêà÷êàìè, êîòîðûì è ïîñâÿù¼í äàííûéòàê íàçûâàåìûåïàðàãðàô.×òîáû ïîä÷åðêíóòü îòëè÷èå îáû÷íûõ êîíå÷íûõ àâòîìàòîâ îò íåäåòåðìèíèðîâàííûõ àâòîìàòîâ ñî ñêà÷êàìè, èõ èíîãäà íàçûâàþò òàêæåòåðìèíèðîâàííûìè êîíå÷íûìè àâòîìàòàìè.äå- äàëüíåéøåì, åñëè ðå÷üçàéä¼ò î ïðîñòî àâòîìàòàõ, òî áóäóò ïîäðàçóìåâàòüñÿ îáû÷íûå êîíå÷íûåàâòîìàòû.Ïåðåéä¼ì ê îïðåäåëåíèÿì. Çàôèêñèðóåì êàêîéëèáî ñèìâîëε.Óäîá-íî áóäåò ïðåäñòàâëÿòü ñåáå, ÷òî êàæäûé ðàç, êîãäà ìû îñóùåñòâëÿåìñêà÷îê (ïåðåõîä èç îäíîãî ñîñòîÿíèÿ â äðóãîå áåç ïîëó÷åíèÿ íà âõîäåêàêîãîëèáî ñèìâîëà), òî íà ñàìîì äåëå ìû îñóùåñòâëÿåì çàìåíó ñîñòî-Ãëàâà 2.
Àâòîìàòíûå ÿçûêè26ÿíèÿ êàê áû â ðåçóëüòàòå ïîëó÷åíèÿ íà âõîäå ýòîãî îñîáåííîãî ñèìâîëàε.Ââèäó ýòîãî ìû âcþäó â äàëüíåéøåì ïðåäïîëàãàåì, ÷òîεíå ïðèíàä-ëåæèò íè îäíîìó èç ðàññìàòðèâàåìîìûõ íàìè àëôàâèòîâ.Íåäåòåðìèíèðîâàííûì êîíå÷íûì àâòîìàòîì ñîñêà÷êàìè íàçûâàåòñÿ ïÿò¼ðêà A = hS, A, I, T, F i, â êîòîðîéÎïðåäåëåíèå 2.3.1• S êîíå÷íîå ìíîæåñòâî ñîñòîÿíèé,• A êîíå÷íûé àëôàâèò, ïðè ýòîì ε ∈/ A,• I ⊆ S ìíîæåñòâî íà÷àëüíûõ ñîñòîÿíèé,• T ôóíêöèÿ ïåðåõîäà, êîòîðàÿ ïî ëþáûì s ∈ S è a ∈ A ∪ {ε}âûäà¼ò íåêîòîðîå ïîäìíîæåñòâî S , T (s, a) ⊆ S ,• F ìíîæåñòâî âûäåëåííûõ (çàêëþ÷èòåëüíûõ) ñîñòîÿíèé.Êàê è äåòåðìèíèðîâàííûå àâòîìàòû, íåäåòåðìèíèðîâàííûå àâòîìàòû ñî ñêà÷êàìè äîïóñêàþò ãðàôè÷åñêèå èçîáðàæåíèÿ.
Ïðè ýòîì òî÷íîòàê æå, êàê è ðàíåå, èõ ñîñòîÿíèÿ îáîçíà÷àþòñÿ êðóæêàìè, âûäåëåííûåñîñòîÿíèÿ äâîéíûìè êðóæêàìè, íà÷àëüíûå ñîñòîÿíèÿ êðóæêàìè ñâõîäÿùèìè â íèõ ñòðåëêàìè áåç ïîìåòîê, à ïåðåõîäû ñòðåëêàìè, ïîìå÷åííûìè ñèìâîëàìè èçA.Êðîìå òîãî, ïåðåõîäû ìîãóò îáîçíà÷àòüñÿsâq ∈ T (s, a),ñòðåëêàìè âîîáùå áåç ïîìåòîê. Òàê ñòðåëêà, âûõîäÿùàÿ èç ñîñòîÿíèÿa ∈ A áóäåò îçíà÷àòü, ÷òîà ñòðåëêà èç ñîñòîÿíèÿ s â ñîñòîÿíèå q , íå ïîìå÷åííàÿ íèêàêèì ñèìâîëîì, áóäåò îçíà÷àòü, ÷òî q ∈ T (s, ε). Èç îäíîãî ñîñòîÿíèÿ ìîæåò îäíîâðå-ñîñòîÿíèåq,ïîìå÷åííàÿ ñèìâîëîììåííî âûõîäèòü íå îäíà, à íåñêîëüêî ñòðåëîê, ïîìå÷åííûõ îäíèì è òåìæå ñèìâîëîì, íåñêîëüêî ñòðåëîê, íå ïîìå÷åííûõ âîîùå íèêàêèìè ñèìâîëàìè èëè âîîáùå íå âûõîäèòü íè îäíîé.
 ñëó÷àå, êîãäà èç ñîñòîÿíèÿsâ ñîñòîÿíèåqâûõîäèò íåñêîëüêî ñòðåëîê, ïîìå÷åííûõ ðàçíûìè ñèì-âîëàìè, èíîãäà äëÿ óìåíüøåíèÿ ãðîìîçäêîñòè ìû áóäåì ðèñîâàòü îäíóñòðåëêó è ïîìå÷àòü å¼ íåñêîëüêèìè ñèìâîëàìè (òåì íå ìåíåå, ïîäðàçóìåâàÿ, ÷òî ñòðåëîê íà ñàìîì äåëå íåñêîëüêî).Íà ðèñóíêå 2.8 ïðèâåä¼í ïðèìåð èçîáðàæåíèÿ íåäåòåðìèíèðîâàííîãî àâòîìàòà ñî ñêà÷êàìè. Èç ðèñóíêà âèäíî, ÷òî èç ñîñòîÿíèÿ 1 ìîæíîïîïàñòü â ñîñòîÿíèå 3 ïðè ïîñòóïëåíèè íà âõîä ñèìâîëîâaèëèbèëèâîîáùå áåç ïîñòóïëåíèÿ êàêîãîëèáî ñèìâîëà, â ðåçóëüòàòå ñêà÷êà, èç2.3. Íåäåòåðìèíèðîâàííûå àâòîìàòû27DEEÐèñ.
2.8: Ïðèìåð èçîáðàæåíèÿ íåäåòåðìèíèðîâàííîãî àâòîìàòà ñî ñêà÷êàìèñîñòîÿíèÿ 1 ìîæíî ïîïàñòü â ðåçóëüòàòå ñêà÷êà â ñîñòîÿíèå 2, èç ñîñòîÿíèÿ 2 ìîæíî ïîïàñòü â ðåçóëüòàòå ñêà÷êà â ñîñòîÿíèå 1, à èç ñîñòîÿíèÿ3 òîëüêî â ñîñòîÿíèå 2 è òîëüêî ïðè ïîñòóïëåíèè íà âõîä ñèìâîëà b.∗Íåôîðìàëüíî ìû áóäåì ãîâîðèòü, ÷òî ñëîâî w ∈ A ðàñïîçíà¼òñÿ(èëè ïðèíèìàåòñÿ) íåäåòåðìèíèðîâàííûì àâòîìàòîì ñî ñêà÷êàìè A,åñëè â ýòîì àâòîìàòå íàéä¼òñÿ õîòÿ áû îäèí ïóòü, ïðîõîäÿùèé ïî åãîñòðåëêàì è âåäóùèé èç íåêîòîðîãî íà÷àëüíîãî ñîñòîÿíèÿ â íåêîòîðîåâûäåëåííîå ñîñòîÿíèå, ïðè÷¼ì òàêîé, ÷òî ñèìâîëû, ïîñëåäîâàòåëüíî ðàñ-w, èíà÷å ãîâîðÿ, åñëèw ïðî÷èòûâàåòñÿ âäîëü íåêîòîðîãî ïóòè èç íåêîòîðîãî íà÷àëüíîãîïîëîæåííûå íà äóãàõ ýòîãî ïóòè îáðàçóþò ñëîâîñëîâî1ñîñòîÿíèÿ àâòîìàòà â íåêîòîðîå âûäåëåííîå ñîñòîÿíèå .Òàê, íàïðèìåð, íåäåòåðìèíèðîâàííûé àâòîìàò ñî ñêà÷êàìè, èçîáðàæ¼ííûé íà ðèñóíêå 2.8, ðàñïîçíà¼ò ñëîâàñëîâîΛ, ab, ababè íå ðàñïîçíà¼òba.Òåïåðü ìîæíî ñôîðìóëèðîâàòü è ôîðìàëüíîå îïðåäåëåíèå ðàñïîçíàâàåìîñòè ñëîâ:Ïóñòü A = hS, A, I, T, F i íåäåòåðìèíèðîâàííûéêîíå÷íûé àâòîìàò ñî ñêà÷êàìè.
Áóäåì ãîâîðèòü, ÷òî ñëîâî w ∈ A∗ ,ðàñïîçíà¼òñÿ àâòîìàòîì A, åñëè ñóùåñòâóþò ñëîâî w0 = a0 a1 . . . ak−1 ∈(A ∪ {ε})∗ , k ∈ N è ñîñòîÿíèÿ s0 , . . . , sk ∈ S òàêèå, ÷òîÎïðåäåëåíèå 2.3.21. s0 ∈ I , sk ∈ F2. äëÿ âñåõ i < k âûïîëíåíî si+1 ∈ T (si , ai )1Âñëó÷àå, êîãäà äóãà íè÷åì íå ïîìå÷åíà, ïðîõîæäåíèå ïî íåé ïðîñòî íå äîáàâëÿåòíîâûõ ñèìâîëîâ â ñëîâî, ïðî÷èòûâàåìîå âäîëü ïóòè.Ãëàâà 2. Àâòîìàòíûå ÿçûêè283.
ñëîâî w ïîëó÷àåòñÿ èç w0 óäàëåíèåì âñåõ ñèìâîëîâ ε.Åñëè â íåäåòåðìèíèðîâàííîì àâòîìàòå ñî ñêà÷êàìè îòñóòñòâóþò äóãè, íå ïîìå÷åííûå íèêàêèìè ñèìâîëàìè, òî òàêîé àâòîìàò íàçûâàåòñÿïðîñòîíåäåòåðìèíèðîâàííûì. Î÷åâèäíî, ÷òî íåäåòåðìèíèðîâàííûå àâ-òîìàòû ìîæíî ñ÷èòàòü ÷àñòíûì ñëó÷àåì íåäåòåðìèíèðîâàííûõ àâòîìàòîâ ñî ñêà÷êàìè (êîãäàT (s, ε) òîæäåñòâåííî ðàâíî ∅), à äåòåðìèíèðîâàí-íûå àâòîìàòû ìîæíî ñ÷èòàòü ÷àñòíûì ñëó÷àåì íåäåòåðìèíèðîâàííûõàâòîìàòîâ (êîãäà ê òîìó æå åù¼ âñå ìíîæåñòâàT (s, a), a 6= εîäíîýëå-ìåíòíû).Ìíîæåñòâî âñåõ ñëîâ, ðàñïîçíàâàåìûõ íåäåòåðìèíèðîâàííûì àâòî-A, îáîçíà÷àåòñÿ êàê è â ñëó÷àå äåòåðìèíèðîâàííûõàâòîìàòîâ, ÷åðåç L(A) è, òàê æå êàê è ðàíåå, íàçûâàåòñÿ ÿçûêîì, ðàñïîçíàâàåìûì ýòèì àâòîìàòîì.Íàçîâ¼ì íåäåòåðìèíèðîâàííûå àâòîìàòû ñî ñêà÷êàìè A è B ýêâèâàëåíòíûìè, åñëè L(A) = L(B).ìàòîì ñî ñêà÷êàìèÄëÿ ëþáîãî íåäåòåðìèíèðîâàííîãî àâòîìàòà ñî ñêà÷êàìè A ñóùåñòâóåò ýêâèâàëåíòíûé åìó äåòåðìèíèðîâàííûé àâòîìàòAd .Òåîðåìà 2.3.1Äîêàçàòåëüñòâî.
Ïóñòü ÏóñòüA = hS, A, I, T, F i íåäåòåðìèíèðîâàí-íûé êîíå÷íûé àâòîìàò ñî ñêà÷êàìè. Îïðåäåëèì äåòåðìèíèðîâàííûé êî-Ad = hSd , Ad , Id , Td , Fd iíå÷íûé àâòîìàòñëåäóþùèì îáðàçîì:• Sd = {X | X ⊆ S}• Ad = A• Id(àëôàâèò îñòà¼òñÿ ïðåæíèì)îïðåäåëèì êàê ìíîæåñòâî âñåõ ñîñòîÿíèé èçùåñòâóåò ïóòü èç íåêîòîðîãî ýëåìåíòà èçI,S,äëÿ êîòîðûõ ñó-âäîëü êîòîðîãî ÷èòà-åòñÿ ïóñòîå ñëîâî•ÎïðåäåëèìTd (X, a)êàê ìíîæåñòâî âñåõ ñîñòîÿíèés,äëÿ êîòîðûõñóùåñòâóåò õîòÿ áû îäèí ïóòü ïî äóãàì àâòîìàòà èç íåêîòîðîãîñîñòîÿíèÿx ∈ X,âäîëü êîòîðîãî ÷èòàåòñÿ ñëîâî, ñîñòîÿùåå ðîâíîèç îäíîãî ñèìâîëàa.• Fd = {X ∈ Sd | X ∩ F 6= ∅} (ñîñòîÿíèå áóäåò âûäåëåííûì, åñëè îíîñîäåðæèò õîòÿ áû îäèí ýëåìåíò èç F ).2.3.
Íåäåòåðìèíèðîâàííûå àâòîìàòûÏðîâåðèì, ÷òîL(A) = L(Ad ).Ïóñòüãðàôè÷åñêîì èçîáðàæåíèè àâòîìàòàaA29w = a0 a1 . . . ak−1 ∈ L(A).Òîãäà âñóùåñòâóåò ïóòüak−1a01s0 99K ◦ −→s1 99K ◦ −→s2 · · · sk−1 99K ◦ −→ sk 99K s0k ,(2.1)s0 ∈ I, s0k ∈ F,èç íåêîòîðîãî íà÷àëüíîãî ñîñòîÿíèÿ s0 â íåêîòîðîå âûäåëåííîå ñîñòî0ÿíèå sk , âäîëü êîòîðîãî ïðî÷èòûâàåòñÿ ñëîâî w .
(Çäåñü ïóíêòèðíûìèñòðåëêàìè 99K îáîçíà÷åíû ó÷àñòêè ýòîãî ïóòè âîçìîæíî ïóñòûå ñîñòîÿùèå èç íåñêîëüêèõ íåïîìå÷åííûõ äóã.) Òåïåðü ðàññìîòðèì â àâòîìàòåAdId ,âäîëüi < k)(2.2)(óæå åäèíñòâåííûé) ïóòü èç íà÷àëüíîãî ñîñòîÿíèÿêîòîðîãî ÷èòàåòñÿ ñëîâîaaw:ak−101Id = S0 −→S1 −→· · · −→ Sk (Si+1 = Td (Si , ai ),è äîêàæåì, ÷òîSk ∈ Fd .äëÿ âñåõÒåì ñàìûì áóäåò óñòàíîâëåíî, ÷òî ñëîâîwðàñïîçíà¼òñÿ àâòîìàòîì Ad , ò.å., w ∈ L(Ad ). Äëÿ òîãî, ÷òîáû äîêàçàòü,00÷òî Sk ∈ Fd , ââèäó sk ∈ F áóäåò äîñòàòî÷íî ïîêàçàòü, ÷òî sk ∈ Sk , îòêóäà0ìû ïîëó÷èì sk ∈ Sk ∩ F 6= ∅.s0 ∈ I ⊆ Id = S0 . Äàëåå, ïî îïðåäåëåíèþTd ïîñëåäîâàòåëüíî ïîëó÷àåì s1 ∈ S1 , s2 ∈ S2 , .
. . è, íàêî- ñàìîì äåëå, ìû èìååìîòîáðàæåíèÿ0íåö, sk ∈ Sk , ÷òî è òðåáîâàëîñü.L(A) ⊆ L(Ad ).Òåïåðü ïðîâåðèì îáðàòíîå âêëþ÷åíèå L(Ad ) ⊆ L(A). Ïóñòü w =a0 a1 . . . ak−1 ∈ L(Ad ). Ýòî îçíà÷àåò, ÷òî â àâòîìàòå Ad ñóùåñòâóåò ïóòüÒåì ñàìûì ìû óñòàíîâèëè âêëþ÷åíèåaaak−101Id = S0 −→S1 −→· · · −→ Sk ,â êîòîðîìSk ∈ Fd .Sk ∩ F 6= ∅, è ïîýòîìó ìû ìîs0k ∈ Sk ∩ F .
Ïîñêîëüêó s0k ∈Sk = Td (Sk−1 , ak−1 ), â ñîîòâåòñòâèè ñ îïðåäåëåíèåì îòîáðàæåíèÿ Td , ñó0ùåñòâóåò sk−1 ∈ Sk−1 òàêîé, ÷òî â àâòîìàòå A èìååòñÿ ïóòü èç sk−1 â sk ,âäîëü êîòîðîãî ÷èòàåòñÿ ñëîâî ak−1 . Äàëåå, ðàññóæäàÿ àíàëîãè÷íî, ìûïîëó÷àåì, ÷òî ñóùåñòâóåò sk−2 ∈ Sk−2 òàêîé, ÷òî â àâòîìàòå A èìååòñÿ ïóòü èç sk−2 â sk−1 , âäîëü êîòîðîãî ÷èòàåòñÿ ñëîâî ak−2 . Ïðîäîëæàÿýòîò ïðîöåññ, ìû â êîíöå êîíöîâ ïðèä¼ì ê íåêîòîðîìó ýëåìåíòó s0 ∈ Id .Ïîñêîëüêó s0 ∈ Id , ñóùåñòâóåò ïóòü ïî íåïîìå÷åííûì äóãàì èç íåêîòîðîãî ñîñòîÿíèÿ èç ìíîæåñòâà I â s0 . Ïîýòîìó íà ñàìîì äåëå ìîæíîÏî îïðåäåëåíèþ ìíîæåñòâàFdèìååìæåì çàôèêñèðîâàòü íåêîòîðûé ýëåìåíòÃëàâà 2.
Àâòîìàòíûå ÿçûêè30âûáðàòü äàæås0 ∈ I .Ñîåäèíÿÿ âñå óïîìÿíóòûå ïóòè â îäèí, ìû ïîëó-÷èì íåêîòîðûé ïóòü â àâòîìàòåA,âûõîäÿùèé èç íà÷àëüíîãî ñîñòîÿíèÿè çàêàí÷èâàþùèéñÿ â âûäåëåííîì ñîñòîÿíèè, âäîëü êîòîðîãî ÷èòàåòñÿñëîâîw:aak−1a01s0 99K ◦ −→s1 99K ◦ −→s2 · · · sk−1 99K ◦ −→ sk 99K s0kÑ ó÷¼òîì òîãî, ÷òîs0 ∈ Iès0k ∈ F ,ìû ïîëó÷èì, ÷òî(2.3)w = a0 . . . ak−1 ∈L(A).Îáðàòíîå âêëþ÷åíèå äîêàçàíî. èòîãå ïîëó÷àåì, ÷òîL(A) = L(Ad ). Äîêàçàòåëüñòâî òåîðåìû ôàêòè÷åñêè äà¼ò íàì àëãîðèòì, ïîçâîëÿþùèé ïî ëþáîìó íåäåòåðìèíèðîâàííîìó àâòîìàòó ñî ñêà÷êàìè (è â òîì÷èñëå ëþáîìó íåäåòåðìèíèðîâàííîìó àâòîìàòó) ñòðîèòü äåòåðìèíèðîâàííûé àâòîìàò, ðàñïîçíàþùèé òîò æå ñàìûé ÿçûê. äàëüíåéøåì ìû èíîãäà áóäåì â íàøèõ ôîðìóëèðîâêàõ ïîä÷åðêèâàòü àëãîðèòìè÷åñêóþ ñòîðîíó äîêàçûâàåìûõ óòâåðæäåíèé.
![](https://s.studizba.com/z.php?f=/templates/si/i/noavatar.png&w=100&h=100&t=1"){kind=avatar}
