В последовательности, состоящей из 0 и 1 сдвинуть слово, состоящее из 1 влево

Программа:

(Если в воспринимаемой ячейке символ 0, и МТ находится в состоянии q_1, то состояние не меняется, символ не меняется, УУ сдвигается вправо).

(Если в воспринимаемой ячейке символ 1, и МТ находится в состоянии q_1, то это значит, что УУ находится на начале слова, состояние меняется на q₂, символ не меняется, УУ сдвигается влево).

(Если в воспринимаемой ячейке символ 0, и МТ находится в состоянии q_2, то это значит, что УУ находится в ячейке, с которой должно начаться слово, состояние меняется на q₃, символ меняем на 1, УУ сдвигается вправо).

(Если в воспринимаемой ячейке символ 1, и МТ находится в состоянии q_3, то это значит, что УУ передвигается по слову, состояние не меняется, символ не меняется, УУ сдвигается вправо).

(Если в воспринимаемой ячейке символ 0, и МТ находится в состоянии q_3, то это значит, что УУ дошло до ячейки, которая следует после конца слова, состояние меняется на q₄, символ не меняется, УУ сдвигается влево).

(Если в воспринимаемой ячейке символ 1, и МТ находится в состоянии q_4, то это значит, что УУ дошло до конца слова, состояние меняется на заключительное, символ меняется на 0, УУ останавливается).

В виде таблицы эту программу можно записать следующим образом:

а	q1	q2	q3	q4

2. Доказать, что функция примитивно-рекурсивная:

2.3.f(x,y)=x*y;

По схеме примитивной рекурсии

1) x*0 = х = I₁(x)

2) x*(y+1) =

Т. о. функцию x*y можно получить с помощью операции примитивной рекурсии из функций и h(x,y,z)=z*1.

3. Построить нормальный алгорифм Маркова, который:

3.2. преобразует исходное слово, состоящее из последовательности единиц, в символ Ч, если количество единиц четное и в символ НЧ, если количество единиц нечетное.

Пусть Х – некоторый конечный алфавит. Если словам алфавита, то выражения и называются формулами подстановки в алфавите Х:

- простая подстановка;

- окончательная подстановка.

λ – пустое слово.

Х={λ,1}

Нормальная схема подстановок:

1 1 ® λ

λ 1 1 λ ®.Ч λ

λ 1 λ ®.Н Ч λ

Преобразуемое слово:

λ 1 1 1 1 1 1 λ → λ λ 1 1 1 1 λ → λ λ λ 1 1 λ → Ч λ

λ 1 1 1 1 1 1 1 λ → λ λ 1 1 1 1 1 λ → λ λ λ 1 1 1 λ → λ λ λ λ 1 λ → Н Ч λ

В 3-й контрольной в задании 2.4. не знаю как правильно унифицировать и получить резольвенту.