Как я могу преобразовать машину Тьюринга, распознающую язык

19

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

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

Ава Петрофски
источник

Ответы:

9

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

Вторая важная идея заключается в том, что мы должны повернуть процесс вспять : TM принимают слово в качестве ввода и преобразуют его в или 0 , или они не заканчиваются. Грамматика, однако, должна генерировать слово. К счастью, грамматика по своей природе недетерминирована, поэтому мы можем просто позволить ей «угадать», откуда взялся принимающий 1 ; тогда могут быть сгенерированы все слова, которые заставляют ТМ принять.101

Пусть множество состояний-нетерминалов; wlog, пусть Q 0 будет нетерминалом начального состояния, а Q FQ - множеством принимающих состояний-нетерминалов. Во-первых, нам нужны стартовые правила, которые генерируют все возможные принимаемые конфигурации:Q={Q0,,Qk}Q0QFQ

S#1Qf#для всех .QfQF

Точно так же мы завершаем работу, когда мы «достигаем» начального состояния в правильной позиции, а именно на первом символе:

#aQ0#aдля всех .aΣ

Перевести фактические переходы состояний просто:

aQcQ  for a,cΣ(a,Q,N)δ(c,Q)aQbacQ for a,b,cΣ(b,Q,L)δ(c,Q)abQcQb for a,b,cΣ(a,Q,R)δ(c,Q)

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

Кроме того, конструкция становится немного более сложной, если ТМ использует не входные символы. В этом случае правила завершения могут быть неправильными: если где-то на ленте есть не входные символы, мы не сгенерировали правильное слово. Это можно исправить аналогично удалению : порождает специальный нетерминал из Q 0, который переставляется вправо и удаляется только в том случае, если все символы из Σ .#Q0Σ

Рафаэль
источник