Форум программистов, компьютерный форум, киберфорум
Наши страницы
Теория автоматов
Войти
Регистрация
Восстановить пароль
 
Рейтинг 4.56/9: Рейтинг темы: голосов - 9, средняя оценка - 4.56
Катке
0 / 0 / 0
Регистрация: 02.06.2011
Сообщений: 15
1

МАшина Тьюринга

02.06.2011, 23:48. Просмотров 1702. Ответов 1
Метки нет (Все метки)

помогите пожалуйчта срочно составить таблицу состояний и переходов, вот задание:Задание: Подсчитать количество согласных букв в слове( Фамилии)
Моя фамилия «Смирнова». Представим ее в следующем виде: «--*--*-*», где символ * означает гласную букву, а символ «–» согласную.
Алгоритм: после встречи «-» стирать его, идти в конец слова, ставить 1 или увеличить на 1. Потом каретка возвращается на начало и повторяет все сначала.
0
Similar
Эксперт
41792 / 34177 / 6122
Регистрация: 12.04.2006
Сообщений: 57,940
02.06.2011, 23:48
Ответы с готовыми решениями:

Машина поста и машина тьюринга: необходимо написать алгоритм к данному изображению
нужно решение в виде команд МТ и МП

Сложение четырех целых без знака (Машина Поста), Троичное вычитание "-1" (Машина Тьюринга).
Здравствуйте! Можете пожалуйста помочь с задачками: Машина Поста: Сложение...

Машина Поста и Машина Тьюринга
Помогите решить задачу. На Машине Поста нужно написать программу Необходимо...

Машина Тьюринга
Здачка такая есть,дан Алфавит,состоящий из букв А,В,на ленточном механизме мб...

Машина Тьюринга
Помогите разобраться...хоть подсказку дайте... Постройте машину Тьюринга,...

1
Chipnddail
14 / 14 / 1
Регистрация: 03.09.2009
Сообщений: 109
07.06.2011, 17:11 2
Если нигде не напутал, то такая машина Тьюринга может быть задана следующими правилами:
q1 - начальное состояние, q0 - конечное состояние
Алфавит {* (гласная буква), - (согласная буква), # (символом забиваем отработанные буквы), @ - пустой символ, 1}
Согласно вашему алгоритму:
q1- >> q2#R
q1* >> q1*R
q1@ >> q0@R //все согласные учтены или не найдено согласных
q2- >> q2-R //проходим в конец строки
q2* >> q2*R
q2@ >> q3@R
q31 >> q31R
q3@ >> q41L //добавляем единицу
q4* >> q4*L //переходим в начало строки
q4@ >> q4@L
q4# >> q1#R

Проверим алгоритм на примере входного слова @--*--*-*@
@--*--*-*@ , @#-*--*-*@1 @, @##*--*-*@11@, @##*#-*-*@111@, @##*##*-*@1111@, @##*##*#*@11111@, переходит в конечное состояние q0 @##*##*#*@11111@
получаем, что в Смирнова 5 согласных

Добавлено через 38 минут
Немного подправил, и нашел в соседней теме ссылку на эмулятор машины Тьюринга
алфавит тот же только пустой символ B, а не @
Крутая штука,

-q1->#q2R
*q1->*q1R
Bq1->BSTOPR //все согласные учтены или не найдено согласных
-q2->-q2R //проходим в конец строки
*q2->*q2R
Bq2->Bq3R
1q3->1q3R
Bq3->1q4L //добавляем единицу
*q4->*q4L //переходим в начало строки
-q4->-q4L
1q4->1q4L
Bq4->Bq4L
#q4->#q1R
0
MoreAnswers
Эксперт
37091 / 29110 / 5898
Регистрация: 17.06.2006
Сообщений: 43,301
07.06.2011, 17:11

Машина Тьюринга
Люди.. кто знает машины Тьюринга подскажите пожалуйста реализацию следующей...

Машина Тьюринга
1. A={a,b}. Удалить из слова Р его второй символ, если такой есть. 2....

машина Тьюринга
На ленте машины Тьюринга находится целое положительное число, записанное в...


Искать еще темы с ответами

Или воспользуйтесь поиском по форуму:
2
Ответ Создать тему
Опции темы

КиберФорум - форум программистов, компьютерный форум, программирование
Powered by vBulletin® Version 3.8.9
Copyright ©2000 - 2018, vBulletin Solutions, Inc.
Рейтинг@Mail.ru