27. Расширения мт. Многодорожечные мт. Недетерминированные мт.

Многоленточная МТ. Устройство имеет КУ (состояния) и некоторое конечное число лент. Каждая лента разделена на клетки, и каждая из них может содержать символ из алфавита.

Любой язык, допускаемый многоленточной

МТ является рекурсивно-перечислимым.

Теорема о временной сложности. Время необходимое одноленточной МТ N для имитации n переходов многоленточной МТ М, есть Ο(n²).

Недетерминированная МТ отличается от изученных МТ тем, что ее δ(q, x) для каждого q и ленточного символа x представляет собой множество троек.

δ(q, x)={(q₁, Y₁, D₁), (q₂, Y₂, D₂), …, (q_n, Y_n, D_n)}. НМТ может выбирать любую из троек для следующего перехода. Язык же допускаемый НМТ определяется также как и другими недетерминированными автоматами. Также НМТ допускают языки, допускаемые детерминированными автоматами (это утверждение основано на том что для недетерминированного автомата можно построить эквивалентный ему детерминированный)

28 Мт с ограничениями. Мт с полубесконечной лентой. Мультистековые мт. Счетчиковые мт.

Ограниченным МТ запрещается записывать пробел вместо других ленточных символов. Это ограничение говорит о то, что МО состоят только из значащих символов и всегда начинаются только левым концом ленты.

МТ с односторонними лентами.

В обычной МТ допускалось, что головка машины может находиться как слева, так и справа от начальной позиции, однако достаточно того, что головка находиться на ней или только справа от нее. В действительности можно считать, что лента является бесконечной только в одну сторону.

Такая МТ может имитировать обычную МТ, единственно, что эта МТ содержит две дорожки (одна бесконечна справа, другая слева).

Мультистековые машины.

Данная модель МТ построена на обобщениях магазинных автоматов. Вначале определим, что МП автомат с одним магазином не может допустить язык МТ, но вот присутствие двух магазинов уже позволяет допускать такой язык.

М ултистековая машина представляет собой детерминированный МП-автомат с n-магазинами. Он получает свои входные данные, как и МП-автомат, из некоторого их источника, а не ленты или из магазина. Переход мультистековой машины основывается на состоянии, входном символе и верхних символах всех магазинов.

Счетчиковая машина. Эту машину можно представить одним из двух способов:

1. Счетчиковая машина имеет ту же самую структуру, как и мультистековая, но вместо магазинов у нее счетчики. Они содержат произвольное не отрицательное число, но отличить можно только нулевое от ненулевого. Т.о. переход счетчиковой машины зависит от ее состояния, входного символа и того, какие из счетчиков являются нулевыми. За один переход машина может изменить состояние и отнять 1 от одного из счетчиков (у счетчика со значением ноль 1 отнимать нельзя).

2. Также счетчиковая машина может рассматриваться, как мультистековая с ограничениями: 1) Есть только два магазинных символа Z₀ и Х; 2) в начале Z₀ находиться в каждом магазине; 3) Z₀ можно заменить только на цепочку ХZ₀

Каждый язык, допускаемый счетчиковой машиной, рекурсивно перечислим. Причина в том, что счетчиковая машина является частным случаем магазинных, а та в свою очередь частным случаем многоленточных МТ.

Каждый язык, допустимый односчетчиковой машиной, является КС-языком.