Поделитесь эмулятором Машины Тьюринга

Нашел штук 8 из которых 6 просят какуюто библиотеку ?????????.DLL, а остальные работают только "в пятерках"



______________________
|
|O
/\
/\

«Just hanging around..» © Melhesedek

компилить в VC++:
#include <iostream>
#include <conio.h>
using namespace std;

int main(){
char *s=new(char);
s[0]=0;
int i;
char c;
int q,q0,q1,anow;
char a0,a1;
char Stroka[81];
bool flag;
cout << "Enter filename: ";
cin >>s;
FILE *F1;
F1=fopen(s,"r");
c='a';
while (c!=EOF){
c=fgetc(F1);
if (c<48||c>57) continue;
q0=(int)c-48;
c=fgetc(F1);
if (c<48||c>57) continue;
q0=q0*10+(int)c-48;
c=fgetc(F1);
a0=fgetc(F1);
c=fgetc(F1);
a1=fgetc(F1);
c=fgetc(F1);
c=fgetc(F1);
if (c<48||c>57) continue;
q1=(int)c-48;
c=fgetc(F1);
if (c<48||c>57) continue;
q1=q1*10+(int)c-48;
c=fgetc(F1);
cout << q0<<','<<a0<<','<<a1<<','<<q1<<endl;
}
i=fclose(F1);
cout << "Enter string:";
i=0;
while ((c=getch())!=13) {
cout <<c;
if (c!=8){
Stroka=c;
Stroka[i+1]=0;
i++;}
else{
i--;
Stroka=' ';
cout <<' '<<(char)8;
}
}
anow=i;
for (i;i<81;i++)
Stroka=' ';
Stroka[81]=0;
cout <<endl;
cout << Stroka;

flag=true;

q=0;

while(flag){


F1=fopen(s,"r");
q0=100;
a0=' ';
c='a';
while (c!=EOF && (q0!=q||a0!=Stroka[anow])){
c=fgetc(F1);
if (c<48||c>57) continue;
q0=(int)c-48;
c=fgetc(F1);
if (c<48||c>57) continue;
q0=q0*10+(int)c-48;
c=fgetc(F1);
a0=fgetc(F1);
c=fgetc(F1);
a1=fgetc(F1);
c=fgetc(F1);
c=fgetc(F1);
if (c<48||c>57) continue;
q1=(int)c-48;
c=fgetc(F1);
if (c<48||c>57) continue;
q1=q1*10+(int)c-48;
c=fgetc(F1);
}
i=fclose(F1);
if (q!=q0 || a0!=Stroka[anow]) {
cout << "Stop.";
flag=false;
break;}
else{
q=q1;
cout <<Stroka<<endl;
for (i=0;i<anow;i++)
cout <<' ';
cout <<'^'<<endl;
cout <<q0<<','<<a0<<','<<a1<<','<<q1<<endl;
switch (a1){
case '>': anow++; break;
case '<': anow--; break;
case '#': cout << "Stoped by # comand"<<endl; flag=false; break;
default: Stroka[anow]=a1;
}
if (anow==81){
cout << "Right border interupt"<<endl;
flag=false;
break;
}
if (anow==-1){
cout << "Left border interupt"<<endl;
flag=false;
break;
}

}
}
cout <<Stroka<<endl;
for (i=0;i<anow;i++)
cout <<' ';
cout <<'^'<<endl;
cout << "Thanx for using my Turing Machine Interpreter!"<<endl<< "BobicZdoh (http:////bobiczdoh.narod.ru)";
return 0;
}

Но тока, это не эмулятор, а интерпретатор. И ваще пора бы уже научится самому такое писать.
Чему вас тока в школе учат...

Принеси. диск. кое-что спишу. дай мне свои. Типа бартер.


Автор: avsemenoff Любезный, если вы такой умный, почему вы еще не препод?

123098 писал(а):

> Автор: avsemenoff Любезный, если вы такой умный, почему вы еще
> не препод?
>

