Главная | Обратная связь | Поможем написать вашу работу!

Применение машин Тьюринга к словам

Пример 1. Дана МТ с внешним алфавитом А = {Λ, а } и алфавитом внутренних состояний Q ={0, 1, 2} (причем 1 – начальное состояние, 0 – конечное состояние) и следующей функциональной схемой-программой

(Λ,1) → (Λ, 2П), (Λ,2) → (а,0), (а,1) → (а, 1) → (а, 1П), (а,2) →(а, 2П).

Посмотрим в какое слово переработает эта машина слово а Λ а. Будем последовательно выписывать конфигурации машины при переработке ею этого слова.

На первом шаге действует команда (а, 1) → (а, 1П)

В результате на машине создается конфигурация

На втором шаге действует команда (Λ,1) → (Λ, 2П) и на машине создается конфигурация

Наконец, третий шаг обусловлен командой (Λ,2) → (а,0). В результате него создается конфигурация

Эта конфигурация является заключительной, потому что машина оказалась в состоянии остановки 0. Таким образом, исходное слово а Λ а переработалось в слово а Λ а Λ а.

Пример 2. МТ задается внешним алфавитом А = {Λ, а, б} и алфавитом состояний Q = {0, 1, 2, 3} и программой, заданной в виде таблицы

А\ Q
Λ	Λ1Л	а3П	Λ1Л
а	Λ2Л	а2Л	а3П
б	Λ0	б2Л	б3П

Применим эту машину к слову а а б а а.

Конструирование МТ

Пример 3. Построить такую машину Тьюринга, которая из записанных подряд n букв а оставляла бы на ленте n - 2 (n > 2) буквы.

В качестве внешнего алфавита возьмем множество А = {Λ, а}. Количество внутренних состояний будет определено в процессе составления программы. Считаем, что машина начинает работать из стандартного начального состояния, то есть когда в состоянии 1 обозревается крайняя правая буква а из n записанныхна ленте.

Начнем с того, что сотрем первую букану а и перейдем к обозрению следующей левой ячейки и сотрем там а, если она в этой ячейке записана. На каждом шаге машина должна переходить в другое внутренне состояние, ибо в противном случае будут стерты вообще все буквы а записанные подряд. Вот команды, осуществляющие эти действия: (а,1) → (Λ,2Л); (а,2) → (Λ, 3Л). Машина находится в состоянии 3 и обозревает третью справа ячейку из тех, в которые записано это слово. Не меняя содержимого этой ячейки, машина должна остановиться, т.е. перейти в заключительное состояние 0, независимо от содержимого ячейки. Вот эти команды (Λ,3) → (Λ,0), (а,3) → (а, 0).

Пример 4. Построить МТ применимую ко всем словам в алфавите и переводящую их в слово .

Рассмотрим алфавит внутренних состояний 0,1,2,3,…. Вначале с помощью команд (а,1) → (а,1П), (б,1) → (б,1П) проходим до конца слова, не изменяя его символов.

Признаком окончания слова будет считывание Λ в первом состоянии. С помощью команд (Λ,1) → (Λ, 2Л), (а,2) → (а,3Л), (б,2) → (б,3Л) движемся влево, не изменяя последнего символа слова.

Если в состоянии 3 считываем символ а, значит, и нужно стирать все символы слова кроме последнего. Это можно сделать при помощи команд

(а,3)→(Λ,4Л), (а,4)→(Λ, 4Л), (б,4) → (Λ, 4Л).

Если в состоянии 4 считывается Λ, значит вся работа проделана и пора останавливаться при помощи команды (Λ,4)→ (Λ, 0Н).

Если в состоянии 3 считываем символ б, значит и нужно все символы, кроме последнего заменить буквами б. Это делаем при помощи команд

(б,3)→(б,5Л), (а,5)→(б, 5Л), (б,5) → (б, 5Л).

Если в состоянии 5 считывается Λ, значит, все символы исходного слова пройдены, и можно переходить в состояние 0 с помощью команды (Λ,5)→ (Λ, 0Н).

Запишем программу Тьюринга в виде таблицы

А\ Q
Λ	Λ2Л			Λ0Н	Λ0Н
а	а1П	а3Л	Λ4Л	Λ4Л	б5Л
б	б1П	б3Л	Б5Л	Λ4Л	б5Л

Проверим работу построенной машины Тьюринга над словом абба

Итак, в слове абба предпоследний символ б, и все буквы исходного слова, кроме последней заменены буквой б.

Проверим работу построенной МТ над словом ббаа

В слове ббаа предпоследний символ – а, и все буквы исходного слова, кроме последней заменены пустыми символами Λ.

⇐ Предыдущая 1 23

Воспользуйтесь поиском по сайту: