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
1072
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 ] 

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



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

Сейчас этот форум просматривают: dgwuqtj


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

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