конспекты занятий по курсу

 «Теория и реализация языков программирования»

 

 

 

 

 

^

=

_

 

 

Экзаменационные задачи по ТРЯП за 2009 г.

Пояснения:

1. Задачи обнародуются с разрешения авторов с целью создать больше возможностей подготовиться к успешной сдаче экзамена и освоения курса в целом, в том числе к правильному пониманию принятой записи условий задач.

2. В соответствие с общеинститутскими требованиями предлагаемые на экзамене задачи делятся на основные (сложилось так, что они нумеруются 1, 3 и 4) и дополнительные, для имеющих долги по заданию (№№ 5, 6)  и по лекционной контрольной (№ В1), соответственно.

 

                       Содержание

Подборка 1.

            Подборка 2.

                       Подборка 3.

Подборка 4.

            Подборка 5.

                       Подборка 6.

P.S. При использовании иного обозревателя чем IE возможно неправильное отображение части знаков. В этом случае вы можете просмотреть те же задачи в pdf.

 

 

 

Подборка 1

 

 

 

1. Заданы грамматика = {{S, A, B, C, D}; {a, b};

{S ® A ½ B ½ C;

® aA ½ a;

® bB ½ e;

® CA ½ CB;

® e}; S}

и МП-автомат P = {{q}; {a, b}; {S, A, B, a, b};

{D(q, e, S) = {(q, A),   (q, B),   (q, e)};

D(q, e, A) = {(q, aA),   (q, a)};

D(q, e, B) = {(q, bB),   (q, b)};

D(q, a, a) = {(q, e)};

D(q, b, b) = {(q, e)}

}; q; S}.

Верно ли, что:

а) МП-автомат P допускает язык L(G) опустошением магазина;

б) грамматика G однозначная?

 

3. Является ли язык, задаваемый регулярным выражением

(a | ε)b*(b | a) в алфавите {ab},

эквивалентным языку, распознаваемому конечным автоматом

M = {{PQRS}, {ab},

{D(P, a) = {Q},        D(P, b) = {R},

D(Q, a) = {S},         D(Q, b) = {R},

D(R, b) = {R},         D(R, a) = {S}},

P, {QRS}}?

 

4. Дан язык L = {} в алфавите {a, b}.

а) Является ли этот язык КС-языком?

б) Является ли дополнения языка L КС-языком?

в) Является ли язык L регулярным языком?

г) Является ли дополнение языка L регулярным языком?

 

5. Постройте однозначную КС-грамматику (однозначность нужно доказать) для языка {}.

Корректность построения должна быть доказана.

 

6. КС-грамматика называется левооднозначной, если каждое слово порождаемого ею языка имеет единственный левый вывод. Аналогично определяется правооднозначная грамматика. Можно ли построить пример левооднозначной, но не правооднозначной КС-грамматики.

 

В1. Верно ли, что для всякого ДКА имеется эквивалентный ДКА со всюду определенной функцией переходов?

 

 

 

Подборка 2

 

 

 

1. Заданы грамматика = {{S, A, B, C, D}; {a, b}; {® ½ B ½ ABC; ® aA ½ a; ® bB ½ e; ® BCA ½ CB; ® a}; S} и МП-автомат P = {{q}; {a, b}; {S, A, B, a, b}; {D(q, e, S) = {(q, A), (q, B), (q, e)}; D(q, e, A) = {(q, aA), (q, a)}; D(q, e, B) = {(q, bB), (q, b)}; D(q, a, a) = {(q, e)}; D(q, b, b) = {(q, e)}}; q; S}.

Верно ли, что:

а) МП-автомат P допускает язык L(G) опустошением магазина;

б) грамматика G однозначная?

 

3. Является ли язык, задаваемый регулярным выражением a*(| ε)ab* в алфавите {ab}, эквивалентным языку, распознаваемому конечным автоматом M = {{PQRS, NK}, {ab}, {D(P, a) = {R}, D(P, b) = {Q}, D(R, b) = {S}, D(R, a) = {R}, D(Q, a) = {N}, D(S, a) = {N}, D(S, b) = {K}, D(N, b) = {K}, D(K, b) = {K}}, P, {KRS}}?

 

