Logo GenDocs.ru

Поиск по сайту:  

Загрузка...

Лекции - Теория автоматов - файл 1.doc


Лекции - Теория автоматов
скачать (2918 kb.)

Доступные файлы (1):

1.doc2918kb.17.11.2011 06:46скачать

содержание
Загрузка...

1.doc

  1   2   3   4   5   6
Реклама MarketGid:
Загрузка...
Раздел I. Введение. Общие сведения о цифровых автоматах


Лекция 1. Основные понятия и определения.


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

Все схемы ЭВМ можно разделить на два больших класса:

  1. Класс логических или комбинационных схем (КС).

  2. Класс конечных автоматов.

В логических (комбинационных) схемах значение выходных сигналов в момент времени t однозначно определяется значениями входных сигналов в момент времени t1 t.

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

Технические вопросы синтеза комбинационных схем решаются с помощью аппарата математической логики. При этом используется самая простая часть математической логики, а именно, алгебра логики или Булева алгебра. Основным понятием в алгебре логики, на котором основывается её приложение к синтезу КС, является понятие Булевой или переключательной функции (ПФ).

Переключательной или Булевой функцией называется функция f(x1, x2, …, xn), способная принимать так же как и её аргументы x1, x2, …, xn только два значения 0 или 1.

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

^ Свойства переключательных функций.

  1. Любая ПФ n аргументов определена на 2n наборов.

  2. Число различных ПФ n аргументов конечно и равно .

Мы будим использовать аппарат алгебры логики к синтезу схем ЭВМ. Это использование основано на следующем: будем отождествлять значение ПФ с выходными сигналами КС, а ее аргументы – с входными сигналами. Тогда ПФ будет описывать процесс преобразования КС входных сигналов в выходные и аппарат Булевой алгебры можно применять при синтезе таких схем. Под синтезом КС будем понимать определение таких способов соединения нескольких простейших схем, называемых логическими элементами, при которых построеные схемы реализуют заданный алгоритм преобразования сигналов при заданном критерии качества. В качестве критерии оценки качества технической реализации заданного алгоритма обычно используют критерий сложности или быстродействия схем.

Общий вид КС можно представить следующим образом:





Схема имеет n входов и m выходов и следовательно реализуют m ПФ от n аргументов. Любая сколь угодно сложная КС строится из более простых схем, называемых логическими элементами.

^ Логическим элементом называется электронная схема, реализующая элементарную ПФ и имеющая количество входов, равное числу аргументов ПФ и только один выход.

В ЭВМ в основном используются логические элементы с одним или двумя входами, реализующие ПФ одного или двух аргументов. Поэтому задача синтеза КС заключается в том, чтобы из логических элементов построить любую сколь угодно сложную схему, реализующую заданный набор ПФ. Математически в алгебре логики этой задачи соответствует задача представления любой сложной ПФ через элементарные ПФ. При составлении сложных КС из логических элементов используют два приема:

1. ^ Последовательное соединение элементов.

2. Перестановка входов элементов.

Пусть имеется два логических элемента, реализующие ПФ f1(x1, x2) и f2(у1, у2). При последовательном соединении этих элементов получим схему, реализующую функцию уже трех аргументов:



Эта схема реализует функцию f3(x1,x2, y2), получаемую в результате постановки вместо аргумента y1 функции f2 (y1,y2) значение функции f1(x1,x2). Подстановка в функцию вместо ее аргументов других функций называется суперпозицией.

Таким образом, последовательному соединению логических элементов соответствует математическая операция суперпозиция.

Изменим порядок подключения входов элементов.



В этом случае схема реализует функцию f4(y2,x1,x2), которая в общем случае отличается от функции f3(x1,x2, y2). В математическом плане мы заменили одни аргументы ПФ другими.

Замена одних аргументов функции другими или изменение порядка записи аргументов называется подстановкой аргументов.

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

Рассмотрим ПФ от разного числа аргументов.


^ Переключательные функции одного аргумента.

Существует четыре различных ПФ одного аргумента, таблица истинности которых имеет следующий вид:



Х

f0(x)

f1(x)

f2(x)

