Ответы к задачам (1115041)

Просмтор этого файла доступен только зарегистрированным пользователям. Но у нас супер быстрая регистрация: достаточно только электронной почты!

Текст из файла

Ответы на задачиI. Порождающие грамматики. Языки, порождаемые грамматиками.Классификация грамматик и языков по Хомскому3.Тип гр - 0;Язык L (G) = { an bm an bm | n, m >= 1 }, тип языка - 2.Тип гар. - 0;Язык L (G) = { xx | x {a,b}+ }, тип языка -1.Тип гр. – 1 (неукор.),L(G) = {an bn cn | n = 1,2,3,4}. Тип языка 3 (регулярный)Тип гр. - 0,L(G) ={0n 1n | n = 1,2,3,4,5}.

Тип языка 3 (регулярный).r)s)t)u)4. Построить грамматику, порождающую язык :4a).L = { an bm | n, m >= 1}SAB4b).L = { c c c | , , - любые цепочки из a и b} SA4с).L = { a1 a2 ... an an ... a2 a1 | ai = 0 или 1, n >= 1}SABa | Aab| BbAcAcAcaA | bA | ε0S0 | 1S1 | 00 | 114d).S -> 00A1 | 0илиA -> 00A1 | 0 | εЯзык - КС, гр-ка КС4e).S -> cAA -> aAc | cBB -> bB | εЯзык - КС, гр-ка КС4f).L = { an b m | nm ; n, m >= 0}илиS -> 0A1 | 0A -> 0S | 0SAB4g).L = { цепочки из 0 и 1 с неравным числом 0 и 1} SCDABAB4h).L={|{a,b}+}SDS -> 00S1 | 001 | 0aSb | A | Ba | aAb | bBASB | C | DCA | ADB | BBA01DCaDA | bDB | aA | bBAC aCBC bCAa aABa aBAb bABb bBC ε4i).L={ |{0,1}+ и содержит равное количество 0 и 1, причем любая подцепочка, взятая слевого конца, содержит единиц не меньше, чем нулей}SA1A0AA | 01A | 1A0 | ε4j).L = { (a2m bm)n | m >= 1, n >= 0}4k).nL = { a3 1 | n >= 1}SASA | εaaAb | aabS aKaK KN | NNa aaaNN4l).L={an2 | n >= 1}S CFDF AFB | ABAB aBAAa aAAD DCa aCCB CCD ε4m).L={an3 1| n >= 1}S CFDF EAFB | EABAB GBAAG GAAE EAAD DEG aGEEB EEa aEED DCa aCCG CCD a9.SAaASb | bL (G) = { an bn | n >= 1} – КС-язык.12.Определить тип грамматики.

Описать язык, порождаемый этой грамматикой. Написать дляэтого языка КС-грамматику.S PТип грамматики 0.P 1P1 | 0P0 | TT 021 | 120RR1 0RR0 1R1L = {bi 2 (bi+1)R | bi - двоичное представление числа i N, R – реверс цепочки }КС-грамматика:S P | T1P 1P1 | 0P0 | 0T1T 1T0 | 219.Написать общие алгоритмы построения по данным КС-грамматикам G1 и G2,порождающим языки L1 и L2, КС-грамматики для19a). L1 L2S S1 | S2S1 ........................S2 ........................19b).

L1 * L2L = L1 * L2 - это конкатенация языков L1 и L2, т.е.L = {|L1,L2}S S1S2S1 ........................S2 ........................19c). L1*L=L1* - это итерация языка L1, т.е. объединение { } L1 L1*L1 L1*L1*L1 ...S S1SS1 ........................20.Написать КС-грамматику для L={ i 2 i+1R | i N, i=(i)2 - двоичное представление числа i,R- реверс цепочки }. Написать КС-грамматику для языка L* (см. задачу 19 раздела I).SAB1B01 | 1A1 | 0211A1 | 0A0 | 0B12 | 1B0- без незначащих нулей22.AAAAA |(док-во дляA A|(док-во дляA|A |AA|) – порождаются подцепочки n (n >= 1);AA|) – порождаются подцепочки ( )n (n >= 0);AA | B;(док-во дляB B | , B VN) – порождаются подцепочкиnm(n, m >= 0);24.Дана КС-грамматика G={VT, VN, P, S}.

