9 неделя (1178962)
Текст из файла
Ïóáëè÷íàÿ ðåäàêöèÿ (1) / ACCplyus.pavelÇàäàíèå 9Çàäà÷à 1: L = {xcy | x, y ∈ {a, b}∗ ; x 6= yR }. Ïîñòðîéòå äåòåðìèíèðîâàííûé ÌÏ-àâòîìàò,ðàñïîçíàþùèé ÿçûê L.Ñèìâîë τ îçíà÷àåò ëþáîé êîíêðåòíûé ñèìâîë èç Γ = {a, b, Z0 }, ò.å çàïèñü a, τ /aτ ýêâèâàëåíòíàçàïèñè a, a/aa | a, b/ab | a, Z0 /aZ0a, τ /aτq0b, τ /bτÀâòîìàò M :a, a/ε | b, b/εc, τ /τq1a, τ /τ | b, τ /τa, b/ε | b, a/εq2a, Z0 /Z0 | b, Z0 /Z0ε, Z0 /Z0q3Äîêàçàòåëüñòâî.• L ⊆ L(M ) :Ðàññìîòðèì ïðîèçâîëüíîå ñëîâî ω ∈ L.
Îìî ìîæåò èìåòü ëèøü íåñêîëüêî âèäîâ:1. ω = XcY, |Y | < |X| = n:Àâòîìàò â ñîñòîÿíèè q0 ñ÷èòàåò âñå ñèìâîëû X â ñòåê, ïî c ïåðåéäåò â ïðèíèìàþùååñîñòîÿíèå q1 , ãäå ïðèñòóïèò ê ñ÷èòûâàíèþ ñèìâîëîâ Y , óäàëÿÿ èç ñòåêà ñîîòâåòñòâóþùèå áóêâû X . Åñëè âñòðåòèòñÿ ñèìâîë Yi 6= Xn−i+1 (çíà÷èò íàø Y íå ìîæåò èìåòü âèäY R = X ), òî àâòîìàò ïåðåéäåò â ïðèíèìàþùåå ñîñòîÿíèå q2 , îòêóäà óæå è íå âûéäåò ⇒ω ∈ L(M ).
Åñëè òàêîãî Yi íå íàøëîñü (Y ìîæíî ïðîäîëæèòü äî Y 0 = X R ), òî àâòîìàòòàê è îñòàíåòñÿ â ïðèíèìàþùåì ñîñòîÿíèè q1 , ò.ê ñèìâîë Z0 äîñòèãíóò íå áóäåò(â ñòåêåîñòàíóòñÿ áóêâû X ò.ê X > Y ) ⇒ ω ∈ L(M )2. ω = XcY P, |Y | = |X|, ∃i : Yi 6= Xn−i+1 , |P | ≥ 0 (Y íå ÿâëÿåòñÿ X R , õîòÿ è òîé æåäëèíû):Àâòîìàò â ñîñòîÿíèè q0 ñ÷èòàåò âñå ñèìâîëû X â ñòåê, ïî c ïåðåéäåò â ïðèíèìàþùååñîñòîÿíèå q1 , ãäå ïðèñòóïèò ê ñ÷èòûâàíèþ ñèìâîëîâ Y , óäàëÿÿ èç ñòåêà ñîîòâåòñòâóþùèå áóêâû X . Ïî óñëîâèþ, íàì âñòðåòèòñÿ ñèìâîë Yi 6= Xn−i+1 è àâòîìàò ïåðåéäåò âïðèíèìàþùåå ñîñòîÿíèå q2 , îòêóäà óæå è íå âûéäåò ⇒ ω ∈ L(M ).3. ω = XcX R P, |P | ≥ 1:Àâòîìàò â ñîñòîÿíèè q0 ñ÷èòàåò âñå ñèìâîëû X â ñòåê, ïî c ïåðåéäåò â ïðèíèìàþùååñîñòîÿíèå q1 , ãäå ïðèñòóïèò ê ñ÷èòûâàíèþ ñèìâîëîâ Y .
Òàì îí ïðî÷èòàåò âñå ñèìâîëûY , óäàëÿÿ èç ñòåêà ñîîòâåòñòâóþùèå áóêâû X . Ïðî÷èòàâ âñå Y àâòîìàò äîñòèãíåò Z0è ñäåëàåò ïåðåõîä â q3 . Íî ïðèñòóïèâ ê ñ÷èòûâàíèþ P , àâòîìàò ïåðåéäåò â q2 , ãäå èîñòàíåòñÿ äî êîíöà ðàáîòû ⇒ ω ∈ L(M )Äðóãèõ âèäîâ ω íåò ⇒ â ñèëó ïðîèçâîëüíîñòè ω L ⊆ L(M ).• L(M ) ⊆ L:Ðàññìîòðèì ïðîèçâîëüíîå ñëîâî ω ∈ L(M ). Åñëè îíî áûëî ïðèíÿòî, çíà÷èò åãî îáðàáîòêàçàêîí÷èëàñü â îäíîì èç ôèíàëüíûõ ñîñòîÿíèé q1 èëè q2 . Ðàáîòà àâòîìàòà íà÷àëàñü â q0 ãäåñ÷èòûâàëèñü âñå ñèìâîëû è çàíîñèëèñü â ñòåê. Çàòåì áûëî ïðî÷èòàíî c è àâòîìàò ïåðåøåë âq1 ïðè ëþáîì ñîñòîÿíèè ñòåêà (â òîì ÷èñëå ïóñòîì, òîëüêî ñ Z0 ).Òåîðèÿ è Ðåàëèçàöèÿ ßçûêîâ ÏðîãðàììèðîâàíèÿÏóáëè÷íàÿ ðåäàêöèÿ (1) / ACCplyus.pavel1. Åñëè îáðàáîòêà ω çàâåðøèëàñü â q1 , çíà÷èò â äðóãèå ñîñòîÿíèÿ àâòîìàò áîëüøå íå ïåðåõîäèë (ïåðåõîäîâ â q1 êðîìå êàê èç q0 íåò, ïîïàñòü â q0 íåëüçÿ). À çíà÷èò âñå äàëüíåéøèåñ÷èòûâàåìûå áóêâû (åñëè îíè áûëè) ñîâïàäàëè ñ âåðõíåé áóêâîé èç ñòåêà è èçûìàëèñü.Òàêèì îáðàçîì, ω èìååò âèä X1 .
. . Xn c èëè X1 . . . Xn cXn . . . Xk , n ∈ N0 , 1 < k ≤ n (èíà÷å,ïðè Yi 6= Xn−i+1 ïðîèçîøåë áû ïåðåõîä â q2 , à åñëè áû â íåêîòîðûé ìîìåíò k = 1, òîïðîèçâîøåë áû ïåðåõîä â q3 ). ⇒ ω ∈ L2. Åñëè îáðàáîòêà ω çàâåðøèëàñü â q2 , çíà÷èò àâòîìàò âñå æå ïîêèíóë ñîñòîÿíèå q1 .
Åñëèàâòîìàò îêàçàëñÿ â q2 íàïðÿìóþ èç q1 , çíà÷èò ïðè ñ÷èòûâàíèè Y (âòîðîé ÷àñòè ñëîâàïîñëå c) íàøëîñü òàêîå i, ÷òî Yi 6= Xn−i+1 (íà ýòîé áóêâå àâòîìàò è ïîêèíóë q1 , ïåðåøåëâ q2 è äî÷èòàë îñòàòîê Y , íå ìåíÿÿ ñòåêà). Ýòî çíà÷èò, ÷òî Y 6= X R , à çíà÷èò ñ÷èòàííîåñëîâî ω âèäà XcY, Y 6= X R ïðèíàäëåæèò ÿçûêó L. Òàêæå àâòîìàò ìîã ïîïàñòü èç q3 ïðèïóñòîì ñòåêå ïî ëþáîé áóêâå.  q3 àâòîìàò ïîïàäàåò òîëüêî èç q1 , åñëè â ýòîì ñîñòîÿíèèñòåê îïóñòååò äî Z0 , à çíà÷èò ïðè íàõîæäåíèè â ñîñòîÿíèè q3 áûëî ñ÷èòàíî ñëîâî ω 0âèäà XcX R , íî äàëåå ñ÷èòûâàåòñÿ åùå îäíà áóêâà, ñîâåðøàåòñÿ ïåðåõîä â ïðèíèìàþùååñîñòîÿíèå q2 . Äàëåå, âîçìîæíî, áûëè ñ÷èòàíû åùå áóêâû.
 ëþáîì ñëó÷àå, ñ÷èòàííîåñëîâî ω èìååò âèä XcX R (a|b)(a|b)∗ ∈ LÒàêèì îáðàçîì L(M ) ⊆ L.Çàäà÷à 3: Ïîñòðîéòå ïî ãðàììàòèêå G ïðèâåä¼ííóþ ãðàììàòèêó. Âñå ïîñòðîåíèÿ äîëæíû áûòü âûïîëíåíû ñòðîãî ïî àëãîðèòìó. Ãðàììàòèêà G çàäàíà ïðàâèëàìè:S → A | B | C | E | AGC → BaAbC | aGD | εA → C | aABC | εF → aBaaCbA | aGEB → bABa | aCbDaGb | εE→A1. Óäàëÿåì âñå áåñïëîäíûå ñèìâîëû:• V0 = {a, b}• V1 = {a, b, A, B, C}• V2 = {a, b, A, B, C, S, F, E}• V3 = {a, b, A, B, C, S, F, E}• N = {A, B, C, S, F, E}S→A|B|C|EC → BaAbC | εA → C | aABC | εF → aBaaCbAB → bABa | εE→A2.
