Лабораторная работа № 2

Нормальные алгорифмы Маркова

В каждом варианте лабораторной работы по 5 заданий из приведенного ниже списка.

Задание 1

Задание 2

Задание 3

Задание 4

Задание 5

Вариант 1

1

20

40

41

49

Вариант 2

2

21

39

42

50

Вариант 3

3

22

38

43

51

Вариант 4

4

23

37

44

52

Вариант 5

5

24

36

45

53

Вариант 6

6

25

35

46

54

Вариант 7

7

26

34

47

55

Вариант 8

8

16

33

48

49

Вариант 9

9

17

32

48

50

Вариант 10

10

18

31

48

51

Вариант 11

11

19

30

46

52

Вариант 12

12

20

40

45

53

Вариант 13

13

21

39

44

54

Вариант 14

14

22

30

43

55

Вариант 15

15

23

40

42

53

Вариант 16

1

24

39

41

51

Вариант 17

2

25

38

41

49

Вариант 18

3

26

37

42

50

Вариант 19

4

27

36

43

52

Вариант 20

5

28

35

44

54

Вариант 21

6

29

34

45

55

Вариант 22

7

16

33

46

53

Вариант 23

8

17

32

47

52

Вариант 24

9

18

31

48

51

Вариант 25

10

19

30

45

50

1

Каков результат воздействия на слово P=nnnnnnnnnn алгорифма Маркова:

Z = | nnn → abc | ca → ac | ba → nnnn |

Представьте последовательную трассировку преобразования исходного слова с указанием номеров выполняемых команд схемы алгорифма.

2

Каков результат воздействия на слово P=nnnnnnnnnn алгорифма Маркова:

Z = | nnn → abc | ca → ac | ba →. nnnn |

Представьте последовательную трассировку преобразования исходного слова с указанием номеров выполняемых команд схемы алгорифма.

3

Каков результат воздействия на слово P=twentyonemoney алгорифма Маркова:

Z = | en → ne | ne → t | wt → a | mo → ne | ty →. w|

Представьте последовательную трассировку преобразования исходного слова с указанием номеров выполняемых команд схемы алгорифма.

4

Каков результат воздействия на слово P=twentyonemoney алгорифма Маркова:

Z = | en → ne | ne → t | wt →. a | mo → ne | ty → w |

Представьте последовательную трассировку преобразования исходного слова с указанием номеров выполняемых команд схемы алгорифма.

5

Каков результат воздействия на слово P=abcddacba алгорифма Маркова:

Z = | ab → dc | ac → dc | cb → d | aa → Л | dd → ba |

Представьте последовательную трассировку преобразования исходного слова с указанием номеров выполняемых команд схемы алгорифма.

6

Каков результат воздействия на слово P=ddacbabc алгорифма Маркова:

Z = | ab → ca | ac → dc | bc → cb | cc → Л | dd → ba |

Представьте последовательную трассировку преобразования исходного слова с указанием номеров выполняемых команд схемы алгорифма.

7

Каков результат воздействия на слово P=cbabcdac алгорифма Маркова:

Z = | ab → ca | ac → dc| bc → cb | cc →. Л | dd → ba |

Представьте последовательную трассировку преобразования исходного слова с указанием номеров выполняемых команд схемы алгорифма.

8

Каков результат воздействия на слово P=dacabbca алгорифма Маркова:

Z = | ab → ca | ac → dc | bc → cb | cc → Л | dd → ba | bd →. db |

Представьте последовательную трассировку преобразования исходного слова с указанием номеров выполняемых команд схемы алгорифма.

9

Определите результат действия на слово P = bnbnabnb нормального алгорифма со схемой 

       Z = | an → na | bnb → an | nan →. bnb |

Проведите трассировку алгорифма, т. е. опишите, как будет изменяться строка P после каждого шага алгорифма.

10

Определите результат действия на слово P = n111111n111 нормального алгорифма со схемой

        Z = | nh → gh | 111 → hgd | gh → 1111 |. Проведите трассировку алгорифма, т. е. опишите, как будет изменяться строка P после каждого шага алгорифма.

11

Определите результат действия на слово P = zzzzyxyzzzz нормального алгорифма со схемой

        Z = | xx → y | yy →. z | zz → x | xy → t |

Проведите трассировку алгорифма, т. е. опишите, как будет изменяться строка P после каждого шага алгорифма.

12

Определите результат действия на слово P = zzzzyxyzzzz нормального алгорифма со схемой

        Z = | xx → y | yy → z | zz → x | xy → t |

Проведите трассировку алгорифма, т. е. опишите, как будет изменяться строка P после каждого шага алгорифма.

13

