|
[math]\Rightarrow[/math]
Пусть [math]G = (N, \Sigma, P, S)[/math] — грамматика и [math]L = L(G)[/math]. Опишем неформально недетерминированную машину Тьюринга [math]Tm[/math], допускающую [math]L[/math].
[math]Tm = (Q, \Sigma, \Gamma, D, q_0, F)[/math], где [math]\Gamma = T \cup \Sigma \cup \{B,\#,X\}[/math] и [math]B,\#,X \notin N \cup \Sigma[/math]
Вначале [math]Tm[/math] содержит на ленте [math]w \in \Sigma*[/math]. [math]Tm[/math] вставляет [math]\#[/math] перед [math]w[/math], сдвигая все символы [math]w[/math] на одну ячейку вправо, и [math]\#S\#[/math] после [math]w[/math], так что содержимым ленты становится [math]\#w\#S\#[/math].
Теперь [math]Tm[/math] недетерминированно симулирует вывод [math]G[/math], начиная с [math]S[/math]. Каждая сентенциальная форма вывода появляется по порядку между последними двумя [math]\#[/math]. Если некоторый выбор переходов ведет к терминальной строке, она сравнивается с [math]w[/math]. Если они совпадают, [math]Tm[/math] допускает.
Формально, пусть [math]Tm[/math] имеет на ленте [math]\#w\#A_1A_2...A_k\#[/math]. [math]Tm[/math] передвигает недетерминированно головку по [math]A_1A_2...A_k[/math], выбирая позицию [math]i[/math] и константу [math]r[/math] между [math]1[/math] и максимальной длиной левой части любого правила вывода в [math]P[/math]. Затем [math]Tm[/math] проверяет подстроки [math]A_iA_{i+1}...A_{i+r-1}[/math]. Если [math]A_iA_{i+1}...A_{i+r-1}[/math] — левая часть некоторого правила вывода из [math]P[/math], она может быть заменена на правую часть. [math]Tm[/math] может сдвинуть [math]A_{i+r}A_{i+r+1}...A_k\#[/math] либо влево, либо вправо, освобождая или заполняя место, если правая часть имеет длину, отличную от [math]r[/math].
Из этой простой симуляции выводов в [math]G[/math] видно, что [math]Tm[/math] печатает на ленте строку вида [math]\#w\#y\#[/math], [math]y \in V*[/math] в точности, если [math]S \Rightarrow * y[/math]. Если [math]y = w[/math], [math]Tm[/math] допускает [math]L[/math]. |