Скоро станет. Осталось только поработать над стилем и попасть в полуфинал ЧМ по программированию. Но успехи уже отмечены Учёным Советом МАИ [faq8.mailabs.ru] !!!

avsemenoff писал(а):

> Но тока, это не эмулятор, а интерпретатор. И ваще пора бы уже
> научится самому такое писать.
> Чему вас тока в школе учат...

Да, в школе программированию не учат, но слово
эмуляция согласно толковому словарю вполне соответствует:
"Эмуляция - имитация работы одной системы средствами другой без потери функциональных возможностей и искажений результатов. Эмуляция выполняется программными и/или аппаратными средствами."

Насчёт эмулятора, пардон, не знал...

"Автор: avsemenoff Любезный, если вы такой умный, почему вы еще не препод?"
Нас в школе заставляли программки и посложнее писать. Причём школа отнюдь не московская...
Так что я думал, что большинство (подавляющее) козерогов ДОЛЖНО уметь писать такие программы.

Последнюю версию эмулятора МТ для MS Windows tu05m можно скачать здесь:
[amais.org.ru]Учёба/Первый%20курс&

Последнюю версию эмулятора МТ для MS Windows tu05m можно скачать здесь:
[amais.org.ru]Учёба/Первый%20курс&



Кто-то скачал эту версию? У меня возникает проблема при попытке начать на ней работать:открывается окно эмулятора с руководством по пользованию во время редактирования программы;ознакомившись с руководством, я ,как там и просят,нажимаю "любую клавишу" после чего опять всплывает несколько инструкций.А дальше такая картина-стоит мне нажать какую-либо клавишу, как программа напрочь вылетает...
Это только у меня так? И ,вообще, что тут можно поделать?

[turing.narod.ru]

avsemenoff скорее всего перепутал эмулятор с компилятором.



С уважением, Дмитрий

Поделитесь, плиз, описанием команд для Tu05m.exe.
Перебирать весь алфавит долго. На нестандартные буквы он сообщает об ошибке и вываливается в шел. Встроенный хелп не нашел.
Заранее благодарен.



С уважением, Дмитрий

Эмулятор я скорее всего перепутал с чем-то вроде графической среды.
"Поделитесь, плиз, описанием команд для Tu05m.exe."
В четвёрках:
qq,a,b,ww
где qq и ww - двуразрядное целое
{ ,[a-z],[A-Z],>,<,#} э a,b
где > - головка вправо, < - головка влево, # - останов.
Вроде так.

Спасибо, Андрей.
Надо сказать, что с пятерками он все равно работает не корректно. Он их позволяет редактировать, исполняет, сохраняет в файл, а вот прочитать из файла нормально не может. Крайний правый столбец (номер ветки) всегда обнулен. т.е. пользоваться пятерками можно только в текущем сеансе.



С уважением, Дмитрий

avsemenoff писал(а):

> Эмулятор я скорее всего перепутал с чем-то вроде графической
> среды.

Эмуляция на самом деле более узкий термин. Когда одна ЭВМ микропрограммно моделирует команды другой. Эта идея (Уилкс),
кажется, удостоена Тьюринговской премии. Выполнение процессором AMD Intel'овского кода несколько не то, т.к. их традиционные наборы команд в значительной мере совпадают.

Спасибо за сообщение, баг устранён (файл заменён), + немного переработан интерфейс заполнения ленты.

прочтите эти (выдаваемые программой) инструкции, вам станет всё понятно
подсказка: Программа не вылетает, а корректно завершается

avsemenoff писал(а):

> Нас в школе заставляли программки и посложнее писать. Причём
> школа отнюдь не московская...

Провинциальные школы всегда поставляли лучших невест для столичных женихов!

Александр, мы же взрослые люди.
я писал "На нестандартные буквы он сообщает об ошибке и вываливается в шел." ВЫВАЛИВАЕТСЯ не значит, что не корректно завершается.
Просьба написать маленький хелп в F1 и потомки вас не забудут



С уважением, Дмитрий

zzz писал(а):
> Провинциальные школы всегда поставляли лучших невест для
> столичных женихов!
скорее наоборот...
"школа отнюдь не московская"=3 км от МКАДа)

