Машина Тьюринга - навыки обучения - PullRequest
Новая
       1

Машина Тьюринга - навыки обучения

2 голосов
/ 07 ноября 2010

Мне потребовался целый месяц, чтобы решить эту проблему, как я понял из первой книги упражнения, и я хотел бы знать, как написать это в машине Тьюринга; Я бы очень хотел узнать это. Пожалуйста, кто-нибудь может предложить помощь?

Рассмотрим последние две буквы вашего логина (если обе буквы одинаковы, пожалуйста, выберите следующая буква в латинском алфавите как ваш второй символ). Написать машину Тьюринга который распознает язык Stretch (x + 1). Это язык всех строк, которые содержат непрерывную строку вхождений из двух букв, за которыми следует «*», сопровождаемый другой строкой букв с x + 1 появлением каждой буквы где в первой строке букв было единственное вхождение. Здесь x = 1. Входные данные для машины - ненулевые строки a, b, *. Как Например, где буквы «a» и «b» (и x = 1) aba * aabbaa, bb * bbbb и baab * bbaaaabb на языке, а abb * abbb нет. Вы можете предположить, что вы есть подпрограммы для записи 0 в первой ячейке и удаления оставшейся части ленты и для запись 1 в первой ячейке и удаление оставшейся части ленты.

Я был бы очень признателен, если бы вы могли мне помочь.

1 Ответ

3 голосов
/ 07 ноября 2010

Используйте стопку для каждой уникальной буквы (два стека, в ваших примерах).Это официально не написано или что-то еще, но все, что вам нужно сделать, это предоставить алгоритм, который доказывает, что ТМ может решить проблему. 

F1:
FOREACH letter DO
  IF letter = '*' THEN F2
  ELSE push letter twice onto its respective stack

F2:
FOREACH letter DO
  IF tape is empty THEN F3
  IF respective stack is empty THEN *fail state*
  ELSE pop respective stack

F3:
IF both stacks are empty THEN *accept state*
ELSE *fail state*

Понять идею?Доказательства ТМ - это весело.

РЕДАКТИРОВАТЬ : В ответ на ваши другие посты, если вы не понимаете, как создать доказательство ТМ, вам нужно немного прочесть о доказательствах в целом,Я бы предложил Введение Майкла Сипсера в Теорию вычислений .После того, как вы раскроете руку и ногу для этого текста, вы можете обратиться к странице 137, чтобы узнать все о ТМ.

...