f3(x)

0

0

0

1

1

1

0

1

0

1


Функция f0(x) называется константой нуля и обозначается f0(x)=0 при любом x.

Аналогично функция f3(x) и называется константа единицы т.е. f3(x)=1.

Функция f1(x) повторяет значение аргумента x и следовательно f1(x)=x.

Функция f2(x) принимает значение противоположное значению аргумента x. Эту функцию называют отрицанием (инверсией) переменной x и вводят для нее специальное обозначение f2(x)=. Черта стоящая над аргументом имеет смысл определенного функционального преобразования и называется знаком отрицания.

Логический элемент, реализующий функцию отрицания, называют элементом НЕ или инвертором и по ГОСТу обозначают следующим образом:



^ Переключательные функции двух аргументов.


Для двух аргументов существует четыре набора значений переменных и шестнадцать различных ПФ.


X1

X2

f0

f1

f2

f3

f4

f5

f6

f7

f8

f9

f10

f11

f12

f13

f14

f15

0

0

0

0

0

0

0

0

0

0

1

1

1

1

1

1

1

1

0

1

0

0

0

0

1

1

1

1

0

0

0

0

1

1

1

1

1

0

0

0

1

1

0

0

1

1

0

0

1

1

0

0

1

1

1

1

0

1

0

1

0

1

0

1

0

1

0

1

0

1

0

1


В шестнадцать ПФ входят также функции, которые зависят от меньшего числа аргументов. Таких функций в таблице истинности шесть:

f0(x1,x2)=0 – функция константа нуля.

F15(x1,x2)=1 – функция константа единицы.

F3(x1,x2)=х1,

F5(x1,x2)=х2,

F12(x1,x2)=,

F10(x1,x2)=.

Рассмотрим оставшиеся десять ПФ от двух аргументов.

Функция f1(x1,x2) называется логическое произведение или конъюнкция и обозначается: f(x1,x2)=х1*х2=х1^х2=х1&х2.

Таблица истинности этой функции совпадает с таблицей умножения двух одноразрядных двоичных чисел т.е. f1(x1,x2)=1 тогда, когда аргументы равны между собой и равны единице, в остальных случаях функция равна нулю. Логический элемент, реализующий эту функцию, называют элементом И или конъюнктором. Обозначение конъюнктора на функциональных схемах:



Конъюнкция легко обобщается на случае n аргументов, когда реализуется функция вида: f(x1,x2,…,xn)=x1*x2*…*xn. Функция конъюнкция n аргументов равна единице тогда, когда все аргументы равны единицы.

Функция f7(x1,x2) – называется дизъюнкцией х1 или х2 и обозначается f7(x1,x2)=x1vx2.

Дизъюнкция реализуется элементом, который называется элементом ИЛИ или дизъюнктором.

Сигнал на выходе дизъюнктора принимает нулевое значение только в том случае, если ни один из входных сигналов не имеет в данный момент времени единичное значение.



Функция f9(x1,x2)=x1~x2 – равна единице тогда, когда оба аргумента равны между собой. Это функция носит название логической равнозначности.



Функция f6(x1,x2)=x1x2 – логическая неравнозначность или сумма по модулю 2. эта функция принимает единичное значение тогда, когда х1≠х2. Второе название этой функции объясняется тем, что таблица истинности f6 совпадает с таблицей сложения двух одноразрядных двоичных чисел по модулю 2, т.е. 0+0=0, 1+0=1, 0+1=1, 1+1=0. Обобщим эту функцию на случай n аргументов. Такая функция принимает единичное значение тогда, когда число аргументов равных единице нечетно и равна нулю если число аргументов четно.




Функции f11(x1,x2)= и f13(x1,x2)= называются импликациями и читаются: если х2, то х1 для f11, или если х1, то х2 для f13.

Функция f11 принимает нулевое значение только тогда, когда х2=1, х1=0.



Функция f2(x1,x2)=x1x2 – читается: не верно, что если х1, то х2 и является инверсией функции импликации f13.

.

Функция f13:

.