кстати, Александр, хелп по F1 - действительно полезная вещь.

DIZ писал(а):

> avsemenoff скорее всего перепутал эмулятор с компилятором.
>

Не мог он. Это две большие разницы, эмулятор -- интерпретатор!

Желание сделать F1 есть, когда дойдут руки хелп тогда сделаю (одновременно с переносом на компилятор FPC для всех OS + версия на Turbo Delphi .NET для GUI Windows). Раньше всем сначало показывали программу Лукашевича в терминалке, а потом давали эту. Эти программы похожи по интерфейсу и вопросов не возникало.



Пиво не пью

AlTi писал(а):

> прочтите эти (выдаваемые программой) инструкции, вам станет всё
> понятно
> подсказка: Программа не вылетает, а корректно завершается

Та же, извиняюсь, фигня, что и у Sam-а. И сколько не читай - все равно лучше не становится. Не знаю что делать...

Были люди, обещавшие эмулятор МТ под FreeBSD .



С уважением, Дмитрий

Для запуска программы введите tu05m.exe имя_файла.tu

Вот копия экрана:

Эмулятор машин Тьюринга разработал Горлов А.А в 2001-2006 г.
в среде Borland Pascal.
Руководство по пользованию во время редактирования программы:
Для перехода от занесения данных на ленту к редактированию программы нажмите
клавишу Down
Для обратного перехода ESC
Для запуска нажмите Enter
Для пошагового выполнения нажмите Ctrl+Enter
Для остановки выполнения ESC
Для перехода от пошагового выполнения к автоматическому нажмите Enter
Для обратного перехода Space
Для выхода нажмите ESC
Для сохранения программы нажмите Tab
При включённом Scroll Lock, во время выполнения, вывод на экран не производится
Для удаления пятерки вместо команды движения поставьте ?, а для удаления
четверки вместо команды замены
При вводе программы для сохранения одной строки в буфере нажмите PageUp, а для
восстановления нажмите PageDown

-------------------------------------------------------------------------------

Use:
C:\DOCUME~1\ГОСТЬ\РАБОЧИ~1\TU05M.EXE [имя программы] [-p (Имя файла протокола) [-a]]

Key:
-p - позволяет во время работы создавать протокол, во время автоматического
выполнения если вместо имени вписать con, то протокол будет выводиться на экран.
-a - Автоматическое выполнение без вывода информации на экран.
Без создания протокола не имеет смысла



Пиво не пью

DIZ писал(а):

> Были люди, обещавшие эмулятор МТ под FreeBSD .
>

Будет доставлен бандеролью 3.5".

Спасибо, Александр.
Есть некоторые НО, которые не отражены в подсказке:
1. Команды МТ. В других интерпретаторах используются r,l,R,L и т.д.
Здесь только опытным путем смог определить, что работают <,>,#
Не смог определить команду "стоять на месте" (для "пятерок" актуально).
2. Создать новую программу с помощью TU05M.EXE можно задав имя несуществующего файла. Это тоже было б неплохо указать в хелпе.



С уважением, Дмитрий

В предыдущей версии были r, l, u, s но сейчас ради с совместимостью с четвёрками используется >,<,=,# (сегодня постараюсь добавить возможность использования других символов), для останова можно использовать ничего не делающую команду (символ на ленте, положение ГМТ, состояние не меняется).

Эмулятор МТ под FreeBSD.
Любезно предоставлен Валентином Евгеньевичем.
Тыкаем сюда для скачивания.



С уважением, Дмитрий

Для упрощения запуска программы можно переименовать файл в tu4, к примеру. FreeBSD должна поддерживать русские буквы, т.к. все сообщения, выдаваемые программой, на русском.
Проверено. Работает.



С уважением, Дмитрий

Не мог бы кто-нибудь перезалить МТ для FreeBSD? C webfile.ru файл уже удалили.. Заранее спасибо.

Глюк какой-то обещали 14 дней хранить.
Тогда на другом ресурсе [ifolder.ru]



С уважением, Дмитрий

