👍 0 👎 |
Алгоритм на машине ТьюрингаНужно сделать алгоритм на МТ( A{a,b}), который бы переворачивал(делал реверс) слова, например abb->bba
|
👍 0 👎 |
Машина Тьюринга — это несложно, надо только прочитать и посмотреть пример реализации, хотя бы в интернете.
|
👍 +1 👎 |
Я сначала написал, а потом уже заметил, что я неправильно прочитал задание... я написал программу которая приписывает к данному слову зеркальное: abb to abbbba, например. Но я надеюсь, что Вы сможите модифицировать программу.
Будем считать, что вам нужна программа на классической (одна лента, одна головка) машине Тьюринга. Мы будем считать, что в начале головка стоит на первой букве входного слова (пустой символ будем обозначать как _). q_f --- состояние "я закончила, господин". q_0 --- стартовое состояние. Состояние q_0 делает следующее. q_0(a) = (a,R,q_1), q_0(b) = (b,R,q_1), q_0(_) = (_,N,q_f). Т.е. это состояние отслеживает случай пустого входного слова. Состояние q_1. q_1(a) = (a,R,q_1), q_1(b) = (b,R,q_1), q_1(_) = (_,L,q_2) Задача этого состояния добраться до правого конца входного слова. Состояние q_2. q_2(a) = (*,R,q_3), q_2(b) = (*,R,q_4), q_2(_) = (_,R,q_f) Это состояние заменяет символ на * и запоминает замененную букву в состоянии q_3 или q_4. Состояние q_3. q_3(a) = (a,R,q_3), q_3(b) = (b,R,q_3), q_3(_) = (a,L,q_5). Бежим вправо и на первое пустое место ставим a. Состояние q_4. q_4(a) = (a,R,q_4), q_4(b) = (b,R,q_4), q_4(_) = (b,L,q_6). Бежим вправо и на первое пустое место ставим b. Состояние q_5. q_5(a) = (a,L,q_5), q_5(b) = (b,L,q_5), q_5(*) = (a,L,q_2). Бежим влево, восстанавливаем *. Состояние q_6. q_6(a) = (a,L,q_6), q_6(b) = (b,L,q_6), q_6(*) = (b,L,q_2). Бежим влево, восстанавливаем *. |
👍 0 👎 |
Машина Тьюринга
|
👍 0 👎 |
Логика в информатике
|
👍 0 👎 |
Обработка графической информации
|
👍 0 👎 |
Не могу выполнить алгоритм для чисел. Например: 34. 73 и т. д.…
|
👍 0 👎 |
Как строится машина Тьюринга?
|
👍 0 👎 |
Подскажите алгоритм решения задачи:
|