6 неделя (1178959)
Текст из файла
Ïóáëè÷íàÿ ðåäàêöèÿ (1) / ACCplyus.pavelÄîìàøíÿÿ ðàáîòà 6Çàäà÷à 1:Ðåøèòå óðàâíåíèÿ ñ ðåãóëÿðíûìè êîýôôèöèåíòàìè.  êàæäîìïóíêòå íóæíî âûïîëíèòü òðè çàäàíèÿ:1) íàéòè ÷àñòíîå ðåøåíèå;2) íàéòè ðåøåíèå, ìèíèìàëüíîå ïî âêëþ÷åíèþ;3) íàéòè âñå ðåøåíèÿÓðàâíåíèå X = αX + β , ãäå α îçíà÷àåò ìíîæåñòâî, ñîäåðæàùåå ïóñòóþ öåïî÷êó,èìååò áåñêîíå÷íî ìíîãî ðåøåíèé: X = α∗ (β+γ) äëÿ ëþáîãî, íåîáÿçàòåëüíî ðåãóëÿðíîãîγ . Íàèìåíüøåå ðåøåíèå â òàêèõ ñèòóàöèÿõ áóäåì íàçûâàòü íàèìåíüøåé íåïîäâèæíîéòî÷êîé - ìíîæåñòâî X = α∗ β . Åñëè æå α íå ñîäåðæèò ïóñòîé öåïî÷êè, òî óðàâíåíèåèìååò åäèíñòâåííîå ðåøåíèå X = α∗ β1.2.X = ((101)∗ + 110∗ )X ýòîì óðàâíåíèè α = ((101)∗ + 110∗ )•×àñòíîå ðåøåíèå:•Âñå ðåøåíèÿ çàäàþòñÿ•Íàèìåíüøåé íåïîäâèæíîé òî÷êîé ÿâëÿåòñÿβ = ∅.Òîãäà:X = ∅: ∅ = α∅ ⇒ ∅ = ∅X = ((101)∗ + 110∗ )∗ γ ,ãäåγ- ëþáîåX = ((101)∗ + 110∗ )∗ ∅ = ∅X = (00 + 01 + 10 + 11)X + (0 + 1 + ε)α = (00 + 01 + 10 + 11), β = (0 + 1 + ε)X = α∗ β = (00 + 01 + 10 + 11)∗ (0 + 1 + ε)•Âñå ðåøåíèÿ çàäàþòñÿ•Òàê êàê â ýòîì óðàâíåíèèαíå ñîäåðæèò ïóñòîé öåïî÷êè, òî Íàèìåíüøåéíåïîäâèæíîé òî÷êîé ÿâëÿåòñÿ•3.ñîäåðæèò ïóñòóþ öåïî÷êó, àX = (00 + 01 + 10 + 11)∗ (0 + 1 + ε)×àñòíûì ðåøåíèåì ìîæíî âçÿòü Q0Q1Q2X = (00 + 01 + 10 + 11)∗ (0 + 1 + ε)= Q0 0 + Q1 1 + ε= Q0 1 + Q2 0= Q1 0 + Q2 1.X = Xα + βX(ε − α) = β1X = β ε−αÄîìíîæèì íà îáðàòíûé ê(ε − α)ñïðàâàÏîëüçóÿñü ðàçëîæåíèåì â ðÿä Òåéëîðà ïîëó÷èìX = βα∗Èç (3) ⇒ Q2 = Q1 01∗ Ïîäñòàâëÿåì â (2):Q1 = Q0 1+Q1 01∗ 0 ⇒ Q1 = Q1 01∗ 0+Q0 1 ⇒ Q1 = Q0 1(01∗ 0)∗ ⇒ Q2 = Q0 1(01∗ 0)∗ 01Ïîäñòàâëÿåì â (1):∗ ∗Q0 = Q0 0 + q0 1(01 0) 1 + ε Q0 =Q1 =Îáùåå ðåøåíèå:Q2 =⇒ Q0 = Q0 (0 + 1(01∗ 0)∗ 1) + ε ⇒(0 + 1(01∗ 0)∗ 1)∗(0 + 1(01∗ 0)∗ 1)∗ 1(01∗ 0)∗, êîòîðîå òàêæå ÿâëÿåòñÿ(0 + 1(01∗ 0)∗ 1)∗ 1(01∗ 0)∗ 01è íàèìåíüøåé íåïîäâèæíîé òî÷êîé, êîòîðîå ìîæíî âçÿòü è â êà÷åñòâå ÷àñòíîãîðåøåíèÿ.Òåîðèÿ è Ðåàëèçàöèÿ ßçûêîâ ÏðîãðàììèðîâàíèÿÏóáëè÷íàÿ ðåäàêöèÿ (1) / ACCplyus.pavelÇàäà÷à 2: Âåðíî ëè, ÷òî äëÿ ëþáîé ëèíåéíîé ãðàììàòèêè G, L(G) ∈ REG?Íåò, íå âåðíî.
Ïðèâåäåì êîíòðïðèìåðG : S → aA, A → Bb, B → S, S → εÐàññìîòðèì ïðîèçâîëüíûé âûâîä ïðîèçâîëüíîãî ñëîâà. Ïåðâàÿ âîçìîæíîñòü ïðåîáðàçîâàíèÿS : S ⇒ ε.Ïîëó÷èëè ïóñòîå ñëîâî. Èëè,ìîæíî çàìåíèòü èçíà÷àëüíûé íàáîð ïðàâèë íàÄîêàæåì, ÷òî ãðàììàòèêàGçàäàåò ÿçûêS ⇒ aA ⇒ aBb ⇒ aSb.S → aSb|ε.an bn ,Òàêèì îáðàçîì,êîòîðûé íå ÿâëÿåòñÿ ðåãóëÿðíûì ïîëåììå î íàêà÷êå, ÷òî è ïîäòâåðäèò êîððåêòíîñòü êîíòðïðèìåðà:Äîêàçàòåëüñòâî.• an bn ⊆ L(G)ε = a0 b0 , ε ∈ G. Êàæäîå ïðèìåíåíèå ïðàâèëà S → aSbäîïèñûâàåò ê òåêóùåé ñòðîêå ñëåâà a, ñïðàâà - b. Òàêèì îáðàçîì, ìû ìîæåì ïîëó÷èòü ïðîèçâîëüíîå ñëîâî ω = an bn ïðèìåíèâ ïåðâîå ïðàâèëî n ðàç: S ⇒n an Sbn ⇒an bn = ωÊàê ìû óâèäåëè âûøå,• L(G) ⊆ an bnε ∈ G, ε = a0 b0 - áàçà. Äîêàæåì ïî ñòðóêòóðíîé èíäóêöèè,÷òî èìåÿ ñëîâî a b (ïîëó÷àåìîå èç as Sbs ⇒ as bs ), ïðèìåíåíèå ïðàâèë ñîõðàíÿåòñâîéñòâà ÿçûêà an bn . Ïðèìåíÿÿ ïåðâîå ïðàâèëî, öåïî÷êà as Sbs ïðåîáðàçóåòñÿ âas+1 Sbs+1 - êîëè÷åñòâî áóêâ a ñëåâà è áóêâ b - ñîâïàäàåò, çíà÷èò ñâîéñòâî ñîõðàíÿåòñÿ, ïðèìåíèâ ïðàâèëî S → ε.
Âòîðîå ïðàâèëî, ïðèìåíåííîå ê öåïî÷êå, òàêæåñîõðàíÿåò ñâîéñòâî ÿçûêà. ⇒ G ⊆ an bn .Êàê ìû óâèäåëè âûøå,s sÇàäà÷à 3: ßçûê L= ÿâëÿåòñÿ ÿçûêîì âñåõ ñëîâ ñ ðàâíûì ÷èñëîì ñèìâîëîâ aè b.1. Ïîêàæèòå èíäóêöèåé ïî äëèíå ñëîâà, ÷òî ÊÑ-ãðàììàòèêàaSb | bSa | ε ïîðîæäàåò ÿçûê L= .G ñ ïðàâèëàìè S → SS |Äîêàçàòåëüñòâî.• L(G) ⊆ LÄîêàæåì ïî ñòðóêòóðíîé èíäóêöèè, ÷òî ïðèìåíåíèå ïðàâèë ê öåïî÷êå, ïîðîæäàþùåé ñëîâî äëèíûS ⇒ ε, ε ∈ L.Ïóñòün,αïðèíàäëåæàùåå ÿçûêóLñîõðàíÿåò ñâîéñòâà ÿçûêà.
Áàçà:ω äëèíû n ïðèìåS → ε. Òîãäà êàæäóþ S èç α ìîæíî çàìåíèòü íà aSbèëè bSa, íî êîëè÷åñòâî áóêâ a è b ïðîäîëæàåò îñòàâàòüñÿ ðàâíûì, ÷òî ñîõðàíÿåòñâîéñòâà ÿçûêà (åñëè çàìåíèòü âñå S íà ε è ïîëó÷èòü ñëîâà, äëèíåå n).íåíèåì êî âñåìS- öåïî÷êà, èç êîòîðîé ïîëó÷àåòñÿ ñëîâîïðàâèëà• L ⊆ L(G)Ñíîâà âîñïîëüçóåìñÿ ñòðóêòóðíîé èíäóêöèåé: ëþáîå ñëîâî èçL ïîðîæäàåòñÿ G.ε ïðèíàäëåæèò è L è G. Ïóñòü ëþáîå ñëîâî èç L äëèíû n è ìåíüøå ïîðîæäàåòñÿ G. Ðàññìîòðèì ïðîèçâîëüíîå ñëîâî ω ∈ G, ω 6= ε äëèíû n + 1. Ñóùåñòâóåòíåñêîëüêî ïðåäñòàâëåíèé ω :Ñëîâî1.ω = aU b èëè ω = bU a, ãäå U ∈ LS ⇒ aSb ⇒∗ aU b. ω - âûâîäèìîïî ïðåäïîëîæåíèþ èíäóêöèèS ⇒∗ U, ò.åÒåîðèÿ è Ðåàëèçàöèÿ ßçûêîâ ÏðîãðàììèðîâàíèÿÏóáëè÷íàÿ ðåäàêöèÿ (1) / ACC2.plyus.pavelω = u · v , u, v ∈ L, u, v 6= ε.
u, v- âûâîäèìû âG â ñèëó ïðåäïîëîæåíèÿS ⇒n u, s ⇒m v . Òîãäà ïîëó÷èì è ω :S ïðåîáðàçóåì â u, à âòîðóþ - â v . S ⇒ SS ⇒nèíäóêöèè, ò.å ñóùåñòâóþò âûâîäûS ⇒ SS , òåïåðü ïåðâóþuS ⇒m uv = ω . ω - âûâîäèìî.012n+1ω =− ω1 − ω2 − . . . ωn+1 − . Íî òîãäà ïîÒåîðåìå Âåéåðøòðàññà íàéäåòñÿ òàêîå n, ÷òî ôóíêöèÿ d(n) = |w0n |a − |w0n |b ,ãäå w0n - ñëîâî, ïîëó÷àåìîå èç áóêâ ìåæäó 1 è n ïîçèöèÿìè, ïðèíèìàåò íóëåâîåçíà÷åíèå. À çíà÷èò, ðàçáèòü ω íà äâà ñëîâà (âòîðîå - âîçìîæíî, ε ), îòâå÷àþùèìóñëîâèþ L ìîæíî.Äðóãèõ ïðåäñòàâëåíèéíåò, ò.êωÇàäà÷à 4:Ïîêàæèòå, ÷òî ÿçûê âñåõ íåïàëèíäðîìîâÿçûêà ïàëèíäðîìîâ) ÿâëÿåòñÿ ÊÑ-ÿçûêîì.Ïðåäúÿâèì ãðàììàòèêó G:L (òî åñòü äîïîëíåíèåS → aSb|bSb|EE → aKb|bKaK → ε|aK|bKÄîêàæåì, ÷òî ãðàììàòèêàGçàäàåò ÿçûê âñåõ íåïàëèíäðîìîâLÄîêàçàòåëüñòâî.• L ⊆ L(G)Ðàññìîòðèì ïðîèçâîëüíîå ñëîâîαω- íåïàëèíäðîì.
Îíî èìååò âèä- íåêîòîðàÿ, âîçìîæíî ïóñòàÿ, ïîñëåäîâàòåëüíîñòü áóêâ, àïåðåâåðíóòàÿ.β1èβ2αRαβ1 γβ2 αR ,- íåêîòîðûå, íå ðàâíûå äðóã äðóãó áóêâû, àñëåäîâàòåëüíîñòü áóêâ, âîçìîæíî, ïóñòàÿ. Ïîêàæåì, ÷òîãäå- îíà æå, òîëüêîγ- ëþáàÿ ïî-G.S → aSb|bSb, ïîêà íå ïîëó÷èì S ⇒∗íåòåðìèíàëó E . Íåòåðìèíàë E ïîðîæäàåòωâûâîäèìî âÑïåðâà ê àêñèîìå áóäåì ïðèìåíÿòü ïðàâèëàαSαR .Äàëåå ïåðåõîäèì îò àêñèîìû êîäíó èç âñåâîçìîæíûõ ïàð íåðàâíûõ äðóã äðóãó áóêâ àëôàâèòà, ìåæäó áóêâ êîòîðîé íàõîäèòñÿ íåòåðìèíàëαβ1 Kβ2 αRK , òàêèì îáðàçîì ïîëó÷àåì S ⇒∗ αSαR ⇒ αEαR ⇒.Òåïåðü äîêàæåì, ÷òîK- ïîðîæäàåò ÿçûê âñåõ ñëîâ.ïîðîæäàþòñÿ âñå ñëîâà äëèíûnεïîðîæäàåòñÿK.Ïóñòüè ìåíåå, äîêàæåì, ÷òî òîãäà ïîðîæäàåòñÿ è ïðî-èçâîëüíîå ñëîâî äëèíûn+1 p.
Ýòî äåéñòâèòåëüíî òàê, òàê êàê ñëîâî p ïîëó÷àåòñÿp0 äëèíû n ïðèïèñûâàíèåì ê åãî êîíöó îäíîé èç äâóõ áóêâ àëôàâèòà.Òàê êàê p èìååò íåêîòîðûé âûâîä K ⇒∗ p0 K ⇒ p0 , òî ïðèìåíèì åùå îäíî èç äâóõïðàâèë K → aK|bK è ïîëó÷èì p: K ⇒∗ p0 K ⇒ pK ⇒ p.  ñèëó ïðîèçâîëüíîñòè pèç ñëîâàóòâåðæäåíèå äîêàçàíî.Âåðíåìñÿ ê öåïî÷êåαβ1 Kβ2 αR , çíàÿ òåïåðü, ÷òî K ìîæåò ïîðîäèòü ëþáîå ñëîâîγ , ïîëó÷àåì, ÷òî S ⇒∗ αβ1 γβ2 αR = ω , ÷òî è çàâåðøàåòëþáîé êîíå÷íîé äëèíûäîêàçàòåëüñòâî• L(G) ⊆ LÐàññìîòðèì ïðîèçâîëüíîå ñëîâîàêñèîìåmðàç (m∈ N0 )ωäëèíûnG. S ⇒∗ ω . Ñïåðâà êS → aSa|bSb. Òàêèì îá-, âûâîäèìîåïðèìåíåòñÿ îäíî èç ïðàâèëðàçîì, ñëåâà è ñïðàâà îò íåòåðìèíàëà íàõîäèòñÿ îäèíàêîâîå êîëè÷åñòâî áóêâÒåîðèÿ è Ðåàëèçàöèÿ ßçûêîâ ÏðîãðàììèðîâàíèÿÏóáëè÷íàÿ ðåäàêöèÿ (1) / ACCS ⇒m α1 Sα2 .plyus.pavelÇàòåì ïðèìåíèòñÿ ïðàâèëîîäíî èç äâóõ ïðàâèëE → aKb|bKa,S → E.Êòàêèì îáðàçîìE ìîæíî ïðèìåíèòü òîëüêîωp+1 6= ωn−p , ò.å ñóùåñòâóþòäâå ðàçëè÷íûå áóêâû, ðàâíîîòñòàþùèå îò íà÷àëà è êîíöà öåïî÷êè.
Îò íåòåðìèíàëàK óæå íè÷åãî íå çàâèñèò, òàê êàê ñâîéñòâî ïàëèíäðîìà óæå íàðóøåíî. ÊàêîåK ñëîâî íå ïîðîäè, ïîëó÷åííîå ω = α1 β1 γβ2 α2 , íå ÿâëÿåòñÿ ïàëèíäðîìîì(|α1 | = |α2 |, β1 6= β2 ).áûÒåîðèÿ è Ðåàëèçàöèÿ ßçûêîâ Ïðîãðàììèðîâàíèÿ.
Характеристики
Тип файла PDF
PDF-формат наиболее широко используется для просмотра любого типа файлов на любом устройстве. В него можно сохранить документ, таблицы, презентацию, текст, чертежи, вычисления, графики и всё остальное, что можно показать на экране любого устройства. Именно его лучше всего использовать для печати.
Например, если Вам нужно распечатать чертёж из автокада, Вы сохраните чертёж на флешку, но будет ли автокад в пункте печати? А если будет, то нужная версия с нужными библиотеками? Именно для этого и нужен формат PDF - в нём точно будет показано верно вне зависимости от того, в какой программе создали PDF-файл и есть ли нужная программа для его просмотра.
![](https://s.studizba.com/z.php?f=/templates/si/i/noavatar.png&w=100&h=100&t=1"){kind=avatar}
