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

6. Дана КС-грамматика G — (Ут , Vn, Р, S) с правилами

Определить сложность вывода терминальных цепочек, длине кото­ рых не превышает 10.

2.10.Абстрактные автоматы и их связь с языками

играмматиками

2.10.1.Основные понятия теории автоматов

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

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

Каждая лента ограничена слева, и крайняя левая ячейка всегда занята символом, не входящим в соответствующий алфавит.

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

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

а) замена обозреваемого символа другим с одновременным сдвигом головки вправо и переходом машины в другое состояние;

б) то же, но со сдвигом влево; в) то же, но без< сдвига.

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

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

Машина находится в заключительной ситуации, если на вход­

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

Языком, допускаемым машиной М, называется множество до­ пускаемых его цепочек.

Автомат в общей форме представлен на рис. 22.

150

•с некоторой структурой. Автомат делает элементарные шаги, за­ висящие от состояния конечного управления, символа, считываемо­ го входной головкой, и конечного объема информации из беско­ нечной памяти. За один шаг он может сделать следующее:

Хп

конечное

упродление

Уо\У,\ Уг

Рис. 22

1)изменить состояние конечного управления;

2)передвинуть входную головку на одну клетку в любом на­ правлении или оставить ее на месте;

3)изменить бесконечную память.

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

В начале конечное управление автомата находится в некотором начальном состоянии при некотором начальном содержании бес­ конечной памяти и с входной_головкой у метки левого конца.

Условимся знаками С и 5 обозначать левую и правую метки концов соответственно и будем предполагать, что они не содержат­ ся ни в каком алфавите, если это не оговорено специально.

Множество автоматов с «одинаковой» структурой бесконечной памяти образует семейство автоматов. Семейство имеет четыре класса автоматов: односторонних детерминированных, односторон­ них недетерминированных, двусторонних детерминированных и

двусторонних недетерминированных. Сокращения эти классы обо­ значаются соответственно ID, IN, 2D, 2N.

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

Остановимся более подробно на законах функционирования ав­

ходной сигнал y(t) может появиться либо раньше, либо позже это­

нутой—от состояния s(t), в которое автомат переходит в текущий момент времени, и входного сигнала x(t).

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

S ( 0 = ? ( s ( * - 1 ) , x(t));

которые определяют закон функционирования этих автоматов, а автоматами второго рода называют автоматы, закон функциониро­ вания которых задается уравнениями.

152

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

Покажем теперь, каким образом определить отображение, ин­ дуцируемое заданным конечным автоматом А. Как известно, авто­

мата А, установленного в начальное состояние, конечной последова­

рования автомата А, и наоборот.

Опишем классы автоматов, которые связаны с типами грамма­ тик в иерархии Хомского. -

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

15а