задан 22 Апр '15 2:50

изменен 22 Апр '15 8:19

%D0%92%D0%B8%D1%82%D0%B0%D0%BB%D0%B8%D0%BD%D0%B0's gravatar image


9917

А что такое $%K_2$%?

(22 Апр '15 9:50) falcao
10|600 символов нужно символов осталось
1

Помечаем начало пленки любым символом из алфавита пленки, например, можно пометить символом $%\square $%, перемещаем головку вправо и переходим в другое состояние, далее в зависимости от символа:
Если $%|$%, переходим в состояние $%{q_{rej}}$% и останавливаем машину.
Если символ $%\{ $%, переходим в определенное состояние, через которое наша цель будет зачеркнуть $%\{ $% или заменить символом из алфавита пленки -> переместить головку до $%|$% -> перемещать головку вправо до тех пор, пока мы читаем зачеркнутые символы и пока не прочтем $%\{ $% или $%\} $% или $%\square $%.

В общем, идея зачеркивать символы по левую сторону от черточки, двигатся вправо до тех пор, пока не найдем черточку, и искать такой же первый незачеркнутый символ по правую сторону от черточки. Далее нужно правильно реализовать логику и случаи остановки. Машина должна остановится и принять решение только в случае, если кол-во зачеркнутых символов до черточки равно кол-ву зачеркнутых символов после черточки. Черточка вам дана как определитель середины строки, у которой первая половина должна быть идентична правой половине.

Это самый простой и базовый пример для построения машины Тюринга. Обычно формулировка звучит: "Построить детерминированную машину Тюринга с одной пленкой, которая будет распозновать язык $%L = \{ w\# w|w \in {\{ a,b\} ^*}\} $% над алфавитом $%\{ a,\# ,b\} $%". Допустим, мы записали на пленке слово $%ab\# ab$% и включили машину. Ее головка бут передвигатся влево и вправо зигзагом, анализируя символы и заменяя/зачеркивая определенные символы до тех пор, пока машина не поймет, что стринг слева не равен стрингу справа или пока не зачеркнет все символы: $$\square ab\# ab\square \to \square xb\# ab\square \to \square xb\# xb\square \to \square xx\# xx\square \to {q_{acc}}$$ $$\square ab\# aa\square \to \square xb\# aa\square \to \square xb\# xa\square \to \square xx\# xa\square \to b \ne a \to {q_{rej}}$$

Вот два простеньких примера, когда машина примет стринг и когда не примет.

Собственно, помечать начало не обязательно. Можно сразу зачеркнуть первый символ, перейти в состояние, через которое мы попытаемся найти по правую сторону от решетки такой же символ на такой же позиции.

Вот более подробная иллюстрация процесса над алфавитом $%\{ 0,\#,1\} $%:

alt text

Сама машина выглядит так:

alt text

ссылка

отвечен 22 Апр '15 3:27

изменен 22 Апр '15 8:22

%D0%92%D0%B8%D1%82%D0%B0%D0%BB%D0%B8%D0%BD%D0%B0's gravatar image


9917

Спасибо большое!

(22 Апр '15 11:45) svain
10|600 символов нужно символов осталось
Ваш ответ

Если вы не нашли ответ, задайте вопрос.

Здравствуйте

Математика - это совместно редактируемый форум вопросов и ответов для начинающих и опытных математиков, с особенным акцентом на компьютерные науки.

Присоединяйтесь!

отмечен:

×153

задан
22 Апр '15 2:50

показан
418 раз

обновлен
22 Апр '15 11:45

Отслеживать вопрос

по почте:

Зарегистрировавшись, вы сможете подписаться на любые обновления

по RSS:

Ответы

Ответы и Комментарии

Дизайн сайта/логотип © «Сеть Знаний». Контент распространяется под лицензией cc by-sa 3.0 с обязательным указанием авторства.
Рейтинг@Mail.ru