Название: Информатика (формальные языки и грамматики) - Методическая разработка(С.Е. Рояк)

Жанр: Информатика

Просмотров: 1363


Приложение 2 алгоритмические системы.

1. Что означает свойство  алгоритма быть детерминированным?

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

b)в каждый фиксированный момент времени алгоритм делает элементарное действие;

c)последовательность действий, соответствующая алгоритму, всегда выполняется одинаково на одних и тех же данных;

d)последовательность инструкций, представляющая алгоритм, имеет конечные размеры.

2. В списке формальных систем:

a)исчисление высказывания;

b)рекурсивные функции;

c)формальные грамматики;

d)машины Тьюринга;

e)нормальные алгоритмы Маркова;

h)алгоритмический язык.

формальная арифметика;

алгоритмическими системами являются________________

3. Т = <А,Q,q0,D,F> – машина Тьюринга. Определите словами смысл заданных объектов: A, Q, q0, D, F.

4. Определите теоретико-множественное отношение между данными формальными системами: машины Тьюринга, частично рекурсивные функции, нормальные алгоритмы Маркова

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

b)эквивалентность;

c)строгая вложенность в обратном порядке;

d)нестрогая вложенность.

5. Машина Тьюринга – это ________________

a) математическая абстракция;

b) устройство переработки информации,

c) способ записи алгоритма;

d) электронная вычислительная машина;

e) алгоритмическая  система

6. Данная запись q0a®q1bR означает:_______________________________

7. В машине Тьюринга слово bbaaq1baa означает______________________

8. Дано: S1=11101, S2=11001, S3=10001, S4=10101.

Машина Тьюринга <{0,1},{q0,q1,q2},q1,D,{q0}>             D:q10®q10R

            q11®q20R

            q21®q10R

применима к словам ________________  q20®q01S

9. Машина имеет минимальное число команд и применима к любому слову в алфавите {1,0}. Это машина – Т =<A,Q,q0,D,F>, где

A _______Q________ q0 ______ D _________________________________________ F ______

10. Дана машина Тьюринга

 

    A

Q

0

1

®

q1

q11L

q21R

 

q2

q00L

q10R

 

q0

 

 

 

 

Начальная конфигурация q11010. Конечная конфигурация____________

11. Дано

T1=

    A

Q

0

1

®

q1

q21R

q20L

 

q2

q01S

q11L

 

q0

 

 

 

T2=

    A

Q

0

1

®

q1

q11L

q21R

 

q2

q00L

q10R

 

q0

 

 

 

T3=

    A

Q

0

1

®

q1

q20L

q10R

 

q2

q21L

q00R

 

q0

 

 

 

T4=

    A

Q

0

1

®

q1

q01S

q20R

 

q2

q10L

q21S

 

q0

 

 

Машина  ___________ не применима к слову 10111.

12. Для функции f(x)=2x машина Тьюринга Т = <A,Q,q0,D,F>

A _______Q________ q0 ______ D _________________________________________ F ______

13. Даны следующие машины:

T1=

    A

Q

0

1

®

q1

q21L

q11R

 

q2

q00R

q21L

 

q0

 

 

 

T3=

    A

Q

0

1

®

q1

q21R

q10R

 

q2

q20L

q31L

 

q3

q00R

q31R

 

q0

 

 

 

T2=

    A

Q

0

1

®

q1

q20R

q11R

 

q2

q10L

q00R

 

q0

 

 

 

T4=

A

Q

0

1

®

q1

q00S

q21R

 

q2

q31L

q10R

 

q3

q11L

q31R

 

q0

 

 

 Функция f(x,y)=x+y+1 вычисляется машиной______________

14. Аналитический вид функции (см. задание13) вычисляемой машиной Т2____

15. Даны функции: f1(x,y)=[1/(2–x)] , f2(x)=[1/(3–x)], f3(x)=3–x; Машина

 

    A

Q

0

1

#

®

q1

q00S

q21R

 

 

q2

 

q31R

q4#L

 

q3

 

q31S

q5#L

 

q4

 

q00S

 

 

q5

 

q0#R

 

 

q0

 

 

 

0 – 0

1 – 1

11 – 2

111 – 3

1111 –4

и т. д.

 

правильно вычисляет функцию_________

 

16. Какие из следующих утверждений истинны  ?

 

если функция F построена с помощью оператора минимизации из примитивно-рекурсивных функций, то F может быть как примитивно-рекурсивной, так и частично-рекурсивной функцией;

понятие примитивно-рекурсивной функции эквивалентно по определению алгоритма;

3)  если функция частично-рекурсивная, то она и примитивно-рекурсивная;