Óäàëÿåì âñå íåäîñòèæèìûå íåòåðìèíàëû:• V0 = {S}• V1 = {S, A, B, C, E}• V2 = {S, A, B, C, E}• N = {A, B, C, S, E}Òåîðèÿ è Ðåàëèçàöèÿ ßçûêîâ ÏðîãðàììèðîâàíèÿÏóáëè÷íàÿ ðåäàêöèÿ (1) / ACCplyus.pavelÃðàììàòèêà G:S→A|B|C|EA → C | aABC | εC → BaAbC | εB → bABa | εE→AÇàäà÷à 4: Ïóñòü G ãðàììàòèêà â íîðìàëüíîé ôîðìå Õîìñêîãî. Äîêàæèòå, ÷òî ëþáîåñëîâî äëèíû n ≥ 1 âûâîäèìî ðîâíî çà 2n − 1 øàã.Ðàññìîòðèì ïðîèçâîëüíîå ω , âûâîäèìîå â G, |ω| ≥ 1.
 ãðàììàòèêå G âñå ïðàâèëà èìåþò âèäA → BC, A → a, ãäå A, B, C ∈ N ; a ∈ T , (òàêæå, âîçìîæíî, S → ε, íî òîãäà S íå âñòðå÷àåòñÿ âïðàâûõ ÷àñòÿõ ïðàâèë, íî ýòîò ñëó÷àé ìû ðàññìàòðèâàòü íå áóäåì, òàê êàê òîãäà S → ε ïîðîæäàåòëèøü ε , ñëîâî äëèíû ìåíüøåé 1). Çíà÷èò êàæäàÿ áóêâà âûâîäèòñÿ èç îäíîãî íåòåðìèíàëà ðîâíîçà îäèí øàã A → a (è èç îäíîãî íåòåìèíàëà íåëüçÿ âûâåñòè áîëüøå îäíîé áóêâû). Òàêèì îáðàçîì,íàì ïîíàäîáèòñÿ n øàãîâ ÷òîáû ïîëó÷èòü n áóêâ èç n íåòåðìèíàëîâ (n áóêâ íåëüçÿ âûâåñòè èçìåíüøåãî êîëè÷åñòâà íåòåðìèíàëîâ).Òàêæå, ïðàâèëîì âèäà A → BC ìû ìîæåì óâåëè÷èòü êîëè÷åñòâî íåòåðìèíàëîâ â öåïî÷êå íàîäèí.