4. Дан язык L = {} в алфавите {a, b}.

а) Является ли этот язык КС-языком?

б) Является ли дополнения языка L КС-языком?

в) Является ли язык L регулярным языком?

г) Является ли дополнение языка L регулярным языком?

 

5. Построить грамматику, порождающую язык . Корректность построения должна быть доказана.

 

6. Замкнуто ли множество КС-языков относительно обращения? (верно ли, что если L – КС-язык, то LR – тоже КС-язык.)

 

В1. Верно ли, что ДМП может иметь e-переходы?

 

 

 

Подборка 3

 

 

 

1. Заданы грамматика

= {{S, A, B, C, D}; {a, b}; {® ½ B ½ C; ® aA ½ e; ® bB ½ b; ® CA ½ CB; ® e}; S}

и МП-автомат

P = {{q}; {a, b}; {S, A, B, a, b}; {D(q, e, S) = {(q, A), (q, B), (q, e)}; D(q, e, A) = {(q, aA), (q, a)}; D(q, e, B) = {(q, bB), (q, b)}; D(q, a, a) = {(q, e)}; D(q, b, b) = {(q, e)}}; q; S}.

Верно ли, что:

а) МП-автомат P допускает язык L(G) опустошением магазина;

б) грамматика G однозначная?

 

3. Является ли язык, задаваемый регулярным выражением (1 | 0)*(11 | 01)0* в алфавите {0, 1}, эквивалентным языку, распознаваемому конечным автоматом = {{P, Q, R}, {0, 1}, {D(P, 0) = {Q}, D(P, 1) = {Q}, D(Q, 0) = {Q}, D(Q, 1) = {R}, D(R, 0) = {R}, D(R, 1) = {R}}, P, {R}}?

 

4. Дан язык L = {} в алфавите {a, b}.

а) Является ли этот язык КС-языком?

б) Является ли дополнения языка L КС-языком?

в) Является ли язык L регулярным языком?

г) Является ли дополнение языка L регулярным языком?

 

5. Построить КС-грамматику, порождающую язык . Корректность построения должна быть доказана.

 

6. Пусть A – магазинный автомат. Построить магазинный автомат B, допускающий все префиксы языка L(A), т. е. язык L(B) = {| xy Î L(A)}.

 

В1. Верно ли, что для всякого регулярного языка существует принимающий его НКА с единственным финальным состоянием?

 

 

 

Подборка 4

 

 

 

1. Заданы грамматика = {{S, A, B, C, D}; {a, b}; {® ½ B ½ ABC; ® aA ½ a; ® bB ½ e; ® CA ½ CB; ® a}; S} и МП-автомат P = {{q}; {a, b}; {S, A, B, a, b}; {D(q, e, S) = {(q, A), (q, B), (q, e)}; D(q, e, A) = {(q, aA), (q, a)}; D(q, e, B) = {(q, bB), (q, b)}; D(q, a, a) = {(q, e)}; D(q, b, b) = {(q, e)}}; q; S}.

Верно ли, что:

а) МП-автомат P допускает язык L(G) опустошением магазина;

б) грамматика G однозначная?

 

3. Является ли язык, задаваемый регулярным выражением (aa | ε)(bb)*(| b)* в алфавите {a, b}, эквивалентным языку, распознаваемому конечным автоматом = {{P, Q, R, S, N, K}, {a, b}, {D(P, a) = {Q}, D(P, b) = {S}, D(R, b) = {S}, D(R, a) = {N}, D(Q, a) = {R}, D(S, b) = {K}, D(K, a) = {N}, D(K, b) = {S}}, P, {Q, N, S}}?

 

4. Дан язык L = {0, 1}* \ {} в алфавите {0, 1}.

а) Является ли этот язык КС-языком?