Предложить алгоритм построения множества= {A VN | A}.Алгоритм:1.N0 = , i = 1.2.Ni = {A | (A) Pи(Ni-1)} Ni-1.3.Если Ni Ni-1, то i = i + 1 и переходим к шагу 2, иначе X = Ni.X25.Для произвольной КС-грамматики G предложить алгоритм, определяющий, пуст ли языкL(G).Алгоритм:1.N0 = , i = 1.2.Ni = {A | (A) Pи(Ni-1 VT)*} Ni-1.3.Если Ni Ni-1, то i = i + 1 и переходим к шагу 2,иначе, если S Ni – ответ «да», иначе «нет».II.

Регулярные грамматики, ДС, анализаторы по ДС.Преобразовааание НКА к ДКА4.a)SBABAy | ByAx | Bx | xd)SABA |B |B1 | 1A0 | B0 | 0e)SBACDB1 | C1B1 | C1 | A11A0 | B0 | D0C010. c).L = {a {dn,(aa)m }* a | n, m >=0}SBABAaBa | Ad | ab)SABCDAByCyDyAx | xF (H, 1) = AF (A, 0) = CF (A, 1) = BF (B, 0) = CF (B, 1) = BSF (C, 0) = DF (C, 1) = BSF (D, 0) = CF (BS, 0) = CF (BS, 1) = BS//SSBACDB1 | C1 | S1A11A0 | B0 | D0 | S0C011. Тип грамматики – УКС.L = {0m (1 02*in )n 0k | in, n, m, k >=0}НКА: S A | B | D |A A0 | 0B A1 | C0 | D1 | 1C B0D C0 | D012c). F(H,0)=ABF(H,1)=CF(H, )=F(AB,0)=F(AB,1)=ACF(AB, )=КА:SABCDEA |B |D |E |A0 | 0A1 | E1 | D1 | 1B0C0 | E0D0F(C,0)=ABF(C,1)=F(C, )=SF(AC,0)=ABF(AC,1)=ACF(AC, )=SПусть AB = X, AC = Y, тогдаG:S -> C | Y12d). F(H,a)=AF(H,b)=BF(H, )=C ->1F(A,a)=F(A,b)=F(A, )=SY -> Y1 | X1X -> C0 | Y0 | 0F(B,a)=F(B,b)=ABF(B, )=F(AB,a)=F(AB,b)=ABF(AB, )=SПусть AB = X, тогдаG:S -> A | XA ->aX -> Xb | BbB -> b12e).

F(H,0) = ABF(AB,0) = BSF(AB,1) = CF(BS,0) = BSF(C,0) = SF(C,1) = CAB ABS BS DДва заключительныхсостояния BS и S сводимв одно S' S с исп. .SBADCB |DB0 | A00C0C1 | A112f).BC BBS DCS CДва заключительныхсостояния BS и CS сводимв одно S' S с исп. .SCADBC |DCc | BcaDb | BbAbF(H,a) = AF(A,b) = BCF(BC,b) = BSF(BC,c) = CSF(BS,b) = BSF(CS,c) = CS12g).

