ВУЗ:
Составители:
Рубрика:
Операция замыкания . Основные замкнутые классы .
__________________________________________________________________________________________
129
заменить символ
1
x на
Λ
и, двигаясь вправо до первой пустой ячейки,
вписать в нее символ
1
x . Так как в алфавите всего два символа
a
и
b
,
то введите два состояния:
2
q вписывает символ
a
, если ax
i
=
;
3
q впи -
сывает символ
b
, если bx
i
=
.
4. Построить МТ, вычисляющую нуль -функцию
(
)
0
=
xO в алфавите
{
}
1,
Λ
.
Указание: Взять множество
{
}
10
q,qQ
=
, подставить вместо всех еди-
ниц символ
Λ
, а когда встретится символ
Λ
, то поставить символ 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. Вычисляет ли МТ в алфавите
{
}
Λ
,1
1) с программой
1
q
2
q
3
q
Λ
2
1 qЛ
0
qП
Λ
0
qН
Λ
1
3
1qН
3
qЛ
Λ
функцию
≠
=
=
.xесли,
,xесли,
xsign
00
01
2) с программой
1
q
2
q
3
q
4
q
Λ
2
qЛ
Λ
0
qП
Λ
4
qП
Λ
4
qП
Λ
1
3
1qЛ
3
qЛ
Λ
0
1 qН
функцию
≠
=
=
.xесли,
,xесли,
xsign
01
00
7. Построить МТ, которая вычисляет функцию :
1)
(
)
;yxy,xf
⋅
=
2)
(
)
;xxf
2
=
3) функцию выбора аргумента
(
)
(
)
2321
3
2
xx,x,xJ =
.
129
Операция замыкания. Основные замкнутые классы.
__________________________________________________________________________________________
заменить символ 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 .
