учебное пособие - Конечные автоматы - Силин В.Б., Мельников Б.С., страница 3

Входные выходные и в т енине пе еменные.В спо- собах опасання переменных абстрактных и реапьных автоматов имеются определенные отпячим. Так в реальных автоматах, встречающихся в цифровых электронных устройствах, переменные, как правнпо, носят бинарный характер, при этом чнспо таких бинарных входов а выходов может быть не ограничено. Анапогнчным образом представпяются и внутренние переменные реальных автоматов. Можно, в частности, считать, что переменные реальиьск автоматов представпяют собой много- мерные величины с двоичными компонентами (ркс. 4,а). обоБ а) о МВ оннбоныб оыооди Рис. 4. К определению входных и выходных переменных реального (а) и абстрактного (б) автоматов (1.6) При описании абстрактных автоматеэ, напротив, исходят иэ того, что они имеют тоньке по одному входу и выходу (рис.

4,6). ЧиСло значений, которое при этом может прикн- мать входная и выходная перебинбоныа онабм мецнвя (анапогкчно к ввутревняц), не ограничкваэтск. Испопьзуетси специапьиди терминология дня описания зна Рообьнын бБСТРББТНый ББтомот оБ теист чений переменных абстрактных Б) автоматов. Для каждой из переменных етк знвчекия при.а нато называть симвоиами. Все скмволы, относящиеся х каждой нз переменныхб образуют соответствующий аифавкт.

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

1.3.4. Ал витное п еоб рвание. Преобразоваиикб представленные ракее выражениями (1.3) и (1.4), могут бъгп теперь,сформупированы бонзе четко в новых терминах. Будам говорить, что абстрактный автомат обпадает двумя харахтеристкчесхими функциями, опредепеввыми на трех абстрактных алфавитах - входном Х, выходном У и внутреннем Я в абстрактном автоматном времеви: функцией выходов уй)= ~(Х(Ю, БЯ) (1.6) и функцией переходов БН )=~ЯХМ,БЯ), э которых 1 -1, 2, 3, ...; ХсХ; ус У, ус Я. 12 Пркведенкые харахтеристичесхие фу'вкцкя определяют так наээбваеббзе алфавитное ( посимвопьнэе) преобразование всех абстрактных переменных во времени.

