что язык распознается машиной Тьюринга

Докажем, что язык распознается машиной Тьюринга тогда и только тогда, когда он генерируется грамматикой типа 0. Для доказательства части "если" мы построим недетерминированную машину Тьюринга, которая будет Связь машин Тьюринга и грамматик типа 0 35 недетерминированно выбирать выводы в грамматике и смотреть, является ли вывод входом. Если да, машина допускает вход.

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

Теорема 2.4. Если L генерируется грамматикой типа 0, то L распознается машиной Тьюринга.

Доказательство. Пусть - грамматика типа 0 и L = L(G). Опишем неформально недетерминированную машину Тьюринга Tm, допускающую L.



где

Предполагается, что последние три символа не входят в .

Вначале Tm содержит на входной ленте . Tm вставляет # перед w, сдвигая все символы w на одну ячейку вправо, и #S# после w, так что содержимым ленты становится #w#S#.

Теперь Tm недетерминированно симулирует вывод в G, начиная с S. Каждая сентенциальная форма вывода появляется по порядку между последними двумя #. Если некоторый выбор переходов ведет к терминальной строке, она сравнивается с w. Если они совпадают, Tm допускает.

Формально, пусть Tm имеет на ленте #w#A1A2...Ak#. Tm передвигает недетерминированно головку по A1A2...Ak, выбирая позицию i и константу r между 1 и максимальной длиной левой части любого правила вывода в P. Затем Tm проверяет подстроки AiAi+1...Ai+r-1. Если AiAi+1...Ai+r-1

- левая часть некоторого правила вывода из P, она может быть заменена на правую часть. Tm может сдвинуть Ai+rAi+r+1...Ak# либо влево, либо вправо, освобождая или заполняя место, если правая часть имеет длину, отличную от r.

Из этой простой симуляции выводов в G видно, что Tm печатает на ленте строку вида в точности, если . Если y = w, Tm допускает L.



Теорема 2.5. Если L распознается некоторой машиной Тьюринга,то L генерируется грамматикой типа 0.

Доказательство. Пусть допускает L. Построим грамматику G, которая недерминированно генерирует две копии представления некоторого слова из

и затем симулирует поведение Tm на одной из копий. Если Tm допускает слово, то G трансформирует вторую копию в терминальную строку. Если Tm не допускает L, то вывод никогда не приводит к терминальной строке.

Формально, пусть

, где

Продукции таковы:

1. 
2. 
   для каждого
   
3. 
4. 
5. 
6. 
   для каждого
   
   и каждого
   
   и
   
   такого, что
   
7. 
   для каждого C, J, I из
   
   , a и b
8. 
   для каждого
   

Используя правила 1 и 2



где для некоторого

Предположим, что Tm допускает строку a1a2 ... an. Тогда для некоторого m Tm использует не более, чем m ячеек справа от входа. Используя правило 3, затем правило 4 m раз, и наконец, правило 5, имеем



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

, то





где a1, a2, ... an принадлежат , an+1 = an+2 = ... an+m = e,

X1 X2, ...Xn+m принадлежат и XS+1=XS+2=...Xn+m=B

Предположение индукции тривиально для нуля шагов. Предположим, что оно справедливо для k - 1 шагов. Пусть



за k шагов. По предположению индукции



Пусть E = L, если j2 = j1 - 1 и E = R, если j2 = j1 + 1. В этом случае D(q1, Xj1 ) = (q2, Yj1, E).

По правилам 6 или 7





в зависимости от того, равно ли E значению R или L.

Теперь Xi = Yi для всех .

Таким образом,



что доказывает предположение индукции.

По правилу 8, если , легко показать, что



Таким образом, G может генерировать a1a2 ... an, если a1a2 ... an допускается Tm. Таким образом, L(G) включает все слова, допускаемые Tm. Для завершения доказательства необходимо показать, что все слова из L(G) допускаются Tm. Индукцией доказывается, что только если w допускается Tm.


Содержание раздела

---

---