В.А. Серебряков, М.П. Галочкин и др. - Теория и реализация языков программирования (2006) (1134633), страница 46
Текст из файла (страница 46)
Ïîñòðîèòü êîíå÷íûé àâòîìàò, äîïóñêàþùèé ÿçûê{xy} ∪ {yx}, ãäå x ∈ {a}∗ \ ε; y ∈ {b}∗ \ ε.3.2.4. Ïîñòðîèòü äåòåðìèíèðîâàííûé êîíå÷íûé àâòîìàò, äîïóñêàþùèé ÿçûê L âñåõ ñëîâ â àëôàâèòå {0, 1}, ñîäåðæàùèõ ÷¼òíîå ÷èñëî åäèíèö è íå÷¼òíîå ÷èñëî íóëåé;C.3.3. Àëãîðèòìû ïîñòðîåíèÿ êîíå÷íûõàâòîìàòîâ3.3.1. Äëÿ ðåãóëÿðíîãî âûðàæåíèÿ íàä àëôàâèòîì T ={a, b} ïîñòðîèòü ýêâèâàëåíòíûé äåòåðìèíèðîâàííûé êîíå÷íûé àâòîìàò:à) b(ba | b)∗ | bá) (ab | b)∗ ba | abâ) (a | b)∗ ba(a | b)ã) (a | b)∗ ab(a | b)∗ä) a(ab | b)∗ | baå) (ba | b)∗ ab | baæ) (a∗ b)∗ ab∗ aç) (a | b)∗ (a | b)(a | b(a | b)C.3.4. Ðåãóëÿðíûå ìíîæåñòâà è èõ ïðåäñòàâëåíèÿ3.4.1. Áóäåò ëè ðåãóëÿðíûì ÿçûêL = {x ∈ {a, b} | x íå ñîäåðæèò ïîäöåïî÷êè aba}?3.4.2.
Âîçìîæíî ëè ïîñòðîèòü ðåãóëÿðíóþ ãðàììàòèêó,ïîðîæäàþùóþ ÿçûê, âêëþ÷àþùèé â ñåáÿ âñå íåïóñòûå öåïî÷êè èç 0 è 1, íå ñîäåðæàùèå òð¼õ 1 ïîäðÿä?C.3.5. Àëãåáðàè÷åñêèå ñâîéñòâà ðåãóëÿðíûõ ìíîæåñòâ. Ëåììà î ðàçðàñòàíèè.3.5.1. Áóäóò ëè ðåãóëÿðíûìè ñëåäóþùèå ÿçûêè â àëôàâèòå {a}:à) L1 = {{a2n+5 } ∪ {a7n+4 }, n = 0, 1, ...};á) L2 = {{a2n+5 } ∩ {a7n+4 }, n = 0, 1, ...};4n+5â) L3 = {{a}, n = 0, 1,o..., n 6= 5(mod11)};n2ä) L4 = an , n = 0, 1, ... .C.4. Ñèíòàêñè÷åñêèé àíàëèç3393.5.2. Áóäóò ëè ðåãóëÿðíûìè ñëåäóþùèå ÿçûêè â àëôàâèòå Σ = {a, b}:à) ÿçûê L1 èç âñåõ ñëîâ Σ∗ , ñîäåðæàùèõ ïîäñëîâà a?b;á) ÿçûê L2 èç âñåõ ñëîâ Σ∗ , íå ñîäåðæàùèõ äâóõ b ïîäðÿä;â) ÿçûê L3 èç âñåõ ñëîâ Σ∗ , íå ïðèíàäëåæàùèõ L1 èëè L2 ;ã) L4 = {{a2n+5 b7n+4 }, n = 0, 1, ....}?3.5.3.
Çàäàåòñÿ ëè ÿçûê {an bm | n > m > 1} ðåãóëÿðíûìâûðàæåíèåì?3.5.4. ßâëÿåòñÿ ëè ãðàììàòèêà ñ ïðàâèëàìè:S → aA | bB | C;B → bB | b | ε;A → aA | a | ε;C → cSC.ïðàâîëèíåéíîé ãðàììàòèêîé?C.4. Ñèíòàêñè÷åñêèé àíàëèçC.4.1. ÊÑ-ãðàììàòèêè è ÌÏ-àâòîìàòû4.1.1. Ïóñòü G ãðàììàòèêà ñ ïðàâèëàìè:S → SbS | ScS | aÍàéòè 2 ðàçëè÷íûõ äåðåâà âûâîäà äëÿ öåïî÷êè abaca.4.1.2. Äàíà îäíîçíà÷íàÿ ÊÑ-ãðàììàòèêà G=(N, T, P, S) è öåïî÷êà w ∈ L(G). Êîëè÷åñòâî ýëåìåíòîâ âî ìíîæåñòâàõ N, T, P ðàâíî n1 , n2 , n3 ñîîòâåòñòâåííî,à |w| = l. Íàéòè íèæíþþ è âåðõíþþ ãðàíèöó äëÿ ÷èñëàäåðåâüåâ ðàçáîðà w â G.4.1.3. ßâëÿþòñÿ ëè îäíîçíà÷íûìè ñëåäóþùèå ãðàììàòèêè?à) S → a | C; C → AB; A → aA | Ba | a; B → aB ;á) S → BA; A → Aa | bA | ε; B → Bb | aB | b;â) S → b | C; C → aC | AC; A → aA | Aa | a;ã) S → AB; A → aA | bA | a; B → Ba | Bb | ε;ä) S → A | B; A → AA | a; B → aB | b | C; C → cC ;å) S → aA | bB; A → aA | a | b; B → bB | b | ε;æ) S → aAc | bS; A → aA | Aa | ε;ç) S → aA | b; A → abA | abAcb; B → c;è) S → aB | cA; A → BaA | a; B → A | a;ê) S → ABS | ε; A → abA | a; B → Ba | Bab | ε.340Ïðèëîæåíèå C.
Çàäà÷è ïî ðàçäåëàì êíèãè4.1.4. ßâëÿåòñÿ ëè îäíîçíà÷íîé ãðàììàòèêà ñ ïðàâèëàìè:à) S → A | B; B → aB | b | C; A → AA | a; C → cC ;á) S → aAc | bS; A → aA | Aa | c;â) S → aA | b; A → abA | abAcb; B → c;ã) S → aB | cA; A → BaA | a; B → A | b;ä) S → a | C; C → AB;A → aA | Ba | a; B → aB ;å) S → BA; A → Aa | bA | ε; B → Bb | aB | b;æ) S → b | C; C → aC | AC; A → aA | Aa | a;ç) S → AB; A → aA | bA | a; B → Ba | Bb | ε.4.1.5. Ïóñòü G1 ãðàììàòèêà, èìåþùàÿ ïðîäóêöèè:S → bA | ab; A → a | aS | bAA; B → b | bS | aBB,à G2 ãðàììàòèêà, îïðåäåëÿåìàÿ ïðîäóêöèÿìè:S → aB | aBS | bAS | bA; A → bAA | a; B → bBB | b.Ïîêàçàòü, ÷òî1) G1 íåîäíîçíà÷íàÿ ãðàììàòèêà;2) G2 îäíîçíà÷íàÿ ãðàììàòèêà;3) L(G1 ) = L(G2 ).4.1.6. Êàêîé ÿçûê äîïóñêàåòñÿ àâòîìàòîì ñ ìàãàçèííîéïàìÿòüþP = ({q0 }, {a, b}, {z0 }, ∅, q0 , z0 , {q0 }) ?îïðåäåëÿþùèå ÿçûêè©4.1.7.
Ïîñòðîèòü ÌÏ-àâòîìàòû,∗ªà) wwR : w ∈ {a, b} ;á) ÿçûê âñåõ öåïî÷åê èç íóëåé è åäèíèö ñ îäèíàêîâûì ÷èñëîì© òåõ è∗ äðóãèõªâ) © {a, b} \ {am bn am bn } : m, n >ª1 ;∗ã) ©{a, b} \ {am bn am } : m, n >ª1 ;∗∗ä) {a, b} \ {ww} : w ∈ {a, b] .4.1.8. Ïîñòðîèòü àâòîìàò ñ ìàãàçèííîé ïàìÿòüþ, äîïóñêàþùèé ÿçûê:à) ({an bn cm | n, m > 1}) ∪ ({am bn cn | n, m > 1});á) {an ck bn | k, n > 1};â) {am bn cp | m + n + p ≡ 0(mod2); 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 };C.4. Ñèíòàêñè÷åñêèé àíàëèç341æ) {x | x ∈ {a, b}∗ , |x|a = |x|b , è äëÿ ∀ u, v : x = uv, |u| 6=0, |v| 6= 0 âûïîëíåíî |u|a > |u|b }.4.1.9.
Ïóñòü A ìàãàçèííûé àâòîìàò. Ïîñòðîèòü ìàãàçèííûé àâòîìàò B , äîïóñêàþùèé âñå ïðåôèêñû ÿçûêàL(A), òî åñòü ÿçûêL(B) = {x | xy ∈ L(A)}.4.1.10. Ïîñòðîèòü äåòåðìèíèðîâàííûå ÌÏ-àâòîìàòû,îïðåäåëÿþùèå ÿçûêè:à) {wcwR : w ∈ {a, b}∗ };á) {0n 1n : n > 1}â) {xcxR ycy R | x, y ∈ {a, b}∗ }.4.1.11. ßâëÿåòñÿ ëè ÿçûê L = {xcxR | x ∈ (a∗ b∗ )∗ } äåòåðìèíèðîâàííûì? Îáîñíîâàòü îòâåò ñ ïîìîùüþ ìàãàçèííîãîàâòîìàòà, äîïóñêàþùåãî ÿçûê L.4.1.12. ßâëÿåòñÿ ëè äåòåðìèíèðîâàííûì ñëåäóþùèéÿçûê:à) L = {xR cx | x ∈ (a∗ b∗ )∗ };á) L = {xcxR | x ∈ (b∗ a∗ )∗ };â) L = {xcxR | x ∈ b∗ (a∗ )∗ }.4.1.13. Äîêàçàòü, ÷òî äëÿ ëþáîé ÊÑ-ãðàììàòèêè G0 ñóùåñòâóåò ýêâèâàëåíòíàÿ åé ÊÑ ãðàììàòèêà G, èìåþùàÿëèøü ïðàâèëà âèäàA → BC; A → a , ãäå A, B, C ∈ VN , a ∈ VT .4.1.14. Äîêàçàòü, ÷òî åñëè L1 ÊÑ-ÿçûê, òî ÿçûê L,ñîñòîÿùèé èç âñåõ ñëîâ L1 ÷åòíîé äëèíû ÊÑ-ÿçûê, òîåñòüL = {X | X ∈ L1 , |X| = 2K, K = 0, 1, ..., } ÊÑ-ÿçûê.4.1.15.
Äîêàçàòü, ÷òî äëÿ ÊÑ-ãðàììàòèêè G ñóùåñòâóåòíåóêîðà÷èâàþùàÿ ÊÑ-ãðàììàòèêà G0 , ïîðîæäàþùàÿ ÿçûêL(G0 ) = L(G) \ {ε}.4.1.16. Ïðèâåñòè àëãîðèòì, ïîçâîëÿþùèé óçíàòü, ïðèíàäëåæèò ëè äàííîå ñëîâî äàííîìó ÊÑ-ÿçûêó è äîêàçàòüåãî ïðàâèëüíîñòü.342Ïðèëîæåíèå C. Çàäà÷è ïî ðàçäåëàì êíèãè4.1.17. ÊÑ-ãðàììàòèêà íàçûâàåòñÿ ëåâîîäíîçíà÷íîé, åñëè êàæäîå ñëîâî ïîðîæäàåìîãî åþ ÿçûêà èìååò åäèíñòâåííûé ëåâûé âûâîä.
Àíàëîãè÷íî îïðåäåëÿåòñÿ ïðàâîîäíîçíà÷íàÿ ãðàììàòèêà. Ïîñòðîèòü ïðèìåð ëåâîîäíîçíà÷íîé,íî íå ïðàâîîäíîçíà÷íîé ÊÑ-ãðàììàòèêè.C.4.2. Àëãåáðàè÷åñêèåñâîéñòâàÊÑÿçûêîâ. Ëåììà î ðàçðàñòàíèè.4.2.1. Ïóñòü L1 , L2 ÊÑ-ÿçûêè. Äîêàæèòå:1) L1 ∪ L2 ÊÑ-ÿçûê;2) L1 L2 ÊÑ-ÿçûê.4.2.2. Ïóñòü L ÊÑ-ÿçûê.
Äîêàæèòå:1) L∗ ÊÑ-ÿçûê;2) LR ÊÑ-ÿçûê.4.2.3. Äîêàçàòü, ÷òî íå ñóùåñòâóåò ÊÑ-ãðàììàòèê, ïîðîæäàþùèõ ÿçûêèà) {an bn cn } : n > 1};á) {ww : w ∈ {a, b}∗ };n 2on 3oâ) an : n > 1 ;ã) an : n > 1 .4.2.4. Âûÿñíèòü, êàêèå èç ïðèâåäåííûõ íèæå ÿçûêîâ íåÿâëÿþòñÿ ÊÑ-ÿçûêàìè:1) {ai bj ck | 0 6 i < j < k};2) {ai bj ck | 0 6 i = j = k};3) {ai bj ck | 0 6 i = j, k > 0, i 6= k};4) {ai bj ck | 0 6 i = j, k > 0}.4.2.5. Ïîêàçàòü, ÷òî ÿçûê {an bn cn | n>1} íå ÿâëÿåòñÿÊÑ-ÿçûêîì.4.2.6. ßâëÿåòñÿ ëè ÿçûê {an bm an bm | n > 1, m > 1} ÊÑÿçûêîì?4.2.7. ßâëÿåòñÿ ëè ÿçûê {an bm bn am | n > 1, m > 1} ÊÑÿçûêîì?4.2.8. ßâëÿåòñÿ ëè ÿçûê {ap | p ïðîñòîå ÷èñëî} ÊÑÿçûêîì?C.4. Ñèíòàêñè÷åñêèé àíàëèç34324.2.9.
ßâëÿåòñÿ ëè ÿçûê {an bn | n ∈ N } ÊÑ-ÿçûêîì?4.2.10. Îïðåäåëèòü, çàìêíóòî ëè ìíîæåñòâî ÊÑ-ÿçûêîâîòíîñèòåëüíî äîïîëíåíèÿ?4.2.11. Çàìêíóòî ëè ìíîæåñòâî ÊÑ-ÿçûêîâ îòíîñèòåëüíîîáðàùåíèÿ ? (Èíà÷å ãîâîðÿ, âåðíî ëè, ÷òî åñëè L ÊÑÿçûê, òî LR òîæå ÊÑ-ÿçûê).C.4.3. Ïðåîáðàçîâàíèÿ ÊÑ-ãðàììàòèê4.3.1. Óêàçàòü ìíîæåñòâî áåñïîëåçíûõ ñèìâîëîâ äëÿãðàììàòèêè:S → A | B; B → aB | b | C; A → AA | a; C → cC.4.3.2. Óêàçàòü ìíîæåñòâî áåñïîëåçíûõ ñèìâîëîâ â ãðàììàòèêå G = ({S, A, B, C}, {a, b, c}, P, S), ãäå P ñîñòîèò èçS → aSb | Abb | εB → ABA → aBCb | bAbC → a | c.4.3.3.
Óêàçàòü ìíîæåñòâî áåñïîëåçíûõ ñèìâîëîâ â ãðàììàòèêå G = ({S, A, B, C},{a, b, c}, P, S), ãäå P ñîñòîèò èçS→A|BA → aB | bS | bB → AB | BaC → AS | b.4.3.4. Óêàçàòü ìíîæåñòâî áåñïîëåçíûõ ñèìâîëîâ â ãðàììàòèêå G=({S, A, B, C, D}, {a, b, c}, P, S}, ãäå P ñîñòîèò èçS → aBb | aCbA → Dc | cAB → aS | bC → AB | aDD → AB | cDa.4.3.5. Óêàçàòü ìíîæåñòâî áåñïîëåçíûõ ñèìâîëîâ â ãðàììàòèêå G = ({S, A, B, C}, {0, 1, 2}, P, S), ãäå P ñîñòîèò èçS → SS | AA → 0A1 | C | 0B → 0C | 1C → BC | CS .4.3.6.
ßâëÿþòñÿ ëè ñëåäóþùèå ãðàììàòèêè ïðèâåä¼ííûìè? Óêàçàòü äëÿ êàæäîé ãðàììàòèêè ìíîæåñòâà íåäîñòèæèìûõ, áåñïëîäíûõ è áåñïîëåçíûõ ñèìâîëîâ:344Ïðèëîæåíèå C. Çàäà÷è ïî ðàçäåëàì êíèãèà) S → a | CC → ABA → aA | Ba | aB → aB ;á) S → BAA → Aa | bA | εB → Bb | aB | b;â) S → b | CC → aC | ACA → aA | Aa | a;ã) S → ABA → aA | bA | aB → Ba | Bb | ε;ä) S → A | BA → AA | aB → aB | b | CC → cC ;å) S → aA | bBA → aA | a | bB → bB | b | ε;æ) S → aAc | bSA → aA | Aa | ε;ç) S → aA | bA → abA | abAcbB → c;è) S → aB | cAA → BaA | aB → A | a;ê) S → ABS | εA → abA | aB → Ba | Bab | ε.4.3.7.
Ïîñòðîèòü ïðèâåä¼ííûå ãðàììàòèêè, ýêâèâàëåíòíûå ñëåäóþùèì ãðàììàòèêàì:a) S → A | BA→C|DB→D|EC→S|a|εá) S → ABD→S|bE → S | c | ε;A → Aa | bBB → a | Sb.4.3.8. Ïîñòðîèòü ε-ñâîáîäíûå ÊÑ-ãðàììàòèêè, ýêâèâàëåíòíûå ñëåäóþùèì ãðàììàòèêàì:1) S → AB2) S → ABCA → C | abA → BB | εC→c|εB → CC | εB → aAa;C → AA | b;3) S → aSbSS → bSaS | ε;4) S → ABA → SA | BB | bBB → b | aA | ε.C.4. Ñèíòàêñè÷åñêèé àíàëèç3454.3.9. Äîêàçàòü, ÷òî äëÿ êàæäîé ÊÑ-ãðàììàòèêè ñóùåñòâóåò ýêâèâàëåíòíàÿ åé ïðèâåäåííàÿ ÊÑ-ãðàììàòèêà.4.3.10. Ïðèâåñòè àëãîðèòì ïîñòðîåíèÿ ìíîæåñòâà äîñòèæèìûõ ñèìâîëîâ è äîêàçàòü åãî ïðàâèëüíîñòü4.3.11.
Äîêàçàòü, ÷òî äëÿ êàæäîé ÊÑ-ãðàììàòèêè ñóùåñòâóåò ýêâèâàëåíòíàÿ åé ÊÑ-ãðàììàòèêà, íå ÿâëÿþùàÿñÿëåâîðåêóðñèâíîéC.4.4. Ïðåäñêàçûâàþùèé ðàçáîð ñâåðõóâíèç4.4.1. Ïîñòðîèòü ìíîæåñòâà F IRST è F OLLOW äëÿêàæäîãî íåòåðìèíàëà ãðàììàòèêèà) S → aAB | Bá) S → aAB | BAA → aA | aA → BBB | aB → BS | A | b;B → AS | b;â) S → S + TS→TT →aT → S[S];ã) S → ABCA → BB | εB → CC | aC → AA | b;ä) S → aB | bAA → aS | bAA | aB → bS | aBB | b;å) S → Ba | AbA → Sa | AAb | aB → Sb | BBa | b;æ) S → (SbS)S → (T )S→aT → TST → S;ç) B → begin D; S endB→sD → D; dD→dS → S; BS → B;è) A → aACd | bC → c | ε.4.4.2.
ßâëÿåòñÿ ëè ñëåäóþùàÿ ãðàììàòèêà LL(1)? Èñ-346Ïðèëîæåíèå C. Çàäà÷è ïî ðàçäåëàì êíèãèïîëüçîâàòü êðèòåðèé LL(1).S → aAb; A → 0; A → aaA.4.4.3. Äëÿ ãðàììàòèêè íàïèñàòü ýêâèâàëåíòíóþ LL(1)ãðàììàòèêóà) S → aS | a;á) S → ba | AA → a | Aab | Ab;â) S → aaS | abAA → ε | Aa | Ab;ã) S → baaA | babAA → ε | Aa | Ab;ä) S → abaA | abbAA → ε | Aa | Ab;å) S → ab | baAA → ε | Aab | Ab.4.4.4. Äëÿ ñëåäóþùèõ ãðàììàòèê îïðåäåëèòü, ÿâëÿþòñÿ ëè îíè LL(k) ãðàììàòèêàìè è íàéòè òî÷íîå çíà÷åíèåk . Äëÿ LL(1)-ãðàììàòèê ïîñòðîèòü äåòåðìèíèðîâàííûé ëåâûé àíàëèçàòîð:a) S → aAS | bA → a | bSA;á) S → A | BA → aAb | 0B → aBbb | 1;â) S → ε | abAA → Saa | b;ã) S → aS | a;ä) S → aAaa | bAbaA → b | ε;å) S → Sa | b;æ) S → T E 0 ;E 0 → +T E 0 | εT → FT0T 0 → ∗F T 0 | εF → (S) | a.4.4.5.
![](https://s.studizba.com/z.php?f=/templates/si/i/noavatar.png&w=100&h=100&t=1"){kind=avatar}
