3Etap (Лекция), страница 3

3.2.{Xi} 0,1, i= 1,m;{Yi} 0,1, j= 1,k.Автомат Ас состоит из комбинационной логической схемы (КЛС) иэлементов памяти.3.2. Основные понятия абстрактной теории автоматовДадим содержательное определение автомата:Под автоматом понимается математическая модель или устройствопреобразования входной дискретной информации в выходную дискретнуюинформацию с учётом предыстории.Общееопределение:Абстрактныйавтомат–дискретныйпреобразователь входных букв (сигналов) x множества X в выходные буквыy множества Y,поведение которого <входная буква x , выходная буква y >зависит от предистории, выражением которой являются конечное множествосостояний.Входная информация – это последовательностьx(1),x(2),…,x(t),x(t+1), … ,которая называется входным словом.Выходная информация – это последовательностьy(1),y(2),…,y(t),y(t+1), … ,которая называется выходным словом.Автоматфункционируетвабстрактномавтоматномвремени.Последовательность моментов времени можно представить как t=0,1,2,3,…T,…∞ .

Отсчет времени можно представить как тиканье часов.В каждый момент времени t он находится в определённом состоянииS(t) из множества состояний S = {S1,S2,…,Sn} .В каждый момент времени автомат способен воспринимать входнойсигнал x(t), т.е. произвольную букву входного алфавита X,и выдаватьсоответствующий выходной сигнал y(t), т.е.

некоторую букву выходногоалфавита Y.Причём выходной сигнал зависит не только от входного сигнала вданный момент времени, но и от некоторой предыстории, т.е. от сигналов,которые поступали на вход автомата ранее. Состояния как раз и отражаютнекоторую память о прошлом. В связи с этим абстрактные автоматыназываютавтоматамиспамятью.Дадимформальноеопределениеабстрактного автомата.Определение 3.1. Абстрактный автомат – это конструкция вида:< X,Y,S,φ,ψ >,где: X = {X1,X2, … ,Xm} - входной алфавит;Y = {Y1,Y2, … ,Yk} - выходной алфавит;S = {S1,S2, … ,Sn} - множество внутренних состояний.φ и ψ- автоматные операторы:φ - оператор переходов φ: S*x S;ψ – оператор выходовψ: S*x Y.Типизация конечных автоматовОпределение 3.2. Автомат называется конечным, если конечнымножества X,Y,S.Пусть Sf =S, где Sf – финитные состояния.Определение 3.3.

Автомат называется распознающим, если автоматпереходит в финитное состояние. Это говорит о том, что на вход былиподаны определённые слова р.Определение 3.4. Если автомат представляет собой конструкцию<Y,S,φ,ψ>, то он называется автоматом без входа (генератор).Определение 3.5. Конечный автомат, для которого указано начальноесостояние So S, называется инициальным.Определение3.6.АвтоматнымотображениемАназываетсяоднозначное соответствие входных слов длины р с выходными словамидлины q , когда длина р равна длине q, т.е. |p|=|qI.Определение 3.7.

Автоматным оператором называется абстрактнаяконструкция (заданная аналитически, таблично, графически), определяющаяавтоматное отображение.Определение3.8.Абстрактныйавтоматназываетсядетерминированным, если для него выполняется условие однозначностидля функции переходов:однознач.S*XS.Условие однозначности заключается в том, что автомат, находящийся внекотором состоянии, под действием входного сигнала не может перейтиболее чем в одно состояние. Применительно к графу автомата это означает,что из любой вершины не могут выходить две и более дуги, отмеченныеодним и тем же входным сигналом.Недетерминированныйконечныйавтомат:S*XSS.Для недетерминированного автомата возможны переходы сразу в несколькосостояний.Определение 3.9. Если для недетерминированного автомата переходывзвешены вероятностями, то такой автомат называется вероятностным.Определение 3.10.

Абстрактный конечный автомат I рода, автоматМили (G.Mealy), – это конструкция, определяемая рекуррентно:для оператора φI: s(t)= [x(t),s(t-1)],для оператора ψI: y(t)= [x(t),s(t-1)],где t=1,2,…- такты,S- множество внутренних состояний s.Определение 3.11. Абстрактный конечный автомат Мура (E.Moore) –конструкция, определяемая рекуррентно:для оператора φI: q(t)=[x(t),q(t-1)],для оператора ψI: y(t)=[q(t)],где t=1,2,…- такты,Q – множество внутренних состояний q.Определение 3.13. Абстрактный автомат называется частичным, еслиего функция φ переходов или функция ψ выходов, или обе эти функцииопределены не для всех пар значений аргументов S и X.Вотличиеотчастичныхавтоматовсуществуютполностьюопределённые автоматы, у которых функция φ переходов и функция ψвыходов определены для всех пар значений аргументов S и X.Определение 14.

