![]() |
Главная Случайная страница Контакты | Мы поможем в написании вашей работы! | |
|
1) Так как, по условию, задана десятичная система счисления, то внешний алфавит МТ должен содержать все цифры от 0 до 9 и символ пустой клетки
Чтобы решить задачу, МТ должна в первом такте работы стереть последнюю цифру числа заменить ее цифрой, на единицу большей, и перейти в состояние
если последняя цифра числа
была меньше цифры 9.
Если же последняя цифра числа была 9, то МТ должна стереть её, записать в освободившуюся клетку цифру 0 и произвести сдвиг головки влево на одну клетку, оставаясь в том же начальном состоянии. Во втором такте МТ должна прибавить единицу к цифре, стоявшей в левой клетке, т.е. в клетке, куда сдвинулась головка.
Если после сдвига влево головка МТ будет обозревать пустую клетку, то в следующем такте она должна записать в пустую клетку цифру 1 и перейти в состояние . Таким образом, для вычисления заданной функции МТ должна пребывать лишь в двух состояниях:
и
, а функциональная схема должна иметь вид следующей таблицы
| ![]() | ||||||||||||
![]() | 1н q 0 | 1н q 0 | 2н q 0 | 3н q 0 | 4н q 0 | 5н q 0 | 6н q 0 | 7н q 0 | 8н q 0 | 9н q 0 | 0л q 1 |
Конфигурации для будут иметь вид:
a 05 6 a 0; a 05 7 a 0; .
q 1 q 0
Конфигурации для будут такими:
a 01 9 9 a 0; a 01 9 0 a 0; a 01 0 0 a 0; a 02 0 0 a 0; .
q 1 q 1 q 1 q 0
Для будем иметь конфигурации:
a 09 9 a 0; a 09 0 a 0; a 00 0 a 0; a 01 0 0 a 0; .
q 1 q 1 q 1 q 0
2) В двоичной системе счисления сложение двух чисел выполняется в соответствии с правилами
,
,
,
.
Очевидно, что внешний алфавит должен состоять из символов , число состояний МТ должно быть равно двум:
, а функциональная схема иметь вид таблицы
| ![]() | ||||
![]() | 1н q 0 | 1н q 0 | 0л q 1 |
Соответствующие конфигурации будут иметь вид:
, a 01 0 1 a 0; a 01 0 0 a 0; a 01 1 0 a 0;
;
q 1 q 1 q 0
, a 01 1 0 a 0; a 01 1 1 a 0;
;
q 1 q 0
, a 01 1 1 a 0; a 01 1 0 a 0; a 01 0 0 a 0; a 00 0 0 a 0;
q 1 q 1 q 1 q 1
a 01 0 0 0 a 0;
q 0
3) Внешний алфавит будет . Для реализации алгоритма необходимо, чтобы МТ, находясь в начальном состоянии
заменяла последнюю цифру числа
если она меньше 6, цифрой, на четыре единицы большей, и переходила в состояние
.
Если последняя цифра числа равна 6,7,8 или 9, то ее нужно заменить соответственно на цифру 0,1,2 или 3 и сдвинуться влево на одну клетку, перейдя в состояние
. Состояние
должно добавлять 1 к следующему разряду.
Таким образом, МТ будет иметь три состояния: , а ее функциональная схема будет представлена таблицей
| ![]() | ||||||||||||
![]() | 4н q 0 | 5н q 0 | 6н q 0 | 7н q 0 | 8н q 0 | 9н q 0 | 0л q 2 | 1л q 2 | 2л q 2 | 3л q 2 | |||
![]() | 1н q 0 | 1н q 0 | 2н q 0 | 3н q 0 | 4н q 0 | 5н q 0 | 6н q 0 | 7н q 0 | 8н q 0 | 9н q 0 | 0л q 2 |
Соответствующие конфигурации будут иметь вид:
, a 04 8 a 0; a 04 2 a 0; a 05 2 a 0;
;
q 1 q 2 q 0
, a 02 9 7 a 0; a 02 9 1 a 0; a 02 0 1 a 0; a 03 0 1 a 0;
.
q 1 q 2 q 2 q 0
4) В основу решения задачи можно положить следующий принцип. Если в исходном слове, которое в МТ будет представлять начальную конфигурацию вида
a 0 а 1 а 2 …а n a 0
q 1
букву заменить на символ пустой клетки
и, двигаясь вправо до первой пустой клетки, вписать в нее букву
а все остальные буквы этого слова оставить без изменения, то мы и получим искомое решение. Если при этом управляющая головка в исходном состоянии
обозревает букву
, то она должна заменить ее на букву
и, сдвинувшись вправо на одну клетку, перевести МТ в новое состояние
. Это состояние во всех следующих тактах не должно менять буквы.
Если же головка в исходном состоянии обозревает букву
, то она должна заменить ее на букву
и, сдвинувшись вправо, перевести МТ в новое состояние
. Это состояние во всех следующих тактах не должно менять буквы.
Находясь же в состоянии и обозревая головкой правую пустую клетку
, МТ должна вписать в эту клетку букву
, остаться на месте и перейти в состояние
. Находясь в состоянии
и обозревая правый символ
, МТ должна вписать в эту клетку букву
, остаться на месте и перейти в состояние
.
Обобщая всё изложенное, функциональную схему МТ для решения данной задачи можно представить в виде
| ![]() | ![]() ![]() | ![]() | ||
![]() | а 0п q 2 | а 0п q 3 | |||
![]() | а 1н q 0 | а 1п q 2 | а 2п q 2 | ||
![]() | а 2н q 0 | а 1п q 3 | а 2п q 3 |
Последовательности всех конфигураций для заданных слов
а 0 а 1 а 2 а 2 а 1 а 2 а 0,; а 0 а 2 а 1 а 2 а 1 а 2 а 0,;
q 1 q 1
а 0 а 0 а 2 а 2 а 1 а 2 а 0; а 0 а 0 а 1 а 2 а 1 а 2 а 0;
q 2 q 3
а 0 а 2 а 2 а 1 а 2 а 0; а 0 а 1 а 2 а 1 а 2 а 0;
q 2 q 3
а 0 а 2 а 2 а 1 а 2 а 0; а 0 а 1 а 2 а 1 а 2 а 0;
q 2 q 3
а 0 а 2 а 2 а 1 а 2 а 0; а 0 а 1 а 2 а 1 а 2 а 0;
q 2 q 3
а 0 а 2 а 2 а 1 а 2 а 0; а 0 а 1 а 2 а 1 а 2 а 0;
q 2 q 3
а 0 а 2 а 2 а 1 а 2 а 1 а 0; а 0 а 1 а 2 а 1 а 2 а 2 а 0.
q 0 q 0
5) Очевидно, что всё многообразие чисел, которые могут использоваться при заданных условиях, исчерпывается следующими словами: *, 0, и * 0 * * 0… …* *.
Таким образом, достаточно, чтобы управляющая головка различала всего лишь три символа: 0 и *. Тогда, если слово представлено всего лишь одним символом *, то для решения задачи достаточно, чтобы головка МТ, обозревая в исходном состоянии правую пустую клетку (с символом
), сдвинулась влево на одну клетку. Поскольку там записан символ *, то МТ должна во втором такте выработать команду, которая в правой пустой клетке сохранила бы символ
и, обозревая символ *, перешла бы в состояние
Если задано , то нужно в первом такте сдвинуться влево на одну клетку, сохранив символ
. Но поскольку любое число
большее 9, может состоять из 0 в младшем разряде и из любых чисел в последующих разрядах, то это нужно проверить. То есть во втором такте нужно вновь сдвинуться на клетку влево, сохранив в предыдущей клетке 0, и перейти в новое состояние. Если окажется, что новая клетка будет пуста, т.е. в ней записан символ
, то в следующем такте нужно возвратиться в предыдущую клетку, сохранив левый символ
и изменив состояние МТ на новое. Поскольку в клетке, к которой возвратится головка, записан 0, то его надо зафиксировать. Для этого нужно выработать команду подтверждения 0 и переход в состояние
.
Если же после 0 в младшем разряде в заданном слове окажется хотя бы один символ, то это значит, что заданное число . Следовательно, все символы, располагающиеся левее первого нуля в младшем разряде, нужно стереть, заменить их на символ пустой клетки
, возвратиться к первому нулю, заменить его на символ * (что будет эквивалентно 1) и перейти в состояние
.
Обобщая все сказанное, один из вариантов решения задачи, т.е. функциональной схемы, можно представить в виде следующей таблицы и соответствующих конфигураций:
| ![]() | ![]() | * | ||
![]() | а 0л q 2 | ||||
![]() | 0л q 3 | *н q 0 | |||
![]() | а 0п q 4 | а 0л q 3 | а 0л q 5 | ||
![]() | а 0п q 4 | 0н q 0 | *н q 0 | ||
![]() | а 0п q 7 | а 0л q 5 | а 0л q 6 | ||
![]() | а 0п q 6 | *н q 0 | |||
![]() | а 0п q 7 | *н q 0 | |||
1. а 0 * а 0, 1. а 0 0 а 0, 4. а 0 0 а 0,
q 1 q 1 q 4
2. а 0 * а 0, 2. а 0 0 а 0, 5. а 0 0 а 0 − результат
q 2 q 2 q 0
3. а 0 * а 0 − результат. 3. а 0 0 а 0,
q 0 q 3
/ 1. a 0 * 0 * 0 a 0, 6. a 0 a 0 a 0 a 0 0 a 0,
q 1 q 6
2. a 0 * 0 * 0 a 0,7. a 0 a 0 a 0 a 0 0 a 0,
q 2 q 6
3. a 0 * 0 * 0 a 0, 8. a 0 a 0 a 0 0 a 0,
q 3 q 6
4. a 0 * 0 * 0 a 0, 9. a 0 a 0 0 a 0,
q 5 q 6
5. a 0 * a 0 a 0 0 a 0, 10. a 0 0 a 0,
q 5 q 6
11. a 0 * a 0 – результат
q 0.
Дата публикования: 2015-01-10; Прочитано: 241 | Нарушение авторского права страницы | Мы поможем в написании вашей работы!