1. 1 Петабайт неге тең?А) 1024 терабайтӘ) 1024 гигабайтБ) 109 байтВ) 8 бит​

1.1 А) 1024 терабайт

1. На ленте машины Тьюринга содержится последовательностью символов “+”. Напишите программу для машины Тьюринга, которая каждый второй символ “+” заменит на “–”. Замена начинается с правого конца последовательности. Автомат в состоянии q1 обозревает один из символов указанной последовательности. Кроме самой программы-таблицы, описать словами, что выполняется машиной в каждом состоянии.

2. Дано число n в восьмеричной системе счисления. Разработать машину Тьюринга, которая увеличивала бы заданное число n на 1. Автомат в состоянии q1 обозревает некую цифру входного слова. Кроме самой программы-таблицы, описать словами, что выполняется машиной в каждом состоянии.

3. Дана десятичная запись натурального числа n > 1. Разработать машину Тьюринга, которая уменьшала бы заданное число n на 1. Автомат в состоянии q1 обозревает правую цифру числа. Кроме самой программы-таблицы, описать словами, что выполняется машиной в каждом состоянии.

4. Дано натуральное число n > 1. Разработать машину Тьюринга, которая уменьшала бы заданное число n на 1, при этом в выходном слове старшая цифра не должна быть 0. Например, если входным словом было “100”, то выходным словом должно быть “99”, а не “099”. Автомат в состоянии q1 обозревает правую цифру числа. Кроме самой программы-таблицы, описать словами, что выполняется машиной в каждом состоянии.

5. Дан массив из открывающих и закрывающих скобок. Построить машину Тьюринга, которая удаляла бы пары взаимных скобок, т.е. расположенных подряд “( )”.

Например, дано “) ( ( ) ( ( )”, надо получить “) . . . ( ( ”.

Автомат в состоянии q1 обозревает крайний левый символ строки. Кроме самой программы-таблицы, описать словами, что выполняется машиной в каждом состоянии.

6. Дана строка из букв “a” и “b”. Разработать машину Тьюринга, которая переместит все буквы “a” в левую, а буквы “b” — в правую части строки. Автомат в состоянии q1 обозревает крайний левый символ строки. Кроме самой программы-таблицы, описать словами, что выполняется машиной в каждом состоянии.

розгалуження виконується, коли виконання попереднього розгалуження ще не закінчено.

Наприклад, вам потрібно встановити будильник на завтра. Якщо

завтра робочий день, то ви повинні встати о 7-й годині ранку, щоб іти

до школи. Якщо завтра субота, то ви повинні встати о 8-й годині ранку, щоб їхати на заняття гуртка. Якщо завтра неділя, то ви встаєте о

9-й годині ранку.

У наведеному на малюнку алгоритмі друге розгалуження з

умовою Завтра субота? міститься всередині першого розгалуження з

умовою Завтра робочий день?.

Такий фрагмент алгоритму називають вкладеним розгалуженням.

Вкладені розгалуження - це фрагмент алгоритму, у якому одне

розгалуження міститься всередині іншого розгалуження.

Розглянемо виконання наведеного на малюнку 3.26 фрагмента алгоритму. Спочатку перевіряється умова Завтра робочий день?. Якщо

результат перевірки цієї умови Так, то виконується команда Установити будильник на 7-му годину ранку і на цьому виконання всього

цього фрагмента алгоритму закінчується. Якщо результат перевірки

умови Завтра робочий день? - Ні, то перевіряється умова Завтра субота?. Якщо результат перевірки цієї умови Так, то виконується команда

Установити будильник на 8-му годину ранку і на цьому виконання всього цього фрагмента алгоритму закінчується, а якщо результат перевірки

цієї умови Ні, то виконується команда Установити будильник на 9-ту

годину ранку і виконання всього цього фрагмента алгоритму закінчується.

У наведеному на малюнку

фрагменті алгоритму внутрішнє

розгалуження виконується, якщо результат перевірки умови зовнішнього розгалуження Ні.

Объяснение:

рисунок 3.26 (во вложении)