Конечный автомат, для которого указано начальноесостояниеSo S, называется инициальным.3.3 . Способы задания автоматов.Существуют 4 способа задания автоматов:аналитический,табличный,графический,матричный.1) Аналитический способ был рассмотрен ранее и состоит в заданииконструкции < X,Y,S,φ,ψ,S0>2) Табличный способ.Функционирование автомата Мили описывается двумя таблицами:таблицей переходов и таблицей выходов.

Строки таблиц соответствуютвходным буквам, столбцы - состояниям, причём крайний левый столбецобозначается начальным состоянием. На пересечении столбца Si и строки хj:- в таблице переходов ставится состояние Sk, в которое автоматпереходит из состояния Si под воздействием буквы хj;- в таблице выходов ставится соответствующая этому переходувыходная буква yt.Пример: Задан автомат Мили А1 таблично:φ Таблица переходовS0S1S2x1S2S0S0x2S1S2S1ψТаблица выходовS0S1S2x1у1у1у2x2у1у2у1Для частичных автоматов на месте неопределённых состояний ивыходных букв ставятся прочерки.Часто для описания автомата Мили используется совмещенная таблицапереходов/выходов, которая приведена ниже для автомата Мили А1.А1S0S1S2x1S2/ у1S0/ у1S0/ у2x2S1/ у1S2/ у2S1/ у1Совмещённая таблица переходов/выходовНа пересечении столбца Si и строки хj записывается состояние Sk, вкоторое переходит автомат А1из состояния Si под воздействием входнойбуквы хj.

При этом на выходе автомата А1 выдаётся выходная буква yt.Автомата Мура задаётся одной так называемой отмеченной таблицейпереходов. Для автомата Мура в отличии от автомата Мили множествосостояний будем обозначать буквой Q={q1,q2, . . . , qn}. Каждому столбцутакой таблицы кроме состояния gi приписана ещё и выходная буква yt,соответствующая этому состоянию. Т.е.

каждое состояние в таблицеотмеченоещеисоответствующейемувыходнойбуквой.соответствуют входным буквам. На пересечении gi столбца иСтрокихj строкизаписывается состояние gk, в которое переходит автомат из состояния gi подвоздействием входной буквы хj.А2-у1у3у2у3q0q1q2q3q4х1q1q4q4q2q2х2q3q1q1q3q33) Графический способ.Графический способ основан на использовании направленныхграфов. Вершины отождествляются с состояниями автомата, а рёбра – свходными сигналами. Если входной сигнал Xi вызывает переход изсостояния Sj в состояние Sk , то ребро проводится от вершины Sj к вершинеSk и обозначается буквой Xi.

Однако такой граф задаёт только функциюпереходов.Для задания функции выходов автомата Мили,ребра графаобозначаются не только входными, но и соответствующими им выходнымибуквами.В случае автомата Мура выходная буква приписывается вершинеграфа.Пример: Построить графы автоматов А1 и А2А1А2---Soх1/y1х2/y1х1/y2S2q4х1/y1S1х2/y2qoх2y3х2х2/y1х2х1х1y2х1y1qх1х2х1q3q2y3х2Пример.

С помощью модели Мили описать работу автомата,управляющего включением и выключением электрической лампы. Лампазажигается и горит, если в помещении находится человек. В помещениимогут находиться два человека.Х = { a, a }вошёлАвтомат Миливышелa/*Y = { *, 0}S1a/*S2горит выключенаa/0S0S1S2aS2/ *S3/ *-a-S1/ 0S2/ *S3a/*Пример: Используя графовую модель Мура синтезировать автомат,описывающий работу D-триггера.X= { 0, 1 },Y= { 0, 1 }.Автомат Мура0011000q1q12001q0-Для автомата Мура всегда в явном виде указывается начальноесостояние q0.Вых. -01q0q1q20q1q1q11q2q2q2Вх4) Матричный способ.При этом способе используется автоматная матрица (квадратная), вкоторой как строки так и столбцы обозначены состояниями.

Элементамматрицы, стоящим на пересечении Si – строки и Sj столбца, служитмножество входных сигналов, вызывающих переход автомата из состояния Sв состояние Sj , и множество выходных сигналов, выдаваемых на этомпереходе.Для автомата Мура элемент матрицы состоит из множества входныхбукв, а выход описывается с помощью вектора.Пример: Построить автоматные матрицы для A1 и А2А1x2 /y1х1 /y1-х1 /y2 х2 /y1А2x1 /y1-x1-x2-y1х2 /y2-x2--x1y1--x2--x1y3x2 -x1--y2x2x1--y3-3.4 Эквивалентность автоматов.Определение 3.15.