Определите результат действия на слово P = zzzzyxyzzzz нормального алгорифма со схемой

        Z = | xx → y | yy → z | xy → t | zz → x |

Проведите трассировку алгорифма, т. е. опишите, как будет изменяться строка P после каждого шага алгорифма.

14

Определите результат действия на слово P = abbba нормального алгорифма, заданного в алфавите А={a, b}, со схемой 

               Z = | aab → a | b → ab | aa → b |

Проведите трассировку алгорифма, т. е. опишите, как будет изменяться строка P после каждого шага алгорифма.

15

Определите результат действия на слово P = abba нормального алгорифма, заданного в алфавите А={a, b}, со схемой 

               Z = | aab → a | b → ab | a →. ba |

Проведите трассировку алгорифма, т. е. опишите, как будет изменяться строка P после каждого шага алгорифма.

16

Разработайте алгорифм Маркова, для вычисления функции f(x)=x*210+110, где x задано в двоичной системе счисления. Ответ так же должен быть получен в двоичной системе счисления. Запишите алгорифм дважды: в полной и в сокращенной форме.

17

Разработайте алгорифм Маркова, для вычисления функции f(x)=x*410+210, где x задано в двоичной системе счисления. Ответ так же должен быть получен в двоичной системе счисления. Запишите алгорифм дважды: в полной и в сокращенной форме.

18

Разработайте алгорифа Маркова, для вычисления функции f(x)=x*810+310, где x задано в восьмеричной системе счисления. Ответ так же должен быть получен в восьмеричной системе счисления. Запишите алгорифм дважды: в полной и в сокращенной форме.

19

Разработайте алгорифм Маркова, для вычисления функции f(x)=x*1610+310, где x задано в четверичной системе счисления. Ответ так же должен быть получен в четверичной системе счисления. Запишите алгорифм дважды: в полной и в сокращенной форме.

20

Разработайте алгорифа Маркова, для вычисления функции f(x)=x*2510+510, где x задано в пятеричной системе счисления. Ответ так же должен быть получен в пятеричной системе счисления. Запишите алгорифм дважды: в полной и в сокращенной форме.

21

Разработайте алгорифа Маркова, для вычисления функции f(x)=x*6410+1210, где x задано в двоичной системе счисления. Ответ так же должен быть получен в двоичной системе счисления. Запишите алгорифм дважды: в полной и в сокращенной форме.

22

Разработайте алгорифа Маркова, для вычисления функции f(x)=x*2510+710, где x задано в пятеричной системе счисления. Ответ так же должен быть получен в пятеричной системе счисления. Запишите алгорифм дважды: в полной и в сокращенной форме.

23

Разработайте алгорифм Маркова, для вычисления функции f(x)=x*4910+1110, где x задано в семеричной системе счисления. Ответ так же должен быть получен в семеричной системе счисления. Запишите алгорифм дважды: в полной и в сокращенной форме.

24

Разработайте алгорифм Маркова, для вычисления функции f(x)=x*910+510, где x задано в троичной системе счисления. Ответ так же должен быть получен в троичной системе счисления. Запишите алгорифм дважды: в полной и в сокращенной форме.

25

Разработайте алгорифм Маркова, для вычисления функции f(x)=x*3610+710, где x задано в шестеричной системе счисления. Ответ так же должен быть получен в шестеричной системе счисления. Запишите алгорифм дважды: в полной и в сокращенной форме.

26

Дано число X в двоичной системе счисления. Напишите нормальный алгорифм Маркова для функции F(X), проверяющей четность числа X. F(X) = 1, если число X четное, и F(X) = 0, если число X нечетное. Запишите алгорифм дважды: в полной и в сокращенной форме.

27

Дана строка символов, содержащая одно число X в семеричной системе счисления. Напишите нормальный алгорифм Маркова для вычисления функции Y(X) = X mod 4910. Ответ так же должен быть получен в семеричной системе счисления. Запишите алгорифм дважды: в полной и в сокращенной форме.

28

Дана строка символов, содержащая одно число X в шестеричной системе счисления. Напишите нормальный алгорифм Маркова для вычисления функции Y(X) = X mod 610. Ответ так же должен быть получен в шестеричной системе счисления. Запишите алгорифм дважды: в полной и в сокращенной форме.

29

Дана строка символов, содержащая одно число X в пятеричной системе счисления. Напишите нормальный алгорифм Маркова для вычисления функции Y(X) = X mod 12510. Ответ так же должен быть получен в пятеричной системе счисления. Запишите алгорифм дважды: в полной и в сокращенной форме.

30

