Промежуточный тест по теме "Формальные грамматики и языки"

Страницы работы

17 страниц (Word-файл)

Фрагмент текста работы

Приложение 1

ПРОМЕЖУТОЧНЫЙ ТЕСТ ПО ТЕМЕ

 "ФОРМАЛЬНЫЕ ГРАММАТИКИ И ЯЗЫКИ".

1. Даны следующие понятия:


a)  упорядоченное множество правил подстановки;

b)  конечное множество входных символов;

c)  конечное множество правил вывода;

d)  множество вспомогательных символов;

e)  множество нетерминальных символов;

f)   алфавит;

g)  аксиома;

h)  начальное состояние;

i)   множество состояний;

j)   функции перехода.


Формальную грамматику определяют следующие ____________________

2. Дана грамматика: G=<{a, b}, {S, A, B}, S, {S®e|AB, A®aA|e, B®e|bB}> и цепочки:            1) aaaAbbbB, 2) aabab,                    3) aaaaaa,        4) bbbbbbbbb,                  5) aAB.
Цепочки, принадлежащие языку определяемому данной грамматикой ______________

3. Язык, определяемый формальной грамматикой – это множество _______________, построенных из ______________________________ и выводимых из ______________                                  (Вставьте пропущенные слова).

4. Даны грамматики :

G1 = <{a, b}, {S}, S, {S®e|aS|bS}>

G2 = <{a, b}, {S}, S, {S®ab|aSb}>

G3 = <{a, b}, {S, A, B}, A, {A®e|SB, S®aS|e, B®e|bB}>

G4 = <{a, b}, {S, A}, S, {S®e|aSb|aA, A®aA|e}>

Язык L={anbn|n>1} определяется грамматикой__________

5. Дана грамматика G = <{0,1}, {S, A, B, D, C}, S, {S®0A0|1B0|1D1|0C1,                                 A®01B|B1, C1®A10|0A0, 1B®0C|C11, D®A0|1C11|0D0|B00|11|e}>

ей соответствует язык L={____________________}

6. Дана грамматика G=<{a, c, b}, {S, A, B, C}, S, {S®aSbB|bSaA, A®aA|aS|B, B®bB|A, C®a|b|c}>,      ей соответствует язык L={____________________}

7. Дан язык L={wbwR|wÎ{a,c}*}. Грамматика для этого языка G=<T,N,S,P>, где

T_____ N ________ S ___ P _______________________________________________

8. Дана грамматика G = <{a, b}, {S, A, B}, S, {S®ABS|AS|a, B®SBB|b, A®a}>
вывод цепочки aaabba ______________________________________________________

9. Для цепочки (см. задание 8) можно построить _____ выводов. ( a)1     b)2             c)>2 )

10. Канонический вывод этой цепочки (см. задание 8 ) ________________________

11. Инвариантом для этих выводов (см. задания 8,9,10) является ________________

12. Синтаксическое дерево вывода цепочки aabbaa для грамматики (см. задание 8)

Таких деревьев для данной цепочки (см. задание 8) можно построить __ (1,2,3,...)

13. Язык называется неоднозначным, если ___________________________________

14. Грамматика называется неоднозначной, если ...

1)  ... она порождает неоднозначные цепочки;

2)  ... существует цепочка, которая имеет несколько синтаксических деревьев вывода;

3)  ... существует цепочка, которая имеет множество выводов;

4)  ... существует цепочка, которая имеет несколько канонических выводов.

15. Даны грамматики :

G1=<{a, b}, {S, B}, S, {S®aSB|e, B®b}>

G2=<{a, b}, {S, A}, S, {S®aS|Sb|ab}>

G3=<{a, b}, {S, A, B, C}, S, {S®AB|AC, B®SC, A®a, C®b}

G4=<{a, b}, {S, B}, S, {S®aSB|e, B®bB|b}>

G5=<{a, b}, {S}, S, { S®aSb|ab}>

                                эквивалентными являются ___________

16. Неоднозначными грамматиками (см. задание 15) являются __________

17. Язык, определяемый этой грамматикой (см. Задание 16) является _____________

          a) однозначным   b) неоднозначным

18. КС-грамматика порождает дерево вывода:  

   

 постройте канонический вывод соответствующей цепочки_____________________________

19. Если в дереве вывода (см. задание 18) использованы все правила, то ему соответствует грамматика G=<T, N, S, P>

T_____ N ________ S ___ P ___________

20. Даны грамматики

G1=<{a, b, c}, {S, C}, S, {S®aSb|abcC, cC®ccC|c}>

G2=<{0, 1}, {S, C, B}, S, {S®B0|B|0, B®B1|C0, C®C1|1}>

G3=<{a, b}, {I, S, B}, I, {I®aB|bB|a|b, B®SB, S®a|b}>

G4=<{3, 4}, {S, 0, 1, 2}, S, {S®S312|302, 0®21, 12®4, 2®e}>

G5=<{0, 1}, {2}, 2, {2®02|12|0|1}>

G6=<{a, b}, {I, S, B}, I, {I®aaB|bbB|aa|bb, B®aaB|bbB|aa|bb}>

G7=<{a, b}, {S, C, B}, S, {S®aCa, C®aCBa|b, aB®Ba, bB®bb}>

G8=<{a, c}, {S, C, B}, S, {S®BC|B|C, B®aB|a, C®cC|c}>

G9=<{a, b}, {S}, S, {S®aS|Sb|a|b}>

                                автоматными являются ____________

21. Для грамматик (см, задание 20) КС-грамматиками являются _________

22. Для грамматик (см. задание 20) НС-грамматиками являются ________

23. Грамматики _______________ (см. задание 20) А-язык.

24. Грамматики _______________ (см. задание 20) КС-язык.

25. Грамматики _______________ (см. задание 20) НС-язык.

26. Даны языки :L1={w½wÎ{a, b, c}*}, L2={ambmcnan|m>n, m,n³1}, L3={(aв)m|m³1}, L4={ap(ba)ncm|n,m,p³1}, L5={ambnanbm|n,m³1}, L6={(aв)m(aв)m|m³1}, L7=L1°L6
 Язык L5={0m1n0n1m|n,m³1} эквивалентен языку _______________

27. Для языков (см. задание 26) А-языки __________________

28. Для языков (см. задание 26) КС-языки __________________

29. Для  языков(см. задание 26) НС-языки __________________

30. Дан язык L={anbnamdm|n,m³1}. Он может быть получен операцией ________________над языками L1={____________} и L2={____________}

Похожие материалы

Информация о работе

Предмет:
Информатика
Тип:
Тестовые вопросы и задания
Размер файла:
393 Kb
Скачали:
0