Пусть входная строка будет задана как . Затем, если NFA в настоящее время находится в состоянии (и прочитал входной алфавит ), то перед чтением следующего входного символа NFA разделяется на два NFA, один из которых находится в состоянии а другой - в , если происходит переход тип . Если существует цикл типа , где - некоторые состояния NFA, тогда бесполезно вспоминать другой NFA в состоянии до точки, где ввод был прочитан до алфавита r w i r s r ϵ → s r ϵ → s ϵ → q 1 . , , , & epsi ; → д к & epsi ; → г д я г ш I,
Если КПК (недетерминированный) находится в состоянии (и ввод читается до ) и существует цикл (где переход средство означает, что ничего после читается из ввода, ничего не выталкивается или не читается из стека, а алфавит помещается в стек), затем перед чтением следующего входного алфавита будет бесконечный КПК в состоянияхw i r ϵ , ϵ → a → s ϵ , ϵ → a → q 1 . , , , ϵ , ϵ → a → q k ϵ , ϵ → a → потому что в отличие от NFA, хотя состояния конечного стека могут быть разными (бесконечные возможности), если я не ошибаюсь.
Как и в случае с NFA и PDA, сила недетерминизма проистекает из переходов. Поэтому я предполагаю, что недетерминированная машина Тьюринга также получает свою недетерминированность от ϵ переходов, таких как NFA и PDA (больше похоже на PDA). Я знаю, что детерминированная машина Тьюринга может симулировать недетерминированную (я знаю доказательство, которое использует поиск в первую очередь). Но сейчас я сомневаюсь, как это возможно. Поскольку, если цикл типа, описанного выше в КПК, существует на диаграмме состояний недетерминированной машины Тьюринга, то перед чтением следующего символа w i + 1детерминированная машина Тьюринга даже при моделировании конфигурации в некоторой ветви недетерминированной машины Тьюринга (в то время как bfs) должна будет отслеживать бесконечную машину Тьюринга (опять-таки состояния конечны, но символы на ленте имеют бесконечные возможности).
Так как именно недетерминизм определяется в случае машин Тьюринга? Я неправильно понимаю что-то тривиальное? Используют ли недетерминированные машины Тьюринга переходы?
Я прошу прощения за мои тривиальные сомнения. Если что-то не так, я могу обновить свой вопрос.
Ответы:
Недетерминизм - это одно и то же понятие во всех контекстах - машине разрешено использовать несколько опций в любой заданной точке. Однако семантика немного отличается, так как DFA / NFA и PDA всегда определяют общие функции, тогда как машины Тьюринга (детерминированные или недетерминированные) в целом определяют частичные функции.
Частичная функция - это функция, определенная только для части домена. Если не определено на x, то мы пишем f ( x ) = ⊥ . (Таким образом, f на самом деле является полной функцией, но в диапазоне есть специальный элемент, обозначающий, что выходные данные не определены.) Детерминированная машина Тьюринга M определяет частичную функцию следующим образом: если M останавливается на x, то M ( x ) является содержимое ленты, когда M останавливается на x ; и в противном случае M ( x ) = ⊥f x f(x)=⊥ f M M x M(x) M x M(x)=⊥ ,
Детерминированная машина Тьюринга Решающий имеют два вида остановочных состояний, принятие и отказ, и определяет частичную функцию следующим образом : если останавливается на х на допускающем состоянии, то М ( х ) = 1 ; если он останавливается в состоянии отказа, то M ( x ) = 0 ; если он не останавливается, то M ( x ) = ⊥ . Если M всегда останавливается, мы говорим, что он принимает язык L = { x : M ( x)M x M(x)=1 M(x)=0 M(x)=⊥ M .L={x:M(x)=1}
Недетерминированной машине Тьюринга (которая всегда является решающим фактором) разрешается «ветвиться» (иметь несколько возможных вариантов в любой заданный момент времени) и имеет следующую семантику:
Учитывая это определение, мы надеемся, что будет ясно, как имитировать недетерминированную машину Тьюринга, используя детерминистское решение для машины Тьюринга: вы пробуете все ветви, проверяя, приводит ли какая-либо из них к принятию состояния остановки. После остановки всех веток вы можете решить, переходить ли в состояние принятия или в состояние отклонения. Если недетерминированная машина Тьюринга не останавливается на некоторой ветви, то будет и детерминированная.
Что о служит для перемещения? Они вызывают проблемы в том, что соответствующий автомат может никогда не остановиться. Для конечных автоматов (NFA и PDA) мы молчаливо игнорируем вычисления без остановки. Наша причина для этого заключается в том, что полученные языки всегда вычислимы, хотя наивный алгоритм их детерминированного моделирования (имитация всех путей вычислений) не совсем работает. Это не так сложно для НФА, которые могут быть преобразованы в ДФА. Однако детерминированные КПК строго слабее, чем недетерминированные КПК. Тем не менее, вы можете показать, что каждый КПК эквивалентен одному без ϵ- перехода (хотя доказательство может проходить через контекстно-свободные грамматики).ϵ ϵ
Вы можете смоделировать перемещения в машинах Тьюринга, но вы должны быть осторожны, чтобы не было циклов, которые бы приводили к непрерывным вычислениям. Однако в некоторых случаях мы можем использовать тот же прием, что и выше. Например, предположим, что ваша машина Тьюринга ограничена в пространстве: мы знаем верхнюю границу используемого пространства (в зависимости от длины ввода). В этом случае каждое вычисление без остановки обязательно циклично (поскольку машина Тьюринга имеет конечное число состояний, включая содержимое ленты), и поэтому, если мы «игнорируем» вычисления без остановки, как указано выше, полученная модель вычисления все еще вычислима. В более общем смысле, это работает до тех пор, пока нам гарантировано, что каждый не прекращающийся цикл вычислений. (Это касается NFA, но не PDA.)ϵ
источник