Написать алгорифм Маркова для вычисления функции f(x)=x-910, где x задано в троичной системе счисления и не имеет незначащих нулей. Ответ так же должен быть получен в троичной системе счисления. Показать правильность его работы для x=100, x=211, x=1001. Ведущие нули в результате нужно удалить.

31

Написать алгорифм Маркова для вычисления функции f(x)=x–510, где x задано в пятеричной системе счисления и может иметь незначащие нули. Ответ так же должен быть получен в пятеричной системе счисления. Показать правильность его работы для x=10, x=21, x=002001. Ведущие нули в результате нужно удалить.

32

Написать алгорифм Маркова для вычисления функции f(x)=x–410, где x задано в семеричной системе счисления и не имеет незначащих нулей. Ответ так же должен быть получен в семеричной системе счисления. Показать правильность его работы для x=4, x=21, x=1003. Ведущие нули в результате нужно удалить.

33

Написать алгорифм Маркова для вычисления функции f(x)=x–510, где x задано в шестеричной системе счисления и может содержать незначащие нули. Ответ так же должен быть получен в шестеричной системе счисления. Показать правильность его работы для x=100, x=5, x=0110. Ведущие нули в результате нужно удалить.

34

Написать алгорифм Маркова для вычисления функции f(x)=x–1210, где x задано в шестеричной системе счисления и не содержит незначащих нулей. Ответ так же должен быть получен в шестеричной системе счисления. Показать правильность его работы для x=1000, x=20, x=101. Ведущие нули в результате нужно удалить.

35

Написать алгорифм Маркова для вычисления функции f(x)=x–610, где x задано в троичной системе счисления и не содержит незначащих нулей. Ответ так же должен быть получен в троичной системе счисления. Показать правильность его работы для x=1000, x=20, x=101. Ведущие нули в результате нужно удалить.

36

Написать алгорифм Маркова для вычисления функции f(x)=x–310, где x задано в четверичной системе счисления и может содержать незначащие нули. Ответ так же должен быть получен в четверичной системе счисления. Показать правильность его работы для x=100, x=3, x=0110. Ведущие нули в результате нужно удалить.

37

Написать алгорифм Маркова для вычисления функции f(x)=x–210, где x задано в пятеричной системе счисления и не имеет незначащих нулей. Ответ так же должен быть получен в пятеричной системе счисления. Показать правильность его работы для x=2, x=21, x=100. Ведущие нули в результате нужно удалить.

38

Написать алгорифм Маркова для вычисления функции f(x)=x–610, где x задано в восьмеричной системе счисления и не содержит незначащих нулей. Ответ так же должен быть получен в восьмеричной системе счисления. Показать правильность его работы для x=1000, x=6, x=10101. Ведущие нули в результате нужно удалить.

39

Написать алгорифм Маркова для вычисления функции f(x)=x–510, где x задано в девятеричной системе счисления и может содержать незначащие нули. Ответ так же должен быть получен в девятеричной системе счисления. Показать правильность его работы для x=100, x=5, x=0200. Ведущие нули в результате нужно удалить.

40

Написать алгорифм Маркова для вычисления функции f(x)=x–3010, где x задано в десятичной системе счисления и может содержать незначащие нули. Ответ так же должен быть получен в десятичной системе счисления. Показать правильность его работы для x=100, x=30, x=10107. Ведущие нули в результате нужно удалить.

41

Нормальный алгорифм Маркова задается в алфавите А={0,1,2,3,4,5,6,7,8,9} с использованием дополнительных символов a, b, c. Схема алгорифма:

  Z=|0c→.1|1c→.2|2c→.3|3c→.4|4c→.5|5c→.6|6c→.7|7c→.8|8c→.9|9c→c0|

|0b→.2|1b→.3|2b→.4|3b→.5|4b→.6|5b→.7|6b→.8|7b→.9|8b→c0|9b→c1| |a0→0a|a1→1a|a2→2a|a3→3a|a4→4a|a5→5a|a6→6a|a7→7a|a8→8a|a9→9a|a→b|Л→a|

Определите, какую задачу решает данный алгорифм, если в качестве входных данных подается десятичное число X (X>0). Приведите один пример, когда алгорифм работает неправильно. Внесите исправления в алгорифм, чтобы он всегда работал правильно.

42

Нормальный алгорифм Маркова задается в алфавите А={0,1,2,3,4,5,6,7,8} с использованием дополнительных символов a, b, c. Схема алгорифма

  Z=|с→.1|0c→.1|1c→.2|2c→.3|3c→.4|4c→.5|5c→.6|6c→.7|7c→.8|8c→c0|

