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




Связь машин Тьюринга и грамматик типа 0


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

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

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

Доказательство. Пусть

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

Tm = (Q, \Sigma, \Gamma, D, q_0, F)

где

\Gamma=Т \cup \Sigma \cup \{B,\sharp,X\}

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

N \cup \Sigma
.

Вначале Tm содержит на входной ленте

w \in \Sigma^*
. 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 печатает на ленте строку вида

\sharp w \sharp y \sharp , y \in V^*
в точности, если
S \Rightarrow _{G*y}
. Если y = w, Tm допускает L.




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