F(H,0) = CF(C,0) = CF(C,1) = AF(A,0) = BSF(BS,1) = ASF(AS,0) = BSAS RF(AS,1) = SBS QF(S,1) = SS PТри заключительныхсостояния AS, BS и S сводимв одно S'12h). F(H,a) = BSF(BS,a) = BSF(BS,b) = CBS XS YS с исп..SXYSPRQACX |YXa | Ya |aCcP | Q |RP1 | R1Q1A0 | R0C1C0 | 0Два заключительныхсостояния BS и S сводимв одно S' S с исп. .F(C,c) = SF(S,a) = BS12i).F(H,0)=ABF(H,1)=CF(H, )=F(AB,0)=F(AB,1)=ACF(AB, )=F(C,0)=ABF(C,1)=F(C, )=SCXbF(AC,0)=ABF(AC,1)=ACF(AC, )=SПусть AB = X, AC = Y, тогдаG:S -> C | YC ->1Y -> Y1 | X1X -> C0 | Y0 | 0Пусть AB = X, тогда12j).F(H,a)=AF(H,b)=BF(A, )=SF(B,b)=ABF(AB,b)=ABF(AB, )=SG:13.L = {1n 0m 1 {0, 1}k | n, k >=0, m >= 1}L1 = {0m 1 {0, 1}k | k >=0, m >= 1}L2 = {1n 0m 1 {0, 1}k | k >=0, n, m >= 1}L1 L2 = {0m 1 {0, 1}k 1n 0i 1 {0, 1}j | j, k >=0, n, m, i >= 1}G(L1 L2): S EE E0 | E1 | D1D D0 | C0C C1 | B1B B0 | B1 | A1A A0 | 015.L1 = { 0m 1n | n, m >= 1}L1*L1 = { 0m 1n 0m1 1n1 | n, m, n1, m1 >= 1}SCBAS -> A | XA ->aX -> Xb | BbB -> bS1 | C1B0 | C0B1 | A1A0 | 0III.