Саша, еще одна просьба есть по модернизации TU05M. Хотелось бы чтобы программа в статусбаре выводила количество тактов "пройденных" машиной до останова. Эта цифра будет показывать эффективность реализации алгоритмов для разных программ с одинаковыми входными данными. Например, на листе с заданиями к Л5 дана программа суммирования двоичных чисел. Можно написать другую программу делающую то же самое, но выполняющую вычисления за меньшее кол-во тактов.



С уважением, Дмитрий

Фи, а на Питоне слабо сбацать было?

Вот эмулятор на Питоне:

1 #! /usr/bin/env python
2
3 import sys
4
5 class BadSyntax: pass
6 class NothingToDo: pass
7
8 class Machine:
9 def __init__(self, filename):
10 f = open(filename, "r")
11 self.program = []
12 while True:
13 line = f.readline()
14 if not line: break
15 tuple = line.strip().split(",")
16 if len(tuple) > 4 or len(tuple[1]) > 1 or len(tuple[2]) > 1:
17 raise BadSyntax()
18 self.program.append(tuple)
19
20 def init(self, tape, pos, state):
21 self.tape = list(tape)
22 self.pos = pos
23 self.state = state
24
25 def step(self):
26 for tuple in self.program:
27 if tuple[0] == self.state and tuple[1] == self.tape[self.pos]:
28 self.state = tuple[3]
29 if tuple[2] == "<": self.pos -= 1
30 elif tuple[2] == ">": self.pos += 1
31 elif tuple[2] == "=": pass
32 elif tuple[2] == "#": return False
33 else: self.tape[self.pos] = tuple[2]
34 if len(self.tape) <= self.pos: self.tape.append(' ')
35 return True;
36 raise NothingToDo()
37 def run(self):
38 while self.step(): pass
39 def trace(self):
40 while self.step():
41 print ''.join(self.tape)
42
43 if len(sys.argv) != 2:
44 print "Usage: machine <program.ru>"
45 sys.exit(1)
46
47 try:
48 machine = Machine(sys.argv[1])
49 except SyntaxError:
50 print "Syntax error"
51 sys.exit(1)
52 tape = sys.stdin.readline().rstrip("\n")
53 posstr = sys.stdin.readline()
54 pos = posstr.find('^')
55 machine.init(tape + " ", pos, '00')
56 try:
57 #machine.trace()
58 machine.run()
59 print ''.join(machine.tape)
60 except NothingToDo:
61 print "Nothing to do"

Программа принимает на стандартный ввод в первой строке ленту, а во второй -- символ рабочей ячейки ^ в нужной позиции, предварённый пробелами.
Кроме того, программа может выполнять трассировку (метод trace класса machine).

Да уж! После удаления вьюером форума пробелов программа стала неработоспособной.
Но этого удалось избежать заменой всех пробелов на "нбсп":

#!&nbsp;/usr/bin/env&nbsp;python

import&nbsp;sys

class&nbsp;BadSyntax:&nbsp;pass
class&nbsp;NothingToDo:&nbsp;pass

class&nbsp;Machine:
&nbsp;&nbsp;def&nbsp;__init__(self,&nbsp;filename):
&nbsp;&nbsp;&nbsp;&nbsp;f&nbsp;=&nbsp;open(filename,&nbsp;"r")
&nbsp;&nbsp;&nbsp;&nbsp;self.program&nbsp;=&nbsp;[]
&nbsp;&nbsp;&nbsp;&nbsp;while&nbsp;True:
&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;line&nbsp;=&nbsp;f.readline()
&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;if&nbsp;not&nbsp;line:&nbsp;break
&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;tuple&nbsp;=&nbsp;line.strip().split(",")
&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;if&nbsp;len(tuple)&nbsp;>&nbsp;4&nbsp;or&nbsp;len(tuple[1])&nbsp;>&nbsp;1&nbsp;or&nbsp;len(tuple[2])&nbsp;>&nbsp;1:
&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;raise&nbsp;BadSyntax()
&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;self.program.append(tuple)

