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

3). Как следует из рис. 3, сигналы, входюпне в предысториюИ„,(, могут входить и в ряд других предысторий, в частности сигнал Х (» ) вхпдит всего в й предысторий. и» а лг л» а«» ю«-» а «ч Рыс. 3. Временная диаграмма, поясняющая по- натка конечной предыстории Все это означает, что в зависимости от предыстории Н„ ~ ддя одной и той же поспедовательности входных снгнапов из 4 смгналов, начинающейся с снгнапа й' (М ) (данае такие 7 последовательности входвых сигвапов будем обозначать как )( ~), могут быть получены отличающиеся па этом квтервапе л и произвольном числе моментов времени друг вт друга поспедоватепьвости выходных сигвадов Ул й(кх обозвачевие вво дится аиапогичво обозввчеикю эходвйх поспедоватепьвоствй).

В предепьвом спучве дпя любой фкхскроваквой поспвдоватедь костиХл ~ каждой пРвдыстоРик У 1 бУдвт соотввтство;вать своя выходввя последоватепьвость У, ~. Одвакв ка практике чаще спедует ожидать того, что многие предыстории Й, й при фкксапии входвой последоватепьвости будут вызывать йоявпввие одинаковых выходных поспедоватепьиостей. Более того, многие предыстории могут вызывать одиваковый выходкой эффект ие топько ка каких-то отдвпьщях входных поспвдеввтелз костях, по и ва всем их мвожестве.

Такие предысторик мошко считать эквкввкекткыми по их впиявкю ва выход устройства, т.е. ва реадкзуемую им фуикпкю обработки ивформвпяя. Существенно, что эквивапевтвость предысторий ив зависят от моментов времени, отпосктепьно которых они рассматриваются, что определяется неизмеиностью формы зависимости (1.2) при изменениях и .

Такам образом, все мпожество возможных предысторий, которое может включать в себя до Я предысторий, может быть разбито иа некоторое чиспо (обозначаемое далее как 1 ) иепересекаюшихся подмножеств ~у,каждому кз которых теперь можво поставить в соответствие некоторый индекс ), дпя которого выпоппяетсяУв. ~ к. 1. Отметим, что с точки зрения впиявия на поспедующее поведеиие устройства все эквивапентвые дредысторик, входящие в одво подмножество Яу, веразпичкмы между собой и поэтому впоппе могут представляться именем самого подмножества 8.

Но тогда каждому моменту времеви дпя рассматриваемого устройства может быть поставпево в соответствие некоторое значение Я( 1 ), подобно эходиому и выходному сигналам,соотввтствевяо Х (г ) к у (е ). В отличке от поспедпих ~Й,) пепосредс.,аенко пе пабпюдвется, характеризуя собой зафиксированную устройством его предысторию. Можно сказать, что Я(~л ) представляет собой хак бы ввутренпее состояние устройства. Зависимость (1.2) теперь может быть переписана в иной форме: Однако получепвое выражение пе в подвой мере эквивалентно (1.2), так как в пем отсутствует опредепение Я.

Это определение может быть сделано бвз труда. Так как переход 8 от едкой предыстории к другой связав только с удапевием из предыдущей ее первого эпемеита и добавлением вского зпаче- ккк вхсдпого скгкапа в качестве вв поспеднего элемеята(что хорошо вкдво из рис. 3), то вся трудиость закпючается топь- хо в отношении предыдущей и поспедующей предысторий к соответствующим иодмиожвствам $„. Это позволяет опреде- пкть зависимость дпя изменений Ы к~г„„)=р~хи ), г~'г„)), ( 1.4) Проведепшэе рассмотревие позвопипо в описании исспедуе- мого устройства перейти от выражения (1.2), включавшего в себя предысторию устройства в явкам виде, к выражениям (1.3) к (1.4), испопьзующям эведвпкое понятие внутреннего состояния, в хомпэхтиой форме отражающее всю предысторию иди же, мошко сказать, рекпизуюшее фуякпию памяти устрой- ства. .Выражение (1.2) принято называть рекуррептяым бупвв- сккм выражвикем (2), в то время квх выражвккя (1.3) и (1.4) описывают исследуемое устройство в так вазываемой авто- матной форме.

