Файл: Алферова З.В. Теория алгоритмов учеб. пособие.pdf

ленточной головкой. За один шаг, зависящий от ее состояния и символов, считываемых входной и ленточной головками, машина Тьюринга может:

1)изменить состояние;

2)изменить символ считываемой ленточной головкой;

3)передвинуть входную и ленточные головки на одну клетку • независимо в любом направлении.

конечное

управление

бесконечной

память

Рис. 23

Формально двусторонняя недетерминированная машина Тью­ ринга (или просто машина Тьюринга) обозначается так:

лов, ленточных символов и заключительных состояний соответствен­

осуществляет отображение вида С X X X Y—>S X Y X di X d2. Это означает, что машина Тьюринга М находится в состоянии s, считы­ вает х на входе и у на ленте, то она имеет право перейти в состоя­ ние «г напечатать непустой символ yi вместо у и передвинуть свои

стая часть ленты машины М. Входная и ленточная головки считы­

S} и у из Y множество b(s, х, у) содержит не более одного элемен-

154

2.10.2.Линейноограниченные автоматы

1.Машина Тьюринга с входной лентой называется линейноограниченной, если существует такое число с, что в процессе «до-

пускания» цепочки со машина не может использовать более чем с - | со) рабочих ячеек.

Таким образом, объем памяти такого автомата не является не­ ограниченным, как в машинах Тьюринга, а определяется длиной последовательности входных символов. Линейная зависимость меж­ ду объемом памяти и длиной входной последовательности опреде­ лила название этого класса автоматов — линейноограниченные ав­ томаты.

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

дующим образом. В начальный момент на входной ленте записана последовательность входных символов, так что левее крайнего ле­ вого символа последовательности и правее крайнего правого симво­ ла лента пуста, т. е. клетки заполнены символом Л . Автомат на­ ходится в состоянии s0 и считывает крайний левый символ входной последовательности, записанный на ленте.

Условие допустимости или приемлемости входной последова­ тельности для детерминированного линейноограниченного автома-

155

та те же, что и для двустороннего. Последовательность считается приемлемой, если считывающая головка сходит с правого конца за­ полненной части ленты и при этом управляющее устройство нахо­ дится в одном из состояний множества F.

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

Для детерминированных линейноограниченных автоматов дока­ зана следующая теорема.

Теорема 34 (Ландвебера). Множество цепочек, представимых линейноограниченным автоматом, есть язык типа 1, т. е. контекст­ но связанный.

Эта теорема, однако, не утверждает, что для любого языка ти­ па 1 существует детерминированный линейноограниченный автомат, который представляет этот язык. Вопрос о том, существует ли язык типа 1, не представимый детерминированным линейноограниченным автоматом, остается пока открытым. Доказана лишь подобная теорема для бесконтекстных языков.

Теорема 35 (Курода). Любой язык типа 2 представим в детер­ минированном линейноограниченном автомате.

Недетерминированным линейноограниченным автоматом с од­ ной лентой называется линейноограниченный автомат с одной лен­ ной, функция отображения которого неоднозначна, а начальным •состоянием может быть любое из состояний множества S0. Для недетерминированного линейноограниченного автомата входная последовательность считается приемлемой, если существует такой вариант работы автомата, что автомат сходит с правого конца за­ полненной ленты в одном из состояний s, множества F.

Область представимости недетерминированных линейноограни­ ченных автоматов определяется следующей теоремой.

Теорема 36 (Курода). Множество входных последовательностей является языком типа 1 тогда и только тогда, когда оно является множеством приемлемых последовательностей какого-либо недетеряинированного линейноограниченного автомата, т. е. когда это множество представимо таким автоматом.

Из этой теоремы и из того факта, что детерминированный ли­ нейноограниченный автомат заведомо не может делать больше, чем недетерминированный автомат такого же типа, следует, что класс -линейноограниченных автоматов обоих этих типов заведомо уже, чем класс машин Тьюринга, в том смысле, что область представи­ мости этих автоматов является точным включением области пред­ ставимости машин Тьюринга. В то же время класс линейноогра­ ниченных автоматов заведомо шире, чем класс конечных автома­ тов, которые, как мы увидим далее, представляют только языки типа 3. Следовательно, линейноограниченные автоматы являются промежуточными между конечными автоматами и машинами Тью­ ринга и притом адекватными определенному классу языков ти­ па 1 —контекстным языкам.

Теорема (37). Классы 2N и IN линейноограниченных автоматов

156

эквивалентны, и каждый распознает язык L тогда и только тогда,, когда L — {/} является контекстным.

Теорема (38). Классы 2D и ID линейноограниченных автоматовэквивалентны.

2.10.3. Автоматы с магазинной памятью

У автоматов с магазинной памятью, кроме бесконечной вправо входной ленты, есть специальная вспомогательная лента, также бесконечная вправо. При движении вспомогательной ленты влево на ней записываются вспомогательные символы, а при движении этой ленты вправо эти символы считываются и стираются. Первым всегда считывается последний записанный символ. В таком авто­ мате невозможно считать символ с ленты памяти, не стерев его.

157

и содержимое ее не меняется. Если же v = а — стирающий символ,

Входная последовательность считается приемлемой, если после того, как головка 1 считывает последний символ входной последо­ вательности, управляющее устройство переходит в одно из состоя­ ний выделенного подмножества F состояний *.

Для теории автоматов с магазинной памятью основной являет­

минированных автоматов с магазинной памятью совпадает с клас­

Однако обратное неверно, так как существуют языки типа 2 без неоднозначности, не являющиеся детерминированными.

2.10.4. Конечные автоматы

Наиболее простой моделью является автомат с конечным чис­ лом состояний (с конечной памятью) —конечный автомат.

Детерминированным конечным автоматом называется упорядо­ ченная система из пяти символов — «упорядоченная пятерка».

* Определение приемлемости в различных работах трактуется по-разному.

.158