&nbsp;&nbsp;def&nbsp;init(self,&nbsp;tape,&nbsp;pos,&nbsp;state):
&nbsp;&nbsp;&nbsp;&nbsp;self.tape&nbsp;=&nbsp;list(tape)
&nbsp;&nbsp;&nbsp;&nbsp;self.pos&nbsp;=&nbsp;pos
&nbsp;&nbsp;&nbsp;&nbsp;self.state&nbsp;=&nbsp;state

&nbsp;&nbsp;def&nbsp;step(self):
&nbsp;&nbsp;&nbsp;&nbsp;for&nbsp;tuple&nbsp;in&nbsp;self.program:
&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;if&nbsp;tuple[0]&nbsp;==&nbsp;self.state&nbsp;and&nbsp;tuple[1]&nbsp;==&nbsp;self.tape[self.pos]:
&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;self.state&nbsp;=&nbsp;tuple[3]
&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;if&nbsp;tuple[2]&nbsp;==&nbsp;"<":&nbsp;self.pos&nbsp;-=&nbsp;1
&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;elif&nbsp;tuple[2]&nbsp;==&nbsp;">":&nbsp;self.pos&nbsp;+=&nbsp;1
&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;elif&nbsp;tuple[2]&nbsp;==&nbsp;"=":&nbsp;pass
&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;elif&nbsp;tuple[2]&nbsp;==&nbsp;"#":&nbsp;return&nbsp;False
&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;else:&nbsp;self.tape[self.pos]&nbsp;=&nbsp;tuple[2]
&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;if&nbsp;len(self.tape)&nbsp;<=&nbsp;self.pos:&nbsp;self.tape.append('&nbsp;')
&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;return&nbsp;True;
&nbsp;&nbsp;&nbsp;&nbsp;raise&nbsp;NothingToDo()
&nbsp;&nbsp;def&nbsp;run(self):
&nbsp;&nbsp;&nbsp;&nbsp;while&nbsp;self.step():&nbsp;pass
&nbsp;&nbsp;def&nbsp;trace(self):
&nbsp;&nbsp;&nbsp;&nbsp;while&nbsp;self.step():
&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;print&nbsp;''.join(self.tape)

if&nbsp;len(sys.argv)&nbsp;!=&nbsp;2:
&nbsp;&nbsp;print&nbsp;"Usage:&nbsp;machine&nbsp;program.tu"
&nbsp;&nbsp;sys.exit(1)

try:
&nbsp;&nbsp;machine&nbsp;=&nbsp;Machine(sys.argv[1])
except&nbsp;SyntaxError:
&nbsp;&nbsp;print&nbsp;"Syntax&nbsp;error"
&nbsp;&nbsp;sys.exit(1)
tape&nbsp;=&nbsp;sys.stdin.readline().rstrip("\n")
posstr&nbsp;=&nbsp;sys.stdin.readline()
pos&nbsp;=&nbsp;posstr.find('^')
machine.init(tape&nbsp;+&nbsp;"&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;",&nbsp;pos,&nbsp;'00')
try:
&nbsp;&nbsp;#machine.trace()
&nbsp;&nbsp;machine.run()
&nbsp;&nbsp;print&nbsp;''.join(machine.tape)
except&nbsp;NothingToDo:
&nbsp;&nbsp;print&nbsp;"Nothing&nbsp;to&nbsp;do"

А подскажите пожалуйста как можно на машине Тьюринга посчитать целую часть от гиперболического синуса х, х>0

AnnaS писал(а):

> А подскажите пожалуйста как можно на машине Тьюринга посчитать
> целую часть от гиперболического синуса х, х>0
>
Соответствующий материал будет на лекциях в ноябре.

На 3 факультете диссертация по эмуляции:
[www.mai.ru]

спасибо

Ещё один, из Википедии (отступы, составляющие неотъемлемую часть программы на Python, будут съедены вьюером форума?!):

"Если что-то осталось непонятным, можно рассмотреть симулятор работы МТ на языке Python, который мы будем использовать, чтобы проиллюстрировать процесс работы машин Тьюринга.

