Мы кодируем содержимое ленты машины Тьюринга в предложениях; специальный набор нетерминалов кодирует текущее состояние. В любой момент времени может быть только один из них в форме предложения, расположенный справа от символа, на который в данный момент указывает ТМ.
Вторая важная идея заключается в том, что мы должны повернуть процесс вспять : TM принимают слово в качестве ввода и преобразуют его в или 0 , или они не заканчиваются. Грамматика, однако, должна генерировать слово. К счастью, грамматика по своей природе недетерминирована, поэтому мы можем просто позволить ей «угадать», откуда взялся принимающий 1 ; тогда могут быть сгенерированы все слова, которые заставляют ТМ принять.101
Пусть множество состояний-нетерминалов; wlog, пусть Q 0 будет нетерминалом начального состояния, а Q F ⊆ Q - множеством принимающих состояний-нетерминалов. Во-первых, нам нужны стартовые правила, которые генерируют все возможные принимаемые конфигурации:Q ={ Q0, … , QК}Q0QF⊆ Q
S→ # 1 Qе#для всех .Qе∈ QF
Точно так же мы завершаем работу, когда мы «достигаем» начального состояния в правильной позиции, а именно на первом символе:
# a Q0→ # aдля всех .a ∈ Σ
Перевести фактические переходы состояний просто:
aQaQbabQ→cQ′ for a,c∈Σ∧(a,Q,N)∈δ(c,Q′)→acQ′ for a,b,c∈Σ∧(b,Q,L)∈δ(c,Q′)→cQ′b for a,b,c∈Σ∧(a,Q,R)∈δ(c,Q′)
Есть некоторые технические перегибы, чтобы сгладить; например, вы должны избавиться от маркеров границы в конце. Это можно сделать, породив два специальных нетерминала вместо завершения, поменяв их местами, а затем удалив # вместе с ними. Кроме того, больше # должно быть создано по требованию; это требует некоторого взлома правил с d = # .###d=#
Кроме того, конструкция становится немного более сложной, если ТМ использует не входные символы. В этом случае правила завершения могут быть неправильными: если где-то на ленте есть не входные символы, мы не сгенерировали правильное слово. Это можно исправить аналогично удалению : порождает специальный нетерминал из Q 0, который переставляется вправо и удаляется только в том случае, если все символы из Σ .#Q0Σ