ДОПОМОЖІТЬ БУДЬ ЛАСОЧКА!!!!!!!!!!!!!! Машина Тюрінга. Скласти алгоритм, але за такою програмою:
T(i,j) –> (l, d, k)
i - внутрішній стан машини;
j - символ, що зчитується;
l - новий символ;
d - напрямок руху пристрою зчитування ( Л - ліворуч, П- праворуч);
k - новий внутрішній стан машини;
Сортування ланцюжка з букв "а" і "б" так, щоб спочатку стояли всі букви "а", а потім - всі букви "б". Каретка стоїть над рядком.
T(i,j) –> (l, d, k)
i - внутрішній стан машини;
j - символ, що зчитується;
l - новий символ;
d - напрямок руху пристрою зчитування ( Л - ліворуч, П- праворуч);
k - новий внутрішній стан машини;
Сортування ланцюжка з букв "а" і "б" так, щоб спочатку стояли всі букви "а", а потім - всі букви "б". Каретка стоїть над рядком.
More Questions From This User See All
Answers & Comments
Початковий стан: 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).
[tex]\\[/tex]⇒Якщо j = 'b', то записати на місці каретки символ 'b', перемістити каретку вправо та перейти до наступного стану: T(1, 'b') -> ('b', 'П', 1).
Повторювати кроки 2-9 до тих пір, поки не будуть всі символи відсортовані.
⇒Вихід з програми.