Теория и реализация языков программирования


         

допускает L. Построим грамматику G,


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

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


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

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

, где


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

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


Используя правила 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.


Содержание  Назад  Вперед