В.А. Серебряков, М.П. Галочкин и др. - Теория и реализация языков программирования (2006) (1134633), страница 45
Текст из файла (страница 45)
Âåðíî ëè ñîîòíîøåíèå ca∗ b∗ ∈ L(G) äëÿ ñëåäóþùåé ãðàììàòèêè G?S → bcD | aB; A → Db | cA; B → bS | ε;D → BA | cD.2.3.8. Âåðíî ëè ñîîòíîøåíèå c∗ ab∗ ∈ L(G) äëÿ ñëåäóþùåé ãðàììàòèêè G?S → ASS | A; A → c | Ab | aD; B → aDD;D → AB | BaB.2.3.9. Ïóñòü ãðàììàòèêà G îïðåäåëÿåòñÿ ïðàâèëàìèC.2. ßçûêè è èõ ïðåäñòàâëåíèå331S → AB; AB → CBb; CB → ABB;A → a; aB → a.Êàêîìó êëàññó (ïî Õîìñêîìó) îíà ïðèíàäëåæèò?Ïîðîæäàåòñÿ ëè L(G) ãðàììàòèêîé áîëåå óçêîãî êëàññà?2.3.10. Ïóñòü ãðàììàòèêà G îïðåäåëÿåòñÿ ïðàâèëàìèS → aAbB; AbB → aAbB; bBb → bb; A → ε.Êàêîìó êëàññó (ïî Õîìñêîìó) îíà ïðèíàäëåæèò?Ïîðîæäàåòñÿ ëè L(G) ãðàììàòèêîé áîëåå óçêîãî êëàññà?2.3.11. Ïóñòü ãðàììàòèêà G îïðåäåëÿåòñÿ ïðàâèëàìèS → AaB; AaB → aAaBb; aBb → abb; A → ε.Êàêîìó êëàññó (ïî Õîìñêîìó) îíà ïðèíàäëåæèò?Ïîðîæäàåòñÿ ëè L(G) ãðàììàòèêîé áîëåå óçêîãî êëàññà?2.3.12.
Ïóñòü ãðàììàòèêà G îïðåäåëÿåòñÿ ïðàâèëàìèS → AB; AB → aDB; DB → ABB; B → b;Ab → b.Êàêîìó êëàññó (ïî Õîìñêîìó) îíà ïðèíàäëåæèò?Ïîðîæäàåòñÿ ëè L(G) ãðàììàòèêîé áîëåå óçêîãî êëàññà?2.3.13. Êàêîìó êëàññó ïî Õîìñêîìó ïðèíàäëåæèò:à) Ãðàììàòèêà ñ ïðàâèëàìè:S → AS | ε; A → a | b.á) ßçûê, ïîðîæäàåìûé ýòîé ãðàììàòèêîé?2.3.14. Êàêîìó êëàññó ïî Õîìñêîìó ïðèíàäëåæèò:à) Ãðàììàòèêà ñ ïðàâèëàìè:S → AB ; AB → aABB ; B → b; A → a;á) ßçûê, ïîðîæä¼ííûé ýòîé ãðàììàòèêîé?2.3.15.
Êàêîìó êëàññó ïî Õîìñêîìó ïðèíàäëåæèò:à) Ãðàììàòèêà ñ ïðàâèëàìè:S → ASB | BSA; A → a; B → b | ε; SB → ε;á) ßçûê, ïîðîæä¼ííûé ýòîé ãðàììàòèêîé?2.3.16. Êàêîìó êëàññó ïî Õîìñêîìó ïðèíàäëåæèò:à) Ãðàììàòèêà ñ ïðàâèëàìè:S → AcBs; A → AcA | B ; B → a | b;á) ßçûê, ïîðîæä¼ííûé ýòîé ãðàììàòèêîé?332Ïðèëîæåíèå C. Çàäà÷è ïî ðàçäåëàì êíèãè2.3.17. Ñêîëüêî ñóùåñòâóåò ðàçëè÷íûõ âûâîäîâ öåïî÷êè baaaab, ïðèíàäëåæàùåé ÿçûêó, ïîðîæäàåìîìó ãðàììàòèêîé ñ ïðàâèëàìè:S → bAb; A → AA | a2.3.18.
Ïîñòðîèòü ïðàâîëèíåéíûå ãðàììàòèêè äëÿ ÿçûêîâ, ñîñòîÿùèõ èç:à) èäåíòèôèêàòîðîâ ïðîèçâîëüíîé äëèíû, íà÷èíàþùèõñÿ ñáóêâû;á) èäåíòèôèêàòîðîâ, ñîäåðæàùèõ îò 1 äî 6 ñèìâîëîâ è íà÷èíàþùèõñÿ ñ áóêâ I, J, K, L, M, N ;â) âåùåñòâåííûõ êîíñòàíò;ã) âñåõ öåïî÷åê èç íóëåé è åäèíèö, èìåþùèõ: ÷¼òíîå ÷èñëî íóëåé è ÷¼òíîå ÷èñëî åäèíèö; ëèáî íå÷¼òíîå ÷èñëî íóëåé è íå÷¼òíîå ÷èñëî åäèíèö.2.3.19. Ïîñòðîèòü ÊÑ-ãðàììàòèêè äëÿ ñëåäóþùèõÿçûêîâ:n nà) {0© 1R : n > 1}∗ªá) ww : w ∈ {a, b}â) Âñå öåïî÷êè èç íóëåé è åäèíèö ñ îäèíàêîâûì ÷èñëîì òåõè äðóãèõ©ª∗ã) {a, b} \ {am bn am bn } : m, n > 1 ;©©ªª∗ä) {a, b} \ a2m b3n a2m bn : m, n > 1 ;©ª∗å) {a, b} \ {am bn am } : m, n > 1 ;©∗ª∗æ) {a, b} \ {ww} : w ∈ {a, b ;ç) {{a, b}∗ \ {an bn an } : n > 1} ;2.3.20.
Îïðåäåëèòü ÊÑ-ãðàììàòèêè, êîòîðûå ïîðîæäàëè áû ñëåäóþùèå ÿçûêè:1) âñå ñòðîêè ýëåìåíòû ìíîæåñòâà {0, 1}∗ òàêèå, ÷òî âêàæäîé èç íèõ íåïîñðåäñòâåííî ñïðàâà îò êàæäîãî ñèìâîëà0 ñòîèò ñèìâîë 1.2) âñå ñòðîêè ýëåìåíòû ìíîæåñòâà {0, 1}∗ òàêèå, ÷òî ðåçóëüòàòû ÷òåíèÿ ýòèõ ñòðîê ñëåâà íàïðàâî è ñïðàâà íàëåâîñîâïàäàþò;3) âñå ñòðîêè ýëåìåíòû ìíîæåñòâà {0, 1}∗ , êîòîðûå ñîäåðæàò ñèìâîëîâ 0 âäâîå áîëüøå, ÷åì ñèìâîëîâ 1;C.2. ßçûêè è èõ ïðåäñòàâëåíèå3334) âñå ñòðîêè ýëåìåíòû ìíîæåñòâà {0, 1}∗ , êîòîðûå èìåþò îäèíàêîâîå ÷èñëî ñèìâîëîâ 0 è 1;5) âñå ñòðîêè ýëåìåíòû ìíîæåñòâà {0, 1}∗ , êîòîðûå èìåþò ÷åòíîå ÷èñëî ñèìâîëîâ 0 è íå÷åòíîå ÷èñëî ñèìâîëîâ 1;6) âñå ñòðîêè ýëåìåíòû ìíîæåñòâà {0, 1}∗ , â êîòîðûõñêîáêè ðàññòàâëåíû ïðàâèëüíî.2.3.21.
Ïîñòðîèòü ÊÑ-ãðàììàòèêè, ïîðîæäàþùèåÿçûêè:à) {am bn cp | m + n + p ≡ 0(mod 2); m, n, p > 0};á) {ap bq cr | p + q > r; p, q, r > 0};â) {x | x ∈ {a, b}∗ , |x|a = |x|b };ã) {x | x ∈ {a, b}∗ , |x|a > |x|b };ä) ïîñòðîèòü îäíîçíà÷íóþ ÊÑ-ãðàììàòèêó (îäíîçíà÷íîñòüäîëæíà áûòü äîêàçàíà ) äëÿ ÿçûêà {x | x ∈ {a, b}∗ , |x|a =|x|b , è äëÿ ∀ u, v : x = uv, |u| 6= 0, |v| 6= 0 âûïîëíåíî|u|a > |u|b }.2.3.22. Ïîñòðîèòü ÊÑ-ãðàììàòèêó, ïîðîæäàþùóþ ÿçûêà) {an cbn } ∪ {bn acn }; n > 0á) {x | x ∈ {a, b}∗ \ ε, x 6= yy R }2.3.23. Ïîñòðîèòü ÍÑ-ãðàììàòèêè äëÿ ñëåäóþùèõÿçûêîâ:à) {w ∈ {a, b, c}∗ , |w|a = |w|b = |w|c } (Âèíåãðåò)á) {w ∈ {a, b, c}∗ , 3|w|a = 5|w|b = 7|w|c } (Âèíåãðåò 2)â) {an pn rn } : n > 1} (Òðè ìóøêåò¼ðà)ã) {am bn am bn : m, n > 1} (Äâå êàëîøè)ä) {a2m bn am b5n : m, n > 1} (Êàëîøè 2)å) {am bn ck : m > n > k > 1} (Ãîðêà)æ) {am bn ck : 2m > 3n > k > 1} (Ãîðêà 2)nç) {a3 | n > 1} (Áîã ëþáèò òðîèöó)nè) {a5 bn | n > 1}2ê) {an : n > 1} (Êâàäðàòíûå ÷èñëà)2ë) {an −5n+1 : n > 5}2ì) {an bn : n > 1} (Äàìà ñ ñîáà÷êîé)2í) {dn −3n+2 hn : n > 1}nî) {a : n = 1, 2, 3, 5, 8, 13, ...} (×èñëà Ôèááîíà÷è)ï) {an : n = 1, 3, 6, 10, 15, ...} (Òðåóãîëüíûå ÷èñëà, an =n(n + 1)/2)334Ïðèëîæåíèå C.
Çàäà÷è ïî ðàçäåëàì êíèãèð) {an : n = 1, 5, 12, 22, ...} (Ïÿòèóãîëüíûå ÷èñëà, an =n + 3n(n − 1)/2. Ïÿòèóãîëüíîå ÷èñëî ìîæåò áûòü ðàçáèòîíà òðè òðåóãîëüíûõ + n òî÷åê)ñ) {ww : w ∈ {a, b}∗ } (Äâà ëåáåäÿ)3ò) {an : n > 1} (Êóáè÷åñêèå ÷èñëà)32ó) {f n −n +2n−1 t3n : n > 1}ô) {an : n = 1, 2, 6, 24, ..., k!} (Ôàêòîðèàë)õ) {012 ...0n−1 1n 0n−1 ...12 0 | n > 1} (Ïèðàìèäà Õåîïñà)÷) {012 ...0n−1 1n 1n 0n−1 ...12 0 | n > 1} (Ïèðàìèäû ìàéÿ)n2ø) {a3 bn an | n > 1}2ù) {{a}+ \an : n > 1} (Äëÿ ñòóäåíòîâ ñ èññëåäîâàòåëüñêîé æèëêîé).2.3.24. Ïîñòðîèòü ÊÑ-ãðàììàòèêè, ïîðîæäàþùèå ÿçûêèà) {xcy | x 6= y; x, y ∈ {a, b}∗ };á) {ai bj ck | i, j, k > 1} \ {an bn cn | n > 1};â) {a, b, c}∗ \ {an bn cn | n > 0}.2.3.25. Ïóñòü G ãðàììàòèêà ñ ïðàâèëàìè:S → CDC → aCA | bCB | εAD → aDBD → bDAa → aAAb → bABa → aBBb → bBD→εÏîêàçàòü, ÷òî L(G) = {xx | x ∈ {a, b}∗ }.2.3.26.
Ïîñòðîèòü ãðàììàòèêó, ïîðîæäàþùóþ äàííûéÿçûê:{an cbn an cbn | n > 0}.2.3.27. Ïîñòðîèòü ðåãóëÿðíóþ ãðàììàòèêó, ïîðîæäàþùóþ öåïî÷êè â àëôàâèòå (a, b), â êîòîðîì ñèìâîë a íåâñòðå÷àåòñÿ äâà ðàçà ïîäðÿä.2.3.28. Ïîñòðîèòü ãðàììàòèêó, ïîðîæäàþùóþ ñáàëàíñèðîâàííûå îòíîñèòåëüíî êðóãëûõ ñêîáîê öåïî÷êè â àëôàâèòå {a, (, ), ⊥}.
Ñáàëàíñèðîâàííóþ öåïî÷êó α îïðåäåëèìðåêêóðåíòíî: öåïî÷êà α ñáàëàíñèðîâàíà, åñëè:à) α íå ñîäåðæèò ñêîáîê,á) α = (α1 ) èëè α = α1 α2 , ãäå α1 è α2 ñáàëàíñèðîâàíû.C.3. Ëåêñè÷åñêèé àíàëèç3352.3.29 Ïîêàçàòü, ÷òî íàëè÷èå â ÊÑ-ãðàììàòèêå ïðàâèëâèäàà) A → AA | α á) A → AαA | β â) A → αA | Aβ | γ ,ãäå α, β, γ ∈ (VN ∪ VT )∗ , A ∈ VN , äåëàåò å¼ íåîäíîçíà÷íîé.Ìîæíî ëè ïðåîáðàçîâàòü ýòè ïðàâèëà òàêèì îáðàçîì, ÷òîáû ïîëó÷åííàÿ ýêâèâàëåíòíàÿ ãðàììàòèêà áûëà îäíîçíà÷íîé?2.3.30.
Ïîêàçàòü, ÷òî ãðàììàòèêà G íåîäíîçíà÷íà.G : S → abC | aB B → bc; bC → bc2.3.31. Äàíà ÊÑ-ãðàììàòèêà G = (VT , VN , P, S). Ïðåäëîæèòü àëãîðèòì ïîñòðîåíèÿ ìíîæåñòâàX = {A ∈ VN | A → ε}.2.3.32. Äëÿ ïðîèçâîëüíîé ÊÑ-ãðàììàòèêè G ïðåäëîæèòü àëãîðèòì, îïðåäåëÿþùèé, ïóñò ëè ÿçûê L(G).2.3.33. Îäèíàêîâûå ëè ÿçûêè ïîðîæäàþò ãðàììàòèêè èçà), á), â)?à) S → aAbA → BBB → ab | A | ε;á) S → aAbA → AaAb | ε;â) S → aBB → aBB | b.2.3.34. Ýêâèâàëåíòíû ëè ãðàììàòèêè ñ ïðàâèëàìèS → AB; B → Bb | A; A → Aa | B; C → c.èS → ε.2.3.35. Ýêâèâàëåíòíû ëè ãðàììàòèêè ñ ïðàâèëàìèA → AB; B → bC; A → aAc | Sa; C → c | Ca.èS → As | Bc; B → Ac | cS; A → Bd; C → c.C.3.
Ëåêñè÷åñêèé àíàëèçC.3.1. Ðåãóëÿðíûå ìíîæåñòâà è âûðàæåíèÿ3.1.1. Ïîêàçàòü, ÷òî ìíîæåñòâà, ñîîòâåòñòâóþùèå äâóìäàííûì ðåãóëÿðíûì âûðàæåíèÿì, ñîâïàäàþò,336Ïðèëîæåíèå C. Çàäà÷è ïî ðàçäåëàì êíèãè1) (a∗ b)c è a∗ (bc);2) a∗ b è b + aa∗ b;3) b(b + ab)∗ a è b(b∗ ab)∗ b∗ a;4) b(ab + b)∗ è bb∗ a(bb∗ a)∗ .3.1.2. Çàìåíèòü êàæäîå èç ñëåäóþùèõ âûðàæåíèé ýêâèâàëåíòíûì, â êîòîðîì íå èñïîëüçóþòñÿ çíàê "+":1) (a + b)∗ ;2) (a + bb + ba)∗ ;3) (a + (bb + ab)∗ )∗ .3.1.3.
Íàéòè ðåãóëÿðíûå âûðàæåíèÿ, îáîçíà÷àþùèåÿçûêè, âñå ñëîâà êîòîðûõ ýëåìåíòû ìíîæåñòâà {0, 1}∗ .1) îêàí÷èâàþùèåñÿ íà 011, 101, 110;2) íà÷èíàþùèåñÿ ñ 110, 101 èëè 011;3) ó êîòîðûõ êàæäûé òðåòèé ñèìâîë åñòü 0 èëè êàæäûéâòîðîé 1;4) íå ñîäåðæàùèå íè îäíîé èç ïîäñòðîê 011 è 101;5) ñîäåðæàùèå êàæäóþ èç ïîäñòðîê 011 è 101;6) íà÷èíàþùèåñÿ ñ 011 è îêàí÷èâàþùèåñÿ íà 110 èëè 101;7) íà÷èíàþùèåñÿ ñ 011 èëè 110 è îêàí÷èâàþùèåñÿ íà 101;8) íà÷èíàþùèåñÿ ñ 011 è ñîäåðæàùèå âõîæäåíèÿ ïîäñòðîêè110;9) {01n | n > 1};10) {01n 0 | n > 0};11) {0m 1n | n, m > 1};12) {α ∈ {0, 1}∗ : |α|/3 öåëîå íåîòðèöàòåëüíîå ÷èñëî};13) {αa | α ∈ {0, 1}+ , a ∈ {0, 1}, a âõîäèò â α};14) {(010)n | n > 0};15) {0m | m > 2} èëè {1n | n > 0};16) {(01)m (10)n | m > 0, n > 0};17) ñîäåðæàùåå ÷åòíîå ÷èñëî ñèìâîëîâ 0 è íå÷åòíîå ÷èñëîñèìâîëîâ 1;18) ñîäåðæàùåå ÷åòíîå ÷èñëî ñèìâîëîâ 0 èëè ÷åòíîå ÷èñëîñèìâîëîâ 1.3.1.4.
ßâëÿåòñÿ ëè ÿçûê, ñîñòîÿùèé èç âñåõ öåïî÷åê èç0 è 1, íå ñîäåðæàùèõ ïîäöåïî÷êè 010, ðåãóëÿðíûì?3.1.5. ßâëÿåòñÿ ëè ÿçûê, ñîñòîÿùèé èç âñåõ öåïî÷åê èç0 è 1, ñîäåðæàùèõ ÷¼òíîå ÷èñëî 0 è íå÷¼òíîå 1, ðåãóëÿðíûì?C.3. Ëåêñè÷åñêèé àíàëèç3373.1.6. ßâëÿåòñÿ ëè ÿçûê, ñîñòîÿùèé èç âñåõ öåïî÷åê ÷¼òíîé äëèíû â àëôàâèòå {a, b, c}, ðåãóëÿðíûì?3.1.7. Ðåãóëÿðåí ëèà) ÿçûê ôîðìóë âèäà A∗ (B), ãäå A, B ∈ {a, b}+ ?á) ÿçûê ôîðìóë âèäà (A1 .A2 ), ãäå äëÿ i = 1, 2 Ai åñòü ëèáîñëîâî â àëôàâèòå {a, b}, ëèáî, â ñâîþ î÷åðåäü, ôîðìóëà?â) ÿçûê ôîðìóë âèäà (A + B), ãäå A, B ∈ {a, b}+ ?ã) ÿçûê ôîðìóë âèäà (A1 )A2 , ãäå äëÿ i = 1, 2 Ai åñòü ëèáîñëîâî â àëôàâèòå {a, b}, ëèáî, â ñâîþ î÷åðåäü, ôîðìóëà?3.1.8. Îïðåäåëèòü ÿçûê, ñîñòîÿùèé èç âñåõ èäåíòèôèêàòîðîâ, ñ ïîìîùüþ:à) ðåãóëÿðíîãî âûðàæåíèÿ;á) ëåâîëèíåéíîé ãðàììàòèêè;â) êîíå÷íîãî àâòîìàòà;ã) ïðàâîëèíåéíîé ãðàììàòèêè.3.1.9.
Áóäåò ëè ðåãóëÿðíûì ÿçûê L = {x ∈ {a, b}∗ : |x|a÷åòíî è |x|b íå÷åòíî}?3.1.10. Ïîñòðîèòü ïðàâîëèíåéíóþ ãðàììàòèêó, ïîðîæäàþùóþ ÿçûê L âñåõ ñëîâ â àëôàâèòå {0, 1}, ñîäåðæàùèõ÷¼òíîå ÷èñëî åäèíèö è íå÷¼òíîå ÷èñëî íóëåé. Áóäåò ëè îíàîäíîçíà÷íîé?3.1.11. Ïîñòðîèòü ðåãóëÿðíîå âûðàæåíèå äëÿ ÿçûêà LR ,ãäå L ÿçûê âñåõ ñëîâ â àëôàâèòå {0, 1}, ñîäåðæàùèõ ÷¼òíîå ÷èñëî åäèíèö è íå÷¼òíîå ÷èñëî íóëåé.C.3.2. Êîíå÷íûå àâòîìàòû3.2.1. Êàêîé ÿçûê äîïóñêàåòñÿ êîíå÷íûì àâòîìàòîìM = ({q0 }, {a, b}, ∅, q0 , {q0 })?3.2.2. Ïîñòðîèòü íåäåòåðìèíèðîâàííûé êîíå÷íûé àâòîìàò, äîïóñêàþùèé öåïî÷êè â àëôàâèòå {1, 2}, ó êîòîðûõïîñëåäíèé ñèìâîë öåïî÷êè óæå ïîÿâëÿëñÿ â íåé ðàíüøå.Ïîñòðîèòü ýêâèâàëåíòíûé äåòåðìèíèðîâàííûé êîíå÷íûéàâòîìàò. Ïîñòðîèòü àíàëîãè÷íûå êîíå÷íûå àâòîìàòû â àëôàâèòå {1, 2, 3}.338Ïðèëîæåíèå C. Çàäà÷è ïî ðàçäåëàì êíèãè3.2.3.
![](https://s.studizba.com/z.php?f=/templates/si/i/noavatar.png&w=100&h=100&t=1"){kind=avatar}