Функция f14(x1x2)=x1/x2= называется штрихом Шеффера и является отрицанием функции конъюнкции. Элемент, реализирующий эту функцию, называется элемент И-НЕ и обозначается:

.


f8(x1x2)=x1↓x2=. Функция f8 – называется стрелкой Пирса и является отрицанием от дизъюнкции. Элемент, реализующий эту функцию, называется элемент ИЛИ-НЕ и обозначается:




Две последних функции играют очень важную роль в вычислительной технике, поскольку все остальные функции могут быть выражены через каждую из них.

Система ПФ {f1, f2,,…,fm}, из которых с помощью операций суперпозиции и подстановки можно получить любую сколь угодно сложную ПФ, называется функционально полной системой (ФПС) ПФ. Такие системы ПФ называют базисом.

Приведем примеры некоторых базисов:

  1. f=x1/x2

  2. f=x1↓x2

Первые два базиса называются универсальными. Кроме универсального базиса существует булев базис:

  1. f1=x1vx2

f2=x1&x2

f3=

  1. f1=x1x2

f2=x1&x2

f3=1 – базис Жигалкина

Возникает вопрос какие ПФ представляют наибольший практический интерес?

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


^ Логические элементы.

Среди систем элементов, выпускаемых промышленностью, наибольшее распространение получили логические элементы, реализующие операции: И-НЕ, ИЛИ-НЕ, И-ИЛИ-НЕ, а так же элементы булевого базиса.

В эту систему элементов входят как элементы универсального базиса: И-НЕ, ИЛИ-НЕ, так и комбинации операций булевого базиса: И-ИЛИ-НЕ.





Логические элементы характеризуются следующими параметрами:

  1. коэффициентом объединения;

  2. коэффициентом разветвления.

1. Коэффициент объединения. Из-за взаимных наводок в цепях передачи сигналов возникают помехи, которые суммируются при объединении нескольких цепей на одном элементе. Поэтому для исключения возможности появления недопустимо больших помех, налагаются ограничения на предельное число входных сигналов в одном элементе. Это число входов и называется коэффициентом объединения J.

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

Покажем процедуру разделения входов на примерах:

  1. Пусть необходимо реализовать в булевом базисе функцию от четырёх аргументов f=x1x2x3x4 при J=2.



  1. Пусть необходимо реализовать функцию f= в базисе И-НЕ при J=2.



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


2. Коэффициент разветвления обозначается F. Всякий реальный элемент обладает конечной нагрузочной способностью, не позволяющей подсоединить выход одного элемента к неограниченному числу входов других элементов. Нарушение нагрузочной способности приводит к искажению сигналов в схеме. Нагрузочная способность элемента характеризуется коэффициентом разветвления F, т.е. наибольшим количеством входов других элементов, которые можно подсоединить к выходу данного элемента. Если число входов элементов, подключаемых к выходу данного элемента больше F, то принимаются меры к разгрузке данного элемента. Разгрузка может выполнятся двумя способами:

  1. Дублированием выходного сигнала.

  2. Дублированием элемента.

Покажем, как производится разгрузка элементов на примерах:

Пусть F=4 и к выходу некоторого элемента необходимо подключить семь входов других элементов. Тогда для дублирования сигнала можно использовать два инвертора.





Пусть элемент имеет два выхода прямой и инверсный:



Недостаток этого метода заключается в увеличении задержки сигнала в схеме. От этого недостатка свободен способ разгрузки за счет дублирования элемента.



^ Раздел 2. Синтез цифровых автоматов без памяти

Лекция 2. Этапы синтеза

Будем рассматривать синтез КС, реализующих одну ПФ. Процесс синтеза КС на элементах заданного базиса разбивается на следующие этапы:

  1. Аналитическая запись ПФ в булевом базисе (запись в виде СДНФ или в СКНФ).

  2. Минимизация ПФ в булевом базисе.

  3. Представление полученного после минимизации выражения в заданном базисе (переход к заданному базису).

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


^ Минимизация ПФ в булевом базисе.

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

В процессе минимизации СДНФ получается последовательно в начале сокращенная ДНФ, далее тупиковая и минимальная.