Òàêèì îáðàçîì, ÷òîáû ïîëó÷èòü èç 1 íà÷àëüíîãî íåòåðìèíàëà S n íåòåðìèíàëîâ íàì ïîòðåáóåòñÿ n − 1 øàã.Òàêèì îáðàçîì äëÿ âûâîäà ω íàì ïîòðåáóåòñÿ íå ìåíüøå n+n−1 = 2n−1 øàãîâ. Íî è íå áîëüøå,ò.ê åñëè ìû ñäåëàëè áîëüøå øàãîâ, çíà÷èò ìû èìåëè â ñåíòåíöèàëüíîé ôîðìå íåòåðìèíàëîâ áîëüøå,÷åì n. Êàæäûé íåòåðìèíàë äàñò íàì ïî áóêâå, à çíà÷èò ìû ïîëó÷èì ñëîâî äëèíû áîëüøåé n.⇒ óòâåðæäåíèå äîêàçàíîÇàäà÷à 5: Ïîñòðîéòå ïî ãðàììàòèêå G ãðàììàòèêó â íîðìàëüíîé ôîðìå Õîìñêîãî.S → ABC | SBACB → ab | b | AA → S | B | aCB | εC → A | B | aBbA1.
Óäàëåíèå ε -ïåðåõîäîâ:(a) Íàéäåì ìíîæåñòâî ε -ïîðîæäàþùèõ òåðìèíàëîâ. T0 = {ε}, Ìíîæåñòâî Ti+1 ñòðîèì ïî Tiñëåäóþùèì îáðàçîì: åñëè äëÿ ïðàâèëà A → α ñïðàâåäëèâî α ∈ Ti∗ , òî äîáàâèì íåòåðìèíàë A â ìíîæåñòâî Ti+1 .••••••T0T1T2T3T4T5= {ε}= {A, ε}= {A, B, ε}= {A, B, C, ε}= {A, B, C, S, ε}= {A, B, C, S, ε}(b) Äëÿ êàæäîãî ïðàâèëà âèäà A → α0 B1 α2 B2 .
. . Bk αk , ãäå αi - ïîñëåäîâàòåëüíîñòü òåìèíàëîâ è íåòåðìèíàëîâ, à Bi ε -ïîðîæäàþùèå íåòåðìèíàëû äîáàâèì â P âñå âîçìîæíûåâàðèàíòû ïðàâèë, â êîòîðûõ ëèáî ïðèñóòñòâóåò, ëèáî óäàë¼í êàæäûé èç íåòåðìèíàëîâBj , 1 ≤ j ≤ k . Óäàëèì âñå ε -ïðàâèëà, à S 0 îáúÿâèì íîâîé àêñèîìîé, äîáàâèì ïðàâèëàS 0 → S|ε:Òåîðèÿ è Ðåàëèçàöèÿ ßçûêîâ ÏðîãðàììèðîâàíèÿÏóáëè÷íàÿ ðåäàêöèÿ (1) / ACCplyus.pavelS→CA→SS→BS→SA→BS → BCS → SCA → aBS→AS → SAA → aCS → ACS → SACA → aCBS → ABS → SBA→aS → ABCS → SBCB → ab|b|AS → BAS → SBAC → A|B|aBbA|ab|abA|ABbS → BACS → SBACS 0 → S|ε2.
Óäàëåíèå öåïíûõ ïðàâèë:(a) Ñïåðâà íàéäåì âñå öåïíûå ïàðû. Äëÿ êàæäîãî íåòåðìèíàëà ñîçäàäèì öåïíóþ ïàðó (A, A).Ðàññìîòðèì öåïíîå ïðàâèëî A → B , åñëè ñóùåñòâóåò öåïíàÿ ïàðà (C, A), âòîðîé ýëåìåíòêîòîðîé ñîâïàäàåò ñ ëåâûì íåòåðìèíàëîì èç ïðàâèëà, äîáàâèì â ìíîæåñòâî ïàðó (C, B).Äàëåå ïðèâåäåì õîä ðàáîòû àëãîðèòìà, óêàçûâàÿ èç êàêîãî ïðàâèëà ïîëó÷àåì íîâûåïðàâèëà:I (S 0 , S )(S , S )( A, A)(B , B )(C , C )S → C : (S , C )S → B : (S , B )S → A: ( S , A)A → S : ( A, S )A → B : ( A, B )B → A: ( B , A)C → A: ( C , A)C → B : (C , B )S 0 → S :(S 0 , S )II S → C : (A, C ) (S 0 , C )S → B : (S 0 , B )S → A: ( S 0 , A)A → S : (B , S ) (C , S )B→AC→AC→BIII S → C : (B , C )S→BS→AA→SA→BB→AC→AC→BIV S → CS→BS→AA→SA→BB→AC→AC→B(b) Äëÿ êàæäîé öåïíîé ïàðû (A, B) äîáàâèì â ãðàììàòèêó âñå ïðàâèëà A → α, ãäå B → α íåöåïíîå ïðàâèëî, âñå öåïíûå ïðàâèëà óäàëèìS→BC|AC|AB|ABC|BA|BAC|SC|SA|SAC|SB|SBC|SBA|SBAC|aBbA|ab|abA|ABb|aB|aC|aCB|bA→BC|AC|AB|ABC|BA|BAC|SC|SA|SAC|SB|SBC|SBA|SBAC|aBbA|ab|abA|ABb|aB|aC|aCB|bB→BC|AC|AB|ABC|BA|BAC|SC|SA|SAC|SB|SBC|SBA|SBAC|aBbA|ab|abA|ABb|aB|aC|aCB|bC→BC|AC|AB|ABC|BA|BAC|SC|SA|SAC|SB|SBC|SBA|SBAC|aBbA|ab|abA|ABb|aB|aC|aCB|bS0→BC|AC|AB|ABC|BA|BAC|SC|SA|SAC|SB|SBC|SBA|SBAC|aBbA|ab|abA|ABb|aB|aC|aCB|b|εÒåîðèÿ è Ðåàëèçàöèÿ ßçûêîâ ÏðîãðàììèðîâàíèÿÏóáëè÷íàÿ ðåäàêöèÿ (1) / ACCplyus.pavel3.
Óáåðåì äëèííûå ïðàâèëà:S→BC|AC|AB|AK1 |BA|BK2 |SC| C→BC|AC|AB|AK1 |BA|BK2 |SC|SA|SK2 |SB|SK1 |SK3 |SK4 |K8 K5 |K8 K9SA|SK2 |SB|SK1 |SK3 |SK4 |K8 K5 |K8 K9|K8 K6 |K8 K10 |K8 B|K8 C|K8 K11 |b|K8 K6 |K8 K10 |K8 B|K8 C|K8 K11 |bS0→BC|AC|AB|AK1 |BA|BK2 |SC|A→BC|AC|AB|AK1 |BA|BK2 |SC|SA|SK2 |SB|SK1 |SK3 |SK4 |K8 K5 |K8 K9SA|SK2 |SB|SK1 |SK3 |SK4 |K8 K5 |K8 K9|K8 K6 |K8 K10 |K8 B|K8 C|K8 K11 |b|ε|K8 K6 |K8 K10 |K8 B|K8 C|K8 K11 |bK1 → BCK2 → ACK3 → BAB→BC|AC|AB|AK1 |BA|BK2 |SC| K4 → BK2K5 → BK6K6 →SA|SK2 |SB|SK1 |SK3 |SK4 |K8 K5 |K8 K9K9 AK8 → aK9 → bK10 →|K8 K6 |K8 K10 |K8 B|K8 C|K8 K11 |bBK9K11 → CBÒåîðèÿ è Ðåàëèçàöèÿ ßçûêîâ Ïðîãðàììèðîâàíèÿ.
Характеристики
Тип файла PDF
PDF-формат наиболее широко используется для просмотра любого типа файлов на любом устройстве. В него можно сохранить документ, таблицы, презентацию, текст, чертежи, вычисления, графики и всё остальное, что можно показать на экране любого устройства. Именно его лучше всего использовать для печати.
Например, если Вам нужно распечатать чертёж из автокада, Вы сохраните чертёж на флешку, но будет ли автокад в пункте печати? А если будет, то нужная версия с нужными библиотеками? Именно для этого и нужен формат PDF - в нём точно будет показано верно вне зависимости от того, в какой программе создали PDF-файл и есть ли нужная программа для его просмотра.
![](https://s.studizba.com/z.php?f=/templates/si/i/noavatar.png&w=100&h=100&t=1"){kind=avatar}
