Методические указания к контрольной работе по дисциплине «Теория алгоритмов» для студентов заочного факультета специальности ИУС
Контрольная работа состоит из двух заданий: разработка машины Тьюринга и нормального алгоритма Маркова.
Задание 1 на контрольную работу
1. Разработать машину Тьюринга, выполняющую заданное действие.
Необходимо выполнить следующее:
-
Формализовать задачу для реализации машины Тьюринга: привести словесное описание алгоритма решения задачи, на основании которого определить перечень букв алфавита, перечень и назначение состояний.
-
Разработать таблицу переходов.
-
Составить алгоритмы работы машины Тьюринга для 3-4 входных последовательностей.
-
Продемонстрировать работу машины Тьюринга в виде ленты и управляющего автомата на тех же самых входных последовательностях с использованием предложенной преподавателем программы или существующей программы.
Пример
Разобpать идентификатоp в тексте пpогpаммы:
id ::= <бyква>{цифpа|бyква}
(начинается с бyквы, далее идет пpоизвольная смесь бyкв и цифp, оканчивается, если встpетился не бyквенноцифpовой символ)
Машина Тьюринга бyдет пpимеpно такой:
|
|
состояние |
|
с и м в о л |
|
Start |
Ident |
Буква |
Ident,<nothing> |
Ident,<nothing> |
|
Цифра |
|
Ident,<nothing> |
|
другое |
|
Start,<занести новое имя в таблицу> |
Следyет заметить, что <бyква>, <цифpа> и <дpyгое> - это в общем слyчае не одна ячейка, а много (т.е. вместо <бyква> надо подставить a,b,c,d,e... и т.д., вместо <цифpа> -- 1,2,3,4,5,6,7,8,9,0, вместо <дpyгое> - все остальное)
Пример программы:
/* опpеделяем константы обозначающие состояния */
#define STATE_1 1
#define STATE_2 2
....
#define STATE_N N
int state; /* здесь хpанится наше текyщее состояние */
char symbol; /* это символ, котоpый мы считали */
..
main() {
FILE * input;
..
input = fopen("Input_file");
/* основной алгоpитм pазбоpа */
while(! feof(input) ) {
c = fgetc(input);
switch (state) { /* выбиpаем нyжнyю колонкy Состояния */
case STATE_1:
switch(c) { /* выбиpаем нyжнyю стpокy Символ */
case 'a':
do_some_action(); /* выполняем действие, записанное в
клетке таблицы */
state = STATE_2; /* пеpеходим в новое состояние */
break;
case 'b':
...
} /* end switch */
case STATE_2:
...
} /* end switch */
} /* end while */
fclose(input);
..
} /* end main */
Еще можно реализовать в виде таблицы указателей на функции и т.д.
Программа для тестирования машины Тьюринга
Дана машина Тьюринга с внешним алфавитом А = {а0, 1, *}, алфавитом внутренних состояний Q = {q0, q1, q2, q3, q4} и со следующей функциональной программой:
Q A |
q1 |
q2 |
q3 |
q4 |
а0 |
q1а0П |
q3 а0П |
q3а0Л |
q1а0Л |
1 |
q3а0Л |
q21Л |
q4 а0П |
q41П |
* |
q0 а0С |
q3*Л |
q21П |
q4*П |
#include<iostream.h>
#include<conio.h>
#include<process.h>
#include<string.h>
#include<stdio.h>
char *A=" 1*"; //Внешний алфавит
char *K="LRS"; //Перемещение ленты
//Функция выделения символа из строки и
//сопоставления с символом внешнего алфавита
int kod_alf(char *c)
{
if(strstr(A,c)) return strstr(A,c)-A;
else return -1;
}
//Таблица переходов
int perehod[3][4]={{1,3,3,1},{3,2,4,4},{0,3,2,4}};
int zamena[3][4]={{0,0,0,0},{0,1,0,1},{0,2,1,2}};
int komanda[3][4]={{1,1,0,0},{0,0,1,1},{2,0,1,1}};
//Функция печати конфигурации машины
void pechat(char *S,int k,int q)
{
int i;
for(i=0;i<k;i++)
{
if(S[i]!=' ') cout<<S[i];
else cout<<"s0";
}
cout <<"q"<<q;
for(i=k;i<strlen(S);i++)
{
if(S[i]!=' ') cout<<S[i];
else cout<<"s0";
}
cout<<endl;
}
void main()
{
char S[256],c[2]="";
int q=1,j=0,simv,sdvig;
clrscr();
cout<<"Input string"<<endl;
gets(S);
cout<<" Algoritm Konfiguration "<<endl;
cout<<" ";
pechat(S,j,q);
//Цикл движения по ленте
while(q>0 && j<strlen(S))
{
cout<<"q"<<q;
c[0]=S[j];c[1]='\0';
simv=kod_alf(c);
if (simv==-1)
{
cout<<"Error in string"<<endl;
exit(0);
}
if(simv>0)cout<<A[simv];
else cout<<"s0";
cout<<"->";
//Реализация команды машины
S[j]=A[zamena[simv][q-1]];
sdvig=komanda[simv][q-1];
q=perehod[simv][q-1];
cout<<"q"<<q;
if(S[j]!=' ') cout<<S[j];
else cout<<"s0";
cout<<K[sdvig]<<" ";
if(sdvig==0)j++;
else if(sdvig==1)j--;
pechat(S,j,q);
}
}
Варианты заданий Группа иус 12з
-
На ленте машины Тьюринга записаны два набора единиц 1. Они разделены звездочкой *. Составьте функциональную схему машины так, чтобы она, исходя из стандартного начального положения, выбрала больший из этих наборов, а меньший стерла. Звездочка должна быть сохранена, чтобы было видно, какой из массивов выбран.
-
Слово Р имеет следующий вид: . Реализовать операцию получения остатка от деления в единичной системе счисления (в качестве ответа выдать слово справа от стрелки):
-
Постройте машину Тьюринга (называемую «удвоение» и обозначаемую Г), которая перерабатывает слово 01x0 в слово 01x01x0, причем в начальном и конечном положении обозревается крайняя левая ячейка.
-
A={a,b}. Определить, является P палиндромом (перевёртышем, симметричным словом) или нет. Ответ: a (да) или пустое слово.
-
A={a,b}. Если в P символов a больше, чем символов b, то выдать ответ a, если символов a меньше символов b, то выдать ответ b, а иначе в качестве ответа выдать пустое слово.
-
A={0,1}. Считая непустое слово P записью двоичного числа, получить это же число, но в четверичной системе. (Замечание: учесть, что в двоичном числе может быть нечётное количество цифр.)
-
A={(, )}. Определить, сбалансировано ли слово P по круглым скобкам. Ответ: Д (да) или Н (нет).
-
Пусть P имеет вид Q+R, где Q и R – непустые слова из символов 0, 1 и 2. Трактуя Q и R как записи чисел в троичной системе счисления (возможно, с незначащими нулями), выдать в качестве ответа запись суммы этих чисел в той же троичной системе.
-
A={ | }. Считая слово P записью числа n в единичной системе, получить в этой же системе число 2n.
-
Слово Р имеет следующий вид: . Реализовать операцию сложения в единичной системе счисления (в качестве ответа выдать слово справа от стрелки):: .
-
На информационной ленте машины Тьюринга находится десятичное число. Найдите результат целочисленного деления этого числа на 2.
-
Заданное в двоично-десятичной системе счисления число заменить десятичным числом.
-
Удалить из текста подслова вида 'abc'.
-
Слово Р имеет следующий вид: . Реализовать операцию определения максимального из чисел в единичной системе счисления (в качестве ответа выдать слово справа от стрелки):
-
В паскале комментарии заключаются в фигурные скобки: begin {начало цикла} i:=i+1; {увеличиваем i на 1
Удалить комментарии и вставить вместо исключенного комментария пробел (чтобы '1{один}2' превратилось бы не в '12', а в '1 2').
-
На ленте машины Тьюринга находится целое положительное число, записанное в десятичной системе счисления. Найдите произведение этого числа на число 11. Каретка обозревает крайнюю правую цифру числа.