Группа иус12зуск

1. На информационной ленте машины Тьюринга находится массив, состоящий из символов А, Б, B, Д. Сожмите массив, удалив из него все элементы B.

2. Даны два натуральных числа n и m, представленные в десятичной системе счисления. Между этими числами стоит знак «?». Выясните отношение n и m, т. е. знак «?» замените на один из подходящих знаков «>», «<», «=».

3. На информационной ленте машины Тьюринга в произвольном порядке записаны цифры: 1, 2, 3, 7, 8. Каретка обозревает крайнюю левую цифру. Необходимо составить функциональную схему машины Тьюринга, которая расположит эти цифры в порядке возрастания.

4. A={а, к, м, н, о, п, р, е}. В исходном тексте удалить все четные слова.

5. Записанные на ленте числа с фиксированной точкой заменить записью в экспоненциальной форме.

6. На ленте машины Тьюринга находится десятичное число. Определите, делится ли это число на 6 без остатка. Если делится, то запишите справа от числа слово «да», если нет — «нет». Каретка находится где-то над числом.

7. Пусть P имеет вид Q>R, где Q и R – непустые слова из символов 0, 1, 2, 3. Трактуя Q и R как записи чисел в четверичной системе счисления (возможно, с незначащими нулями), выдать в качестве ответа слово 1, если число Q больше числа R, и слово 0 иначе.

8. Записанные на ленте числа в экспоненциальной форме заменить записью с фиксированной точкой.

9. Необходимо подсчитать, сколько слов и десятичных чисел содержится в тексте.

10. Реализовать функцию x*y в пятеричной системе счисления.

11. Реализовать функцию f= 5*(x+y) с помощью композиции двух машин Тьюринга.

12. Слово Р имеет следующий вид: . Реализовать операцию деления нацело в единичной системе счисления (в качестве ответа выдать слово справа от стрелки):

13. A={a, b, с, d}. В исходном слове удалить все вхождения символа d, а затем удвоить полученное слово.

14. На ленте задано число с фиксированной точной. Представить его в виде целого, деленного на соответствующую степень 10. Например: 1024.655=1024655/1000.

15. На ленте машины Тьюринга находится последовательность 2N символов. Уменьшите этот массив в 2 раза.

16. На ленте машины Тьюринга находится десятичное число. Определите, делится ли это число на 9 без остатка. Если делится, то запишите справа от числа слово «да», если нет — «нет». Каретка находится где-то над числом.

17. Пусть P имеет вид Q=R, где Q и R – непустые слова из символов 0, 1, 2, 3, 4. Трактуя Q и R как записи двоичных чисел (возможно, с незначащими нулями), выдать в качестве ответа слово 1, если эти числа равны, и слово 0 иначе.

18. Заданное десятичное число заменить числом в двоично-десятичной системе счисления.

19. Слово Р имеет следующий вид: . Реализовать операцию вычитания в единичной системе счисления (в качестве ответа выдать слово справа от стрелки):

20. A={ | }. Пусть слово P является записью числа 2ⁿ (n=0, 1, 2, …) в единичной системе. Получить в этой же системе число n.

Задание 2

Тема: Представление алгоритмов с помощью нормальных алгоритмов Маркова

Цель работы: Освоить методы анализа работы нормальных алгоритмов Маркова и их разработки для реализации заданного алгоритма.

Требования к выполнению работы

Разработать нормальный алгоритм Маркова, реализующий заданную программу. Для этого:

1. Определить внешний алфавит А, если он не задан (набор входных символов);

2. Составить последовательность подстановок нормального алгоритма Маркова;

3. Проверить функционирование алгоритма с помощью тестовой программы, задавая различные входные последовательности.

Описание тестовой программы

Функция new_str реализует заданную командой замену:

S1 – подстрока для поиска в исходной строке S2;

S3 – подстрока для замены.

Массив Alg – указатель на двумерный массив строк. Количество строк массива равно количеству команд нормального алгоритма Маркова (переменная n). Количество столбцов равно 3, при этом первый и второй столбец содержат информацию о соответствующей замене: S1 -> S2. В третьем столбце содержится «0», если замена не конечная или «1» - если замена конечная.

Для использования программы необходимо:

1. Заменить значение переменной n;

2. Заполнить массив Alg.

#include<iostream.h>

#include<conio.h>

#include<stdlib.h>

#include<string.h>

#include<stdio.h>

void new_str(char* S1,char* S2,char* S3)

{

char S[256]="";

char *p=strstr(S2,S1);

strcat(S,S2);

S[p-S2]='\0';

strcat(S,S3);

strcat(S,p+strlen(S1));

strcpy(S2,S);

}

void main()

{

char S[256]="",tmp[256],*p;

int i,n=10,flag=1;

char *Alg[10][3]={{"*0","0*","0"},

{"*1","1*","0"},

{"0*","1","0"},

{"1*","#0","0"},

{"0#","1","0"},

{"1#","#0","0"},

{"##","1","1"},

{"#0","#

","0"},

{"#1","1","1"},

{"","#*","0"}};

clrscr();

cout<<"Input string"<<endl;

gets(tmp);

strcat(S,tmp);

while(flag)

{

for(i=0;i<n;i++)

{

p=strstr(S,Alg[i][0]);

if(p!=NULL)

{

new_str(Alg[i][0],S,Alg[i][1]);

puts(S);

if(strcmp(Alg[i][2],"1")==0)

{

flag=0;

break;

}

i=-1;

}

}

if(i==n) break;

}

getch();

}

Варианты заданий

Группа ИУС12з

1. A={a, b}. Если слово P имеет чётную длину (0, 2, 4, …), то удалить правую половину этого слова.

2. Реализовать функцию f=x+6.

3. Проверить, есть ли в тексте вещественные числа в форме с десятичной точкой.

4. A={0,1,2,3}. Преобразовать слово P так, чтобы сначала шли все чётные цифры (0 и 2), а затем – все нечётные.

5. A={a, b, c}. Если в слове P не менее двух символов, то переставить каждую пару символов местами.

6. Подсчитать количество буквосочетаний «аб» и «ба» во входном тексте. Считаем, что их не может быть больше 8.

7. Проверить, есть ли в тексте числа в экспоненциальной форме.

8. На ленте записано выражение 2^n, получить результат операции в двоичной системе счисления.

9. A={a,b,c}. Если в слово P не входит символ a, то заменить в P все символы b на с, иначе в качестве ответа выдать слово из одного символа a.

10. A={м, н, о, п, р, е}. Определить, имеются ли слова, содержащие не меньше двух гласных символов.

11. A={a, b, с, d}. В непустом слове P поменять местами его первый и предпоследний символы.

12. При разработке программного кода не рекомендуется использовать оператор goto. Необходимо проверить текст студенческой программы и подсчитать, сколько раз встречается оператор goto.

13. На ленте записано выражение 2^n, получить результат операции в двоичной системе счисления.

14. A={a, b}. Перевернуть слово P (например: abb → bba).

15. A={0, 1}. Считая непустое слово P записью числа в двоичной системе, получить двоичное число, равное неполному частному от деления числа P на 2 (например: 1011 → 101).

16. A={0, 1, 2, 3}. Считая непустое слово P записью числа в четверичной системе счисления, определить, является оно чётным числом или нет.