|
Персональные инструменты |
![]() |
||
|
![]() |
![]() Машина Тьюринга:Распознавание строки, с одинаковым количеством 0 и 1Материал из 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». |
![]() |
||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||
![]() |
![]() |