1.3.6. Оп еделенне конечного абст хтного автомата. Приведенные вылив рассуждения .поэвопяют таперь непосредственно сформулировать общее определение конечного абстрахтвагэ автамата. Конечный абст ный автомат - это дискретный преобраэоватець информации, дпя которого в автоматном временк б 1, 3, 3, ... заданы конечные апфавкты входных сигналов Х (хб ~х, 1абал), выходных скгвапов У ( у,.с У, ~в~'~ю) ивнутреииих состояний 8 (Бйс ~, боя- б) к функционирование которого описывается характеристическими фунхдкямк выхздов и входов у®- Г(г(й, у(Б)); Б(Б" ) у(Х(о) Б(Б» о о с фиксированным начальным состоянием Б (Б с 1 ). Оцредепеввмй таким образом конечный аботрахтный автомат носит наименование автомата Минц.

Существует и нескопьхо иное определение, отпкчающееся от приведенного только видом функции выходов: У®= Г(Б(И) (1.7) все остальные компоненты определения сохраняютси неизменными. Определенный таким образом автомат носит наименование автомата Мура. Далее будет показано, что дпя каждого автомата Мили может быть получек эквцвапентный ему автомат Мура и наоборот. Отметим, что выше бып рарэдецен только абстрахтный конечный автомат, но не реапьвый. Очевкдво, может быть сформупировано соответствующее определение и дпя реального автомата, хоти при этом и могут возцкхнуть некоторые затруднения иэ-эа напичия средк реальных автоматов кх син.— хронных и асинхронных вариантов. Видимо, бопее простым будет подход к опредепекию конечных реацьных автоматов,основанный на том опредекеник абстрактного автомата, который был приведен ранее (см. с.10 ).

Конечным реальным автоматом будэм называть тот реапьнай автомат, математичесхой модепью которого будет конечный абстрактный автомат. 1 3.6. Полностью о деленные к частичные автоматы. В обоих выражениях (1.6) и -(1.6) в качестве кх аргументов находатск паРы символов ж и Бц, В соответствии с опРеделе- 13 вием конечного абстрактного автомата число разпичыых симвопов и,. составпяэт и, а 5 — ~, тахим образом, мвкснмапьное число возможных пар х,. 5й составпяет а ъ .

Тогда конечный абстрактный автомат считается полностью определенньйь(, если зависимости (1.6) и (1.6) определены для всех л ~ пар х, 5й, если же дыя части таких пар выражения (1.6) и (1.6) не определены, то автомат ивляется не полностью опредепенным, ипи, ках говорит, частичным. Интерпретация частичного автомата иногда вызывает затрудненны. На первый взгляд, не должно быть никаких обстоятепьств, на основании которых на автомат, находящийся в некотором внутреннем состоянии, нельзя было бы подать тот иди иной входной сигнал. В то же время отсутствие опредепенностн для какой-либо пары х,. 5А говорит именно о том, что одновременное существование тахих значений ыедолустнмо, а значит, при существующем гй действительно невозможно появление входного сигнала х 1 Объяснение этого обстоятельства закпючается в спедую щем.

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

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

1,3,7. С ва нее ц еоб азование. Введенные в пп. 1.2, 1.3.4 и 1.3.6 формальные средства описания поведения конечных абстрахтных автоматов позвопици в компахтной форме представить посимвопьный (алфавитный) процесс преобраззж- 14 ния входных сигналов. Однако основным назыачением конечных автоматов является обработка информации, представпиющей собой не отдецьные символы, а поспедоватепьности сигнапрв, развернутые во времени. Дпя описания таких процессов в теорик конечных автоматов используется специальная термииопогия.

Тах, вместо цонятия поспедоватепьности сигыалев, характерного дпя реальных объектов, используется понятие снова, состоюцего из символов соответствующего апфавита. Слово обладает длиной„ равной чиспу входящих в ыеге символов. Отсчет снова может начинаться с любого момента времени. Говорят о входщ>м сцене Х41 длкны ~., о выходном слове 1й ~ и о слове внутренних сбстояний уй,, дпя которых выполниетсн Х(1 ~хй),хй'~),...хй ~-~Д; (1.3) У,',-~Уй), Уй ~), У(~ 4-5)~, (1.3) 5 (5/Ю 1 ). 5( ' ж )).

(1 10) У Захономеоности преобразования входного снова.)(~ ( в снова выходное У1~ и внутренних состояний 5А 1, называемого словарным преобразованием, полностью основываются на рассмотренном ранее ацфавитнэм преобразовании. йпя словарного преобразования нет компактной аналитической формы, оно осуществпяетсн обычно алгоритмическим образом, путем посцедоватепьного выполнения адфавитного преобразовании ыад символами входного снова и снова внутренних состояний.

2. ФОРМЫ ПРЕДСТАВЛЕНИЯ АБСТРАКТНЫХ КОНЕЧНЫХ АВТОМАТОВ 2.1. Общие т ебования х мам и с едствам и едставпеыия абст актных конечных автоматов Содержащиеся в пц. 1.2, 1.3.4 н 1.3.6 соотношения (1 3), (1.4), (1.6), (1 6) и (1.7), опредепяя функционирование абстрактно о конечного автомата, сами, тем не менее,по своей коыкретной форме остались еще не определенными. Это, в частности, явипось причиной того, что до сих пор ые было рассмотрено ии одного примера абстрактного хонечыого автомата.

Приводившиеся ранее записи функций выходов и цереходов тоцько лишь декцаряронали необходимость соответствующей функционапьной зависимости между нарами значений аргументов х (1), 5 (й) и функций у (с), 5(1~ /). Таким образом, этн зависимости цишь обозначали переход тыла хЮ, уЮ-час), уЫ. ). (1 11) Однако до сих пор еще не было установлено, какими конкретными средствамн првдставляетсн эта функциональная связь. Этк формы и дредстонт обсудить ниже. Првдваритвпьне сфермулнруем основные требования, которым деюкны удовпетвв— рить формы и средства представления абстрахтиык кзиечиык автоматов, 1.