Машина Тьюринга:Распознавание строки, с одинаковым количеством 0 и 1 — различия между версиями

Версия 16:49, 5 марта 2007

Приведем пример машины Тьюринга, распознающей строчки с одинаковым количеством нулей и единиц.

Табличное представление МТ

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»