|
Персональные инструменты |
|||
|
Машина Тьюринга:Распознавание строки, с одинаковым количеством 0 и 1Материал из CustisWikiВерсия от 20:15, 17 октября 2005; BenderBot (обсуждение | вклад) (реплицировано из внутренней CustisWiki) Это снимок страницы. Он включает старые, но не удалённые версии шаблонов и изображений. Приведем пример машины Тьюринга, распознающей строчки с одинаковым количеством нулей и единиц. СодержаниеТабличное представление МТMT={ 'k':1, 'start': 's', 'stop': 'q', 'program': { #(Состояние, символы на лентах) -> (новое состояние, (действия по каждой ленте)) ('s', ('.')): ('s', (('.','R'))), #проматываем уничтоженные символы ('s', ('0')): ('skip0', (('.','R'))), #стираем один ноль, ('s', ('1')): ('skip1', (('.','R'))), #стираем одну единицу ('s', ('*')): ('2ok', (('*','L'))), #не нашли 1 и 0 - видимо все ок... ('skip0', ('0')): ('skip0', (('0','R'))), #проматываем 0-ли ('skip0', ('.')): ('skip0', (('.','R'))), #проматываем уничтоженные символы ('skip0', ('*')): ('2fail', (('*','L'))), #так и не нашли симметричную единицу ('skip0', ('1')): ('2start', (('.','L'))), #стираем симметричную единицу ('skip1', ('1')): ('skip1', (('1','R'))), #проматываем 1-цы. ('skip1', ('.')): ('skip1', (('.','R'))), #проматываем уничтоженные символы ('skip1', ('*')): ('2fail', (('*','L'))), #так и не нашли симметричный ноль ('skip1', ('0')): ('2start', (('.','L'))), #стираем симметричный ноль ('2start', ('0')): ('2start', (('0','L'))), #проматываем, все, ('2start', ('1')): ('2start', (('1','L'))), #кроме маркера начала данных ('2start', ('.')): ('2start', (('.','L'))), ('2start', ('*')): ('s', (('*','R'))), #тогда становимся на первый символ ('2ok', ('.')): ('2ok', (('*','L'))), #проматываем, в начало. ('2ok', ('*')): ('ok', (('*','R'))), # ('ok', ('*')): ('q', (('1','R'))), # пишем "1" и выходим. ('2fail', ('.')): ('2fail', (('*','L'))), #проматываем в начало. ('2fail', ('0')): ('2fail', (('*','L'))), #проматываем в начало. ('2fail', ('1')): ('2fail', (('*','L'))), #проматываем в начало. ('2fail', ('*')): ('fail', (('*','R'))), # до начала ('fail', ('*')): ('q', (('0','R'))) # до начала } } Графовое представление МТ
Примеры выполнения МТНа пустой строкеНа «10»На «00»На «110»На «1001»На «1100»Внимание! Эта статья была создана путем автоматического реплицирования из внутренней базы знаний компании Заказные Информ Системы. Любые правки этой статьи могут быть перезаписаны при следующем сеансе репликации. Если у вас есть серьезное замечание по тексту статьи, запишите его в раздел «discussion». |
||