Дискретная математика. Элементы теории, задачи и упражнения. Часть 2. Булгакова И.Н. - 74 стр.

UptoLike

ВУЗ: 

ВГУ | Воронеж

Составители: 

Рубрика: 

74
заменить символ
1
x на
L
и, двигаясь вправо до первой пустой ячейки,
вписать в нее символ
1
x . Так как в алфавите всего два символа
a
и
b
,
то введите два состояния:
2
q вписывает символ
a
, если ax
i
=
;
3
q впи-
сывает символ
b
, если bx
i
=
.
4. Построить МТ, вычисляющую нуль-функцию
(
)
0
=
xO в алфавите
{
}
1,
L
.
Указание: Взять множество
{
}
10
q,qQ
=
, подставить вместо всех еди-
ниц символ
L
, а когда встретится символ
L
, то поставить символ 1.
5. Реализовать на МТ алгоритм вычисления функции
(
)
2
+
=
nnf , где
N
n
.
Указание: Взять множество состояний
{
}
210
q,q,qQ
=
. Число
n
на
ленте МТ записывается в десятичной системе счисления. Состояние
1
q
заменяет последнюю цифру числа
n
, если эта цифра меньше 8, цифрой,
на две единицы большей, и переходит в стоп-состояние. Если послед-
няя цифра числа
n
равна 8, то ее заменить на 0 и перейти влево в со-
стояние
2
q . Состояние
2
q добавляет к следующему разряду 1. Если же
последняя цифра числа
n
равна 9, то ее заменить на 1 и перейти влево
в состояние
2
q .
6. Вычисляет ли МТ в алфавите
{
}
L
,1
1) с программой
1
q
2
q
3
q
L
2
1 qЛ
0
qП
L
0
qН
L
1
3
1 qН
3
qЛ
L
функцию
î
í
ì
¹
=
=
.xесли,
,xесли,
xsign
00
01
2) с программой
1
q
2
q
3
q
4
q
L
2
qЛ
L
0
qП
L
4
qП
L
4
qП
L
1
3
1 qЛ
3
qЛ
L
0
1 qН
функцию
î
í
ì
¹
=
=
.xесли,
,xесли,
xsign
01
00
7. Построить МТ, которая вычисляет функцию:
1)
(
)
;yxy,xf
×
=
2)
(
)
;xxf
2
=
3) функцию выбора аргумента
(
)
(
)
2321
3
2
xx,x,xJ
=
. 
   заменить символ x1 на � и, двигаясь вправо до первой пустой ячейки,
   вписать в нее символ x1 . Так как в алфавите всего два символа a и b ,
   то введите два состояния: q 2 вписывает символ a , если x i � a ; q 3 впи-
   сывает символ b , если x i � b .
4. Построить МТ, вычисляющую нуль-функцию O � x � � 0 в алфавите
    �� ,1�.
    Указание: Взять множество Q � �q 0 , q1 �, подставить вместо всех еди-
    ниц символ � , а когда встретится символ � , то поставить символ 1.
5. Реализовать на МТ алгоритм вычисления функции f �n � � n � 2 , где
    n� N .
    Указание: Взять множество состояний Q � �q 0 , q1 , q 2 �. Число n на
    ленте МТ записывается в десятичной системе счисления. Состояние q1
    заменяет последнюю цифру числа n , если эта цифра меньше 8, цифрой,
    на две единицы большей, и переходит в стоп-состояние. Если послед-
    няя цифра числа n равна 8, то ее заменить на 0 и перейти влево в со-
    стояние q 2 . Состояние q 2 добавляет к следующему разряду 1. Если же
    последняя цифра числа n равна 9, то ее заменить на 1 и перейти влево
    в состояние q 2 .
6. Вычисляет ли МТ в алфавите �1, ��
1) с программой
                                       q1          q2          q3
                           �         1 Л q2      � П q0      � Н q0
                            1                    1 Н q3      � Л q3
                    �1, если x � 0 ,
функцию sign x � �
                    �0 , если x � 0.
2) с программой
                                q1          q2          q3          q4
                    �         � Л q2      � П q0      � П q4      � П q4
                    1                     1 Л q3      � Л q3      1 Н q0

                         �0 , если x � 0 ,
функцию sign x � �
                         �1, если x � 0.
7. Построить МТ, которая вычисляет функцию:
1) f � x , y � � x � y ;                  2) f � x � � x 2 ;
3) функцию выбора аргумента J 2�3 � � x1 , x 2 , x 3 � � x 2 .




                                            74

Страницы