2014 dxdy logo

Научный форум dxdy

Математика, Физика, Computer Science, Machine Learning, LaTeX, Механика и Техника, Химия,
Биология и Медицина, Экономика и Финансовая Математика, Гуманитарные науки


Правила форума


Посмотреть правила форума



Начать новую тему Ответить на тему
 
 Машина Тьюринга и алгорифм Маркова
Сообщение17.01.2021, 02:56 


27/09/17
22
Здравствуйте! Учусь на первом курсе, по матлогике, дали такие задачи.
Не подскажете в правильном ли я начинала решать их.

Реализовать машину Тьюринга и алгорифм Маркова:
Добавить в начало слова 1, если разность между количеством нулей и количеством единиц делится на 3.

При реализации машины Тьюринга, я так поняла, разность между количеством $0$ и $1$ можно посчитать по модулю 3. то есть если $1$, то $+1$, если $0$, то $-1$ т все считается за один проход). Поступала вот так:

Будем следить за количеством 0 минус количество 1 по модулю 3. Остатки 0, 1, 2 от деления на 3 будем запоминать в состояниях q0, q1, q2, соответственно. Рассмотрим функции $f(r)$ и $g(r)$, определяемые следующим образом.
$\begin{array}{c|c|c|c}r&0&1&2\\\hline f(r)&1&2&0\\\hline g(r)&2&0&1\end{array}$


Рассмотрим такие правила.
\begin{align*}q_r\;0&\to q_{f(r)}\;0\;R\\q_r\;1&\to q_{g(r)}\;1\;R\end{align*}

для всех $r=0,1,2$.
Тогда после одного прохода, начиная с состояния $q_0$, машина будет снова в состоянии $q_0$ тогда и только тогда, когда разность между количеством 0 и количеством 1 делится на 3.
А вот алгорифмы Маркова, начала изучать недавно и не понимаю как реализовать правило которое считает разность количества между 0 и 1. Была идея сделать соотношения пар 0 и 1, но все равно не получается.

Буду благодарна любой помощи, спасибо

 Профиль  
                  
 
 Re: Машина Тьюринга и алгорифм Маркова
Сообщение17.01.2021, 18:12 


15/11/15
1080
khammisha в сообщении #1501482 писал(а):
Будем следить за количеством 0 минус количество 1 по модулю 3. Остатки 0, 1, 2 от деления на 3 будем запоминать в состояниях q0, q1, q2, соответственно. Рассмотрим функции ...

Задача, по моему, проще, чем кажется на первый взгляд. Не вводите никаких функций, просто распишите матрицу переходов состояний. Например, вы в состоянии $q_0$ (оно же и начальное). И тут вы видите 0. В какое состояние вы перейдете? Если же в состоянии $q_0$ вы видите 1, в какое состояние вы перейдете? И т.д. Это считая, что мы двигаемся справа налево.

Наконец, вы в состоянии $q_0$ видите элемент пусто. Что делаем?
Или вы в состоянии $q_1$ видите элемент пусто. Что делаем?...
Или вы в состоянии $q_2$ видите элемент пусто. Что делаем?...

Единственное замечание, обычно принято обозначать за $q_0$ конечное состояние, и иногда еще именно $q_1$ - начальное состояние. Возможно, придется переобозначить, хотя и немного теряется наглядность.
Решив задачу, можете проверить работы на тренажере . Отличный тренажер, пригодился мне при проведении занятий по матлогике.

 Профиль  
                  
Показать сообщения за:  Поле сортировки  
Начать новую тему Ответить на тему  [ Сообщений: 2 ] 

Модераторы: Модераторы Математики, Супермодераторы



Кто сейчас на конференции

Сейчас этот форум просматривают: нет зарегистрированных пользователей


Вы не можете начинать темы
Вы не можете отвечать на сообщения
Вы не можете редактировать свои сообщения
Вы не можете удалять свои сообщения
Вы не можете добавлять вложения

Найти:
Powered by phpBB © 2000, 2002, 2005, 2007 phpBB Group