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

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

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. Даны грамматики :

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

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

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

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

Язык L={aⁿbⁿ|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={wbw^R|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. Даны грамматики :

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

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

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

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

G₅=<{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. Даны грамматики

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

26. Даны языки :L₁={w½wÎ{a, b, c}^*}, L₂={a^mb^mcⁿaⁿ|m>n, m,n³1}, L₃={(aв)^m|m³1}, L₄={a^p(ba)ⁿc^m|n,m,p³1}, L₅={a^mbⁿaⁿb^m|n,m³1}, L₆={(aв)^m(aв)^m|m³1}, L₇=L₁°L₆
 Язык L₅={0^m1ⁿ0ⁿ1^m|n,m³1} эквивалентен языку _______________

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

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

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

30. Дан язык L={aⁿbⁿa^md^m|n,m³1}. Он может быть получен операцией ________________над языками L₁={____________} и L₂={____________}