Существуют различные методы минимизации ПФ, из которых чаще всего используются методы Квайна, Мак-Класки, Блейка-Порецкого, диаграмм Вейча и карт Карно. В принципе все эти методы являются равновидностями метода Квайна.


^ Метод минимизации Блейка-Порецкого.


Недостатком метода Квайна является то, что для его применения необходимо представить функцию в СДНФ. Процесс такого представления для функции с большим числом аргументов зачастую является весьма громоздкой задачей, т.е. было бы желательно найти возможность построения сокращенной ДНФ, не по СДНФ, а по произвольной ДНФ данной функции. Идея построения сокращенной ДНФ по произвольных ДНФ была предложена в работах А. Блейка и П.С. Порецкого и основывается на следующей лемме.

Лемма:

Если в ДНФ для данной функции f(x1,…,xn) входят две конъюнкции вида Ахi и B, то имеет место следующее равенство:


f=fvAB.

Доказательство леммы:

Запишем функцию f в следующем виде:


.


Из доказанной леммы вытекает метод построения сокращенной ДНФ. Этот метод заключается в том, что исходную функцию необходимо пополнить новыми членами вида АВ согласно лемме. После этого надо провести поглощения и вновь повторить пополнение ДНФ. Этот процесс необходимо производить до тех пор, пока будут возникать новые конъюнкции вида АВ. По окончании преобразований получаем сокращенную ДНФ. Процесс пополнения ДНФ осуществляется согласно лемме по формуле, которая называется операцией обобщенного склеивания:


Axi v B= Axi v B v AB.


В основе метода Квайна так же лежит операция склеивания, но другая, которая называется операцией неполного склеивания.

Операция неполного склеивания является частным случаем операцией обобщенного склеивания при А=В.


Axi v A = A v Axi v A.


Рассмотрим примеры:

  1. Найти сокращенную ДНФ для функции трех аргументов:


.

При использовании метода Блейка-Порецкого применяется операция поглощения, которую можно представить в виде х v xy=x.

  1. Пусть дана функция трех аргументов:



.


Табличный метод минимизации ДНФ.

Метод диаграмм Вейча или карт Карно.


Методы Квайна и Блейка-Порецкого являются аналитическими. В этих методах наиболее трудоемким является процесс отыскания склеивающихся между собой конъюнкций. Существуют методы, которые позволяют упростить поиск склеивающихся членов. Один из наиболее удобных методов минимизации ПФ от небольшого числа переменных основан на использовании диаграмм Вейча или карт Карно. Диаграмма Вейча представляет собой фактически таблицу истинности ПФ, которая представляется не в виде столбцов, а в виде специальных карт. Каждой клетке диаграммы соответствует определенный набор значений аргументов. Поэтому диаграммы можно рассматривать как графическое представление совокупности всех конституэнт единицы. При этом диаграмма строится таким образом, что склеивающиеся между собой конституэнты оказываются расположенными в соседних клетках, т.к. отличаются значением только одной переменной. Приведем примеры построения диаграммы Вейча и карт Карно для ПФ от разного числа аргументов.

^ Переключательные функции двух аргументов.



Диаграмма Вейча:



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


^ Переключательные функции трех переменных.





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

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


Переключательные функции четырех переменных.





  1. нарисуем схему в булевом базисе.

ДНФ:



КНФ:



Построим схему, реализующую функции f1 в базисе И-НЕ (штрих Шеффера). Для этого осуществим переход от булевого базиса к базису И-НЕ.




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


^ Лекция 3. Переключательная функция для пяти переменных.


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




^ Преобразование функции в минимальную конъюнктивную нормальную форму (КНФ).


Для того, чтобы получить выражение заданной ПФ в форме, содержащей минимальное количество букв, следует, кроме минимальной ДНФ получить также минимальную КНФ и выбрать ту из них, которая содержит меньшее число букв. Существуют различные методы минимизации КНФ. Рассмотрим один из таких методов основанной на минимизации функции и в переходе с помощью формулы де Моргана к функции f. При минимизации можно использовать все методы, которые применялись ранее при нахождении минимальной ДНФ. После получения минимальной ДНФ функции с помощью формул де Моргана переходят к минимальной КНФ функции f.

