 |
Главная Случайная страница Контакты | Мы поможем в написании вашей работы! | |
Подраздел 4.4
|
|
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
| * | ||
|
| а 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; Прочитано: 220 | Нарушение авторского права страницы | Мы поможем в написании вашей работы!