б) Является ли дополнения языка L КС-языком?

в) Является ли язык L регулярным языком?

г) Является ли дополнение языка L регулярным языком?

 

5. Построить КС-грамматику, порождающую язык . Корректность построения должна быть доказана.

 

6. Замкнуто ли множество КС-языков относительно дополнения?

 

В1. Верно ли, что для всякого регулярного языка существует принимающий его ДКА с единственным финальным состоянием?

 

 

 

Подборка 5

 

 

 

1. Заданы грамматика = {{S, A, B, C, D}; {a, b}; {® ½ B ½ C; ® aA ½ a; ® bB ½ e; ® CCA ½ CB; ® e}; S} и МП-автомат P = {{q}; {a, b}; {S, A, B, a, b}; {D(q, e, S) = {(q, A), (q, B), (q, e)}; D(q, e, A) = {(q, aA), (q, a)}; D(q, e, B) = {(q, bB), (q, b)}; D(q, a, a) = {(q, e)}; D(q, b, b) = {(q, e)}}; q; S}.

Верно ли, что:

а) МП-автомат P допускает язык L(G) опустошением магазина;

б) грамматика G однозначная?

 

3. Является ли язык, задаваемый регулярным выражением (ab)*(| ε)(a* | b*) в алфавите {a, b}, эквивалентным языку, распознаваемому конечным автоматом = {{P, Q, R, S, N}, {a, b}, {D(P, a) = {Q}, D(P, b) = {R}, D(R, b) = {R}, D(R, a) = {S}, D(Q, a) = {S}, D(Q, b) = {N}, D(S, a) = {S}, D(N, a) = {Q}, D(N, b) = {N}}, P, {Q, R, N, S}}?

 

4. Дан язык L = {0, 1}* \ {} в алфавите {0, 1}.

а) Является ли этот язык КС-языком?

б) Является ли дополнения языка L КС-языком?

в) Является ли язык L регулярным языком?

г) Является ли дополнение языка L регулярным языком?

 

5. Построить магазинный автомат, допускающий язык .

Корректность построения должна быть доказана.

 

6. Является ли язык  контекстно-свободным?

 

В1. Верно ли, что для всякого ДКА существует эквивалентный НКА с единственным заключительным состоянием?

 

 

 

Подборка 6

 

 

 

1. Заданы грамматика = {{S, A, B, C, D}; {a, b}; {® ½ B ½ ABC; ® aA ½ a; ® bB ½ e; ® CA ½ ACB; ® a}; S} и МП-автомат P = {{q}; {a, b}; {S, A, B, a, b}; {D(q, e, S) = {(q, A), (q, B), (q, e)}; D(q, e, A) = {(q, aA), (q, a)}; D(q, e, B) = {(q, bB), (q, b)}; D(q, a, a) = {(q, e)}; D(q, b, b) = {(q, e)}}; q; S}.

Верно ли, что:

а) МП-автомат P допускает язык L(G) опустошением магазина;

б) грамматика G однозначная?

 

3. Является ли язык, задаваемый регулярным выражением (0* | ε)(101 | 11)* в алфавите {0, 1}, эквивалентным языку, распознаваемому конечным автоматом = {{P, Q, R}, {0, 1}, {D(P, 0) = {P}, D(P, 1) = {Q}, D(Q, 0) = {R}, D(Q, 1) = {P}, D(R, 1) = {P}}, P, {P}}?

 

4. Дан язык L = {0, 1}* \ {} в алфавите {0, 1}.

а) Является ли этот язык КС-языком?

б) Является ли дополнения языка L КС-языком?

в) Является ли язык L регулярным языком?

г) Является ли дополнение языка L регулярным языком?

 

5. Построить магазинный автомат, допускающий язык .

 

6. Является ли язык  контекстно-свободным?

 

В1. Верно ли, что НКА может НЕ иметь  e-переходов?

 

 

 

^

=

_

 

 

 

 

 

Используются технологии uCoz