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

клетки. Вначале на ленте записана входная цепочка так, что в каж­ дой клетке ленты содержится по одному символу цепочки. На­ чальный символ записан в крайней левой клетке, а все клетки той части ленты, которая расположена правее последнего символа за­ писи входной цепочки, пусты, т. е. в каждой из этих клеток записан «пустой» символ Л . Головка в начальный момент расположена

против крайней левой клетки

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

Допустимой, или приемлемой, называется входная последова­ тельность, обладающая следующим свойством: когда головка вос­

жество, являясь множеством цепочек символов из конечного алфа­

возникает способ сопоставления автоматов, языков и грамматик.

Для конечных автоматов множество L(A) выделяется известной теоремой Клини.

Теорема 41 (Клини). Для любого конечного автомата А множе­ ство L(A) допустимых последовательностей является регулярным, т. е. языком типа 3. Эта теорема объясняет, почему языки типа 3 называются языками с конечным числом состояний.

Детерминированным конечным автоматом с двумя лентами на­

ющая отображение 5 X X в У, т. е. X : S X X—»-У.

Интерпретация этого автомата представлена на рис. 26. Кроме входной ленты автомат имеет бесконечную вправо выход­

ную ленту, которая может перемещаться только в одну сторону — справа налево. Каждый очередной такт в клетке ленты печатается

159

символ, и лента сдвигается на одну клетку. Этот автомат назы­ вается последовательной машиной, или автоматом Мили. Автомат

Представление множества входных последовательностей в не­ детерминированном автомате понимается следующим образом. Множество входных последовательностей U допустимо в недетер­ минированном конечном автомате, если для каждой последова­ тельности этого множества найдутся два таких состояния Si Sg и 5i F и такой вариант работы (т. е. такие конкретные, значения функции б), что последовательность U переводит автомат И3| состоя­ ния Si в состояние Sj.

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

Конечный автомат с двумя лентами является недетерминиро­ ванным, если при одной и той же ситуации, характеризуемой па­ рой (Si, Xj), возможно конечное число вариантов его действия. Сле­ довательно, такой автомат может одной входной цепочке поставить в соответствие конечное множество выходных цепочек.

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

сдвинуться входная лента: —1 соответствует сдвигу на одну клетку вправо, + 1 — с д в и г у влево на одну клетку, 0 — лента остается не­ подвижной.

160

Множество L(A) всех допустимых последовательностей такого автомата определяется следующей теоремой.

Теорема 43 {Рабина, Скотта, Шепердсона). Для каждого дву­ стороннего автомата А можно эффективно определить такой ав­ томат В, который имеет то же множество приемлемых входных по­ следовательностей, что и автомат А. Поэтому множество L(A) ре­ гулярно, т. е. является языком типа 3.

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

Т а б л и ц а 4

В этой таблице использованы следующие обозначения. Стрелка о- означает, что язык тогда и только тогда типа i (i = О, 1,2, 2D , 3), когда он представим в автомате типа Ah (k = 1, 2, . . . , 6). Стрелка —>- означает, что если язык представим в автомате Л&, то он является языком типа i. Стрелка -*- означает, что если язык яв­ ляется языком типа i, то найдется автомат типа Аи, в котором он представим.

Т а б л и ц а 5

161

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

В табл. 5 собраны аналогичные понятия из этих трех областей и указаны соответствующие им понятия общей теории языков.

Упражнения:

1. По каждому из приводимых ниже конечных автоматов А по­ строить праволинейную КС-грамматику, порождающую .множество

Т(А).

множество всех цепочек, содержащих одинаковое число входящих символов а и Ь.

( a 1 S 0 ) - * S 1 ;

(«А) -> 5 ь

( * A ) - *S a ;

( * i S a ) - S a ;

Построить грамматику, порождающую этот язык, и определить

еетип.

6.Построить линейноограниченные автоматы, допускающие языки:

162