1610906281-ae38486ec859a3a9dcd398b8f34f26aa (824377), страница 5
Текст из файла (страница 5)
Âàæíîéîñîáåííîñòüþ òåîðèè àâòîìàòîâ ÿâëÿåòñÿ òî, ÷òî âî ìíîãèõ òåîðåìàõ,óòâåðæäàþùèõ ñóùåñòâîâàíèå êàêèõëèáî îáúåêòîâ, óäà¼òñÿ íå ïðîñòîóñòàíîâèòü ñóùåñòâîâàíèå äàííîãî îáúåêòà, íî è îïèñàòü àëãîðèòì äëÿïîëó÷åíèÿ äàííîãî îáúåêòà ïî èñõîäíûì îáúåêòàì, êàê ýòî äåëàåòñÿ âòîëüêî ÷òî ïðîâåä¼ííîì äîêàçàòåëüñòâå òåîðåìû 2.3.1. Õîòÿ çäåñü ìû ïîíèìàåì ñëîâî àëãîðèòì â èíóòèòèâíîì, íåôîðìàëüíîì ñìûñëå, äàííûéàëãîðèòì ìîæíî îïèñàòü â áîëåå ñòðîãèõ òåðìèíàõ, ðàññìîòðåâ, íàïðèìåð, íåêîòîðîå åñòåñòâåííîå êîäèðîâàíèå êîíå÷íûõ àâòîìàòîâ íàòóðàëüíûìè ÷èñëàìè è ïîêàçàâ, ÷òî êîä äåòåðìèíèðîâàííîãî àâòîìàòà, ïîëó÷àåìîãî â ðåçóëüòàòå ïðèìåíåíèÿ àëãîðèòìà, âû÷èñëÿåòñÿ ñ ïîìîùüþ ðåêóðñèâíîé ôóíêöèè ïî êîäó èñõîäíîãî íåäåòåðìèíèðîâàííîãî àâòîìàòà.Çäåñü ìû îäíàêî íå ñòàâèì ñâîåé öåëüþ äîêàçàòåëüñòâî ïîäîáíûõ ðåçóëüòàòîâ.
Ìû òàêæå îñòàâëÿåì â ñòîðîíå âîïðîñû î êà÷åñòâåííîñòè òàêèõàëãîðèòìîâ (íàïðèìåð, ÷èñëà íåîáõîäèìûõ øàãîâ â èõ âûïîëíåíèè, ðàñõîä ïàìÿòè) è íàõîæäåíèÿ íàèëó÷øèõ àëãîðèòìîâ, îãðàíè÷èâàÿñü ëèøüäîêàçàòåëüñòâîì ñóùåñòâîâàíèÿ õîòÿ áû îäíîãî àëãîðèòìà.Ïîä÷åðêí¼ì, ÷òî â äîêàçàòåëüñòâå ìû óñòàíîâèëè ñóùåñòâîâàíèå åäèíîãî àëãîðèòìà, êîòîðûé îáñëóæèâàåò âñå âîçìîæíûå ñèòóàöèè.  òàêèõ¾îáúåêò . . . ñòðîèòñÿðàâíîìåðíî ïî . . . ¿. Íàïðèìåð, ìîæíî ñôîðìóëèðîâàòü ñëåäóþùåå óòâåðñëó÷àÿõ ìû áóäåì óïîòðåáëÿòü âûðàæåíèÿ òèïàæäåíèå:2.3. Íåäåòåðìèíèðîâàííûå àâòîìàòû31Àâòîìàò Ad ñòðîèòñÿ ðàâíîìåðíî ïî íåäåòåðìèíèðîâàííîìó àâòîìàòó ñî ñêà÷êàìè A.Ïðåäëîæåíèå 2.3.1Ïðîöåññ íàõîæäåíèÿ äåòåðìèíèðîâàííîãî àâòîìàòà, ýêâèâàëåíòíîãîäåòåðìèíèçàöèåé àâòîìàòà.A çàäàí ñâîèì ãðàôè÷åñêèì èçîá3ðèñóíêå 2.9.
Ó àâòîìàòà Ad áóäåò 2 = 8 ñîñòîÿíèé äàííîìó, áóäåì íàçûâàòüÐàññìîòðèì ïðèìåð. Ïóñòü àâòîìàòðàæåíèåì, êàê íàDEEEÐèñ. 2.9: Íà÷àëüíûé íåäåòåðìèíèðîâàííûé àâòîìàò∅, {0}, {1}, {2}, {0, 1}, {1, 2}, {0, 2}, {0, 1, 2}. Íà÷àëü{0, 1}. Âûäåëåííûìè ñîñòîÿíèÿìè áóäóò {0}, {1},{0, 1}, {1, 2}, {0, 2}, {0, 1, 2}.Îïðåäåëèâ ïåðåõîäû ñîãëàñíî îïðåäåëåíèþ Ad , ìû ïîëó÷èì àâòîìàò,ýòî ìíîæåñòâàíûì ñîñòîÿíèåì áóäåòãîðàçäî áîëåå ãðîìîçäêèé, èçîáðàæ¼ííûé íà ðèñ. 2.10.
Âïðî÷åì, åãî ìîæ-^`^`DE^`E D ED ^` DE DE^`DED^`EED^`Ðèñ. 2.10: Ðåçóëüòàò äåòåðìèíèçàöèè àâòîìàòà íà ðèñ. 2.9.íî óïðîñòèòü. Ïîñìîòðåâ âíèìàòåëüíî íà ðåçóëüòàò, ìû îáíàðóæèì, ÷òîâ àâòîìàòåAd ïðèñóòñòâóþò ñîñòîÿíèÿ, â êîòîðûå íåâîçìîæíî äîáðàòüñÿÃëàâà 2. Àâòîìàòíûå ÿçûêè32èç íà÷àëüíîãî ñîñòîÿíèÿ. Ýòî âñå ñîñòîÿíèÿ êðîìå{0, 1}, {1}è∅.Î÷å-âèäíî, ÷òî åñëè ìû óáåð¼ì èç àâòîìàòà âñå òàêèå ñîñòîÿíèÿ, òî ÿçûê,ðàñïîçíàâàåìûé ïîëó÷åííûì â ðåçóëüòàòå àâòîìàòîì, íå èçìåíèòñÿ! Ïîëó÷åííûé â ðåçóëüòàòå àâòîìàò èçîáðàæ¼í íà ðèñ.
2.11.^`DEEDE^`DÐèñ. 2.11: È ðåçóëüòàò óäàëåíèÿ èç íåãî ëèøíèõ ñîñòîÿíèé.Ïîñòðîèòü äåòåðìèíèðîâàííûå àâòîìàòû, ýêâèâàëåíòíûå àâòîìàòàì, èçîáðàæ¼ííûì íà ñëåäóþùèõ ðèñóíêàõ:Óïðàæíåíèÿ.a)á)DDEED2.4DÎïåðàöèè íàä àâòîìàòíûìè ÿçûêàìèÊëàññ àâòîìàòíûõ ÿçûêîâ çàìêíóò îòíîñèòåëüíî îáúåäèíåíèÿ, ïåðåñå÷åíèÿ, ðàçíîñòè, äîïîëíåíèÿ, êîíêàòåíàöèè è çâ¼çäî÷êè Êëèíè. Ïðè ýòîì àâòîìàòû, ðàñïîçíàþùèå ðåçóëüòàòû ýòèõ îïåðàöèé ñòðîÿòñÿ ðàâíîìåðíî ïî àâòîìàòàì, ðàñïîçíàþùèì èñõîäíûåÿçûêè.Òåîðåìà 2.4.1Äîêàçàòåëüñòâî.
Äîêàæåì, ÷òî îáúåäèíåíèå àâòîìàòíûõ ÿçûêîâ òîæåÿâëÿåòñÿ àâòîìàòíûì ÿçûêîì. Ïóñòü ó íàñ åñòü àâòîìàòûA0èA1 .Áåçîãðàíè÷åíèÿ îáùíîñòè ìîæíî ñ÷èòàòü, ÷òî ìíîæåñòâà ñîñòîÿíèé ýòèõ àâòîìàòîâ íå èìåþò îáùèõ ýëåìåíòîâ. Òåïåðü åñëè ìû èçîáðàçèì îáà ýòèõàâòîìàòà îäèí îêîëî äðóãîãî íà îäíîì ðèñóíêå, òî, êàê íåòðóäíî óáåäèòüñÿ, ó íàñ ïîëó÷èòñÿ èçîáðàæåíèå íåäåòåðìèíèðîâàííîãî êîíå÷íîãîàâòîìàòà, ðàñïîçíàþùåãî ÿçûêL(A0 ) ∪ L(A1 ).2.4.
Îïåðàöèè íàä àâòîìàòíûìè ÿçûêàìè33Äîêàæåì, ÷òî äîïîëíåíèå àâòîìàòíîãî ÿçûêàLíàä àëôàâèòîìòîæå ÿâëÿåòñÿ àâòîìàòíûì ÿçûêîì. Äåéñòâèòåëüíî, åñëè ÿçûêLAðàñïî-çíà¼òñÿ íåêîòîðûì äåòåðìèíèðîâàííûì àâòîìàòîì, òî ïîñëå èçìåíåíèÿâ í¼ì ñòàòóñà êàæäîãî âûäåëåííîãî ñîñòîÿíèÿ íà íåâûäåëåííîå è íàîáîðîò, ìû ïîëó÷èì àâòîìàò, ðàñïîçíàþùèé äîïîëíåíèå ýòîãî ÿçûêà.Çàìêíóòîñòü àâòîìàòíûõ ÿçûêîâ îòíîñèòåëüíî ïåðåñå÷åíèÿ ñëåäóåòèç òîëüêî ÷òî äîêàçàííûõ ñâîéñòâ è òîãî, ÷òî ïåðåñå÷åíèå ïðîèçâîëüíûõìíîæåñòâAèBÀíàëîãè÷íî, èç ïðåäñòàâëåíèÿB = A∩BA ∩ B = A ∪ B.ðàçíîñòè ìíîæåñòâ A è Bìîæíî ïðåäñòàâèòü â âèäåâ âèäåA\è òîëüêî ÷òî äîêàçàííûõ óòâåðæäåíèé ñëåäóåò çàìêíóòîñòüêëàññà àâòîìàòíûõ ÿçûêîâ îòíîñèòåëüíî ðàçíîñòè.Òåïåðü äîêàæåì, ÷òî êîíêàòåíàöèÿ àâòîìàòíûõ ÿçûêîâ ñíîâà àâòîìàòíà.
ÏóñòüLi = L(Ai ), i = 0, 1.Äîêàæåì, ÷òî ÿçûêL0 L1Áåç îãðàíè÷åíèÿ îáùíîñòè ìîæíî ñ÷èòàòü, ÷òî àâòîìàòûàâòîìàòíûé.A0èA1íåèìåþò îáùèõ ñîñòîÿíèé.Èçîáðàçèì àâòîìàòûA0èA1íà îäíîì ÷åðòåæå è ïðîäåëàåì ñ ïîëó-÷åííûì èçîáðàæåíèåì ñëåäóþùèå ìàíèïóëÿöèè:a) ïðîâåä¼ì äóãè îò âñåõ âûäåëåííûõ ñîñòîÿíèé àâòîìàòà÷àëüíîìó ñîñòîÿíèþ àâòîìàòàA0 .A0ê íà-Íèêàêèì ñèìâîëîì ýòè äóãè ìûíå ïîìå÷àåì.b) ëèøèì âûäåëåííûå ñîñòîÿíèÿ àâòîìàòàa) ëèøèì íà÷àëüíîå ñîñòîÿíèå àâòîìàòàA0A1èõ ñòàòóñà âûäåëåííûõ,ñòàòóñà íà÷àëüíîãî. ðåçóëüòàòå, êàê íåòðóäíî âèäåòü, ìû ïîëó÷èì èçîáðàæåíèå àâòîìàòà,ðàñïîçíàþùåãîL0 L1 = L(A0 )L(A1 )(ñì.
ðèñ. 2.12).Òåïåðü äîêàæåì, ÷òî êëàññ àâòîìàòíûõ ÿçûêîâ çàìêíóò îòíîñèòåëüíîçâ¼çäî÷êè Êëèíè.ÏóñòüA êîíå÷íûé àâòîìàò. Äîáàâèì â íåãî íîâîå ñîñòîÿíèå, êî-òîðîå îáúÿâèì íà÷àëüíûì, è ëèøèì ýòîãî ñòàòóñà ïðåæíåå íà÷àëüíîåñîñòîÿíèå. Ïðîâåäåì íåïîìå÷åííóþ äóãó èç íîâîãî íà÷àëüíîãî ñîñòîÿíèÿ â áûâøåå íà÷àëüíîå ñîñòîÿíèå.
Èç êàæäîãî âûäåëåííîãî ñîñòîÿíèÿïðîâåä¼ì äóãó â íà÷àëüíîå ñîñòîÿíèå è îáúÿâèì íà÷àëüíîå ñîñòîÿíèå âûäåëåííûì (ñì. ðèñ. 2.13). Íåòðóäíî âèäåòü, ÷òî ïîëó÷åííûé â ðåçóëüòàòå∗àâòîìàò áóäåò ðàñïîçíàâàòü ÿçûê L(A) . Ãëàâà 2. Àâòîìàòíûå ÿçûêè34Ðèñ. 2.12: Ïîñòðîåíèå àâòîìàòà äëÿ êîíêàòåíàöèè. Ñëåâà èñõîäíûéàâòîìàò, ñïðàâà ðåçóëüòàò.2.5Ïîðîæäåíèå àâòîìàòíûõ ÿçûêîâ: ðåãóëÿðíûå âûðàæåíèÿÏîñëå òîëüêî ÷òî äîêàçàííîé â 2.4 ñåðèè ðåçóëüòàòîâ î òîì, êàê ìîæíîêîíñòðóèðîâàòü íîâûå àâòîìàòíûå ÿçûêè èç óæå èìåþùèõñÿ ïðè ïîìîùè îïåðàöèé îáúåäèíåíèÿ, ïåðåñå÷åíèÿ, ðàçíîñòè è äîïîëíåíèÿ, êîíêàòåíàöèè, à òàêæå çâ¼çäî÷êè Êëèíè, âîçíèêàåò åñòåñòâåííûé âîïðîñ: àíåëüçÿ ëè ñ ïîìîùüþ òàêèõ îïåðàöèé ñêîíñòðóèðîâàòü ëþáîé àâòîìàòíûé ÿçûê èç íåêîòîðûõ äîñòàòî÷íî ïðîñòûõ ÿçûêîâ? Ñåé÷àñ ìû óáåäèìñÿ, ÷òî ýòî èìåííî òàê è åñòü: ëþáîé íåïóñòîé àâòîìàòíûé ÿçûê ìîæíîïðåäñòàâèòü, êàê ðåçóëüòàò ïðèìåíåíèÿ íåêîòîðîé êîíå÷íîé ïîñëåäîâàòåëüíîñòè îïåðàöèé îáúåäèíåíèÿ, êîíêàòåíàöèè è çâ¼çäî÷êè Êëèíè ê2.5.
Ïîðîæäåíèå àâòîìàòíûõ ÿçûêîâ: ðåãóëÿðíûå âûðàæåíèÿ35Ðèñ. 2.13: Ïîñòðîåíèå àâòîìàòà äëÿ îïåðàöèè ¾çâ¼çäî÷êà Êëèíè¿. Ñëåâà èñõîäíûå àâòîìàòû, ñïðàâà ðåçóëüòàò.îäíîýëåìåíòíûì ÿçûêàì, îáðàçîâàííûõ ñëîâàìè, ñîñòîÿùèìè èç íå áîëåå, ÷åì îäíîãî ñèìâîëà. Çàìåòèì, ÷òî ïðè ýòîì ìîæíî îáîéòèñü äàæåáåç ïåðåñå÷åíèÿ, ðàçíîñòè è äîïîëíåíèÿ! Ýòîò çàìå÷àòåëüíûé ðåçóëüòàò íàõîäèò ñâî¼ îòðàæåíèå â øèðîêîì èñïîëüçîâàíèè ñïåöèôè÷åñêèõîáîçíà÷åíèé äëÿ àâòîìàòíûõ ÿçûêîâ òàê íàçûâàåìûõðàæåíèé,ðåãóëÿðíûõ âû-ïî ñóòè äåëà îïèñûâàþùèõ ïðîöåññ òàêîãî êîíñòðóèðîâàíèÿ.Î íèõ è ïîéä¼ò ðå÷ü â äàííîì ïàðàãðàôå.Ñíà÷àëà ìû ¾çàãîòîâèì¿ âñå âîçìîæíûå ðåãóëÿðíûå âûðàæåíèÿ.Ïóñòü A íåêîòîðûé êîíå÷íûé àëôàâèò. Îïðåäåëèì ìíîæåñòâî ðåãóëÿðíûõ âûðàæåíèé íàä A ñëåäóþùèì îáðàçîì:Îïðåäåëåíèå 2.5.11. Âñå ñèìâîëû a èç A ÿâëÿþòñÿ ðåãóëÿðíûìè âûðàæåíèÿìè.2.
Ñèìâîë ∅ ÿâëÿåòñÿ ðåãóëÿðíûì âûðàæåíèåì.3. Åñëè α è β ðåãóëÿðíûå âûðàæåíèÿ, òî (α · β), (α + β), (α∗ )ÿâëÿþòñÿ ðåãóëÿðíûìè âûðàæåíèÿìè.4. Ëþáàÿ êîíå÷íàÿ ïîñëåäîâàòåëüíîñòü, ñîñòàâëåííàÿ èç ñèìâîëîâàëôàâèòà A, à òàêæå (, ), +, ∗ , ÿâëÿåòñÿ ðåãóëÿðíûì âûðàæåíèåì òîãäà è òîëüêî òîãäà, êîãäà ýòî ìîæåò áûòü óñòàíîâëåíîêîíå÷íûì ÷èñëîì ïðèìåíåíèé âûøåïåðå÷èñëåííûõ ñâîéñòâ.Ãëàâà 2. Àâòîìàòíûå ÿçûêè36Ïðè çàïèñè ðåãóëÿðíûõ âûðàæåíèé ìû áóäåì îïóñêàòü íåêîòîðûå ñêîá-·êè è ñèìâîëòàê æå, êàê ýòî äåëàåòñÿ â àëãåáðå, ñ÷èòàÿ, ÷òî ñâÿçêè,îáðàçóþùèå ðåãóëÿðíûå âûðàæåíèÿ, ðàñïîëàãàþòñÿ ïî óáûâàíèþ ñèëû∗∗ñëåäóþùèì îáðàçîì: , ·, +. Òàê, íàïðèìåð, çàïèñü ab + cd áóäåò îáîçíà∗÷àòü ðåãóëÿðíîå âûðàæåíèå ((a · b) + (c · (d ))).Ðåãóëÿðíûå âûðàæåíèÿ êàê áû îïèñûâàþò ïðîöåññ ¾ñáîðêè¿ ÿçûêîâèç îäíîýëåìåíòíûõ ÿçûêîâ, ñîñòîÿùèõ èç ñëîâ äëèíû 1, îáîçíà÷àåìûõñèìâîëàìè àëôàâèòà, · áóäåò ñîîòâåòñòâîâàòü êîíêàòåíàöèè ÿçûêîâ, +∗ îáúåäèíåíèþ, à ïðèìåíåíèþ çâ¼çäî÷êè Êëèíè.
Áîëåå ôîðìàëüíî,α ìû ïî èíäóêöèè ñîïîñòàâèìL(α), ñëåäóþùèì îáðàçîì:êàæäîìó ðåãóëÿðíîìó âûðàæåíèþâàåìûé èì ÿçûê, îáîçíà÷àåìûé1.L(a) = {a}2.L(∅) = ∅3.L(α∗ ) = (L(α))∗4.L(αβ) = L(α)L(β)5.L(α + β) = L(α) ∪ L(β).ßçûêè âèäàíûìè.L(α),ãäåα ðåãóëÿðíîå âûðàæåíèå, íàçûâàþòñÿçàäà-ðåãóëÿð-Îêàçûâàåòñÿ, ÷òî ïîíÿòèÿ ðåãóëÿðíîãî è àâòîìàòíîãî ÿçûêîâ íàñàìîì äåëå ñîâïàäàþò:Ïóñòü A êîíå÷íûé àëôàâèò, L ⊆ A∗ . Òîãäà ñëåäóþùèå äâà óñëîâèÿ ýêâèâàëåíòíû:Òåîðåìà 2.5.11. L ðåãóëÿðíûé ÿçûê2. L àâòîìàòíûé ÿçûê.Äîêàçàòåëüñòâî. Äîêàæåì èìïëèêàöèþ÷òî ëþáîé ÿçûê âèäàL(α)(1) ⇒ (2). Óòâåðæäåíèå î òîì,ÿâëÿåòñÿ àâòîìàòíûì, äîêàçûâàåòñÿ ïî èí-äóêöèè ïî ñëîæíîñòè ðåãóëÿðíîãî âûðàæåíèÿâèäàα. ñàìîì äåëå, ÿçûêè{a} è {Λ}, ñîîòâåòñòâóþùèå êðàò÷àéøèì ðåãóëÿðíûì âûðàæåíèÿì,î÷åâèäíî, ÿâëÿþòñÿ àâòîìàòíûìè. Åñëè ïðåäïîëîæèòü, ÷òî ðåãóëÿðíîåâûðàæåíèåαñîñòàâëåíî èç áîëåå êîðîòêèõ âûðàæåíèé, è ÷òî äëÿ íèõòåîðåìà óæå äîêàçàíà, òî ñïðàâåäëèâîñòü òåîðåìû äëÿα ñëåäóåò èç óæåäîêàçàííûõ â 2.4 çàìêíóòîñòè êëàññà àâòîìàòíûõ ÿçûêîâ îòíîñèòåëüíîêîíêàòåíàöèè, îáúåäèíåíèÿ è çâ¼çäî÷êè Êëèíè.2.5.
![](https://s.studizba.com/z.php?f=/templates/si/i/noavatar.png&w=100&h=100&t=1"){kind=avatar}