Спвдувт подчеркнуть, что выражения (1.3) и (1А) были получвиы дпя простейшей формы рассматриваемого устройства, когда его вход и выход опксываютск едивствввными двоичкы- мк переменнымк. Нетрудно убвдктьск в том, что пк ва едком кз этапов вывода это ограничение ве играло приипипиапьвой роди и было введено только дпя простоты рассуждений. Из етого следует, что форме выражений (1.3) к (1.4) может быть попучена и дпя более общего скучая, когда переменные х и и уже пе будут простейшими двоичкымя переменными, а смогут принимать значении из пехоторых заданных множеств. Выше в тексте впервые было употреблено понятие .авто- матного описания.

Можно далее добавить, что устройство,до- пускающее автоматное описакие, само относится к классу тах называемых автоматов. Опредвпеяие точпого смысла этих тер- мявоэ требует обсуждения ряда понятий и иекоторых формаль- ных правип. 1.3. Формапизапия исходных понятий теории автоматов 1.3,1. Абст актиые и п кхдадкые аспекты тес ии автома- ййй Как и бопьшияство иву кых дкспиппик, теория автоматов содержит двв основные части: общие основы теории и совокупность прикладных паправпепий.

Общак теория автоматов входит в состав широхого научного направпевкя — кибернетики. 9 Предметом обшей теории автоматов явпмются тах называемые абстрактные автоматы. Понятие абстрахтиоге автомата влредепявтсм достаточно шнроко. В настоящее время примите очи тать, что абст актный автомат - это матвматачвскам идеапазадиа реального объекта (технической кпм биопоги каской системы), перерабатывающего некоторую информедаю, представ дающую собой впредепенные входные возмущвним.

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

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

1.3.2. Автоматное в емм. В выражениях (1 3) к (1.4),описывающих соответственно изменвнка выходных снгнапов апк внутренних состояний в зависимости. от рада аргументов,связываютсм между собой значенка некоторык переменных, заданных в последовательные моменты времена. Этот ряд поспэдоватепьных вепичии дпя абстрактных автоматов носит наименование автоматного времени. Дпи абстрактных автоматов это время может быть лишено какого-пибо конкретного физического смысла, для реальных автоматов это автоматное время всегда отображается в некоторую реальную физическую вепичиву, которая может и не быть действительным временем. Это может быль номер испытания некоторого обьвкта, номер обращения к нему, нахонец, даже упорадоченнов место его расположения.

Естественно, однако-, что наиболее часто дпм конкретных автоматов автоматное время этпбражавтсм в рнд значений реального физического времени. В етом отображении спвдует отметкть одну существенную особенность. Автоматное время наибопее удобно, как. и ранее, представлять в виде ряда натуральных чисвп: 1, 2> 3 ~ д~ " 10 При отображении этого ряда ~а физическое время могут дейСтвозать разпкчкые закономерности в завксимостн от некоторых свойств реапьмых автоматов.

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

Требуется, однако, соблюдение двух условий: 1) в отображении должно сохраниться отношение предшествовакня значений автоматного и реапьного времени, т.е. поспедующему автоматному времени должно соответствовать н последующее реальное время; 2) дпя реального автомата минимальный интервап между двумя моментами времени, на которые отображаются два последоватепьных значения автоматного времени, не допжен быть меньше некоторой граничной величины, определяемой физическими свойствамм реального автомата. Итак, реальные автоматы асинхронного типа не подвэргаютсм внешней принудительной синхронизации. Интервал между сигналами, поступающими на эти автоматы, может быть ограничен только снизу за счет конечной скорости физических процессов, протекающих в реальных автоматах. 1.3.3.