Question

ДОПОМОЖІТЬ БУДЬ ЛАСОЧКА!!!!!!!!!!!!!! Машина Тюрінга. Скласти алгоритм, але за такою програмою:
T(i,j) –> (l, d, k)
i - внутрішній стан машини;
j - символ, що зчитується;
l - новий символ;
d - напрямок руху пристрою зчитування ( Л - ліворуч, П- праворуч);
k - новий внутрішній стан машини;

Сортування ланцюжка з букв "а" і "б" так, щоб спочатку стояли всі букви "а", а потім - всі букви "б". Каретка стоїть над рядком.
​

Answer 1

Початковий стан: i = 0, каретка у лівому кінці рядка.

⇒Зчитати символ j.

⇒Якщо j = 'a', то записати на місці каретки символ 'a', зберегти стан машини та перемістити каретку вправо: T(0, 'a') -> ('a', 'П', 0).

⇒Якщо j = 'b', то записати на місці каретки символ 'b', зберегти стан машини та перемістити каретку вправо: T(0, 'b') -> ('b', 'П', 0).

⇒Якщо j = кінець рядка, то перемістити каретку наліво до початку рядка та перейти до наступного стану: T(0, '_') -> ('_', 'Л', 1).

⇒Якщо i = 1, то закінчити роботу, бо всі букви відсортовані.

⇒Якщо j = '_', то записати на місці каретки символ '_', зберегти стан машини та перемістити каретку вправо: T(1, '_') -> ('_', 'П', 1).

⇒Якщо j = 'a', то записати на місці каретки символ 'a', зберегти стан машини та перемістити каретку вправо: T(1, 'a') -> ('a', 'П', 1).

⇒Якщо j = 'b', то записати на місці каретки символ 'b', перемістити каретку вправо та перейти до наступного стану: T(1, 'b') -> ('b', 'П', 1).

Повторювати кроки 2-9 до тих пір, поки не будуть всі символи відсортовані.

⇒Вихід з програми.