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




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


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

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

Tm = (Q, \Sigma, \Gamma, D, q_0, F)
допускает L. Построим грамматику G, которая недерминированно генерирует две копии представления некоторого слова из
\Sigma^*

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

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

G=(N, \Sigma, P, A_1)
, где
N=([\Sigma \cup \{e\}]\times \Gamma)\cup Q \cup \{A_1,A_2,A_3\}

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

  1. A_1 \rightarrow q_0 A_2
  2. A_2 \rightarrow [a, \; a] A_2
    для каждого
    a \in \Sigma
  3. A_2 \rightarrow A_3
  4. A_3 \rightarrow [e,B]A_3
  5. A_3 \rightarrow e
  6. q[a, \; C] \rightarrow [a,E]p
    для каждого
    a \in \Sigma \cup \{e\}
    и каждого
    q \in Q
    и
    С \in \Gamma
    такого, что
    D(q, \; C)=(p,\; E, \; R)
  7. [b, \; I]q[a, \; C] \rightarrow p[b, \; I][a, \; J]
    для каждого C, J, I из
    \Gamma
    , a и b
  8. [a,C]q \rightarrow qaq, \; q[a, \; C] \rightarrow qaq, \; q \rightarrow e
    для каждого
    a \in \Sigma \cup \{e\}, C \in \Gamma, q \in F.

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

A_1\Rightarrow^* \; q_0[a_1, \; a_1][a_2, \; a_2]\ldots [a_n, \; a_n]A_2

где

a_i \in \Sigma
для некоторого
i

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

A_1\Rightarrow^* \; q_0[a_1, \; a_1][a_2, \; a_2]\ldots [a_n, \; a_n][e, \; B]^m

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

(\Sigma \cup \{e\}) \times \Gamma
никогда не меняются. Индукцией по числу шагов Tm можно показать, что если

(q_0, \; a_1a_2 \ldots a_n, \;1)\vdash_{Tm*} \; (q, \; X_1 X_2 \ldots X_S, \; r)
, то

q_0[a_1,a_1][a_2,a_2] \ldots [a_n,a_n][e,B]^m \Rightarrow_{G*}

\Rightarrow_{G*} [a_1,X_1][a_2,X_2] \ldots [a_{r-1},X_{r-1}]q[a_r,X_r] \ldots [a_{n+m},X_{n+m}]

где a1, a2, ... an принадлежат

\Sigma
, an+1 = an+2 = ... an+m = e,

X1 X2, ...Xn+m принадлежат

\Gamma
и XS+1=XS+2=...Xn+m=B

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

\begin{multline} (q_0,a_1 a_2 \ldots a_n , \; 1)\vdash_{Tm*}\notag \\ \vdash_{Tm*} \; (q_1,X_1X_2 \ldots X_r,j_1)\vdash_{Tm*} \notag \\ \vdash_{Tm*}(q_2,Y_1Y_2 \ldots Y_S,j_2) \end{multline}

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

\begin{multline} q_0[a_1, a_1 ][a_2,a_2] \ldots [a_n,a_n][e,B]^m \Rightarrow_{G^*}\notag \\ \Rightarrow_{G^*}[a_1,X_1][a_2,X_2] \ldots [a_{r-1},X_{r-1}]q_1[a_{j1},X_{j1}]\ldots \notag \\ \ldots [a_{n+m},X_{n+m}] \end{multline}

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

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

q_1[a_{j1},X_{j1}]\rightarrow [a_{j1},Y_{j1}]q_2 \; или

[ a_{j1-1},X_{j1-1} ] q_1[a_{j1},X_{j1}] \rightarrow q_2[a_{j1-1},X_{j1-1}][a_{j1},Y_{j1}]

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

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

i \neq j_1
.

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

\begin{multline} q_0[a_1,a_1][a_2,a_2] \ldots [a_n,a_n][e,B]^m \Rightarrow^{G*} \notag \\ \Rightarrow^{G*} \; [a_1,Y_1]q_2[a_{j2},Y_{j2}] \ldots [a_{n+m},Y_{n+m}] \end{multline}

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

По правилу 8, если

q \in F
, легко показать, что

[a_1,X_1] \ldots q[a_j,X_j] \ldots [a_{n+m},X_{n+m}]\Rightarrow^* a_1 a_2 \ldots a_n.

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

A_1 \Rightarrow_{G*} w
только если w допускается Tm.




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