10. Конечные автоматы-преобразователи. Рациональные отношения и их свойства. Описание рациональных отношений регулярными выражениями (1162498), страница 4

Просмтор этого файла доступен только зарегистрированным пользователям. Но у нас супер быстрая регистрация: достаточно только электронной почты!

Текст из файла (страница 4)

Ïðåäïîëîæèì,÷òî äëÿ íåêîòîðîé ïàðû âõîäíûõ ñëîâ w 0, w 00 âàâòîìàòå A1 × A2 ñóùåñòâóþò âû÷èñëåíèÿËåììà 2.w0q0 −→∗ (s1 , s2 , [β10 , β20 ]),w 00q0 −→∗ (s1 , s2 , [β100 , β200 ]).Òîãäà [β10 , β20 ] = [β100, β200] .ÄÅÒÅÐÌÈÍÈÐÎÂÀÍÍÛÅÏÐÅÎÁÐÀÇÎÂÀÒÅËÈÏóñòü L(A1×A2)=∅. Ïðåäïîëîæèì,÷òî äëÿ íåêîòîðîé ïàðû âõîäíûõ ñëîâ w 0, w 00 âàâòîìàòå A1 × A2 ñóùåñòâóþò âû÷èñëåíèÿËåììà 2.w0q0 −→∗ (s1 , s2 , [β10 , β20 ]),w 00q0 −→∗ (s1 , s2 , [β100 , β200 ]).Òîãäà [β10 , β20 ] = [β100, β200] .Èç Ëåììû 2 ñëåäóåò, ÷òî â ñëó÷àå L(A1×A2)=∅èç íà÷àëüíîãî ñîñòîÿíèÿ q0 àâòîìàòà A1×A2äîñòèæèìî íå áîëåå |S1| × |S2| ðàçëè÷íûõñîñòîÿíèé. È ïîýòîìó ïðîñòðàíñòâî ïîèñêàñòàíîâèòñÿ îãðàíè÷åííûì.ÄÅÒÅÐÌÈÍÈÐÎÂÀÍÍÛÅÏÐÅÎÁÐÀÇÎÂÀÒÅËÈA1 × A2q0-e(s1 , s2 , [β10 , β20 ])-e(s1 , s2 , [β100 , β200 ])w0ew 00L(A1 × A2 ) = ∅ÄÅÒÅÐÌÈÍÈÐÎÂÀÍÍÛÅÏÐÅÎÁÐÀÇÎÂÀÒÅËÈA1 × A2q0w0ew 00L(A1 × A2 ) = ∅[β10 , β20 ]j= )* e (s1 , s2 ,[β100 , β200 ]ÄÅÒÅÐÌÈÍÈÐÎÂÀÍÍÛÅÏÐÅÎÁÐÀÇÎÂÀÒÅËÈÁåç îãðàíè÷åíèÿîáùíîñòè áóäåì ïîëàãàòü = ε (â ñëó÷àå β20 = εäîêàçàòåëüñòâî ïðîâîäèòñÿ àíàëîãè÷íûìîáðàçîì).Äîêàçàòåëüñòâî ëåììû 2.β10ÄÅÒÅÐÌÈÍÈÐÎÂÀÍÍÛÅÏÐÅÎÁÐÀÇÎÂÀÒÅËÈÁåç îãðàíè÷åíèÿîáùíîñòè áóäåì ïîëàãàòü = ε (â ñëó÷àå β20 = εäîêàçàòåëüñòâî ïðîâîäèòñÿ àíàëîãè÷íûìîáðàçîì).w0Ñîãëàñíî Ëåììå 1 åñëè q0 −→∗ (s1 , s2 , [ε, β2 ]) , òîâ àâòîìàòàõ-ïðåîáðàçîâàòåëÿõ A1 è A2 åñòüâû÷èñëåíèÿw ,αÄîêàçàòåëüñòâî ëåììû 2.β10000s01 −→1 ∗ s1 ,w 0 ,α0s02 −→2 ∗ s2 .è ïðè ýòîì Dif (α10 , α20 ) = (ε, β20 ) .ÄÅÒÅÐÌÈÍÈÐÎÂÀÍÍÛÅÏÐÅÎÁÐÀÇÎÂÀÒÅËÈA1 × A2-ew0q0(s1 , s2 , [ε, β20 ])eA1s01A2s02ÄÅÒÅÐÌÈÍÈÐÎÂÀÍÍÛÅÏÐÅÎÁÐÀÇÎÂÀÒÅËÈA1 × A2-ew0q0(s1 , s2 , [ε, β20 ])eA1s01 w 0 , α01A2s1s02 w 0 , α02s2ÄÅÒÅÐÌÈÍÈÐÎÂÀÍÍÛÅÏÐÅÎÁÐÀÇÎÂÀÒÅËÈÏîñêîëüêó â àâòîìàòå A1 íåòáåñïîëåçíûõ ñîñòîÿíèé, äëÿ íåêîòîðîãî âõîäíîãî ñëîâà u âýòîì àâòîìàòå åñòü ôèíàëüíîå âû÷èñëåíèå èç ñîñòîÿíèÿ s1Äîêàçàòåëüñòâî ëåììû 2.u,γ1s1 −→ fin1 , fin1 ∈ F1ÄÅÒÅÐÌÈÍÈÐÎÂÀÍÍÛÅÏÐÅÎÁÐÀÇÎÂÀÒÅËÈA1 × A2-ew0q0(s1 , s2 , [ε, β20 ])eA1s01 w 0 , α01A2s1s02 w 0 , α02s2ÄÅÒÅÐÌÈÍÈÐÎÂÀÍÍÛÅÏÐÅÎÁÐÀÇÎÂÀÒÅËÈA1 × A2-ew0q0(s1 , s2 , [ε, β20 ])eA1s01 w 0 , α01A2s1 u, γ1- fin1 s02s200w , α2 ÄÅÒÅÐÌÈÍÈÐÎÂÀÍÍÛÅÏÐÅÎÁÐÀÇÎÂÀÒÅËÈÏîñêîëüêó â àâòîìàòå A1 íåòáåñïîëåçíûõ ñîñòîÿíèé, äëÿ íåêîòîðîãî âõîäíîãî ñëîâà u âýòîì àâòîìàòå åñòü ôèíàëüíîå âû÷èñëåíèå èç ñîñòîÿíèÿ s1Äîêàçàòåëüñòâî ëåììû 2.u,γ1s1 −→ fin1 , fin1 ∈ F1Çíà÷èò, RA (w 0u) = α10 γ1 .1ÄÅÒÅÐÌÈÍÈÐÎÂÀÍÍÛÅÏÐÅÎÁÐÀÇÎÂÀÒÅËÈÏîñêîëüêó â àâòîìàòå A1 íåòáåñïîëåçíûõ ñîñòîÿíèé, äëÿ íåêîòîðîãî âõîäíîãî ñëîâà u âýòîì àâòîìàòå åñòü ôèíàëüíîå âû÷èñëåíèå èç ñîñòîÿíèÿ s1Äîêàçàòåëüñòâî ëåììû 2.u,γ1s1 −→ fin1 , fin1 ∈ F1Çíà÷èò, RA (w 0u) = α10 γ1 .Ïîñêîëüêó L(A1 × A2) = ∅ , àâòîìàòû A1 è A2 ýêâèâàëåíòíû.Ïîýòîìó RA (w 0u) = RA (w 0u) .

Çíà÷èò, àâòîìàò A1 èìååòóñïåøíîå âû÷èñëåíèå111w 0 ,α0u,γ2s02 −→2 s2 −→ fin2 , fin2 ∈ F2 ,äëÿ êîòîðîãî èìååò ìåñòî ðàâåíñòâî α10 γ1 = α20 γ2 .ÄÅÒÅÐÌÈÍÈÐÎÂÀÍÍÛÅÏÐÅÎÁÐÀÇÎÂÀÒÅËÈA1 × A2-ew0q0(s1 , s2 , [ε, β20 ])eA1s01 w 0 , α01A2s1 u, γ1- fin1 s02s200w , α2 ÄÅÒÅÐÌÈÍÈÐÎÂÀÍÍÛÅÏÐÅÎÁÐÀÇÎÂÀÒÅËÈA1 × A2-ew0q0(s1 , s2 , [ε, β20 ])eA1s01 w 0 , α01A2u, γ2-s1 u, γ1- fin1 s02sfin2200w , α2 ÄÅÒÅÐÌÈÍÈÐÎÂÀÍÍÛÅÏÐÅÎÁÐÀÇÎÂÀÒÅËÈÐàâåíñòâàα10 γ1 = α20 γ2 è Dif (α10 .α20 ) = [ε, β20 ] âëåêóòÄîêàçàòåëüñòâî ëåììû 2.Dif (α10 γ1 , α20 γ2 ) = [ε, ε]Dif (α10 γ1 , α20 γ2 ) = Dif (γ1 , β20 γ2 ).Òàêèì îáðàçîì, γ1 = β20 γ2 .ÄÅÒÅÐÌÈÍÈÐÎÂÀÍÍÛÅÏÐÅÎÁÐÀÇÎÂÀÒÅËÈÐàâåíñòâàα10 γ1 = α20 γ2 è Dif (α10 .α20 ) = [ε, β20 ] âëåêóòÄîêàçàòåëüñòâî ëåììû 2.Dif (α10 γ1 , α20 γ2 ) = [ε, ε]Dif (α10 γ1 , α20 γ2 ) = Dif (γ1 , β20 γ2 ).Òàêèì îáðàçîì, γ1 = β20 γ2 .Òî÷íî òàêèå æå ðàññóæäåíèÿ ìîæíî ïðîâåñòè èw0000äëÿ âû÷èñëåíèÿ q0 −→∗ (s1 , s2 , [β1 , β2 ]) âàâòîìàòå A1 × A2 .00ÄÅÒÅÐÌÈÍÈÐÎÂÀÍÍÛÅÏÐÅÎÁÐÀÇÎÂÀÒÅËÈA1 × A2-e(s1 , s2 , [ε, β20 ])-e(s1 , s2 , [β100 , β200 ])w0q0ew 00A1s01 w 0 , α01A2u, γ2-s1 u, γ1- fin1 s02sfin2200w , α2 ÄÅÒÅÐÌÈÍÈÐÎÂÀÍÍÛÅÏÐÅÎÁÐÀÇÎÂÀÒÅËÈA1 × A2-e(s1 , s2 , [ε, β20 ])-e(s1 , s2 , [β100 , β200 ])w0q0ew 00A1A2w 00 , α100 w 00 , α200 R u, γ Ru, γ2-112sfinsfin21ss1200w 0 , α10 w 0 , α20 ÄÅÒÅÐÌÈÍÈÐÎÂÀÍÍÛÅÏÐÅÎÁÐÀÇÎÂÀÒÅËÈÒàêèì îáðàçîì,ìû ïðèõîäèì ê ñëåäóþùèì ðàâåíñòâàìÄîêàçàòåëüñòâî ëåììû 2.γ1= β20 γ2β100 γ1= β200 γ2β100 = ε ∨ β200 = ε.ÄÅÒÅÐÌÈÍÈÐÎÂÀÍÍÛÅÏÐÅÎÁÐÀÇÎÂÀÒÅËÈÒàêèì îáðàçîì,ìû ïðèõîäèì ê ñëåäóþùèì ðàâåíñòâàìÄîêàçàòåëüñòâî ëåììû 2.γ1= β20 γ2β100 γ1= β200 γ2β100 = ε ∨ β200 = ε.Îòñþäà ñëåäóåò β100 = ε = β10 è β200 = β100 .QEDÄÅÒÅÐÌÈÍÈÐÎÂÀÍÍÛÅÏÐÅÎÁÐÀÇÎÂÀÒÅËÈÄëÿïðîâåðêè ýêâèâàëåíòíîñòè àâòîìàòîâ-ïðåîáðàçîâàòåëåé A1 è A2 ðàññìîòðèì àâòîìàò A1 × A2 , âêîòîðîì ïðîâåäåì ïîèñê ôèíàëüíûõ ñîñòîÿíèé,äîñòèæèìûõ èç èíèöèàëüíîãî ñîñòîÿíèÿ.Åñëè òàêîå ôèíàëüíîå ñîñòîÿíèå áóäåò íàéäåíîèëè â ïðîöåññå ïîèñêà óäàñòñÿ äîñòè÷ü áîëåå|S1 | × |S2 | ñîñòîÿíèé, òî àâòîìàòûïðåîáðàçîâàòåëè A1 è A2 íåýêâèâàëåíòíû. ïðîòèâíîì ñëó÷àå àâòîìàòû A1 è A2ýêâèâàëåíòíûQEDÄîêàçàòåëüñòâî Òåîðåìû 10.8.ÄÅÒÅÐÌÈÍÈÐÎÂÀÍÍÛÅÏÐÅÎÁÐÀÇÎÂÀÒÅËÈÊàêîâà ñëîæíîñòü àëãîðèòìà ïðîâåðêè ýêâèâàëåíòíîñòè êîíå÷íûõ äåòåðìèíèðîâàííûõàâòîìàòîâ-ïðåîáðàçîâàòåëåé?Çàäà÷à 7.ÄÅÒÅÐÌÈÍÈÐÎÂÀÍÍÛÅÏÐÅÎÁÐÀÇÎÂÀÒÅËÈÊàêîâà ñëîæíîñòü àëãîðèòìà ïðîâåðêè ýêâèâàëåíòíîñòè êîíå÷íûõ äåòåðìèíèðîâàííûõàâòîìàòîâ-ïðåîáðàçîâàòåëåé?Íåäåòåðìèíèðîâàííûé àâòîìàò-ïðåîáðàçîâàòåëüA íàçûâàåòñÿ ôóííêöèîíàëüíûì , åñëè ðåàëèçóåìîå èì îòíîøåíèå RA ÿâëÿåòñÿ ôóíêöèåé, ò.å.äëÿ ëþáîãî âõîäíîãî ñëîâà w ñóùåñòâóåò íå áîëååîäíîé òàêîé ñòðîêè α , ÷òî (w , α) ∈ RA .Çàäà÷à 8 [Òðóäíàÿ].

Cóùåñòâóåò ëè àëãîðèòìïðîâåðêè ñâîéñòâà ôóíêöèîíàëüíîñòè äëÿêîíå÷íûõ àâòîìàòîâ-ïðåîáðàçîâàòåëåé?Çàäà÷à 7.ÀÂÒÎÌÀÒÛ-ÏÐÅÎÁÐÀÇÎÂÀÒÅËÈÈÒÎÃÈ.Êîíå÷íûå àâòîìàòû-ïðåîáðàçîâàòåëè çàíèìàþòïðîìåæóòî÷íîå ïîëîæåíèå ìåæäó àâòîìàòàìèðàñïîçíàâàòåëÿìè è ìàãàçèííûìè àâòîìàòàìè.Äëÿ ðàçðåøèìûõ çàäà÷ àíàëèçà ïîâåäåíèÿàâòîìàòîâ-ïðåîáðàçîâàòåëåé ìîæíî èñïîëüçîâàòüòàêèå æå ìåòîäû, êàê è äëÿ àíàëèçà êîíå÷íûõàâòîìàòîâ-ðàñïîçíàâàòåëåé.À äëÿ äîêàçàòåëüñòâà íåðàçðåøèìîñòè ìîæíîïðèìåíÿòü òå æå ïðèåìû, êîòîðûå áûëèèñïîëüçîâàíû äëÿ ìàãàçèííûõ àâòîìàòîâ.ÀÂÒÎÌÀÒÛ-ÏÐÅÎÁÐÀÇÎÂÀÒÅËÈÈÒÎÃÈ.Êîíå÷íûå àâòîìàòû-ïðåîáðàçîâàòåëè çàíèìàþòïðîìåæóòî÷íîå ïîëîæåíèå ìåæäó àâòîìàòàìèðàñïîçíàâàòåëÿìè è ìàãàçèííûìè àâòîìàòàìè.Äëÿ ðàçðåøèìûõ çàäà÷ àíàëèçà ïîâåäåíèÿàâòîìàòîâ-ïðåîáðàçîâàòåëåé ìîæíî èñïîëüçîâàòüòàêèå æå ìåòîäû, êàê è äëÿ àíàëèçà êîíå÷íûõàâòîìàòîâ-ðàñïîçíàâàòåëåé.À äëÿ äîêàçàòåëüñòâà íåðàçðåøèìîñòè ìîæíîïðèìåíÿòü òå æå ïðèåìû, êîòîðûå áûëèèñïîëüçîâàíû äëÿ ìàãàçèííûõ àâòîìàòîâ.Âñå ýòè ìåòîäû ÿâëÿþòñÿìíîãîðàçîâûìè!ÄÅÒÅÐÌÈÍÈÐÎÂÀÍÍÛÅÏÐÅÎÁÐÀÇÎÂÀÒÅËÈÀ êàê ïîñòðîèòüàëãîðèòì ìèíèìèçàöèè êîíå÷íûõäåòåðìèíèðîâàííûõ àâòîìàòîâ-ïðåîáðàçîâàòåëåé?Çàäà÷à 9 [Òðóäíàÿ].ÊÎÍÅÖ ËÅÊÖÈÈ 10.

Характеристики

Список файлов лекций