задачки (Решённые экзаменационные задачи)
Описание файла
Файл "задачки" внутри архива находится в следующих папках: resh-ekz-zadachi, OPT_zadachi. PDF-файл из архива "Решённые экзаменационные задачи", который расположен в категории "". Всё это находится в предмете "основы построения трансляторов" из 5 семестр, которые можно найти в файловом архиве НИУ «МЭИ» . Не смотря на прямую связь этого архива с НИУ «МЭИ» , его также можно найти и в других разделах. Архив можно найти в разделе "к экзамену/зачёту", в предмете "основы построения трансляторов" в общих файлах.
Просмотр PDF-файла онлайн
Текст из PDF
1. S → dSA | bAcA → dA | c1) Язык: L(G)={dnbd*cc(d*c)n, n≥0}2) МП-автомат:1. δ(q0,d,z0)=(q1,dz0)2. δ(q0,b,z0)=(q2,bz0)3. δ(q1,d,d)=(q1,dd)4. δ(q1,b,d)=(q2,bd)5. δ(q2,d,b)=(q2,b)6. δ(q2,cc,b)=(q3,ε) (если сс не м.б., тогда тут:а) δ(q2,c,b)=(q4,ε)б) δ(q4,c,d)=(q3,d)в) δ(q4,c,z0)=(q3,z0) )7. δ(q3,d,d)=(q3,d)8.
δ(q3,c,d)=(q3,ε)9. δ(q3,ε,z0)=(p,ε)3) ОПП:1. EQUAL = { (d,S), (S,A), (b,A), (A,c), (d,A) }2. first= first+ = { (S,d), (S,b), (A,d), (A,c) }LESS = { (d,d), (d,b), (S,d), (S,c), (b,d), (b,c), (d,c) }3. last+ = { (S,A), (S,c), (A,A), (A,c) }(last+)-1 = { (A,S), (c,S), (A,A), (c,A) }GREATER = { (A,A), (c,A), (A,c), (c,c), (A,d), (c,d) }2.A → abR | bRbAR → bR | a1) Язык: L(G)={(b+ab)*ab+a}2) Конечный автомат:1 ->(b) 2,2 ->(b) 2,2 ->(a) 3,3 ->(b) 1,1 ->(a) 4,4 ->(b) 5,5 ->(b) 5,5 ->(a) 6.1 – начальная, 6 – конечная.3) МП-автомат:δ(q0,b,z0)=(q1,z0)δ(q0,a,z0)=(q2,a)δ(q1,b,z0)=(q1,z0)δ(q1,a,z0)=(q1,az0)δ(q1,b,a)=(q0,ε)δ(q2,b,a)=(q2,a)δ(q2,a,a)=(q2,ε)δ(q2,ε,z0)=(p,ε)4) ОПП:1.
EQUAL = { (a,b), (b,R), (R,b), (b,A) }2. first = first+ = { (A,a), (A,b), (R,b), (R,a) }LESS = { (b,b), (b,a) }3. last+ = { (A,R), (A,A), (R,R), (R,a), (A,a) }(last+)-1 = { (R,A), (A,A), (R,R), (a,R), (a,A) }GREATER = { (R,b), (a,b) }3. S → SS | AA → 0A1 | 011) Язык: L(G)={0n,1n}+2) МП-автомат:-вариант Ромы:δ(q0,0,z0)=(q1,0z0)δ(q1,0,0)=(q1,00) //чтение 0δ(q1,1,0)=(q2,ε) //переходδ(q2,1,0)=(q2,ε) //удаление 0δ(q2,0,z0)=(q1,0z0) //возврат в 1δ(q2,ε,z0)=(p,ε) //конец-вариант Жени:δ(q0,0,z0)=(q1,0z0)δ(q1,0,0)=(q1,00)δ(q1,1,0)=(q1,ε)δ(q1,0,z0)=(q0,0z0) // возврат т.к у нас {01} итерации 000111010011//т.е после того как мы рассмотрели цепочку и в стеке получили z0 и у нас//возник 0, мы возвращаемся в начальное состояние с вершиной 0z0δ(q1,ε,z0)=(q0,ε)3) ОПП:1. EQUAL = { (S,S), (0,A), (A,1), (0,1) }2.
first+ = { (S,S), (S,A), (A,0), (S,0) }LESS = { (S,S), (S,A), (S,0), (0,0) }+3. last = { (S,S), (S,A), (A,1), (S,1) }(last+)-1 = { (S,S), (A,S), (1,A), (1,S) }GREATER = { (S,S), (A,S), (1,1), (1,S), (S,A), (S,0), (A,A), (A,0), (1,0), (1,A) }4. S → aT | TbST → bT | ba1) Язык: L(G)={(b+ab)*ab+a}2) Конечный автомат:S →(b) S1, S1 →(b) S1, S1 →(a) S2, S2 →(b) S, S →(a) S3, S3 →(b) S4, S4 →(b) S4, S4 →(a) ZМП-автомат:δ(q0,b,z0)=(q1,z0)δ(q1,b,z0)=(q1,z0)δ(q1,a,z0)=(q1,az0)δ(q1,b,a)=(q0,z0) //обработка (b+ab)*δ(q0,a,z0)=(q0,az0)δ(q0,b,a)=(q2,ba)δ(q2,b,b)=(q2,b)δ(q2,a,ba)=(q0,ε) //обработка ab+aδ(q0,ε,z0)=(p,ε) //конец3) ОПП:1.
EQUAL = { (a,T), (T,b), (b,S), (b,T), (b,a) }2. first+ = { (S,a), (S,T), (T,b), (S,b) }LESS = { (a,b), (b,a), (b,T), (b,b) }3. last+ = { (S,T), (S,S), (T,T), (T,a), (S,a) }(last+)-1 = { (T,S), (S,S), (T,T), (a,T), (a,S) }GREATER = { (T,b), (a,b) }5.Z → bZZ | a1) Язык: L(G) = {a} U {bn {bmam,ab}* an+1, n>=1,m>=0}.2) МП-автомат:δ(q0,a,z0)=(q2,z0)δ(q0,b,z0)=(q1,bz0)δ(q1,b,b)=(q1,bb)δ(q1,a,b)=(q1,ε)δ(q1,b,z0)=(q1,bz0)δ(q1,a,z0)=(q2,z0)δ(q2,ε,z0)=(p,ε)3) ОПП:1.
EQUAL = { (b,Z), (Z,Z) }2. first+ = { (Z,b), (Z,a) }LESS = { (b,b), (Z,b), (Z,a), (b,a) }3. last+ = { (Z,Z), (Z,a) }(last+)-1 = { (Z,Z), (a,Z) }GREATER = { (Z,Z), (a,Z), (Z,b), (Z,a), (a,b), (a,a) }6. Z → TTT → Ta | bT | c1) Язык: L(G)={b*ca*b*ca*}2) МП-автомат:δ(q0,b,z0)=(q0,z0)δ(q0,c,z0)=(q2,cz0)δ(q1,b,z0)=(q1,z0)δ(q1,c,z0)=(q2,cz0)δ(q1,b,c)=(q1,c)δ(q1,c,c)=(q2,ε)δ(q2,a,c)=(q2,c)δ(q2,b,c)=(q1,c)δ(q2,a,z0)=(q2,z0)δ(q2,ε,z0)=(p,ε)δ(q2,c,c)=(q2,ε)3) ОПП:1. EQUAL = { (T,T), (T,a), (b,T) }2. first+ = { (Z,T), (T,T), (T,b), (T,c), (Z,b), (Z,c) }LESS = { (T,T), (T,b), (T,c), (b,T), (b,b), (b,c) }3. last+ = { (Z,T), (T,a), (T,T), (T,c), (Z,a), (Z,c) }(last+)-1 = { (T,Z), (a,T), (T,T), (c,T), (a,Z), (c,Z) }GREATER = { (a,T), (a,a), (T,T), (T,a), (c,T), (c,a), (a,b), (a,c), (T,b), (T,c), (c,b), (c,c) }7.S → (AS) | (b)A → (aA) | (a)1) Язык: L(G) = { { ( {(a}m (a) {)}m}n (b) {)}n }, n,m>=0.2) ???3) ООП:1.
EQUAL = { [“(”,A], [A,S], [S,”)”], [“(”,b], [b,”)”], [“(”,a], [a,A], [A,”)”], [“(”,a], [a,”)”] }2. first+ = { [S,”(”], [A,”(”] }LESS = { [“(”,”(”], [A,”(”], [a,”(”], }3. last+ = { [S,”)”], [A,”)”] }(last+)-1 = { [“)”,S], [“)”,A] }GREATER = { [“)”,”)”], [“)”,S], [“)”,”(”] }8.S → AA | AS | bA → AS | a1) Язык: L(G)= {b} U {a+ {a*b+}* a*}2) Конечный автомат:S ->(a) S1,S1 ->(a) Z1,S ->(b) Z1,S ->(a) S,S ->(a) S2,S2 ->(b) S2,S2 ->(b) S,S2 ->(b) Z2,Z2 ->(a) Z2.S – начальное, Z1 и Z2 – конечные.3) ОПП:1. EQUAL = { (A,A), (A,S) }2. first+ = { (S,A), (S,b), (A,A), (A,a), (S,a) }LESS = { (A,A), (A,a), (A,b) }3. last+ = { (S,A), (S,S), (S,b), (A,S), (A,a), (S,a), (A,b) }(last+)-1 = { (A,S), (S,S), (b,S), (S,A), (a,A), (a,S), (b,A) }GREATER = { (S,A), (S,S), (a,A), (a,S), (b,A), (b,S), (S,a), (S,b), (a,a), (a,b), (b,a), (b,b) }9.
S → AS | bA → SA | a1) Язык: L(G)= { {a+b*}*ab U {b+a+}*b }2) Конечный автомат:S ->(b) Z,S ->(b) S1,S1 ->(b) S1,S1 ->(a) S2,S2 ->(b) S1,S2 ->(a) S2,S2 ->(b) Z,S ->(a) S3,S3 ->(a) S3,S3 ->(b) S4,S4 ->(a) S3,S4 ->(b) S4,S4 ->(ab) Z,S3 ->(b) Z.3) ОПП:1. EQUAL = { (A,S), (S,A) }2. first+ = { (S,A), (S,b), (A,S), (A,a), (S,S), (S,a), (A,A) }LESS = { (A,A), (A,b), (A,S), (A,a), (S,S), (S,a), (S,A) }3. last+ = { (S,S), (S,b), (A,A), (A,a), }(last+)-1 = { (S,S), (b,S), (A,A), (a,A) }GREATER = { (S,A), (b,A), (A,S), (a,S), (S,S), (S,a), (b,S), (b,a), (A,A), (A,b), (A,a), (a,A), (a,b),(a,a) }1.Сформировать автомат, допускающий цепочки в алфавите {0,1}, где нечетное числонулей и четное число единиц. Описать грамматику.1) Грамматика:S → ε | 0Z | Z0 | 11Z | 1Z1 | Z11 | 1K1K→0Z → ε | S00 | 0S0 | 00S | 11S | 1S1 | S11G → A | 1G1 | 0G0A → 0S1 | 1S02.3.
Сформировать автомат, допускающий цепочки в алфавите {0,1}, где количество нулей и единицнечетно, причем количество нулей и единиц произвольно (могут быть равны, а могут и нет).Описать грамматику.1) Язык: L(G)={1^(2n-1), 0^(2m-1)}+, n,m>=0.2) Конечный автомат:S ->(1) A,A ->(1) S,S ->(0) B,B ->(0) S,A ->(0) Z,Z ->(0) A,B ->(1) Z,Z ->(1) B.S – начальное, Z – заключительное.2) Грамматика:Z -> A0 | B1A -> Z0 | S1 | 1B -> Z1 | S0 | 0S -> A1 | B0.2.5 Сформировать автомат, допускающий цепочки в алфавите {0,1}, где количество нулей нечетно.Цепочка обязательно должна содержать хотя бы по одной букве из алфавита. Описать грамматику.- 1 вариант:1) Конечный автомат:S ->(0) A,A ->(0) S,A ->(1) Z,Z ->(1) Z,S ->(1) B,B ->(1) B,B ->(0) Z,Z ->(0) B.S – начальная, Z – заключительная.2) Грамматика:S -> 0A | 1BA -> 0S | 1ZB -> 1Z | 0BZ -> 1Z | 0B | e.- 2 вариант:1) Конечный автомат:S ->(0) A,S ->(1) B,A ->(00) A,B ->(1) B,A ->(01) B,A ->(1) Z,B ->(0) Z,Z ->(1) Z,Z ->(0) B.S – начальная, Z – заключительная.2) Грамматика:Z -> Z1 | A1 | B0A -> A00 | 0B -> B1 | A01| 1..
