СПРОСИ ПРОФИ
👍
0
👎 03

Алгоритм на машине Тьюринга

Нужно сделать алгоритм на МТ( A{a,b}), который бы переворачивал(делал реверс) слова, например abb->bba
информатика обучение     #1   27 сен 2016 20:42   Увидели: 11 клиентов, 2 специалиста   Ответить
👍
0
👎 0
Машина Тьюринга — это несложно, надо только прочитать и посмотреть пример реализации, хотя бы в интернете.
👍
+1
👎 1
я уже часа 3 сижу, никак не решу это задание
  #3   28 сен 2016 17:06   Ответить
👍
+1
👎 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). Бежим влево, восстанавливаем *.

Задайте свой вопрос по информатике
профессионалам

Сейчас онлайн 75 репетиторов по информатике
Получите ответ профи быстро и бесплатно

Другие вопросы на эту тему:

👍
0
👎 09

Машина Тьюринга   9 ответов

Здравствуйте!
Помогите, пожалуйста, построить машину Тьюринга для переворачивания слов в алфавите {a,b}.
  08 июн 2013 22:14  
👍
0
👎 04

Логика в информатике   4 ответа

Элементами множеств А, P и Q являются натуральные числа, причём P = {2, 4, 6, 8, 10, 12} и Q = {4, 8, 12, 116}. Известно, что выражение (x  P) → (((x  Q)  ¬(x A)) → ¬(x  P)) истинно при любом значении переменной х. Определите наименьшее возможное значение суммы элементов множества A. -значок принадлежности к множеству.
Интересно знать, есть ли какой-то общий алгоритм таких задач.
  30 янв 2018 12:42  
👍
0
👎 00

Обработка графической информации   0 ответов

Здравстуйте! Я бы хотел задать вопрост по Информатике. Я плохо понимаю о Обработке графической информации. Именно формулы, напимер N=2Айзнака. Хоть я и знаю жту формулу, я не понимаю что она значит. Там есть еще формулы. И есть ли какой-гибудь алгоритм для задач по этой теме? У нас в основном задачи на нахождение объёма видеопамяти или файла. Надеюсь вы поможете. Спасибо.
  19 фев 2014 19:14  
👍
0
👎 08

Не могу выполнить алгоритм для чисел. Например: 34. 73 и т. д.…   8 ответов

Добрый день! Не могу выполнить алгоритм для чисел. Например: 34.73 и т.д. Алгоритм: 1.Вычесть 1, 2.Сложить количество единиц в разряде.
  08 фев 2014 16:56  
👍
0
👎 09

Как строится машина Тьюринга?   9 ответов

Извините за любопытство.А как строится машина Тьюринга?На ПК в каком-либо эмуляторе или специальной программе?
  22 авг 2013 08:18  
👍
0
👎 00

Подскажите алгоритм решения задачи:   0 ответов

Для заданного текста определить среднюю информацию на знак алфавита, считая, что алфавит содержит только те символы, которые встречаются в тексте.
  11 янв 2012 14:52  
ASK.PROFI.RU © 2020-2021