Метод рекурсивного спуска (РС-метод), применимость РС-метода.КС-грамматики с действиями1c).SABaSB | bAf |bAc | cScB | dFIRST(S) = {a, b},FOLLOW(S) = {c, d, f }O.K.!1d).SABaSB | bAaS | cA | εbB | dFIRST(A) = {a, c},1e).SABCFOLLOW(A) = {b, d }bABCb | daA | cB |Sca {bb}CaNNO.K.!bbN |FIRST(A)={a, c}, FOLLOW(A)={b, d};=FIRST(N)={b}, FOLLOW(N)= {b};={b}РС-метод неприменим1f).SABCFIRST(B) = {a, c},FIRST(N) = {b},1g).SABaAb | cCa { bab }cAc | aB |BbSAaNNbabN |FOLLOW(B) = {b};=FOLLOW(N) = {b, c};= {b}РС-метод неприменимaA{xx}bA | cBx |bScFIRST(N) = {x},FIRST(A) = {b, c},1h).ASABNaANbA | cBx |bScxxN |FOLLOW(N) = {c} ; =FOLLOW(A) = {x, c} };= {b}РС-метод неприменимaSc | bA |cS {da} bA | dSANaSc | bA |cSNbA | ddaN |Для приведенной грамматики, содержащей только правила вывода из S, РС-методприменим (!), но если (что неверно) рассматривать вторую строчку, то окажется, чтоFIRST(N) = {d},FOLLOW(N) = {b} ;=FIRST(S) = {a, b},FOLLOW(S) = {c, d, b}};= {b}РС-метод неприменим1i).1j).S bS | aABA bcA | ccA |B cbB |FIRST(A)={b,c}, FOLLOW(A)={c};FIRST(B)={c}, FOLLOW(B)=SaASb | cfAd= {c}=> РС-метод неприменимA bA | c |FIRST(A)={b,c}, FOLLOW(A)={a,c,d};2a).= {c}2b).SAB=> PC-метод неприменимSABAB{aB}b|εaA | bBcS | ε{,b}SAaSb | Ab {b}Метод рекурсивного спуска к даннойграмматике неприменим.SABAB {aB} Bb|Метод рекурсивного спуска к даннойграмматике неприменим.2c).2d)3a).S bS | aABA bcA | ccA |B cbB |FIRST(A)={b,c}, FOLLOW(A)={c};= {c}FIRST(B)={c}, FOLLOW(B)=S bS | aA'A' bcA' | ccA' | BbcA' | ccA' | cbB |A bcA' | ccA' |- недостижимые правила, их можно убратьB cbB |S bS | aA'A' bcA' | cA'' |A'' cA' | bBB cbB |3b).O.K.!S aASb | cfAdA bA | c |FIRST(A)={b,c}, FOLLOW(A)={a,c,d};= {c}S aA' | cfAdA' bA' | cSb | SbbA' | cSb | a A'b | cfAdbA bA | c |S aA' | cfAdA' bA' | a A'b | cA''A'' Sb | fAdbaA'b | cfAdb | fAdbA bA | c |3c).SABSa | Sbb | fAcaB | d(левая рекурсия)abB | Sb=>SS'ABFIRST(S')={a,b}, FOLLOW(S')={b};S fAcS'SS' aS' | bbS' |S'A aB | dAB abB | fAcS''B- O.K.!fAcS'aS' | bbS' |aB | dabB | Sb= {b}fAcS'aS' | bbS' |aB | dabB | fAcS''=>SS'ABfAcS'aS' | bbS' |aB | dabB | fAcS'bS''S'' aS'' | bS '''S ''' bS'' |FIRST (S''')={b}, FOLLOW(S''')={c};=3d).SABaS'' | bbS'' | bcAdAa | bB (левая рекурсия)abB |=>SAA'BO.K.!cAdbBA'aA'|abB |= {a}=FIRST(B)={a}, FOLLOW(B)={a,d};FIRST(A')={a}, FOLLOW(A')={d};S cAdS cAdAbB'AbB'A' aA'|A' aA'|B' abB' | A'B' abB' | aA'|FIRST(B')={a}, FOLLOW(B')={d};=FIRST(B'')={a,b}, FOLLOW (B'')={d};=SAA'B'B''cAdbB'aA'|aB'' |bB' | A'S cAdAbB'A' aA'|B' aB'' |B'' bB'|aA'|- O.K.!3e).S ES ES EE () | (E {, E}) | AE () | (E {, E}) | a | bE (E‟ | a | bA a|bE‟ ) | E {, E})...

дальше можно не преобразовывать, т.к. для E‟ конфликта нет (E не начинается „)‟).3f).1)2)3)4)5)6)SPETFIP := E | if E then S | if E then S else S aP‟:=E | bP‟:=E | if E then S S‟I | I (E) P IP‟ aP‟ | bP‟; P‟ (E) | εT {+T}F {*F}P | (E) aP‟ | bP‟ | (E)a|b1)2)3)4)5)6)7)SS‟PP‟ETFaP‟:=E | bP‟:=E | if E then S S‟else S | εFIRST(S‟)={else}; FOLLOW(S‟)={else};-!!!aP‟ | bP‟(E) | εFIRST(P‟)={(}; FOLLOW(P‟)={*,+,:=,then,)};-O.K.!T {+T} – O.K.!F {*F} – O.K.!aP‟ | bP‟ | (E)Замечание: Вообще говоря, исходная грамматика неоднозначна и метод РС неприменим. Ееможно преобразовать. Но если формально писать анализатор РС-методом по этойграмматике, неоднозначность устранится сама по себе правильным образом (так устроеныпроцедуры РС-метода), т.е. else будет относиться к ближайшему if.3g).F function I(I) S; I:=E endS ; I:=E S |E E*I | E+I | IFSEE‟function I(I) S; I:=E end; I:=E S |IE‟*IE‟ | +IE‟ |FS‟SEE‟FIRST(S) = {;}, FOLLOW(S) = {;};= {;}FIRST(E') = {+ , *}, FOLLOW(E') = {; , end};=function I(I) S‟F function I(I) S‟; I := ES‟ | ; I := E endS‟ ; I := ES”; I:=E S | - недостижимые правила.S” S‟ | end; I := ES” | endIE‟E IE‟*IE‟ | +IE‟ |E‟ *IE‟ | +IE‟ |O.K.!3h)S SaAb | Sb | bABaA acAb | cA |B bB |SS‟ABbABaS‟aAbS‟ | bS‟ |acAb | cA |bB |FIRST(S‟) = {a, b}, FOLLOW(S‟) =FIRST(A) = {a, c}, FOLLOW(A) = {a, b};= {a}FIRST(B) = {b}, FOLLOW(B) = {a};=S bA‟A‟ acAbBaS‟ | cA‟ | BaS‟ acAbBaS‟ | cA‟ | bBaS‟ |aS‟S‟ aAbS‟ | bS‟ |A acAb | cA |B bB |S bA‟A‟ aA” | cA‟ | bBaS‟A” cAbBaS‟ | S‟ cAbBaS‟ | aAbS‟ | bS‟ |S‟ aAbS‟ | bS‟ |A acAb | cA |B bB |FIRST(A”) = {a, b, c}, FOLLOW(A') =O.K.!3i)S Ac | dBeaA Aa | Ab | daBcB cB |S Ac | dBea daBcA‟c | dBeaA daBcA‟ - недостижимые правила.A‟ aA‟ | bA‟ |B cB |S dS‟S‟ aBcA‟c | Bea aBcA‟c | cBea | eaA‟ aA‟ | bA‟ |B cB |FIRST(A') = {a, b}, FOLLOW(A') = {c};=FIRST(B) = {c}, FOLLOW(B) = {c, e};= {c}S dS‟S‟ aB‟ | cBea | eaB‟ cB‟ | cA‟cB‟ cB” ; B” B‟ | A‟c cB” | aA‟c | bA‟c | cA‟ aA‟ | bA‟ |B cB |S dS‟S‟ aB‟ | cBea | eaB‟ cB”B” cB‟” | aA‟c | bA‟cB‟” B” |cB‟” | aA‟c | bA‟c |A‟ aA‟ | bA‟ |B cB |FIRST(B‟”) = {a, b, c}, FOLLOW(B”) =O.K.!3j).SABSAB'A'BfASd |Aa | Ab | dB | fbcB |S fASd |A dBA' | fA'A' aA' | bA' |B bcB |FIRST(S) = {f}, FOLLOW(S) = {d};=FIRST(A') = {a, b}, FOLLOW(A') = {f, d};=FIRST(B) = {b}, FOLLOW(B) = {a, b, f, d};= {b}fASd |S fASd |dB' | fA'A dB' | fA'bcB' | A' bcB' | aA' | bA' |B' bС | aA' |aA' | bA' |С cB' | A' cB' | aA' | bA' |bcB | - недостижимые правила.A' aA' | bA' |S - не менялось,FIRST(B') = {a, b}, FOLLOW(B') = {f, d};=FIRST(A') = {a, b}, FOLLOW(A') = {f, d};=O.K.!FIRST(C) = {a, b, c}, FOLLOW(C) = {f, d};=4.Вложенные списки, где уровень вложенности скобок не более 2.5.SA<k =0;> A0 <k++;> A | 1 <k = 0;> A | 2 <if (k >= 2) throw “ER!”; else k = 0;> A |6.SA<k = n = 0;> A <if (n < 3) throw “ER!”;>a <k++; if (k >= 3) throw “ER!”;> A |b <k = 0;> A |c <if (k == 2) throw “ER!”; else k = 0; n++;> A |S‟S<k =0;> S0 <if (k == 1) k = 2; else k = 0;> S |1 <if (k == 2) throw “ER!”; else k = 1;> S |7.8.SABCaAaA | bBbB | cCcC |SABCa <m = 1; n = k = 0;> Aa <m++;> A | b <n++;> Bb <n ++;> B | c <k++;> Cc <k++;> C |<if (m+k != n && m-k != n) throw “ER!”;>9.S‟SS‟a <m=n=0;> S < if (n <= m) throw “ER!”;>SAB1S | 0A |0A | 1B |1B |SAB1 <n++;> S | 0 <m++;> A |0 <m ++;> A | 1 <n++;> B1 <n++;> B |IV.

Характеристики

Тип файла PDF

PDF-формат наиболее широко используется для просмотра любого типа файлов на любом устройстве. В него можно сохранить документ, таблицы, презентацию, текст, чертежи, вычисления, графики и всё остальное, что можно показать на экране любого устройства. Именно его лучше всего использовать для печати.

Например, если Вам нужно распечатать чертёж из автокада, Вы сохраните чертёж на флешку, но будет ли автокад в пункте печати? А если будет, то нужная версия с нужными библиотеками? Именно для этого и нужен формат PDF - в нём точно будет показано верно вне зависимости от того, в какой программе создали PDF-файл и есть ли нужная программа для его просмотра.

Список файлов ответов (шпаргалок)