Рассмотрим пример:

Возьмем функцию четырех переменных:

f=v(4,14)


.


^ Минимизация не полностью определенных переключательных функций.


В ЭВМ иногда применяются КС, закон функционирования которых определен не полностью. В таких схемах некоторые комбинации сигналов на входы никогда не подаются. Эти комбинации входных сигналов называются запрещенными. Для запрещенных входных комбинаций выходные сигналы не определены, т.е. могут принимать любые значения 0 или 1. Поэтому при синтезе КС с не полностью заданным законом функционирования можно произвольно задать значение выходных сигналов для запрещенной комбинации входных сигналов, поскольку нормальная работа схемы при этом не нарушается. Обычно выходным сигналам на запрещенных комбинациях придают такие значения, при которых можно построить наиболее простую схему. Работа схем с запрещенными комбинациями входных сигналов описывается не полностью определенными ПФ, т.е. функциями, значения которых определены не на всех наборах аргументов. Поэтому минимизация не полностью определенных ПФ с помощью карт Карно сводится к такому до определению ПФ, при котором получаются группы с максимальным числом соседних единиц в каждой группе, а число таких групп минимально. При этом ПФ будет содержать минимум букв.

Пример:

Найти минимальную ДНФ и минимальную КНФ не полностью определенной ПФ от четырех переменных. Функция равна единице на наборах: f=v(2,12,13) и равна нулю на наборах: f=v(5,9,15). На остальных наборах функция не определена.




^ Минимизация систем переключательных функций.


Работа КС, имеющей n входов и m выходов, описывается системой m переключательных функций, каждая из которых определяет закон функционирования схемы по одному выходу.



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

Пусть дана система ПФ состоящая из трех ПФ от четырех аргументов




Раздел 3. Общая теория конечных цифровых автоматов с памятью.
Лекция 4. Основные понятия и определения.


В вычислительной технике в основном используется схемы двух классов: комбинационные схемы и цифровые автоматы. Отличительной особенностью комбинационных схем является наличие жесткой функциональной зависимости между выходным сигналом и входным:
y ( t ) = f ( x ( t )). Причем при отсутствии входных сигналов выходные сигналы также отсутствуют, поскольку такие схемы не имеют памяти. В отличии комбинационных схем схемы второго класса содержат в своем составе элементы памяти (запоминающие элементы). Эти схемы называются цифровыми автоматами (ЦА) или просто автоматами. В ЦА выходные сигналы в данный момент времени зависят не только от значения входных сигналов в тот же момент времени, но и от состояния схемы, которое, в свою очередь, определяется значениями входных сигналов, поступивших в предшествующие моменты времени. Введем основные понятия и определения.

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

^ Кодирование информации

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

Например: в алфавите X = (x1, x2), состоящем из двух букв, словами будут: x1, x2, x1x1, x1x2, x2x1,x2x2, x1x1x1 и т.д.

Наряду со словами, состоящими не менее чем из одной буквы, введем слово, не содержащее ни одной буквы, которое будем обозначать символом е и называть пустым словом или пустой буквой.

Математической моделью реального конечного автомата является абстрактный автомат, который имеет один входной канал и один выходной канал.

X(x1,…,xm)

--->

A(a0,...,an)

--->

Y(y1,…,yk)

Автомат функционирует в дискретные моменты времени, интервал, между которыми ^ Т называется тактом. При этом в каждый дискретный момент времени на вход автомата поступает одна буква входного алфавита, автомат переходит из одного состояния в другое и выдается одна буква выходного алфавита. В зависимости от того, как задается длительность такта Т, различают автоматы синхронного действия (T=const) и асинхронного действия (Tconst). Мы будем рассматривать, в основном, синхронные автоматы, функционирующие в дискретные моменты времени, которые можно обозначить целыми неотрицательными натуральными числами, t=0,1,2,3,…., имеющими смысл номера такта.

