|
конспекты
занятий по курсу «Теория и
реализация языков программирования» |
|
|||
|
|
||||
|
Экзаменационные задачи по ТРЯП за Пояснения: 1. Задачи обнародуются
с разрешения авторов с целью создать больше возможностей подготовиться к
успешной сдаче экзамена и освоения курса в целом, в том числе к правильному
пониманию принятой записи условий задач. 2. В соответствие
с общеинститутскими требованиями предлагаемые на экзамене задачи делятся на
основные (сложилось так, что они нумеруются 1, 3 и 4) и дополнительные, для
имеющих долги по заданию (№№ 5, 6) и
по лекционной контрольной (№ В1), соответственно. Содержание P.S. При использовании иного обозревателя чем IE возможно неправильное отображение части знаков. В этом
случае вы можете просмотреть те же задачи в pdf. |
|
|||
|
|
||||
|
1. Заданы грамматика G = {{S, A, B, C, D}; {a, b}; {S ® A ½ B ½ C; A ® aA ½ a; B ® bB ½ e; C ® CA ½ CB; D ® 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) в алфавите {a, b}, эквивалентным языку, распознаваемому конечным
автоматом M = {{P, Q, R, S}, {a, b}, {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, {Q, R, S}}? 4. Дан язык L = { а) Является ли этот язык КС-языком? б) Является ли дополнения языка L КС-языком? в) Является ли язык L регулярным языком? г) Является ли дополнение языка L регулярным языком? 5. Постройте однозначную КС-грамматику
(однозначность нужно доказать) для языка { Корректность построения должна быть доказана. 6. КС-грамматика называется левооднозначной, если
каждое слово порождаемого ею языка имеет единственный левый вывод. Аналогично
определяется правооднозначная грамматика. Можно ли построить пример
левооднозначной, но не правооднозначной КС-грамматики. В1. Верно ли, что
для всякого ДКА имеется эквивалентный ДКА со всюду определенной функцией
переходов? |
|
|||
|
|
||||
|
1. Заданы грамматика G = {{S, A, B, C, D}; {a, b}; {S ® A ½ B ½ ABC; A ® aA ½ a; B ® bB ½ e; C ® BCA ½ CB; D ® 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*(b | ε)ab* в алфавите {a, b},
эквивалентным языку, распознаваемому конечным автоматом M = {{P, Q, R, S, N, K}, {a, b}, {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, {K, R, S}}? 4. Дан язык L = { а) Является ли этот язык КС-языком? б) Является ли дополнения языка L КС-языком? в) Является ли язык L регулярным языком? г) Является ли дополнение языка L регулярным языком? 5. Построить грамматику, порождающую язык 6. Замкнуто ли множество КС-языков относительно
обращения? (верно ли, что если L –
КС-язык, то LR – тоже КС-язык.) В1. Верно ли, что
ДМП может иметь e-переходы? |
|
|||
|
|
||||
|
1. Заданы грамматика G = {{S, A, B, C, D}; {a, b}; {S ® A ½ B ½ C; A ® aA ½ e; B ® bB ½ b; C ® CA ½ CB; D ® 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}, эквивалентным языку, распознаваемому конечным
автоматом M = {{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 = { а) Является ли этот язык КС-языком? б) Является ли дополнения языка L КС-языком? в) Является ли язык L регулярным языком? г) Является ли дополнение языка L регулярным языком? 5. Построить КС-грамматику, порождающую язык 6. Пусть A –
магазинный автомат. Построить магазинный автомат B, допускающий все префиксы языка L(A), т. е.
язык L(B) = {x | xy Î L(A)}. В1. Верно ли, что для всякого регулярного
языка существует принимающий его НКА с единственным финальным состоянием? |
|
|||
|
|
||||
|
1. Заданы грамматика G = {{S, A, B, C, D}; {a, b}; {S ® A ½ B ½ ABC; A ® aA ½ a; B ® bB ½ e; C ® CA ½ CB; D ® 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)*(a | b)* в
алфавите {a, b}, эквивалентным языку, распознаваемому конечным
автоматом M = {{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}* \ { а) Является ли этот язык КС-языком? б) Является ли дополнения языка L КС-языком? в) Является ли язык L регулярным языком? г) Является ли дополнение языка L регулярным языком? 5. Построить КС-грамматику, порождающую язык 6. Замкнуто ли множество КС-языков относительно
дополнения? В1. Верно ли, что для всякого
регулярного языка существует принимающий его ДКА с единственным финальным
состоянием? |
|
|||
|
|
||||
|
1. Заданы грамматика G = {{S, A, B, C, D}; {a, b}; {S ® A ½ B ½ C; A ® aA ½ a; B ® bB ½ e; C ® CCA ½ CB; D ® 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)*(b | ε)(a* | b*) в алфавите {a, b},
эквивалентным языку, распознаваемому конечным автоматом M = {{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}* \ { а) Является ли этот язык КС-языком? б) Является ли дополнения языка L КС-языком? в) Является ли язык L регулярным
языком? г) Является ли дополнение языка L регулярным языком? 5. Построить магазинный автомат, допускающий язык Корректность построения должна быть доказана. 6. Является ли язык В1. Верно ли, что для всякого ДКА
существует эквивалентный НКА с единственным заключительным состоянием? |
|
|||
|
|
||||
|
1. Заданы грамматика G = {{S, A, B, C, D}; {a, b}; {S ® A ½ B ½ ABC; A ® aA ½ a; B ® bB ½ e; C ® CA ½ ACB; D ® 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}, эквивалентным языку, распознаваемому конечным
автоматом M = {{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}* \ { а) Является ли этот язык КС-языком? б) Является ли дополнения языка L КС-языком? в) Является ли язык L регулярным языком? г) Является ли дополнение языка L регулярным языком? 5. Построить магазинный автомат, допускающий язык 6. Является ли язык В1. Верно ли, что НКА может НЕ иметь e-переходов? |
|
|||
|
|
||||
|
|
|
|||