Понимание распознавателей и решателей в теории вычислений

Question

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

Когда говорят, что машина Тьюринга T распознает язык L, где

L = { <A> | A is a DFA }

, где DFA =детерминированный конечный автомат

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

То есть, если этот вход является членом L.Другой пример - сказать, что парень Х - это узнаватель своего отца, поскольку, что бы вы ни ставили перед ним, он сможет сказать вам, является ли то, что перед ним, его отцом или нет.Это правильно?Какая часть неверна?

С другой стороны, decider над языком, по-видимому, является машиной Тьюринга, которая никогда не loops, то есть она всегда останавливается в состоянии принятия или отклонениядля любого входа.Разве это не будет похоже или так же, как я объяснил выше о распознавателях?

Спасибо

Answer 1

После некоторого изучения, я думаю, что я понял разницу между ними.

Как всегда, дьявол кроется в деталях.

Для начала, решающим языком являетсявсегда узнаваемый язык .

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

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

Пример

Давайте разработаем какой-нибудь действительно простой язык:

L = { abc }

этот язык состоит только из слова abc.Это означает, что, чтобы доказать, что этот язык узнаваем, нужно создать одну машину, которая его принимает.Мы неофициально сделаем это:

M - это машина, которая при получении abc в качестве входных данных принимает в противном случае бесконечный цикл.

Эта машина принимает всех членов языкаL, так что это распознаватель для L. Тем не менее, для всех других входов он будет просто навсегда.Если существует машина, которая для каждого ввода принимает / отклоняет этот язык, он также может быть частью класса разрешимых языков.Можете ли вы построить его?

(предупреждение о спойлере !!! 11 @ # $! 1)

M '- это машина, которая при вводе abc в качестве вводапринимает, в противном случае отклоняет.

То есть, поскольку существует машина, которая распознает L и что независимо от того, что вы вводите, вы всегда либо принимаете / отклоняете, язык считается разрешимым.

Более того, если бы вы однажды заинтересовались созданием машины, которая распознает L, вы бы знали, что у вас есть по крайней мере одна машина, которая всегда может это сделать, не сталкиваясь с проблемой возможности принимать abc, но с треском проваливаясь вдругие дела нависают навсегда!

Answer 2

Простой ответ, как я думаю, таков:

Решение всегда останавливается, принимает или отклоняет

Но

Распознаватель не всегда останавливается, машина может принять, отклонить или выполнить цикл,Зацикливание означает, что машина не останавливается.

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

Answer 3

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

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

Чтобы выразить это на английском языке высокого уровня, решающий аппарат должен ответить «Да» или «Нет» на вопрос «Строка х на языке А» Распознаватель должен ответить «Да» на тот же вопрос, если строка написана на языке НО, если строка отсутствует, ему разрешено сказать «Нет» или «Без комментариев, т.е. цикл навсегда»

Answer 4

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