Для задания конечного автомата S необходимо задавать совокупность из пяти объектов: S(A, X, Y, d, l), где A = {a0,a1,a2,...,an}– множество внутренних состояний автомата, X = {x1, x2,…, xm} – множество входных сигналов (входной алфавит), xi – буква входного алфавита, Y = {y1, y2,…, yk} – множество выходных сигналов (выходной алфавит),

d - функция переходов, определяющая состояние автомата a(t+1), в котором автомат будет находится в момент времени (t+1), в зависимости от состояния автомата a(t) и входного сигнала x(t) в момент времени t, то есть a(t+1) = d [a(t), x(t)],

l - функция выходов, определяющая значение выходного сигнала y(t) в зависимости от состояния автомата a(t) и входного сигнала x(t) в момент времени t, т.е. y(t) = l[a(t), x(t)].

Автомат работает следующим образом: в каждый момент времени t он находится в определенном состоянии a(t) из множества А возможных состояний. Причем в начальный момент времени t = 0 он всегда находится в состоянии a(t = 0) = a0. В момент времени t автомат воспринимает входной сигнал x(t), выдает выходной сигналу y(t) = l[a(t), x(t)] и переходит в следующее состояние a(t+1)=d[a(t), x(t)]. Другими словами абстрактный автомат каждой паре символов a(t) и x(t) ставит в однозначное соответствие пару символов a(t+1) и y(t). Такие автоматы называют детерминированными. На преобразование информации в детерминированных автоматах наложены условия.

^ Условия преобразования информации в детерминированных автоматах:

1. Любое входное слово, длинною l букв, преобразуется в выходное слово той же длины.

2. Если каждый раз перед подачей входных сигналов автомат находится в одном и том же состоянии, то при совпадении в двух входных словах первых l1 букв, в выходных словах первые l1 букв также совпадут.

Кроме детерминированных автоматов существуют вероятностные или стохастические автоматы, в которых переход из одного состояния в другое под воздействием случайных или детерминированных входных сигналов происходит случайно. Работа таких автоматов описывается уже матрицей переходов d, элементами которой являются вероятности переходов из одного состояния в другое. Нами будут рассмотрены, в основном, детерминированные автоматы.

Применяемые на практике автоматы принято разделять на два класса - это автоматы Мили и автоматы Мура, названные так по имени американских ученых, которые впервые начали их изучать. Функционирование автоматов строго подчиняется определённым законам (законы функционирования автоматов). Законы функционирования автоматов описываются системами уравнений:

Автомат Мили:

 

a(t + 1) = d[a(t),x(t)]

 

y(t) = l[a(t),x(t)]

 

t = 1,2,3… 

Автомат Мура:

 

a(t + 1) = d[a(t),x(t)]

 

y(t) = l[a(t)]

 

t = 1,2,3…

Отличительной особенностью автоматов Мили является то, что их выходные сигналы зависят как от состояния автомата, так и от значения входного сигнала. В автоматах Мура выходные сигналы y(t) в каждый дискретный момент времени t однозначно определяются состоянием автомата в тот же момент времени и не зависят от значения входного сигнала.


^ Способы задания автоматов

Чтобы задать конечный автомат S, необходимо описать все элементы множества S = {A, X, Y, d, l} . То есть необходимо описать входной, выходной алфавиты и алфавит состояний, а также функции переходов d и выходовl. При этом среди множества A = {a0,a1,…, an} необходимо выделить начальное состояния a0, в котором автомат находится в момент времени t = 0. Существует несколько способов задания работы автомата, но наиболее часто используются табличный и графический.

^ Табличный способ

При табличном способе задания автомат Мили описывается двумя таблицами: таблицей переходов и таблицей выходов.

Таблица переходов

xj\ai

a0



an

x1

d(a0,x1)



d( an,x1)









xm

d( a0,xm)



d( an,xm)

Таблица выходов

xj\ai

a0



an

x1

l( a0, x1)



l( an, x1)









xm

l( a0, xm)



l( an, xm)

  Строки этих таблиц соответствуют входным сигналам x(t), а столбцы – состояниям. На пересечении столбца ai и строки xj в таблице переходов ставится состояние as = d[ ai, xj], в которые автомат перейдет из состояния ai под воздействием сигнала xj; а в таблице выходов – соответствующий этому переходу выходной сигнал yg = l[ ai,xj]. Иногда автомат Мили задают совмещенной таблицей переходов и выходов, она в некоторых случаях более удобна.