4) если функция примитивно-рекурсивная, то она и частично-рекурсивная;

17. Схема примитивной рекурсии для f(x),от трёх переменных:

                                   f(x1,x2,0)        =__________________

            f(x1, x2, y+ 1)             =__________________, y > 0.

18. Дано f(x1,x2,x3),=x1/x2x3,  g1(x,y)=xy,  g2(x, y)=Sg(3x+y),  g3(x,y)=(xy)/(x+1). Функция F(x,y)=S(f; g1, g2, g3)=__ ___________ (записать аналитический вид).

19. Из перечисленных функций: ;;  ; f4(x1) = (2x+1)! по схеме примитивной рекурсии, примененной к функциям: g(x)=1; h(x1,x2,x3) = 2x3x1(2x1+1)

вычисляется____________________

20. Дано :

g(x)=0, h(x,y,z)=x+z;

g(x)=0, h(x,y,z)=xy;

g(x)=0, h(x,y,z)=x+y.

Функция f(x,y)=x(y1) вычисляется по схеме примитивной рекурсии с помощью функций __________ по переменной y.

21. Результат применения М-оператора к функции

f(x)=[x/3]–[x/4] по переменной х:

g(x)= Mx(f(y)=x)                                                                                          f(y)=x

x

g(x)

0

0

1

3

2

15

3

27

 

 

x

y

0

{0, 1, 2,4,5,8}

1

{3, 6, 7,9,10,11,12,13,14,16,17,20}

2

{15,18,19,21,22,23,24,25,26,28,29,32}

3

{27, 30,31,33,34,35,36,37,38,40,41...

 

при х = 5 значение функции g(x)=______________________________

22. Аналитический вид функции (см. задание 21) g(x)=Mx(f(y)=x) _______________________________________________________________

23. Дано:

f(x) =  x2;

f(x) =  x+2;

f(x) =  x–2;

f(x) = 2x+1;

f(x) = 2x1;

f(x) = 2x–1.

Функция f(x)=((x+1)*sg(x))/2 вычисляется с помощью оператора минимизации, который применяется к функции f(x)= ______________ по переменной x.

24. Если частично рекурсивная функция f(x)=1/(x+1), то примитивно рекурсив-ная функция, к которой однократно применена операция минимизации _______

Возможные варианты ответа

f(x)  = (1–x)/x;

f(x)  = (1x)/x;

f(x)= [(1x)/(x +1)];

такой функции не существует.

25. Аналитический вид функции ______________________

26. Полученная функция (см. задание 25) является:

общерекурсивной;

частично рекурсивной;

примитивно  рекурсивной.

27. Дана функция f(1(01)k0) = 0(01)k1, к³1 и подстановки

            ___е ®*         ___*1®0*      ___*0®1       ___*01® 01*.

 Пронумеруйте подстановки так,  чтобы они образовали  алгоритм  Маркова, правильно вычисляющий данную функцию.

28. Даны функции:

1) f((01)n)=0n1n         2) f(1(01)n0)=0n+11n+1, n³1            3) f(1(10)n0) = 10 n1n0, n³1.

Нормальный алгоритм Маркова:

1. *00 ® *00

2. *11 ® *11

3. *01 ® 01*

4. 1* ® +1

5. 10+ ® +01

6.  +01 ® 01*

7. 1+  ® +1

8. + ® e

9. e ® *

правильно вычисляет  функцию________________________

29. Графическая схема алгоритма (см. задание 28):

30. Дана функция f(x,y)=x+yz. Нормальный  алгоритм  Маркова, правильно вычисляющий данную функцию___________________________

31. Из данных нормальных алгоритмов Маркова выберите один, правильно вычисляющий функцию: f(x,y)=x5+y______________   

1) 1.     1+1      ® 1

    2.     11       ®

    3.     11       ® 1

    4.                            ® e                2) 1. 11           ®

2. 11   ® 1

3. 1+1  ® 1

4.         1         ® 1              3) 1.     11      ®

2.         11       ® 1

3.         1         ® 11

4.                                ® e

5.         1+1      ® 1

32. Дан нормальный алгоритм Маркова :

1. 1+1 ® 1

2. 1–1 ®

3. –1 ® –1

4. 1– ® 11

аналитический вид функции, вычисляемой этим алгоритмом

33. На вход алгоритма (см. задание 32) подаётся слово 111111–11+111.

 Пошаговое применение алгоритма к этому слову  ______________________

 

 

 

Приложение 1

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

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

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

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

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

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

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

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

алфавит;

аксиома;

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

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

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

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

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={wbw