Iv_task6 (XPS13_s conflicted copy 2014-12-02) (Задание 6)

Ñåðãåé Èâàíû÷åâÃðóïïà 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)Ïðèâåäåííûå âûøå äåéñòâèÿ ïðèâåäåíû áåç äîêàçàòåëüñòâà, òàê êàê áûëè äîêàçàíû íàñåìèíàðå.