Совмещенная таблица переходов и выходов автомата Мили.

xj\ai

a0



an

x1

d(a0,x1)/

l(a0,x1)



d(an,x1)/

l(an,x1)









xm

d(a0,xm)/

l(a0,xm)



d(an,xm)/

l(an,xm)

Задание таблиц переходов и выходов полностью описывает работу конечного автомата, поскольку задаются не только сами функции переходов и выходов, но также и все три алфавита: входной, выходной и алфавит состояний. Так как в автомате Мура выходной сигнал однозначно определяется состоянием автомата, то для его задания требуется только одна таблица, которая называется отмеченной таблицей переходов автомата Мура.

Отмеченная таблица переходов автомата Мура

yg

l(a0)



l(an)

xj\ac

a0



an

x1

d(a0,x1)



d(an,x1)









xm

d(a0,xm)



d(an,xm)


В этой таблице каждому столбцу приписан, кроме состояния ai, еще и выходной сигнал y(t) = l(a(t)), соответствующий этому состоянию. Таблица переходов автомата Мура называется отмеченной потому, что каждое состояние отмечено выходным сигналом. Примеры табличного задания автоматов Мили и Мура.

Автомат Мура:

yg

y2

y1

y1

y3

y2

xj\xj

a0

a1

a2

a3

a4

x1

a2

a1

a3

a4

a2

x2

a3

a4

a4

a0

a1

Автомат Мили:

xj\ai

a0

a1

a2

a3

x1

a1/y1

a2/y3

a3/y2

a0/y1

x2

a0/y2

a0/y1

a3/y1

a2/y3

По этим таблицам можно найти реакцию автомата на любое входное слово.

^ Для автомата Мура:

 

x1

x2

x2

x2

x1



 

a0

a2

a4

a1

a4

 

 

y2

y1

y2

y1

y2

 

 

 

 

 

 

 

 

^ Для автомата Мили:

 

x1

x2

x2

x2

x1



 

a0

a1

a0

a0

a0

a1

 

y1

y1

y2

y2

y1

 

 Графический способ

При графическом способе задание автомата осуществляется с помощью графа. Этот способ основан на использовании ориентированных связных графов. Вершины графов соответствуют состояниям автомата, а дуги – переходам между ними. Две вершины графа ai и as соединяются дугой, направленной от ai к as, если в автомате имеется переход из ai в as, то есть as = d(ai, xj). В автомате Мили дуга отмечается входным сигналом xj, вызвавшим переход, и выходным сигналом yg, который возникает при переходе. Внутри кружочка, обозначающего вершину графа, записывается состояние.

^ Граф для автомата Мили




Граф для автомата Мура




^ Частичные автоматы

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

Пример таблицы переходов и выходов частичного автомата Мили

xj\ai

a0

a1

a2

a3

x1

a1/y1

a3/y3

a2/y2

a2/y1

x2

- / -

- / -

a0/y4

a0/y2


^ Лекция 5. Элементарные автоматы

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

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

^ Теорема о структурной полноте формулируется следующим образом:

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

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

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

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

^ Элементарные автоматы

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

  1. Элементарные автоматы являются автоматами Мура с двумя внутренними состояниями;

  2. Автомат выдает два различных выходных сигнала, соответствующих двум его внутренним состояниям. В дальнейшем состояния автомата и его выходные сигналы будем обозначать одной буквой Q и кодировать цифрами 0 и 1;

Элементарные автоматы могут иметь в общем случае несколько физических входов, на каждый из которых могут подаваться сигналы, закодированные цифрами 0 и 1.

В качестве элементарных автоматов в вычислительной технике используются, в основном, триггеры различных типов. Здесь рассмотрены некоторые из них.
  1   2   3   4   5   6



Скачать файл (2918 kb.)

Поиск по сайту:  

© gendocs.ru
При копировании укажите ссылку.
обратиться к администрации
Рейтинг@Mail.ru