1610906280-58a805c0f28e2c985192966a2f3bd6d2 (824374), страница 5
Текст из файла (страница 5)
Ïîêàæèòå, ÷òîzìíîæåñòâî âñåõ òàêèì îáðàçîì ïîëó÷åííûõ ñëîâ ðàñïîçíàâàåìî êîíå÷íûì àâòîìàòîì.28Ãëàâà 2. Êîíå÷íûå àâòîìàòû è ãðàììàòèêèÄàëåå ìû äîêàæåì âàæíûå òåîðåòèêîìíîæåñòâåííûå ñâîéñòâà àâòîìàòíûõ ÿçûêîâ.Òåîðåìà 2.2.2 Àâòîìàòíûå ÿçûêè çàìêíóòû îòíîñèòåëüíî îáúåäèíåíèÿ, ïåðåñå÷åíèÿ, äîïîëíåíèÿ, êîíêàòåíàöèè è çâåçäî÷êè Êëèíè.Äîêàçàòåëüñòâî. Íàì ïîíàäîáÿòñÿ îïðåäåëåíèå è ëåììà, èãðàþùèåâàæíóþ ðîëü òàêæå è çà ïðåäåëàìè äàííîãî äîêàçàòåëüñòâà.Áóäåì ãîâîðèòü, ÷òî êîíå÷íûé àâòîìàò A = (Q, A, δ, q0 , F ) îáëàäàåòñâîéñòâîì âàõòåðà åñëè äëÿ ëþáûõ q ∈ Q, a ∈ A âûïîëíåíî δ(q, a) 6= q0 ,òî åñòü åñëè àâòîìàò A ìîæåò íàõîäèòüñÿ â íà÷àëüíîì ñîñòîÿíèè q̃0òîëüêî â ñàìîì íà÷àëå ðàáîòû.Ëåììà 2.2.3 (Î âàõòåðå) Äëÿ ëþáîãî êîíå÷íîãî àâòîìàòàA = (Q, A, δ, q0 , F ) ñóùåñòâóåò êîíå÷íûé àâòîìàò A0 = (Q0 , A, δ 0 , q̃0 , F 0 )òàêîé, ÷òî T (A) = T (A0 ) è A0 îáëàäàåò ñâîéñòâîì âàõòåðà.Äîêàçàòåëüñòâî ëåììû î âàõòåðå. Ìû äàäèì íåôîðìàëüíîå äîêàçàòåëüñòâî.
Ïðåäñòàâèì êîíå÷íûé àâòîìàò A â ãðàôè÷åñêîì âèäå. Äîáàâèì â íåãî íîâîå ñîñòîÿíèå q̃0 . Åñëè q0 áûëî âûäåëåííûì ñîñòîÿíèåì,òî ñäåëàåì è q̃0 òîæå âûäåëåííûì ñîñòîÿíèåì. Äàëåå1. äëÿ êàæäîé ñòðåëêè, èñõîäÿùåé èç ñîñòîÿíèÿ q0 â íåêîòîðîå ñîñòîÿíèå q 0 6= q0 äîáàâèì â àâòîìàò íîâóþ ñòðåëêó èç ñîñòîÿíèÿ q̃0 â q 0è ïîìåòèì åå òîé æå ñàìîé áóêâîé àëôàâèòà;2. ïåðåíàïðàâèì âñå ñòðåëêè, ïðèõîäÿùèå â q0 èç ñîñòîÿíèé q 00 (âêëþ÷àÿ è ñòðåëêè èç q0 â q0 ) òàê, ÷òîáû îíè ïðèõîäèëè èç q 00 â q̃0 ;3.
äëÿ êàæäîé ñòðåëêè èç q0 â q0 äîáàâèì â àâòîìàò íîâóþ ñòðåëêóèç q̃0 â q̃0 è ïîìåòèì åå òîé æå ñàìîé áóêâîé.Îïèñàííîå ïðåîáðàçîâàíèå ñõåìàòè÷åñêè ïîêàçàíî íà ðèñ. 2.2. Äîáàâëåííîå íàìè ñîñòîÿíèå q̃0 êàê áû áåðåò íà ñåáÿ âñå ôóíêöèè ñîñòîÿíèÿ q0ñðàçó ïîñëå òîãî, êàê ìû ïîêèíåì ñîñòîÿíèå q0 . Ëåãêî ïðîâåðèòü íåïîñðåäñòâåííî, ÷òî ïîëó÷åííûé òàêèì îáðàçîì êîíå÷íûé àâòîìàò óäîâëåòâîðÿåò óñëîâèÿì ëåììû.
Ëåììà äîêàçàíà.Îáúåäèíåíèå. Äëÿ òîãî, ÷òîáû ïîëó÷èòü êîíå÷íûé àâòîìàò A∗ , ðàñïîçíàþùèé îáúåäèíåíèå T (A0 ) ∪ T (A1 ), äîñòàòî÷íî ðàññìîòðåòü êîíå÷íûåàâòîìàòû A00 è A01 òàêèå, ÷òî T (A0 ) = T (A00 ) è T (A1 ) = T (A01 ) óäîâëåòâîðÿþùèå ñâîéñòâó âàõòåðà. Áåç îãðàíè÷åíèÿ îáùíîñòè ìîæíî ñ÷èòàòü,÷òî èõ ìíîæåñòâà ñîñòîÿíèé íå ïåðåñåêàþòñÿ. Ïðåäñòàâèì ýòè àâòîìàòû2.2. Íåäåòåðìèíèðîâàííûå àâòîìàòû29²¯²¯cc¾»?Iq0½¼SoSaSbS?¾»¾»Sq0q 00. . . ½¼...½¼=⇒¾» ¾»?Icq̄0q0½¼¶½¼6¶a ¶ab¶?¶¾»¾»/q0q 00. . . ½¼...½¼Ðèñ.
2.2: ê ëåììå î âàõòåðåãðàôè÷åñêè. Çàòåì îòîæäåñòâèì èõ íà÷àëüíûå ñîñòîÿíèÿ, îáúÿâèâ ïîëó÷åííîå òàêèì îáðàçîì ñîñòîÿíèå íà÷àëüíûì äëÿ ïîëó÷èâøåãîñÿ íåäåòåðìèíèðîâàííîãî àâòîìàòà. Ìíîæåñòâî âûäåëåííûõ ñîñòîÿíèé áóäåò ðàâíî îáúåäèíåíèþ ìíîæåñòâ âûäåëåííûõ ñîñòîÿíèé ýòèõ àâòîìàòîâ. Ïðèýòîì íà÷àëüíîå ñîñòîÿíèå áóäåò ÿâëÿòüñÿ âûäåëåííûì â òîì è òîëüêîâ òîì ñëó÷àå êîãäà îíî ÿâëÿåòñÿ âûäåëåííûì õîòÿ áû äëÿ îäíîãî èçèñõîäíûõ àâòîìàòîâ.
Àâòîìàò A∗ ïîëíîñòüþ îïðåäåëåí äàííûì îïèñàíèåì. Íà÷àâ ïóòåøåñòâèå ïî àâòîìàòó A∗ èç íà÷àëüíîãî ñîñòîÿíèÿ, ìûäàëåå ëèáî ïîéäåì ïî äóãàì àâòîìàòà A0 ëþáî ïî äóãàì àâòîìàòà A1 âçàâèñèìîñòè îò òîãî, ïî êàêîìó ïóòè ìû ïîéäåì íà ïåðâîì øàãå. Ïîñêîëüêó èñõîäíûå àâòîìàòû îáëàäàëè ñâîéñòâîì âàõòåðà, â äàëüíåéøåììû òàê è áóäåì ïóòåøåñòâîâàòü ïî äóãàì ýòîãî æå àâòîìàòà. Ñõåìàòè÷íî ïðîöåññ ïîñòðîåíèÿ ýòîãî àâòîìàòà ïîêàçàí íà ðèñ. 2.3. Ïîëó÷åííûéíåäåòåðìèíèðîâàííûé àâòîìàò áóäåò ðàñïîçíàâàòü ÿçûê T (A0 ) ∪ T (A1 ).Äîïîëíåíèå. Äëÿ ïîëó÷åíèÿ àâòîìàòà, ðàñïîçíàþùåãî äîïîëíåíèå ÿçûêà, ðàñïîçíàâàåìîãî äåòåðìèíèðîâàííûì àâòîìàòîì A, äîñòàòî÷íî â èñõîäíîì àâòîìàòå A çàìåíèòü ìíîæåñòâî âûäåëåííûõ ñîñòîÿíèé F íà åãîäîïîëíåíèå â ìíîæåñòâå âñåõ ñîñòîÿíèé.Ïåðåñå÷åíèå.
Çàìêíóòîñòü îòíîñèòåëüíî ïåðåñå÷åíèÿ ñëåäóåò èç çàìêíóòîñòè îòíîñèòåëüíî îáúåäèíåíèÿ è äîïîëíåíèÿ âìåñòå ñ òåîðåòèêîìíîæåñòâåííûì òîæäåñòâîì A ∩ B = A ∪ B .Êîíêàòåíàöèÿ. Âîçüìåì ïðîèçâîëüíûå êîíå÷íûå àâòîìàòû A0 è A1 . Ìîæ-30Ãëàâà 2. Êîíå÷íûå àâòîìàòû è ãðàììàòèêè'A0&$¶³'¶³Iµ´%'A0&I⇓IA1µ´&'$¶³$%$A1µ´%&%Ðèñ. 2.3: Ïîñòðîåíèå íåäåòåðìèíèðîâàííîãî àâòîìàòà äëÿ îáúåäèíåíèÿíî ñ÷èòàòü, ÷òî A1 îáëàäàþò ñâîéñòâîì âàõòåðà. Ê êàæäîìó âûäåëåííîìó ñîñòîÿíèþ àâòîìàòà A0 ïîäâåñèì îòäåëüíóþ êîïèþ àâòîìàòà A1 .Âûäåëåííûìè ñîñòîÿíèÿìè ïîëó÷åííîãî òàêèì îáðàçîì àâòîìàòà îáúÿâèì âñå âûäåëåííûå ñîñòîÿíèÿ èç êîïèé àâòîìàòà A1 . Ïóòåøåñòâèå ïîòàêîìó àâòîìàòó èç íà÷àëüíîãî â âûäåëåííîå ñîñòîÿíèå ñîñòîèò èç ïóòåøåñòâèÿ ïî àâòîìàòó A0 , â õîäå êîòîðîãî âäîëü äóã áóäåò ïðî÷èòàíîíåêîòîðîå ñëîâî α ∈ T (A0 ), è ïîñëåäóþùåãî ïóòåøåñòâèÿ âäîëü äóã îäíîé èç êîïèé àâòîìàòà A1 , â õîäå êîòîðîãî ê ðàíåå ïðîéäåííîìó ñëîâó αáóäåò äîáàâëåíî íåêîòîðîå ñëîâî β ∈ T (A1 ).
Òàêèì îáðàçîì ìîæíî ïîëó÷àòü ëþáûå ñëîâà èç T (A0 )T (A1 ) íî íè÷åãî áîëåå. Çíà÷èò ïîñòðîåííûéòàêèì îáðàçîì àâòîìàò îïðåäåëÿåò ÿçûê T (A0 )T (A1 ).Çâåçäî÷êà Êëèíè. Âîçüìåì ïðîèçâîëüíûé êîíå÷íûé àâòîìàò A, êîòîðûéìîæíî ñ÷èòàòü îáëàäàþùèì ñâîéñòâîì âàõòåðà è ïðåîáðàçóåì åãî â àâòîìàò A∗ òàê, ÷òîáû T (A)∗ = T (A∗ ), èñïîëíèâ ñëåäóþùèå øàãè:1. Äëÿ êàæäîé ñòðåëêè, âûõîäÿùåé èç íà÷àëüíîãî ñîñòîÿíèÿ, ïðîäåëàåì ñëåäóþùåå.
Ïðåäïîëîæèì, ÷òî ýòà ñòðåëêà ïîìå÷åíà ñèìâîëîì a è çàêàí÷èâàåòñÿ â ñîñòîÿíèè q . Èç êàæäîãî âûäåëåííîãîñîñòîÿíèÿ ïðîâåäåì ñòðåëêó, ïîìå÷åííóþ ñèìâîëîì a, â ñîñòîÿíèåq , åñëè îíà åùå íå ñîäåðæàëàñü â àâòîìàòå A.2. Ñäåëàåì íà÷àëüíîå ñîñòîÿíèå àâòîìàòà A âûäåëåííûì.2.2. Íåäåòåðìèíèðîâàííûå àâòîìàòû31 ðåçóëüòàòå ìû ïîëó÷èì àâòîìàò, êîòîðûé îáîçíà÷èì A∗ . Âíîâü äîáàâëåííûå äóãè áóäåì íàçûâàòü íîâûìè. Ñíà÷àëà ïðîâåðèì, ÷òî êàæäîåñëîâî w ∈ T (A∗ ) ïðèíàäëåæèò T (A)∗ .Ñëó÷àé w = Λ òðèâèàëåí.Ðàññìîòðèì ñëó÷àé w 6= Λ.
Çàôèêñèðóåì íåêîòîðûé ïóòü àâòîìàòàA∗ , âäîëü êîòîðîãî ÷èòàåòñÿ ñëîâî w, çàêàí÷èâàþùèéñÿ â âûäåëåííîìñîñòîÿíèè, è ðàçîáüåì ýòî ñëîâî íà ïîäñëîâà w = w0 w1 . . . wk òàê, ÷òîêàæäîå íîâîå ñëîâî wi , i 6= 0 íà÷èíàåòñÿ ñèìâîëîì, ïðî÷èòàííûì íàâíîâü äîáàâëåííîé äóãå, è êàæäûé ñèìâîë ýòîãî ñëîâà, ïðî÷èòàííûé íàâíîâü äîáàâëåííîé äóãå, íà÷èíàåò íåêîòîðîå èç âûøåóêàçàííûõ ïîäñëîâ.Äîñòàòî÷íî ïðîâåðèòü, ÷òî êàæäîå èç ñëîâ wi ïðèíàäëåæèò T (A). ñàìîì äåëå, w0 ∈ T (A), ïîñêîëüêó îíî ïðî÷èòûâàåòñÿ âäîëü ïóòè,êîòîðûé ïðîõîäèò ïî äóãàì èñõîäíîãî àâòîìàòà A, íà÷èíàåòñÿ â íà÷àëüíîì ñîñòîÿíèè è çàêàí÷èâàåòñÿ â âûäåëåííîì ñîñòîÿíèè àâòîìàòà A.Äàëåå ðàññìîòðèì ÷àñòü ïóòè, âäîëü êîòîðîãî ÷èòàåòñÿ ïîäñëîâî wi(i = 1, .
. . , k ). Ïåðâûé ñèìâîë åãî ïîìå÷àåò âíîâü äîáàâëåííóþ äóãó, ïîìå÷åííóþ, ñêàæåì, ñèìâîëîì a è ïðèõîäÿùóþ â ñîñòîÿíèå q . Ïîñëåäíèéñèìâîë ýòîãî ñëîâà ïîìå÷àåò äóãó, ïðèõîäÿùóþ â âûäåëåííîå ñîñòîÿíèåàâòîìàòà A. Çàìåíèì ïåðâóþ äóãó ýòîãî ó÷àñòêà ïóòè íà äóãó, ïîìå÷åííóþ ñèìâîëîì a, íà÷èíàþùóþñÿ â íà÷àëüíîì ñîñòîÿíèè è ïðèõîäÿùóþâ ñîñòîÿíèå q . Òàêàÿ äóãà ñóùåñòâóåò â ñèëó ïîñòðîåíèÿ. Ïîëó÷åííûéòàêèì îáðàçîì ïóòü íà÷èíàåòñÿ â íà÷àëüíîì ñîñòîÿíèè è çàêàí÷èâàåòñÿâ âûäåëåííîì ñîñòîÿíèè àâòîìàòà A, è âäîëü íåãî ÷èòàåòñÿ ñëîâî wi , òîåñòü wi ∈ T (A).Îòñþäà ñëåäóåò, ÷òî w = w0 w1 . . . wk ∈ T (A)∗ .Ïðîâåðêà òîãî, ÷òî T (A)∗ ⊆ T (A∗ ) äîñòàòî÷íî ïðîñòà è ïðåäîñòàâëÿåòñÿ ÷èòàòåëþ.
¤Òåîðåìà 2.2.4 Ëþáîé êîíå÷íûé ÿçûê ÿâëÿåòñÿ àâòîìàòíûì.Äîêàçàòåëüñòâî. Ââèäó ïðåäûäóùåé òåîðåìû äîñòàòî÷íî ïîêàçàòü,÷òî ÿçûêè ∅, {Λ}, à òàêæå ÿçûêè âèäà {a} ÿâëÿþòñÿ àâòîìàòíûìè.Îñòàâëÿåì ïðîâåðêó ýòîãî â êà÷åñòâå óïðàæíåíèÿ. ¤Ñëåäóþùàÿ ëåììà áûâàåò ïîëåçíà äëÿ äîêàçàòåëüñòâà íåðàñïîçíàâàåìîñòè íåêîòîðûõ ÿçûêîâ ñ ïîìîùüþ êîíå÷íûõ àâòîìàòîâ.Ëåììà 2.2.5 (Î íàêà÷èâàíèè) Ïóñòü L àâòîìàòíûé ÿçûê. Òîãäàñóùåñòâóåò n òàêîå, ÷òî äëÿ ëþáîãî ñëîâà w ∈ L è ëþáîãî åãî ïðåäñòàâëåíèÿ â âèäå (w = w0 w0 w1 ), ãäå |w0 | > n, íàéäåòñÿ ïðåäñòàâëåíèå32Ãëàâà 2. Êîíå÷íûå àâòîìàòû è ãðàììàòèêèw0 = αβγ , ãäå β 6= Λ òàêîå, ÷òî äëÿ âñåõ k = 0, 1, 2, .
. . âûïîëíåíîw0 αβ k γw1 ∈ L.Äîêàçàòåëüñòâî. Ïóñòü ÿçûê L ðàñïîçíàåòñÿ êîíå÷íûì àâòîìàòîì Aè n ÷èñëî åãî ñîñòîÿíèé. Èçâåñòíî, ÷òî w ∈ L. Ýòî îçíà÷àåò,÷òî ñóùåñòâóåò ïóòü èç íà÷àëüíîãî ñîñòîÿíèÿ â íåêîòîðîå âûäåëåííîå ñîñòîÿíèå,âäîëü êîòîðîãî ÷èòàåòñÿ ñëîâî w. Ðàññìîòðèì ó÷àñòîê ïóòè, âäîëü êîòîðîãî ïðî÷èòûâàåòñÿ ôðàãìåíò w0 , äëèíà êîòîðîãî áîëüøå n. Ââèäóòîãî, ÷òî ÷èñëî ñîñòîÿíèé ìåíüøå ÷èñëà ïðîéäåííûõ âäîëü ýòîãî ó÷àñòêà ñîñòîÿíèé, ñóùåñòâóåò õîòÿ áû îäíî ñîñòîÿíèå q , ïîñåùàåìîå âäîëüýòîãî ïóòè êàê ìèíèìóì äâàæäû.
Îòñþäà ñëåäóåò, ÷òî âåñü ó÷àñòîê ïóòè, ñîîòâåòñòâóþùèé w, ìîæåò áûòü ðàçáèò íà ïÿòü ïîñëåäîâàòåëüíîðàñïîëîæåííûõ ó÷àñòêîâ:1. ÷àñòü, ñîîòâåòñòâóþùàÿ w0 ;2. ÷àñòü, ñîîòâåòñòâóþùàÿ w0 äî ïåðâîãî ïîñåùåíèÿ ñîñòîÿíèÿ q ;3. ÷àñòü, ñîîòâåòñòâóþùàÿ w0 , ðàñïîëîæåííàÿ ìåæäó ïåðâûì è âòîðûì ïîñåùåíèåì ñîñòîÿíèÿ q ;4. îñòàâøàÿñÿ ÷àñòü, ñîîòâåòñòâóþùàÿ w05.
![](https://s.studizba.com/z.php?f=/templates/si/i/noavatar.png&w=100&h=100&t=1"){kind=avatar}
