10. Конечные автоматы-преобразователи. Рациональные отношения и их свойства. Описание рациональных отношений регулярными выражениями (1162498), страница 2
Текст из файла (страница 2)
Àâòîìàò-ïðåîáðàçîâàòåëü,ðåàëèçóþùèé îòíîøåíèå R , ëåãêî ïðåîáðàçóåòñÿâ ìàãàçèííûé àâòîìàò, ðàñïîçíàþùèé ñëîâà(x,β) 00ÿçûêà LR : íà êàæäîì ïåðåõîäå s 0 −→s îí−1çàïèñûâàåò ñëîâî β â ìàãàçèí, è ïîñëå òîãî, êàêáóäåò ïðî÷òåíî ñëîâî w , ïðîäîëæàåòðàñïîçíàâàíèå ñëîâà α−1 , èñïîëüçóÿ íàêîïëåííîåñîäåðæèìîå ìàãàçèíà.QEDÓòâåðæäåíèå 10.2.ÐÀÖÈÎÍÀËÜÍÛÅ ÎÒÍÎØÅÍÈß È ÈÕÑÂÎÉÑÒÂÀÒàêèì îáðàçîì,îòíîøåíèå R×2 = {(w , ww ) : w ∈ Σ∗} íå ÿâëÿåòñÿðàöèîíàëüíûì, ïîñêîëüêóRange(R) = {ww : w ∈ Σ∗ } íå ÿâëÿåòñÿðåãóëÿðíûì ÿçûêîìîòíîøåíèå Rrev = {(w , w −1) : w ∈ Σ∗} íåÿâëÿåòñÿ ðàöèîíàëüíûì, ïîñêîëüêóLR = {ww : w ∈ Σ∗ } íå ÿâëÿåòñÿ ÊÑ-ÿçûêîì.revÐÀÖÈÎÍÀËÜÍÛÅ ÎÒÍÎØÅÍÈß È ÈÕÑÂÎÉÑÒÂÀÒåîðåìà î íàêà÷êå òîæå èìååò ìåñòî.Óòâåðæäåíèå 10.3.
Ïóñòü R ðàöèîíàëüíîåîòíîøåíèå íàä àëôàâèòàìè Σ, ∆ . Òîãäàñóùåñòâóåò òàêîå ïîëîæèòåëüíîå öåëîå ÷èñëî N ,÷òî äëÿ ëþáîé ïàðû ñëîâ (w , α), (w , α) ∈ R ,ñóììàðíîé äëèíû íå ìåíåå N ñóùåñòâóþò òàêèåðàçáèåíèÿ ýòèõ ñëîâ w = xyz, α = ηβθ , ãäå|xy | ≤ N, |ηβ| ≤ N è y β 6= ε , äëÿ êîòîðûõâêëþ÷åíèå (xy i z, ηβ i θ)∈R âåðíî äëÿ âñåõ i, i≥0 .ÐÀÖÈÎÍÀËÜÍÛÅ ÎÒÍÎØÅÍÈß È ÈÕÑÂÎÉÑÒÂÀÒåîðåìà î íàêà÷êå òîæå èìååò ìåñòî.Óòâåðæäåíèå 10.3.
Ïóñòü R ðàöèîíàëüíîåîòíîøåíèå íàä àëôàâèòàìè Σ, ∆ . Òîãäàñóùåñòâóåò òàêîå ïîëîæèòåëüíîå öåëîå ÷èñëî N ,÷òî äëÿ ëþáîé ïàðû ñëîâ (w , α), (w , α) ∈ R ,ñóììàðíîé äëèíû íå ìåíåå N ñóùåñòâóþò òàêèåðàçáèåíèÿ ýòèõ ñëîâ w = xyz, α = ηβθ , ãäå|xy | ≤ N, |ηβ| ≤ N è y β 6= ε , äëÿ êîòîðûõâêëþ÷åíèå (xy i z, ηβ i θ)∈R âåðíî äëÿ âñåõ i, i≥0 .Äîêàçàòåëüñòâî. Ñîâåðøåííî àíàëîãè÷íîäîêàçàòåëüñòâó òåîðåìû î ðàçðàñòàíèè äëÿàâòîìàòíûõ ÿçûêîâQEDÐÀÖÈÎÍÀËÜÍÛÅ ÎÒÍÎØÅÍÈß È ÈÕÑÂÎÉÑÒÂÀÄëÿ ñëîâàðíûõ îòíîøåíèé ìîæíî îïðåäåëÿòüðàçíîîáðàçíûå îïåðàöèè.Êîíêàòåíàöèåé îòíîøåíèé P, Q íàä àëôàâèòàìèΣ, ∆ íàçûâàåòñÿ òàêîå ñëîâàðíîå îòíîøåíèåR = PQ íàä òåìè æå àëôàâèòàìè, êîòîðîåîïðåäåëÿåòñÿ ñîîòíîøåíèåìR = {(w , α) : w = w1 w2 , α = α1 α2 ,(w1 , α1 ) ∈ P, (w2 , α2 ) ∈ Q}.Èòåðàöèÿîòíîøåíèÿ P îïðåäåëÿåòñÿ òàê:∞SP∗ =Pk .k=0ÐÀÖÈÎÍÀËÜÍÛÅ ÎÒÍÎØÅÍÈß È ÈÕÑÂÎÉÑÒÂÀÊîìïîçèöèåé îòíîøåíèé P, Q íàä àëôàâèòàìèΣ, ∆ è ∆, Γ ñîîòâåòñòâåííî íàçûâàåòñÿ òàêîåñëîâàðíîå îòíîøåíèå R = P ◦ Q íàä àëôàâèòàìèΣ, Γ , êîòîðîå îïðåäåëÿåòñÿ ñîîòíîøåíèåìR = {(w , u) : ∃α((w , α) ∈ P ∧ (α, u) ∈ Q)}.Îáúåäèíåíèå, ïåðåñå÷åíèå è äîïîëíåíèåñëîâàðíûõ îòíîøåíèé ââîäÿòñÿ îáû÷íûì îáðàçîì.ÐÀÖÈÎÍÀËÜÍÛÅ ÎÒÍÎØÅÍÈß È ÈÕÑÂÎÉÑÒÂÀÊëàññ ðàöèîíàëüíûõîòíîøåíèé çàìêíóò îòíîñèòåëüíî îïåðàöèéîáúåäèíåíèÿ, êîíêàòåíàöèè, èòåðàöèè èêîìïîçèöèè.Óòâåðæäåíèå 10.4.ÐÀÖÈÎÍÀËÜÍÛÅ ÎÒÍÎØÅÍÈß È ÈÕÑÂÎÉÑÒÂÀÊëàññ ðàöèîíàëüíûõîòíîøåíèé çàìêíóò îòíîñèòåëüíî îïåðàöèéîáúåäèíåíèÿ, êîíêàòåíàöèè, èòåðàöèè èêîìïîçèöèè.Äîêàçàòåëüñòâî.
Ñîâåðøåííî àíàëîãè÷íîäîêàçàòåëüñòâó òåîðåìû î çàìêíóòîñòè êëàññààâòîìàòíûõ ÿçûêîâ. Çàìêíóòîñòü îòíîñèòåëüíîîïåðàöèè êîìïîçèöèè äîêàçàòü ñàìîñòîÿòåëüíî .QEDÓòâåðæäåíèå 10.4.ÐÀÖÈÎÍÀËÜÍÛÅ ÎÒÍÎØÅÍÈß È ÈÕÑÂÎÉÑÒÂÀÀ åñòü ëè çàìêíóòîñòü ðàöèîíàëüíûõ îòíîøåíèéîòíîñèòåëüíî ïåðåñå÷åíèÿ?ÐÀÖÈÎÍÀËÜÍÛÅ ÎÒÍÎØÅÍÈß È ÈÕÑÂÎÉÑÒÂÀÀ åñòü ëè çàìêíóòîñòü ðàöèîíàëüíûõ îòíîøåíèéîòíîñèòåëüíî ïåðåñå÷åíèÿ? Óâû, åå íåò!Óòâåðæäåíèå 10.5. Êëàññ ðàöèîíàëüíûõîòíîøåíèé íå çàìêíóò îòíîñèòåëüíî îïåðàöèéïåðåñå÷åíèÿ è äîïîëíåíèÿ.ÐÀÖÈÎÍÀËÜÍÛÅ ÎÒÍÎØÅÍÈß È ÈÕÑÂÎÉÑÒÂÀÀ åñòü ëè çàìêíóòîñòü ðàöèîíàëüíûõ îòíîøåíèéîòíîñèòåëüíî ïåðåñå÷åíèÿ? Óâû, åå íåò!Óòâåðæäåíèå 10.5.
Êëàññ ðàöèîíàëüíûõîòíîøåíèé íå çàìêíóò îòíîñèòåëüíî îïåðàöèéïåðåñå÷åíèÿ è äîïîëíåíèÿ.Äîêàçàòåëüñòâî. Ðàññìîòðèì ñëîâàðíûåîòíîøåíèÿ P = {(an bm , c n ) : m, n ≥ 0} èQ = {(am b n , c n ) : m, n ≥ 0} . Íåòðóäíî ïîñòðîèòüàâòîìàòû-ðàñïîçíàâàòåëè, ðåàëèçóþùèå ýòèîòíîøåíèÿ. Îäíàêî èõ ïåðåñå÷åíèåP ∩ Q = {(an b n , c n ) : n ≥ 0} î÷åâèäíî íå ÿâëÿåòñÿðàöèîíàëüíûì îòíîøåíèåì.QEDÐÀÖÈÎÍÀËÜÍÛÅ ÎÒÍÎØÅÍÈß È ÈÕÑÂÎÉÑÒÂÀÐàöèîíàëüíûå îòíîøåíèÿ ìîæíî çàäàâàòü ïðèïîìîùè ðåãóëÿðíûõ âûðàæåíèé:êîíñòàíòàìè îáúÿâëÿþòñÿ âñå ïàðû(x, ε), x ∈ Σ ∪ {ε} , è (ε, y ), y ∈ ∆ ∪ {ε} ;åñëè P1 è P2 ðåãóëÿðíûå âûðàæåíèÿ, òî(P1 + P2 ) , (P1 · P2 ) è (P1∗ ) òàêæåðåãóëÿðíûå âûðàæåíèÿ.Çíà÷åíèå R(P) ðåãóëÿðíîãî âûðàæåíèÿ Pîïðåäåëÿåòñÿ íà îñíîâàíèè îïåðàöèéîáúåäèíåíèÿ, êîíêàòåíàöèè è èòåðàöèè äëÿñëîâàðíûõ îòíîøåíèé òàê æå, êàê è äëÿ ÿçûêîâ.IIÐÀÖÈÎÍÀËÜÍÛÅ ÎÒÍÎØÅÍÈß È ÈÕÑÂÎÉÑÒÂÀÄëÿ ââåäåííûõ òàêèì îáðàçîì ðåãóëÿðíûõâûðàæåíèé ñïðàâåäëèâ àíàëîã òåîðåìû Êëèíè.Óòâåðæäåíèå 10.6.
Ñëîâàðíîå îòíîøåíèåÿâëÿåòñÿ ðåãóëÿðíûì òîãäà è òîëüêî òîãäà, êîãäàîíî ÿâëÿåòñÿ ðàöèîíàëüíûì.ÐÀÖÈÎÍÀËÜÍÛÅ ÎÒÍÎØÅÍÈß È ÈÕÑÂÎÉÑÒÂÀÄëÿ ââåäåííûõ òàêèì îáðàçîì ðåãóëÿðíûõâûðàæåíèé ñïðàâåäëèâ àíàëîã òåîðåìû Êëèíè.Óòâåðæäåíèå 10.6. Ñëîâàðíîå îòíîøåíèåÿâëÿåòñÿ ðåãóëÿðíûì òîãäà è òîëüêî òîãäà, êîãäàîíî ÿâëÿåòñÿ ðàöèîíàëüíûì.Äîêàçàòåëüñòâî. Ïðîâîäèòñÿ àíàëîãè÷íîäîêàçàòåëüñòâó òåîðåìû Êëèíè äëÿ êîíå÷íûõàâòîìàòîâ-ðàñïîçíàâàòåëåé.QEDÐÀÖÈÎÍÀËÜÍÛÅ ÎÒÍÎØÅÍÈß È ÈÕÑÂÎÉÑÒÂÀÏðèìåð.Ñëîâàðíîå îòíîøåíèåR6= = {(w , u) : w , u ∈ Σ∗ , u 6= w }ðàöèîíàëüíûì.ÿâëÿåòñÿÐÀÖÈÎÍÀËÜÍÛÅ ÎÒÍÎØÅÍÈß È ÈÕÑÂÎÉÑÒÂÀÏðèìåð.Ñëîâàðíîå îòíîøåíèåR6= = {(w , u) : w , u ∈ Σ∗ , u 6= w }ðàöèîíàëüíûì.ÿâëÿåòñÿÄëÿ ëþáîé ïàðû áóêâ x, yáóäåì èñïîëüçîâàòü çàïèñü (x, y ) äëÿ îáîçíà÷åíèÿ ðåãóëÿðíîãî âûðàæåíèÿ (x, ε) · (ε, y ) .Òîãäà R6= =PR(F1 + F2 +PF3) , ãäå PF1 = ( (x, x))∗ · ( (x, y )) · ((x, y ))∗ ,x∈Σx6=Pyx,yP∈ΣP∗F2 = ((x, y )) · ( (x, ε)) · ( (x, ε))∗ ,x,y∈Σx∈Σx∈ΣPPP∗F3 = ((x, y )) · ( (ε, y )) · ( (ε, y ))∗ .Äîêàçàòåëüñòâî.IIIx,y ∈Σy ∈Σy ∈ΣÐÀÖÈÎÍÀËÜÍÛÅ ÎÒÍÎØÅÍÈß È ÈÕÑÂÎÉÑÒÂÀÐàçðàáîòàòü àëãîðèòì, êîòîðûé äëÿàâòîìàòîâ-ðàñïîçíàâàòåëåé, ðåàëèçóþùèõîòíîøåíèÿ R1 è R2 , ñòðîèò àâòîìàò,ðåàëèçóþùèé èõ êîìïîçèöèþ R1 ◦ R2 .
Êàêîâàîöåíêà ðàçìåðà ýòîãî àâòîìàòà?Çàäà÷à 2. Âåðíî ëè, ÷òî âñÿêîå ñëîâàðíîåîòíîøåíèå P , êîòîðîå óäîâëåòâîðÿåò óñëîâèÿì1. Dom(P) è Range(P) ðåãóëÿðíûå ÿçûêè,2. L = {wu−1 : (w , u) ∈ P} ÊÑ-ÿçûêÿâëÿåòñÿ ðàöèîíàëüíûì.Çàäà÷à 1.ÐÀÖÈÎÍÀËÜÍÛÅ ÎÒÍÎØÅÍÈß È ÈÕÑÂÎÉÑÒÂÀÂåðíî ëè, ÷òî äëÿ ëþáîãîðàöèîíàëüíîãî îòíîøåíèÿ R , ñëîâàðíîåîòíîøåíèå R −1 = {(u, w ) : (w , u) ∈ R} òàêæåÿâëÿåòñÿ ðàöèîíàëüíûì?Çàäà÷à 4.
Âåðíî ëè, ÷òî äëÿ ëþáîãîðàöèîíàëüíîãî îòíîøåíèÿ R , ñëîâàðíîåîòíîøåíèå R rev = {(w −1, u−1) : (w , u) ∈ R} òàêæåÿâëÿåòñÿ ðàöèîíàëüíûì?Çàäà÷à 3.ÀËÃÎÐÈÒÌÈ×ÅÑÊÈÅ ÏÐÎÁËÅÌÛÀ êàê îáñòîèò äåëî ñ àëãîðèòìè÷åñêèìèïðîáëåìàìè?ÀËÃÎÐÈÒÌÈ×ÅÑÊÈÅ ÏÐÎÁËÅÌÛÀ êàê îáñòîèò äåëî ñ àëãîðèòìè÷åñêèìèïðîáëåìàìè?Î÷åâèäíî, ÷òî ïðîáëåìà ïóñòîòû äëÿðàöèîíàëüíûõ îòíîøåíèé R(A) = ∅? ðàçðåøèìà.Ïî÷åìó?ÀËÃÎÐÈÒÌÈ×ÅÑÊÈÅ ÏÐÎÁËÅÌÛÀ êàê îáñòîèò äåëî ñ àëãîðèòìè÷åñêèìèïðîáëåìàìè?Î÷åâèäíî, ÷òî ïðîáëåìà ïóñòîòû äëÿðàöèîíàëüíûõ îòíîøåíèé R(A) = ∅? ðàçðåøèìà.Ïî÷åìó?Èíà÷å îáñòîèò äåëî ñ äðóãèìè çàäà÷àìè.Óòâåðæäåíèå 10.7. Ïðîáëåìà òîòàëüíîñòè äëÿðàöèîíàëüíûõ îòíîøåíèé R(A) = Σ∗ × ∆∗?àëãîðèòìè÷åñêè íåðàçðåøèìà.ÀËÃÎÐÈÒÌÈ×ÅÑÊÈÅ ÏÐÎÁËÅÌÛÏîêàæåì, ÷òî Ïðîáëåìàñîîòâåòñòâèé Ïîñòà (ÏÑÏ) ñâîäèìà ê ïðîáëåìåòîòàëüíîñòè ðàöèîíàëüíûõ îòíîøåíèé.Ïóñòü çàäàíà ñèñòåìà ïàð ñëîâP = {(u1 , v1 ), (u2 , v2 ), .
. . , (uk , vk )} â àëôàâèòå ∆ .Äëÿ ýòîé ñèñòåìû îïðåäåëèì äâà îòíîøåíèÿ íàäàëôàâèòàìè Σ = {1, 2, . . . , k} è ∆ :Äîêàçàòåëüñòâî.RP1 = {(i1 i2 . . . in , ui1 ui2 . . . uin ) : n ≥ 1},RP2 = {(j1 j2 . . . jm , vj1 vj2 . . . vjm ) : m ≥ 1}.Íåòðóäíî âèäåòü, ÷òî îáà ýòè îòíîøåíèÿ ðàöèîíàëüíûå.ÀËÃÎÐÈÒÌÈ×ÅÑÊÈÅ ÏÐÎÁËÅÌÛÇíà÷èò, ðàöèîíàëüíûì ÿâëÿåòñÿ è îòíîøåíèåRP = (RP1 ◦ R6= ) + (RP2 ◦ R6= ).ÀËÃÎÐÈÒÌÈ×ÅÑÊÈÅ ÏÐÎÁËÅÌÛÇíà÷èò, ðàöèîíàëüíûì ÿâëÿåòñÿ è îòíîøåíèåRP = (RP1 ◦ R6= ) + (RP2 ◦ R6= ).Íî òîãäà ÏÑÏ äëÿ P èìååò ðåøåíèå i1, i2, . . . , inÀËÃÎÐÈÒÌÈ×ÅÑÊÈÅ ÏÐÎÁËÅÌÛÇíà÷èò, ðàöèîíàëüíûì ÿâëÿåòñÿ è îòíîøåíèåRP = (RP1 ◦ R6= ) + (RP2 ◦ R6= ).Íî òîãäà ÏÑÏ äëÿ P èìååò ðåøåíèå i1, i2, .
. . , in⇐⇒ui1 ui2 . . . uin = vi1 vi1 . . . vin = wÀËÃÎÐÈÒÌÈ×ÅÑÊÈÅ ÏÐÎÁËÅÌÛÇíà÷èò, ðàöèîíàëüíûì ÿâëÿåòñÿ è îòíîøåíèåRP = (RP1 ◦ R6= ) + (RP2 ◦ R6= ).Íî òîãäà ÏÑÏ äëÿ P èìååò ðåøåíèå i1, i2, . . . , in⇐⇒ui1 ui2 . . . uin = vi1 vi1 . . . vin = w⇐⇒/ RP2 ◦ R6=(i1 i2 . . . in , w ) ∈/ RP1 ◦ R6= , (i1 i2 . . . in , w ) ∈ÀËÃÎÐÈÒÌÈ×ÅÑÊÈÅ ÏÐÎÁËÅÌÛÇíà÷èò, ðàöèîíàëüíûì ÿâëÿåòñÿ è îòíîøåíèåRP = (RP1 ◦ R6= ) + (RP2 ◦ R6= ).Íî òîãäà ÏÑÏ äëÿ P èìååò ðåøåíèå i1, i2, . . . , in⇐⇒ui1 ui2 . . . uin = vi1 vi1 . .
. vin = w⇐⇒/ RP2 ◦ R6=(i1 i2 . . . in , w ) ∈/ RP1 ◦ R6= , (i1 i2 . . . in , w ) ∈⇐⇒RP 6= Σ∗ × ∆∗ .QEDÀËÃÎÐÈÒÌÈ×ÅÑÊÈÅ ÏÐÎÁËÅÌÛÏðîáëåìà ýêâèâàëåíòíîñòè äëÿêîíå÷íûõ àâòîìàòîâ-ïðåîáðàçîâàòåëåéàëãîðèòìè÷åñêè íåðàçðåøèìà.Ýòî îáñòîÿòåëüñòâî ñèëüíî çàòðóäíÿåòîïòèìèçàöèþ àâòîìàòîâ-ïðåîáðàçîâàòåëåé.Çàäà÷à 5. ßâëÿåòñÿ ëè àëãîðèòìè÷åñêèðàçðåøèìîé ïðîáëåìà âêëþ÷åíèÿ (w , u) ∈ R(A)äëÿ êîíå÷íûõ àâòîìàòîâ-ïðåîáðàçîâàòåëåé?Çàäà÷à 6. ßâëÿåòñÿ ëè àëãîðèòìè÷åñêèðàçðåøèìîé ïðîáëåìà ïóñòîòû ïåðåñå÷åíèÿR(A) ∩ R(B) = ∅ äëÿ êîíå÷íûõàâòîìàòîâ-ïðåîáðàçîâàòåëåé?Ñëåäñòâèå.ÀËÃÎÐÈÒÌÈ×ÅÑÊÈÅ ÏÐÎÁËÅÌÛÏðîáëåìà ýêâèâàëåíòíîñòè äëÿêîíå÷íûõ àâòîìàòîâ-ïðåîáðàçîâàòåëåéàëãîðèòìè÷åñêè íåðàçðåøèìà.Ýòî îáñòîÿòåëüñòâî ñèëüíî çàòðóäíÿåòîïòèìèçàöèþ àâòîìàòîâ-ïðåîáðàçîâàòåëåé.Çàäà÷à 5.
![](https://s.studizba.com/z.php?f=/templates/si/i/noavatar.png&w=100&h=100&t=1"){kind=avatar}
