Iv_task6 (XPS13_s conflicted copy 2014-12-02) (1178903)
Текст из файла
Ñåðãåé Èâàíû÷åâÃðóïïà 376ÔÓÏÌ ÌÔÒÈsergeyivanychev@gmail.comvk.com/ivanychevsergey+79104577995Âåðñèÿ 1.0Çàäàíèå 6ÃðàììàòèêèÓïðàæíåíèå 1Äëÿ äîêàçàòåëüñòâà ñîîòâåòñòâóþùåé ýêâèâàëåíòíîñòè âîçüìåì ïðîèçâîëüíóþ ïðàâîëèíåéíóþ ãðàììàòèêó è äîêàæåì, ÷òî äëÿ íåå ñóùåñòâóåò ýêâèâàëåíòíàÿ ðåãóëÿðíàÿ ïðàâîëèíåéíàÿ ãðàììàòèêà.
Îáðàòíîå óòâåðæäåíèå î÷åâèäíî, òàê êàê ÐÏà óäîâëåòâîðÿåò îïðåäåëåíèþ ÏÃ.Ïóñòü ó íàñ åñòü íåêàÿ ãðàììàòèêà Γ ñ íåêèì êîíå÷íûì íàáîðîì ïðàâèë P . Ðàññìîòðèìïðîèçâîëüíîå ïðàâèëîA → αBÈ ñîïîñòàâèì åìó â îáðàçîâûâàåìîé ÐÏË íàáîð ïðàâèë.A → α[1] · (α[2, |α|]B) ≡ α[1]B1B1 → α[2]B2...Bn−1 → α[n]B(1)Åñëè ñðåäè ïðàâèë âûâîäà èñõîäíîé ãðàììàòèêè ñóùåñòâóåò ïðàâèëî âûâîäàA→εÒî ïåðåîáàçíà÷èì åãî íåòåðìèíàëîì A0 , èçìåíèâ ñîîòâåòñòâóþùèå A ïðàâèëà òàêèì îáðàçîì:A → aB ⇒ A0 → aB(2)E → aA ⇒ {E → aA0 , E → a}Ýòî ñäåëàíî äëÿ òîãî, ÷òîáû âûêèíóòü ïðèìåíåíèå ïðàâèëà A → ε èç âûâîäà, ÷òî ìîæíîñäåëàòü, òàê êàê òåðìèíàë A áûë âûâåäåí ïî íåêîìó ïðàâèëó B → αA, êîòîðîå â íîâîì âûâîäå áóäåò çàìåíåíî ïî 2 íà B → α (âûâîä èìåííî òîãî íåòåðìèíàëà, êîòîðûé â ðåçóëüòàòåñëåäóþùåãî âûâîäà îáðàòèëñÿ áû â ε).1Òàêèì îáðàçîì ïîñòðîåííàÿ ãðàììàòèêà áóäåò ÐÏÃ, òàê êàê âñå ïðàâèëà âûâîäà óäîâëåòâîðÿþò îïðåäåëåíèþ ÐÏÃ.Ðàññìîòðèì íåêîå ñëîâî w ∈ Γ. Òîãäà äëÿ w ñóùåñòâóåò íåêèé êîíå÷íûé âûâîä.
Îáîçíà÷èìçà Γ0 ïîñòðîåííóþ ÐÏË. Íàì íóæíî äîêàçàòü, ÷òî w âûâîäèìî â Γ0 .Ïóñòü â Γ âûâîä ñîñòîèò èç n ïðèìåíåíèé ïðàâèë. Ëþáîå èç ýòèõ ïðàâèë èìååò âèä A → aBèëè A → ε ïî îïðåäåëåíèþ. Ðàññìîòðèì ïåðâîå ïðèìåíåííîå ïðàâèëî âûâîäà â Γ. Åñëè ýòîïðàâèëî ïåðâîå, òî â ðåçóëüòàòå ïîñëåäîâàòåëüíîãî ïðèìåíåíèÿ ïðàâèë, îïèñàííûõ â 1,òàê êàê âûâîä â Γ0 âûâîä âûãëÿäèò êàê A ⇒ α[1]B 0 ⇒ α[1, 2]B 00 .
. . αB .Åñëè ýòî ïðàâèëî âòîðîå, òî ñîïîñòàâëÿåì (âñå åùå ðàññìàòðèâàåì ïåðâîå ïðàâèëî ââûâîäå) åìó S 0 → ε.Äëÿ k -ãî ïðàâèëà â âûâîäå äëÿ Γ: åñëè îíî ïåðâîãî òèïà òî ïî 1 çàìåíÿåì åãî íà ïîñëåäîâàòåëüíîñòü, âòîðîãî âèäà îí áûòü íå ìîæåò ïî ïóíêòó 2, ãäå ìû çàìåíèëè ñîîòâåòñòâóþùèåïðàâèëà ýêâèâàëåíòíûìè.
Òàêèì îáðàçîì ìû ïîëó÷èëè äëÿ ïðîèçâîëüíîãî ñëîâà ãðàììàòèêè Γ ýêâèâàëåíòíûé âûâîä â ãðàììàòèêå Γ0 , òî åñòü ÿçûêè ýòèõ ãðàììàòèê ýêâèâàëåíòíû.Óïðàæíåíèå 2Èç îäíîçíà÷íîñòè ãðàììàòèêè â åäèíñòâåííîñòü ëåâîãî ðàçáîðàÑíà÷àëà äîêàæåì, ÷òî åñëè ãðàììàòèêà Γ(N, T, P, S) ÿâëÿåòñÿ îäíîçíà÷íîé, òî∀w ∈ L(Γ) ∃ ! S ⇒ wlm(3)Ïóñòü ãðàììàòèêà ÿâëÿåòñÿ îäíîçíà÷íîé, òîãäà äëÿ ëþáîãî ñëîâà ÿçûêà äàííîé ãðàììàòèêè ñóùåñòâóåò è åäèíñòâåíåí êîíå÷íûé âûâîä. Èç ñóùåñòâîâàíèÿ âûâîäà äàííîãî ñëîâàw èç àêñèîìû ãðàììàòèêè S íàïðÿìóþ ñëåäóåò ñóùåñòâîâàíèå äåðåâà ðàçáîðà ñ êîðíåì Sè êðîíîé w 1 .
Èç ñóùåñòâîâàíèÿ äåðåâà ðàçáîðà ñëåäóåò, ñóùåñòâîâàíèå ëåâîãî ðàçáîðà. 2 .Ïóñòü ñóùåñòâóåò õîòÿ áû äâà ðàçëè÷íûõ ëåâûõ ðàçáîðà. Ïîñòðîåíèå äåðåâà íà÷èíàåòñÿ ñïîñòðîåíèÿ êîðíÿ(àêñèîìû), êîòîðàÿ ïóñòü èìååò ïðîäóêöèþ S → X1 . . . Xk , Xi ∈ {T ∪ U }.Êàæäàÿ ñëåäóþùàÿ ïðîäóêöèÿ ñòðîèòñÿ çàìåíîé ñàìîãî ëåâîãî íåòåðìèíàëüíîãî ñèìâîëàíåêîé ïîñëåäîâàòåëüíîñòüþ ñèìâîëîâ, ÷òî â öåëîì ñïðàâåäëèâî äëÿ ÊÑ-ãðàììàòèê. Ïðèýòîì ïîíÿòíî, ÷òî ïàðàëëåëüíî ñ êàæäîé ïðîäóêöèåé (ïóñòü áóäåò ïðîèñõîäèòü çàìåíà Xi )ó âåðøèíû Xi ïîÿâëÿþòñÿ ñîîòâåòñòâåííûå ïîòîìêè, ïîðÿäîê ñëåâà íàïðàâî êîòîðûõ áóäåò àíàëîãè÷åí çàìåíå ñèìâîëà Xi â äàííîé ïðîäóêöèè. Ïðè ýòî ìû ïîëó÷àåì, ÷òî ïðèïåðâîì íåñîâïàäåíèè ïðîäóêöèé â äâóõ ëåâûõ âûâîäàõ ìû áóäåò èìåòü ïðè ñîîòâåòñòâóþùèõ âåðøèíàõ äåðåâà ðàçëè÷íûõ ïîòîìêîâ, èç ÷åãî ñëåäóåò ðàçëè÷èå êîíå÷íûõ äåðåâüåâðàçáîðà.
Îäíàêî èç ýòîãî ôàêòà ñëåäóåò íåîäíîçíà÷íîñòü ãðàììàòèêè, ÷òî ïðîòèâîðå÷èòèçíà÷àëüíîìó ïðåäïîëîæåíèþ.12Ä.Õîïêðîôò, Ð.Ìîòâàíè, Ä.Óëüìàí `'Ââåäåíèå â òåîðèþ àâòîìàòîâ è âû÷èñëåíèé, òåîðåìà 5.12Ä.Õîïêðîôò, Ð.Ìîòâàíè, Ä.Óëüìàí `'Ââåäåíèå â òåîðèþ àâòîìàòîâ è âû÷èñëåíèé, òåîðåìà 5.142Èç åäèíñòâåííîñòè ëåâîãî ðàçáîðà â îäíîçíà÷íîñòü ãðàììàòèêèÏóñòü ýòî íå òàê, òîãäà ñóùåñòâóåò õîòÿ áû äâà äåðåâà ðàçáîðà äëÿ íåêîãî ñëîâà w ãðàììàòèêè Γ. Äëÿ êàæäîãî äåðåâà ñóùåñòâóåò è åäèíñòâåíåí ëåâûé âûâîä, ÷òî äîêàçàíî âûøå.Äîêàæåì, ÷òî ïîñòðîåííûå ëåâûå âûâîäû äëÿ êàæäîãî èç äåðåâüåâ ðàçëè÷íû, ÷òî ïðîòèâîðå÷èò èçíà÷àëüíîìó ïðåäïîëîæåíèþ. Äëÿ äîêàçàòåëüñòâà äàííîãî ôàêòà ïðèâåäåìàëãîðèòì ïîñòðîåíèÿ ëåâîãî âûâîäà.Áóäåì èñïîëüçîâàòü èíäóêöèþ ïî âûñîòå äåðåâà.• Áàçà.Ïóñòü âûñîòà äåðåâà ðàâíà 1, òîãäà ìû èìååì äåëî ñ ïðîäóêöèåéA ⇒ t1 .
. . tk , ti ∈ T ∀i, êîòîðàÿ òàêæå ÿâëÿåòñÿ ëåâîé.• Øàã.Ïóñòü âûñîòà äåðåâà n, òîãäà A ⇒ X1 . . . Xk , Xi ∈ {T ∪ U } Xi ∈ T , òîãäà îáîçíà÷èì ýòîò òåðìèíàëüíûé ñèìâîë çà wi . Xi ∈ U , òîãäà äåðåâî ðàçáîðà ýòîé ïåðåìåííîé èìååò âûñîòó < n, òî åñòü ñòðîèòüëåâûé âûâîä äëÿ íåãî ìû óìååì ïî ïðåäïîëîæåíèþ èíäóêöèè.
Îáîçíà÷èì êðîíóäàííîãî ïîääåðåâà çà wi .Çàìåòèì, ÷òî w = w1 . . . wk . ,Òàêèì îáðàçîì âûâîä áóäåò ïðåäñòàâëÿòü ñîáîé ïîñëåäîâàòåëüíîñòü ïðîäóêöèéA ⇒ X1 . . . Xk ⇒∗ w1 X2 . . . Xk ⇒∗ w1 . . . wk ⇒ wlmlmlmlm(4)Äîêàæåì, ÷òî äàííàÿ ïîñëåäîâàòåëüíîñòü ÿâëÿåòñÿ ëåâûì âûâîäîì.
Çäåñü áóäåò èìåòüåùå îäíà èíäóêöèÿ, ïàðàìåòðîì êîòîðîé áóäåò íîìåð ðàñêðûâàåìîãî íåòåðìèíàëà Xi .Ïîä ïîëíûì ðàñêðûòèåì ÿ ïîíèìàþXi ⇒∗ ti1 . . . tim : tij ∈ T .lm Áàçà. A ⇒ X1 . . . Xk ëåâàÿ ïðîäóêöèÿ, òàê êàê â èçíà÷àëüíîé ñòðîêå ëèøülmîäèí íåòåðìèíàëüíûé ñèìâîë. Øàã. Ïóñòü A ⇒ w1 . . . wn Xn+1 . .
. Xk . Òîãäà òàê êàê äëÿ Xn+1 ïîääåðåâî èìååòlmâûñîòó ìåíåå n (åñëè ñèìâîë òåðìèíàëüíûé, òî ïåðåõîäèì ê ñëåäóþùåìó), òîåñòü ìû óìååì ñòðîèòü ïî íåìó ëåâûé âûâîä. Òîãäà èç êîíòåêñòíî-ñâîáîäíîñòèΓ ñëåäóåò, ÷òî ìû ìîæåì ïîäñòàâèòü âûâîä äëÿ Xn+1 â âûâîä äëÿ A ïðè ýòîì îíîñòàíåòñÿ ëåâûì, òàê ñàìûé ëåâûé íåòåðìèíàëüíûé ñèìâîë íàõîäèòñÿ â Xn+1 .Òàêèì îáðàçîì ìû ïîñòðîèëè ëåâûé âûâîä äëÿ äåðåâà ðàçáîðà âûñîòîé n.Òàêèì îáðàçîì äëÿ ëþáîãî äåðåâà ðàçáîðà â ÊÑ ìû ìîæåì ñòðîèòü îäèí è òîëüêî îäèí (äîêàçàíî â ïóíêòå 1) ëåâûé âûâîä.
Ïðèìåíèì äàííûé àëãîðèòì äëÿ äâóõ ðàçëè÷íûõ äåðåâüåâ.Ïîíÿòíî, ÷òî ïðèìåíÿÿ ýòîò àëãîðèòì ê äâóì ðàçëè÷íûì äåðåâüÿì íà íåêîì îäèíàêîâîìøàãå ìû íàòêíåìñÿ íà ðàçëè÷íûå ïðîäóêöèè îäíîãî è òîãî æå òåðìèíàëà, òî åñòü ïîñòðîåííûå ïî íèì ëåâûå âûâîäû áóäóò ðàçëè÷àòüñÿ â ìåñòå ðàñêðûòèÿ ýòîãî òåðìèíàëà, òî åñòüíå áóäóò îäèíàêîâûìè.3Çàäà÷à 1aq1bεεaaaq0q2q3bq4Ïîñòðîèì ãðàììàòèêó Γ = {N, T, P, S}, S = Q0 , N = {Q0 , Q1 , Q2 , Q3 , Q4 }, T = {a, b}. Ïîñòðîèì ïðàâèëà âûâîäà δ → P êàêqj 6∈ F : (qi , a) → qj −→ Qi → aQjqj ∈ F : (qi , a) → qj −→ Qi → a|aQja ∈ T ∪ {ε}(5)Ãäå ãðàììàòèêà 5 ÿâëÿåòñÿ ïðàâîëèíåéíîé ïî îïðåäåëåíèþ.
Äîêàæåì êîððåêòíîñòü ãðàììàòèêè, ïîñòðîåííîé ïî äàííîé ïðîöåäóðå äëÿ äàííîãî ÍÊÀ.Ïóñòü w ∈ L(A), òîãäà (q0 , w) ` (qa , w[2, |w|]) `∗ (qF , ε) - ïîñëåäîâàòåëüíîñòü êîíôèãóðàöèé.Òîãäà ìû èìååì âûâîä ïîñëåäîâàòåëüíîñòè ñèìâîëîâ w[1 : 1]Qa S ⇒ w[1]Qa , ãäå äàííàÿïðîäóêöèÿ ñóùåñòâóåò òàê êàê ñóùåñòâóåò ïîäîáíîå áèíàðíîå ñîîòâåòñòâèå (ñì. ïðàâèëàïîñòðîåíèÿ ïðîäóêöèé, ãäå äëÿ êàæäîãî áèíàðíîãî îòíîøåíèÿ ïîñòðîåíà ñîîòâåòñòâóþùàÿïðîäóêöèÿ).Òàêèì îáðàçîì, åñëè ìû èìååì âûâîä ïîñëåäîâàòåëüíîñòè ñèìâîëîâ w[1 : k]Qm è (qm , w[k −1, |w|]) ` (qn , w[k, |w|], òî ìû èìååì âûâîä ïîñëåäîâàòåëüíîñòè w[1 : k]Qn , òàê êàê w[1 :k − 1]Qm ⇒ w[1 : k − 1]w[k]Qn ≡ w[1 : k]Qn , ãäå ñóùåñòâîâàíèå ïðîäóêöèè Qm ⇒ [k]Qnñëåäóåò èç ñóùåñòâîâàíèÿ îòîáðàæåíèÿ (qm , w[k : |w|]) → qn .w ñëó÷àå ïîñëåäíåãî â ïîñëåäîâàòåëüíîñòè áèíàðíîãî îòíîøåíèÿ, ñîîòâåòñòâóþùàÿ åìóïðîäóêöèÿ áóäåò ôèíàëüíîé â âûâîäå, ïðè ýòîì ñóùåñòâóÿ òàêæå èç ïðàâèë ïîñòðîåíèÿïðîäóêöèé.
Òàêèì îáðàçîì ìû ñîñòàâèëè âûâîä äëÿ ïðîèçâîëüíîãî w, òî åñòü L(A) ⊂ L(Γ)Äîêàæåì, ÷òî ëþáîå ñëîâî, ïðèíàäëåæàùåå ÿçûêó äàííîé ãðàìàòèêè ïðèíàäëåæèò L(A).Âîçüìåì ïðîèçâîëüíîå âûâîäèìîå ñëîâî, à, òî÷íåå, åãî âûâîä. Òîãäà íà êàæäîé ïðîäóêöèèó íàñ ïðîèñõîäèò çàìåíà íåêîãî íåòåðìèíàëà íà êîíêàòåíàöèþ íåêèõ òåðìèíàëà è íåòåðìèíàëà. Åñëè òàêàÿ ïðîäóêöèÿ ñóùåñòâóåò (îáîçíà÷èì åå êàê Qa ⇒ tQb ), òî òàêæå ñóùåñòâóåòîòîáðàæåíèå (qa , t) → qb ïî ñïîñîáó ïîñòðîåíèÿ ïðîäóêöèé. Èç ýòîãî ñëåäóåò, ÷òî êàæäîéïðîäóêöèè ñîîòâåòñòâóåò ñóùåñòâóþùåå îòîáðàæåíèå â àâòîìàòå. Ïîñëåäíåé æå ïðîäóêöèè â ε ñîîòâåòñòâóåò îòîáðàæåíèå â ïðèíèìàþùåå ñîñòîÿíèå, òî åñòü äàííîå ñëîâî áóäåòïðèíÿòî àâòîìàòîì.4Çàäà÷à 2G : S → abaA|abB|ε, A → aB|aa, B → bA|aSÔàêòîðèçóåì äàííûé íàáîð ïðîäóêöèé.SS1S2SS3SAAA1BB→→→→→→→→→→→aS1bS2aAaS3bBεaBaA1abAaS(6) íàøåì íàáîðå ïðîäóêöèé ñóùåñòâóåò S → ε, òîãäà çàìåíèì íåòåðìèíàë S íà S 0 , ïîñòðîèâýêâèâàëåíòíóþ ãðàììàòèêó.S0S10S20S0S30AAA1BBB→→→→→→→→→→→aS10bS20aAaS30bBaBaA1abAaS 0a(7)Ïðèâåäåííûå âûøå äåéñòâèÿ ïðèâåäåíû áåç äîêàçàòåëüñòâà, òàê êàê áûëè äîêàçàíû íàñåìèíàðå.
Характеристики
Тип файла PDF
PDF-формат наиболее широко используется для просмотра любого типа файлов на любом устройстве. В него можно сохранить документ, таблицы, презентацию, текст, чертежи, вычисления, графики и всё остальное, что можно показать на экране любого устройства. Именно его лучше всего использовать для печати.
Например, если Вам нужно распечатать чертёж из автокада, Вы сохраните чертёж на флешку, но будет ли автокад в пункте печати? А если будет, то нужная версия с нужными библиотеками? Именно для этого и нужен формат PDF - в нём точно будет показано верно вне зависимости от того, в какой программе создали PDF-файл и есть ли нужная программа для его просмотра.
![](https://s.studizba.com/z.php?f=/templates/si/i/noavatar.png&w=100&h=100&t=1"){kind=avatar}
