Алгоритмы и алгоритмическая сложность Контр. р. 1 в 18
.docМинистерство образования Республики Беларусь
Учреждение образования
Белорусский государственный университет информатики и радиоэлектроники
Факультет непрерывного и дистанционного обучения
Кафедра информационные технологии автоматизированных систем
КОНТРОЛЬНАЯ РАБОТА № 1
ПО ДИСЦИПЛИНЕ
АЛГОРИТМЫ И АЛГОРИТМИЧЕСКАЯ СЛОЖНОСТЬ
на тему: «Машины Тьюринга»
Выполнил ст. гр. хххххххх
хххххххххххххххххххххххх
E-mail: ххххххххххххххххх
Проверил:
А.Л. Гончаревич
Минск 2011
Контрольное задание №1
Написать правила машины Тьюринга для решения указанной задачи.
1 Вариант: на вход поступает последовательность из 0 и 1. Машина должна записать ее в обратном порядке. Пример 0001110 заменяется на 0111000.
Решение:
Q1 – начальное состояние работы машины Тьюринга. Головка находиться на первом левом элементе ленты. В процессе работы перемещается головка относительно ленты. Qfin – конечное состояние машины Тьюринга.
Таблица1.
|
|
|
0 |
1 |
|
Q1 |
Q1R |
0Q2R |
1Q2R |
|
Q2 |
Q3L |
0Q4S |
1Q4S |
|
Q3 |
Q3S |
Q18R |
Q20R |
|
Q4 |
Q5L |
0Q4R |
1Q4R |
|
Q5 |
Q5S |
Q7R |
Q6R |
|
Q6 |
1Q8L |
0Q6S |
1Q6S |
|
Q7 |
0Q8L |
0Q7S |
1Q7S |
|
Q8 |
Q8L |
Q13L |
Q9L |
|
Q9 |
Q19S |
0Q10R |
1Q10R |
|
Q10 |
Q10R |
0Q11R |
1Q11R |
|
Q11 |
1Q12S |
0Q11R |
1Q11R |
|
Q12 |
Q8S |
0Q12L |
1Q12L |
|
Q13 |
Q17S |
0Q14R |
1Q14R |
|
Q14 |
Q14R |
0Q15R |
1Q15R |
|
Q15 |
0Q16S |
0Q15R |
1Q15R |
|
Q16 |
Q8S |
0Q16L |
1Q16L |
|
Q17 |
Q17R |
0Q18R |
1Q18R |
|
Q18 |
0-S |
0Q18R |
1Q18R |
|
Q19 |
Q19R |
0Q20R |
1Q20R |
|
Q20 |
1-S |
0Q20R |
1Q20R |
В данной таблице Qх – состояние машины Тьюринга.
0, 1, . - символы входного алфавита машины.
- пустой символ.
“–” конечное состояние машины Тьюринга Qfin.
Примеры работы машины:
Заменим пустой символ на _
Начало работы:
|
Лента: 0 |
Лента: 110 |
|
Шаг 1 Состояние Q1 (0) -> Q2 (0, R) Шаг 2 Состояние Q2 (_) -> Q3 (_, L) Шаг 3 Состояние Q3 (0) -> Q18 (_, R) Шаг 4 Состояние Q18 (_) -> Qfin (0, S) |
Шаг 1 Состояние Q1 (1) -> 2 (1, R) Шаг 2 Состояние Q2 (1) -> 4 (1, S) Шаг 3 Состояние Q4 (1) -> 4 (1, R) Шаг 4 Состояние Q4 (0) -> 4 (0, R) Шаг 5 Состояние Q4 (_) -> 5 (_, L) Шаг 6 Состояние Q5 (0) -> 7 (_, R) Шаг 7 Состояние Q7 (_) -> 8 (0, L) Шаг 8 Состояние Q8 (_) -> 8 (_, L) Шаг 9 Состояние Q8 (1) -> 9 (_, L) Шаг 10 Состояние Q9 (1) -> 10 (1, R) Шаг 11 Состояние Q10 (_) -> 10 (_, R) Шаг 12 Состояние Q10 (_) -> 10 (_, R) Шаг 13 Состояние Q10 (0) -> 11 (0, R) Шаг 14 Состояние Q11 (_) -> 12 (1, S) Шаг 15 Состояние Q12 (1) -> 12 (1, L) Шаг 16 Состояние Q12 (0) -> 12 (0, L) Шаг 17 Состояние Q12 (_) -> 8 (_, S) Шаг 18 Состояние Q8 (_) -> 8 (_, L) Шаг 19 Состояние Q8 (_) -> 8 (_, L) Шаг 20 Состояние Q8 (1) -> 9 (_, L) Шаг 21 Состояние Q9 (_) -> 19 (_, S) Шаг 22 Состояние Q19 (_) -> 19 (_, R) Шаг 23 Состояние Q19 (_) -> 19 (_, R) Шаг 24 Состояние Q19 (_) -> 19 (_, R) Шаг 25 Состояние Q19 (_) -> 19 (_, R) Шаг 26 Состояние Q19 (0) -> 20 (0, R) Шаг 27 Состояние Q20 (1) -> 20 (1, R) Шаг 28 Состояние Q20 (_) -> Qfin (1, S) |
|
Символы ленты на момент завершения работы программы: _ 0 Результат: 0 |
Символы ленты на момент завершения работы программы: _ _ _ _ 0 1 1 Результат: 0 1 1 |
Связка состояний Q1 и Q2 читает первый символ и определяет дальнейший ход работы машины. Если за ним оказывается пустой символ машина делает шаг назад, берет символ, вписывает его на пустое место и переходит в конечное состояние Qfin. Если вторым символом оказывается 0 или 1 машина переходит в состояние Q4 и продолжает движение по ленте вправо пока не встретит пустой символ (определит конец ленты); далее машина делает шаг влево считывает символ и вписывает его на пустое место. Этим действием машина определит 1 символ нашей перестановки (состояния Q5,Q6,Q7). Начинаем движение по ленте влево. Встречаем 0 или 1, считываем символ, вписывая на его место пустой, сдвигаем ленту влево еще на один шаг, проверяем находится ли за ним еще 0 или 1 если да - начинаем движение в право. Машина встречает 1 символ перестановки и продолжает движение вправо. Как только на вход поступает пустой символ машина вписывает на его место считаный символ слева и повторяет движение в левую сторону (состояния Q8-Q16). Как только слева после считаного символа появится пустой (достигнут первый элемент ленты) – машина последний раз начнет движение вправо, впишет символ и закончит свою работу (состояния Q17-Q20)
Для демонстрации правильности работы машины Тьюринга была написана программа на Паскале.
Так как последовательность из 0 и 1 представляет собой строку, а строка представляет собой массив символов, следовательно, можно узнать размер этого массива и получить доступ к каждому его элементу. Эта особенность была использована при написании программы.
Листинг:
program Project3;
{$APPTYPE CONSOLE}
uses
SysUtils;
var
s : string;
i,j,l : Integer;
label lb;
begin
lb:
write ('Zadaite posledovatelnost iz 0 и 1: ');
readln(s);
if s='' then
begin
writeln;
writeln(' Oshibka! ');
writeln;
beep;
goto lb
end
else
begin
writeln;
writeln(' Nachalo vipolnenija programmi.');
end;
writeln;
writeln(' Idet proverka lenty . ');
writeln;
for i:=1 to length(s) do
begin
if (s[i]='0') or (s[i]='1') then
begin
write(s[i]) ;
sleep(100);
end
else
begin
writeln(' Oshibka! ');
beep;
writeln;
goto lb
end;
end;
write (' Ok!');
writeln; writeln;
writeln(' Perestanovka.');
writeln;
l:=length(s);
for j:=1 to length(s) do
begin
write(s[l]);
sleep(125);
l:=l-1
end;
write (' Ok!');
beep;
writeln; writeln;
write('Nazmite ENTER dlja vixoda. ');
readln;
end.