Как приступить к созданию машин Тьюринга для конкретных языков?

до сих пор я столкнулся с двумя типами языков. Языки, в которых существует строгий формат, например

L = {a^n b^n c^n | n >= 1}

Этот язык строг, например, a всегда будет стоять перед b и т. д.

другой тип, с которым я столкнулся, - это языки, где может быть любой порядок.

L = {a,b}*, где количество a > количество b

этот язык может быть любым порядком а и б, он не застрял на месте.

Для структурированных языков эта машина передает общую идею

но у меня возникли проблемы с поиском шаблона для машин, где может быть любой порядок символов.

Например

L = {а,б,с}* | a равны минимуму b и c

Каков шаблон для этих языков? и каковы некоторые действительно полезные методы для их разработки?


turing-machines formal-languages automata
person EaEaEa    schedule 29.06.2017    source источник
comment
По причинам, подобным тому, почему существует проблема остановки, не существует общего подхода для решения всех проблем. Если бы это было так, вы могли бы передать требования к машине, которая определяет, останавливается ли данная машина на заданном входе, и общий подход привел бы к машине H, что невозможно. Спецификация машины Тьюринга — это программное обеспечение, и не существует общего решения для написания программного обеспечения, которое решает все проблемы, и точно так же не существует общего решения для спецификации машин Тьюринга. Вы должны подумать о проблеме и найти решение самостоятельно.   -  person Welbog    schedule 29.06.2017
comment
Я знаю, но для приведенных выше примеров, похоже, есть общая структура. только для этих типов языков. Вы, возможно, имеете какое-либо представление о том, как создавать ТМ, как в некоторых техниках? например, выписывание принятых/отклоненных строк. и т.п.   -  person EaEaEa    schedule 29.06.2017
comment
Я бы подошел к этому так же, как и к обычным языкам программирования: разделить части на управляемые части. Например, часть, которая считает определенный символ, часть, которая находит минимум двух отсчетов, и часть, которая вызывает другие части в правильном порядке.   -  person Welbog    schedule 29.06.2017
comment
Повторим то, что сказал Велбог: подходите к этому так же, как к написанию любой другой программы. ТМ — это просто еще один язык программирования, на котором можно научиться писать программы; применимы общие правила, такие как повторно используемый код, разделение задач и т. д.   -  person Patrick87    schedule 29.06.2017

Ответы (1)


arrow_upward
0
arrow_downward

Ваш пример #a > #b является классическим для контекстно-свободного языка, который распознается автоматом выталкивания вниз. Эти устройства перемещаются по входу только один раз и имеют магазин с продавливанием (стек). Основная идея состоит в том, чтобы помещать a в стек для каждого a, который вы читаете во входных данных; для b вы удалите один. Найдите способ обрабатывать префиксы, где у вас больше b, чем a. Затем вы принимаете точно, если у вас осталось некоторое количество a в стеке после чтения всего ввода.

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

Если у вас нет вспомогательных лент, вам придется больше бегать с головкой чтения-записи. Например, используйте структуру:

input%stack1%stack2%stack3%

где % — разделительный символ, который больше нигде не встречается. Другим вариантом является подход, не отделяющийся от выталкивающего автомата: маркировка символов. Например, для #a > #b:

  1. отметить первый неотмеченный b
  2. отметить первый неотмеченный a
  3. если остались неотмеченные b, перейти к 1.; иначе проверьте, есть ли хотя бы один неотмеченный левый - если да, то примите, иначе отклоните

Это две стандартные техники, которые вы можете использовать для решения этих задач на счет. Конечно, как уже прокомментировали люди, для каждого данного языка вы должны адаптировать свое решение.

person Peter Leupold    schedule 30.06.2017