def execute_MT(MT,Tape):
k=MT["k"]
T=MT["program"]
Tape=["*"]+Tape[:]
configuration={"state":MT["start"], "position":1, "tape": Tape}
history=[configuration]
step=0
while 1:
step=step+1
#if we reach the end of the tape --- enlarge it
if configuration["position"]>=len(configuration["tape"]):
configuration["tape"].append("*")

#the symbol we are looking at
symbol=configuration["tape"][configuration["position"]]

#perform transition
key=(configuration["state"],(symbol))
action=T[key]

# Just cloning entire configuration: (state,head position,tape)
new_tape=configuration["tape"][:]
new_configuration=dict(configuration)
new_configuration["tape"]=new_tape
configuration=new_configuration

#changing state
configuration["state"]=action[0]

#write new symbol
symbol=action[1][0]
configuration["tape"][configuration["position"]]=symbol

#move head
move=action[1][1]
if move=="L": configuration["position"]=configuration["position"]-1
if move=="R": configuration["position"]=configuration["position"]+1

#tracking configuration
history.append(configuration)

#if stop state - finishing
if configuration["state"]==MT["stop"] or step>1000:
break

return history


Он принимает на вход описание машины Тьюринга в виде хэш-таблицы — рассмотрим пример машины тьюринга для задачи удвоения входной строки (алфавит состоит только из «1»). Описание соответствующей МТ:

MT={
'k': 1,
'start': 's1',
'stop': 'q',
'program': {
#(Состояние, символы на лентах) -> (новое состояние, (действия по каждой ленте))
('s1', ('1')): ('s2', (('*','R'))),
('s2', ('1')): ('s2', (('1','R'))),
('s2', ('*')): ('s3', (('*','R'))),
('s3', ('*')): ('s4', (('1','L'))),
('s3', ('1')): ('s3', (('1','R'))),
('s4', ('1')): ('s4', (('1','L'))),
('s4', ('*')): ('s5', (('*','L'))),
('s5', ('1')): ('s5', (('1','L'))),
('s5', ('*')): ('s1', (('1','R'))),
('s1', ('*')): ('q', (('*','')))
}
}
"

Еще пример.
Деление на 2 унарного числа между звездочками.

Код:

q1*->q2*R
q11->q11R
q1~->q1~R
q2~->q2~R
q2*->q6~L
q21->q3~R
q3~->q3~R
q31->q5~L
q3*->q6~L
q6*->q8*L
q61->qZ-1E
q6~->q6~L
q5~->q5~L
q5*->q7*L
q7~->q11L
q71->q71L
q81->q81L
q8~->qZ+*E
q8*->qZ+*E

На ленте
*111*

Результат:
Was:*111* ukaz=0 done q1*->q2*R
Was:*111* ukaz=1 done q21->q3~R
Was:*~11* ukaz=2 done q31->q5~L
Was:*~~1* ukaz=1 done q5~->q5~L
Was:*~~1* ukaz=0 done q5*->q7*L
Was:*~~1* ukaz=0 done q7~->q11L
Was:1*~~1* ukaz=-1 done q1~->q1~R
Was:1*~~1* ukaz=0 done q11->q11R
Was:1*~~1* ukaz=1 done q1*->q2*R
Was:1*~~1* ukaz=2 done q2~->q2~R
Was:1*~~1* ukaz=3 done q2~->q2~R
Was:1*~~1* ukaz=4 done q21->q3~R
Was:1*~~~* ukaz=5 done q3*->q6~L
Was:1*~~~~ ukaz=4 done q6~->q6~L
Was:1*~~~~ ukaz=3 done q6~->q6~L
Was:1*~~~~ ukaz=2 done q6~->q6~L
Was:1*~~~~ ukaz=1 done q6*->q8*L
Was:1*~~~~ ukaz=0 done q81->q81L
Was:1*~~~~ ukaz=0 done q8~->q43*E
RESULT:*1*~~~~

Оптимальность алгоритмов в примерах не гарантирую!

Ваши решения ненормированные и используют вспомогательную букву.