143
правки
Изменения
определение переехало
= Теорема =
Вначале <tex>Tm</tex> содержит на ленте <tex>w \in \Sigma^*</tex>. <tex>Tm</tex> вставляет <tex>\#</tex> перед <tex>w</tex>, сдвигая все символы <tex>w</tex> на одну ячейку вправо, и <tex>\#S\#</tex> после <tex>w</tex>, так что содержимым ленты становится <Tex>\#w\#S\#</tex>.
Теперь <tex>Tm</tex> недетерминированно симулирует вывод <tex>G</tex>, начиная с <tex>S</tex>. Каждая [[Формальные грамматики#sform|сентенциальная форма вывода ]] появляется по порядку между последними двумя <tex>\#</tex>. Если некоторый выбор переходов ведет к терминальной строке, она сравнивается с <tex>w</tex>. Если они совпадают, <tex>Tm</tex> допускает.
Формально, пусть <tex>Tm</tex> имеет на ленте <tex>\#w\#A_1A_2...A_k\#</tex>. <tex>Tm</tex> передвигает недетерминированно головку по <tex>A_1A_2...A_k</tex>, выбирая позицию <tex>i</tex> и константу <tex>r</tex> между <tex>1</tex> и максимальной длиной левой части любого правила вывода в <tex>P</tex>. Затем <tex>Tm</tex> проверяет подстроки <tex>A_iA_{i+1}...A_{i+r-1}</tex>. Если <tex>A_iA_{i+1}...A_{i+r-1}</tex> — левая часть некоторого правила вывода из <tex>P</tex>, она может быть заменена на правую часть. <tex>Tm</tex> может сдвинуть <tex>A_{i+r}A_{i+r+1}...A_k\#</tex> либо влево, либо вправо, освобождая или заполняя место, если правая часть имеет длину, отличную от <tex>r</tex>.
