Студопедия

Главная страница Случайная страница

КАТЕГОРИИ:

АвтомобилиАстрономияБиологияГеографияДом и садДругие языкиДругоеИнформатикаИсторияКультураЛитератураЛогикаМатематикаМедицинаМеталлургияМеханикаОбразованиеОхрана трудаПедагогикаПолитикаПравоПсихологияРелигияРиторикаСоциологияСпортСтроительствоТехнологияТуризмФизикаФилософияФинансыХимияЧерчениеЭкологияЭкономикаЭлектроника






Пример нестандартной машины Тьюринга






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

А = { а 0, а 1, а 2},

множеством ее состояний -

Q ={ q 1, q 2, q 3, q 4, q 0},

а таблица переходов имеет вид:

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

аi Q \ { q 0} а 0 а 1 а 2
q 1 a 2 q 3 l a 1 q 2 r a 2 q 1 l
q 2 a 0 q 2 s a 2 q 1 s a 1 q 2 s
q 3 a 0 q 0 r a 1 q 4 r a 2 q 1 s
q 4 a 1 q 3 s a 0 q 4 r a 2 q 4 r

Рисунок 1 - Диаграмма (граф) переходовдля данной машины

Как работает эта машинa?

1-я (начальная) конфигурация:

Выполненная команда: a2q1l

2-я конфигурация:

Выполненная команда: a2q1l

3-я конфигурация:

Выполненная команда a2q3l

4-я конфигурация:

Выполненная команда a 0 q 0 r

5-я конфигурация:

Заключительное состояние

Так как в пятой конфигурации машина перешла в состояние q0, то слово а2а2а2является результатом и машина остановится.

 


Поделиться с друзьями:

mylektsii.su - Мои Лекции - 2015-2024 год. (0.006 сек.)Все материалы представленные на сайте исключительно с целью ознакомления читателями и не преследуют коммерческих целей или нарушение авторских прав Пожаловаться на материал