|0b→.2|1b→.3|2b→.4|3b→.5|4b→.6|5b→.7|6b→.8|7b→c0|8b→c1| |a0→0a|a1→1a|a2→2a|a3→3a|a4→4a|a5→5a|a6→6a|a7→7a|a8→8a|a→b|Л→a|

Определите, какую задачу решает данный алгорифм, если в качестве входных данных подается девятеричное число X (X>0). Приведите один пример, когда алгорифм работает неправильно. Внесите исправления в алгорифм, чтобы он всегда работал правильно.

43

Нормальный алгорифм Маркова задается в алфавите А={0,1,2} с использованием дополнительных символов a, b и c. Схема алгорифма:

  Z=|0b→.2|1b→с0|2b→с1|0с→.1|1с→.2|2с→с0|c→1|a0→0a|a1→1a|a2→2a|a→b|Л→a|

Определите, какую задачу решает данный алгорифм, если в качестве входных данных подается троичное число X. Приведите пример неверной работы алгорифма. Укажите, как исправить ошибку в алгорифме.

44

Нормальный алгорифм Маркова задается в алфавите А={0,1,2,3} с использованием дополнительных символов a и b. Схема алгорифма:

  Z=|0b→b00|1b→b01|2b→b10|3b→b11|b→.Л|a0→0a|a1→1a|a2→2a|a3→3a|a→b|Л→a|

Определите, какую задачу решает алгорифм, если в качестве входных данных подается  число X в четверичной системе счисления. Напишите свое решение данной задачи.

45

Нормальный алгорифм Маркова задается в алфавите А={0,1,2,3} с использованием дополнительных символов a и b. Схема алгорифма:

  Z=|00b→b0|01b→b1|10b→b2|11b→b3|b→.Л|a0→0a|a1→1a|a→b|Л→a|

Определите, какую задачу решает алгорифм, если в качестве входных данных подается  число X в двоичной системе счисления. Определите, возможно ли в результате наличие незначащих нулей. Если возможно, дополните алгорифм так, чтобы незначащие нули в результате были удалены.

46

Нормальный алгорифм Маркова задается в алфавите А={0,1,2,3,4,5,6,7} с использованием дополнительных символов a и b. Схема алгорифма:

Z=|000b→b0|001b→b1|010b→b2|011b→b3|100b→b4|101b→b5|110b→b6|111b→b7|b→.Л|

|a0→0a|a1→1a|a→b|Л→a|

Определите, какую задачу решает алгорифм, если в качестве входных данных подается  число X в двоичной системе счисления. Приведите один пример, когда алгорифм работает неправильно. Внесите исправления в алгорифм, чтобы он всегда работал правильно.

47

Нормальный алгорифм Маркова задается в алфавите А={0,1,2,3,4,5,6,7,8,9} с использованием дополнительного символа a. Схема алгорифма:

  Z=|a0→a|aо→о|Л→a|, где о пробегает алфавит A

Данный алгорифм решает поставленную задачу, но, к сожалению, зацикливается. Определите, какую задачу решает данный алгорифм, если в качестве входных данных подается десятичное число X (X>0). Внесите исправления в алгорифм, чтобы он не зацикливался.

48

Нормальный алгорифм Маркова задается в алфавите А={0,1,2,3} с использованием дополнительных символов a и b. Схема алгорифма:

Z=|0b→b00|1b→b11|2b→b22|3b→b33|b→.Л|aо→оa|a→b|Л→a|,где о пробегает алфавит A

Определите, какую задачу решает алгорифм, если в качестве входных данных подается  число X в четверичной системе счисления. Напишите свое решение данной задачи.

49

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

50

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

51

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

52

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

53

Написать нормальный алгорифм Маркова для решения следующей задачи:

Имеется строка, содержащая выражение в котором унарные числа разделены знаками +(плюс) или –(минус). Сколько именно унарных чисел в выражении заранее не известно. Нужно вычислить значение выражения в унарной системе счисления. Известно, что в результате вычисления получится неотрицательное целое число и в ходе вычислений слева направо все промежуточные результаты тоже являются неотрицательными  целыми числа.

54

Написать нормальный алгорифм Маркова для решения следующей задачи:

Имеется строка, в которой записаны два унарных числа, разделенных знаком?.

Требуется вместо знака вопроса (?) записать знак > (первое число больше второго), < (первое число меньше второго) или = (числа равны). При этом исходные числа нужно стереть.

55

Написать нормальный алгорифм Маркова, позволяющий проверить корректность расстановки скобок в выражении. Считать, что на вход будет подаваться строка из символов ‘(‘ и ‘)’. На выходе нужно записать ‘+’, если скобочная последовательность корректна и ‘-‘, в противном случае. Исходную скобочную последовательность нужно стереть.