Элементы теории конечных автоматов

Определение Конечным автоматом Мили именуется огромное количество из 5 объектов , в каком:

- конечное непустое огромное количество (место) состояний,

- конечное непустое огромное количество входных сигналов (входной

алфавит),

- конечное непустое огромное количество выходных сигналов (выходной

алфавит),

- функция переходов,

- функция выходов.

ЗАМЕЧАНИЕ Автоматы могут задаваться:

1) в виде взвешенного орграфа (диаграмма состояний автомата)

либо в виде блок-схемы программки, реализующей поведение

автомата,

2) таблично (функции переходов и выходов задаются в Элементы теории конечных автоматов виде таблиц

либо совмещенной таблицы состояний).

ЗАМЕЧАНИЕ При графическом изображении автомата состоя

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

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

ются надлежащие значения входа и выхода (взвешенная дуга)

Разглядим особый класс автоматов.

Определение Пусть . Тогда

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

соответственно

,

,

и реализуем в виде Элементы теории конечных автоматов логических схем (ЛС) с входами и соответст венно выходами (рис.2.17). Составим из их ЛС, соединив выходы левого блока с надлежащими входами правого и левого

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


ЗАМЕЧАНИЕ Цифровой автомат задается к тому же:

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

телей),

4) в виде логической схемы.

Случайный автомат можно воплотить как составную часть

цифрового автомата. Для построения последнего нам пригодятся

некие понятия.

ОпределениеПусть - конечное Элементы теории конечных автоматов огромное количество и . Тогда

инъективное отображение именуется кодировщиком

огромного количества , а сюръективное - декодировщиком огромного количества .

ЗАМЕЧАНИЕ Пусть - отображение конечного

огромного количества в конечное огромное количество и .

Тогда это отображение можно представить в виде композиции

, где - кодировщик, -

многофункциональный преобразователь и - декодировщик.

Область определения и область значений многофункционального

преобразователя по числу частей, вообщем говоря, больше

соответственно областей для отображения .

___

Определение Обозначим Элементы теории конечных автоматов алфавит, другими словами конечное множе

ство частей (букв), - огромное количество различных конечных

цепочек букв (слов) вида . Количество букв в слове именует

ся его длиной и обозначается . Операция составления 2-ух слов в одно именуется склеиванием (сцеплением, конкатена цией) этих слов. Если есть пустая цепочка, то .

Пример .

ЗАМЕЧАНИЕОгромное количество представляет собой полугруппу

относительно операции склеивания, потому что последняя обладает

свойством Элементы теории конечных автоматов ассоциативности: .

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

Определение Расширенными функциями переходов и выходов автомата именуются отображения , определяемые рекуррентными формулами:

.

Последующее замечание дает развернутый метод вычисления значений (представления) расширенных функций на слове.

ЗАМЕЧАНИЕ(характеристики расширенных функций)

1) .

2)

Определение Реакцией состояния автомата Мили называ ется вход-выходное Элементы теории конечных автоматов отображение , определяемое по правилу . Реакцией автомата именуется совокупа реакций всех состояний этого автомата.

ЗАМЕЧАНИЕРеакция состояния совпадает с сужением

расширенной функции выходов на огромное количество .

Назад, совокупа реакций всех состояний определяет

расширенную функцию выходов.

­­­­­_____

Определение Состояния автомата именуются эквива

лентными, если их реакции совпадают: , другими словами .

Определение Состояния автомата именуются эквива лентными, если их реакции совпадают словестно длины Элементы теории конечных автоматов :

.

Обозначение либо, что все равно,

Аксиома 12.61) Огромное количество состояний разбивается на

наибольшие классы эквивалентных состояний. Совокупа

таких классов обозначается .

2) .

3) Если , то .

4) (аксиома Хаффмана-Мили) . Другими словами, если

реакции совпадают словестно длины , то

состояния эквивалентны

Понятие эквивалентных состояний естественным образом обобщает

ся на состояния из различных автоматов, у каких схожи соответст

венно входные и выходные алфавиты. Это позволяет дать такое

Определение Два Элементы теории конечных автоматов автомата с схожими входными и выход ными алфавитами именуются эквивалентными автоматами, если каждое состояние 1-го из их эквивалентно некому состоянию другого автомата, и напротив.

ОпределениеАвтомат именуется приведенным (наименьшим либо сокращенным), если все его состояния попарно не эквивалентны.

СЛЕДСТВИЕСогласно аксиоме Хаффмана-Мили, начиная с

разбиения места все состояния, попавшие в один

класс, имеют схожие реакции Элементы теории конечных автоматов. Если отождествить все

состояния, попавшие в один класс, то получаем новый автомат,

который является приведенным по построению. Он эквивалентен

начальному автомату, что следует из определения.

Метод (построения приведенного эквивалентного

автомата). 1) По таблице выходов строим разбиение .

2) По таблице переходов поочередно строим разбиения ,

используя пункт 2) аксиомы. В силу пт 4) таких шагов будет не

более .

3) В Элементы теории конечных автоматов силу пт 3) 1-ое разбиение, для которого ,

определяет классы эквивалентных состояний.

_____

Определение Автомат Мили именуется частичным, если функции перехода либо выхода определены не везде. В данном случае в таблице состояний автомата ставят прочерки.

Для формулировки метода построения малого конечного автомата «покрывающего» случайный частичный автомат, нам пригодится ряд понятий.

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

слов

Определение Дополним алфавиты неопределенным симво лом «-». Слово покрывает слово той же длины, если выходит из подменой неких букв на прочерк. именуются совместимыми словами, если существует слово , покрывающее и и .

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

Метод (построения всех попарно совместимых состояний)

1) Различные пары состояний изображают в виде клеток. Клеточку вычеркивают, если хотя бы для одной буковкы . В невычеркнутую клеточку вчеркивают все те пара определенных состояний, в которые может перейти .

2) Во огромном количестве приобретенных таким макаром невычеркнутых клеток вычеркивают те, в которые вписаны Элементы теории конечных автоматов вычеркнутые на первом шаге пары.

3) Шаг 2) повторяется до того времени, пока будет что вычеркивать. Приобретенное огромное количество невычеркнутых клеток дает все пары совместимых состояний автомата.

Этот метод имеет приятный вид при .

ОпределениеОгромное количество попарно совместимых состояний

частичного автомата именуется группой сопоставимости.

ОпределениеКонечное число групп сопоставимости автомата именуется группировкой, если хоть какое состояние автомата попадает Элементы теории конечных автоматов хотя бы в одну из этих групп.

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

Пусть автоматы , имеют однообразные входные и выходные алфавиты.

ОпределениеСостояние автомата покрывает состояние автомата , если хоть какое слово, применимое к состоянию Элементы теории конечных автоматов , будет так же применимо к состоянию , а слово покрывает слово .

ОпределениеАвтомат покрывает автомат , если каждое состояние последнего покрывается неким состоянием автомата .

Приведем

Метод (построения покрывающего автомата)

1) Определяют все пары совместимых состояний.

2) Выписывают все состояния автомата в порядке возрастания

индексов. В этой последовательности вычеркивают все состояния,

несопоставимые с первым. Потом вычеркивают все состояния Элементы теории конечных автоматов,

несопоставимые с первым невычеркнутым. И т.д..

Невычеркнутые состояния составляют первую группу совмести

мости.

Составляют последовательность вычеркнутых состояний. Проде

лывая с ней то же самое, получают вторую группу сопоставимости.

Получение групп сопоставимости продолжают, пока есть что

вычеркивать. В итоге выходит группировка.

3) Если группировка не замкнута, то строят на ее базе замкнутую,

работая Элементы теории конечных автоматов с таблицей переходов и оставаясь во огромном количестве пар совме

стимых состояний. При всем этом или расширяют группы, совместимо

сти, или добавляют новые.

4) Группы сопоставимости приобретенной замкнутой группировки соста

вляют огромное количество состояний искомого покрывающего автомата. Его

строят, руководствуясь таблицей начального частичного автомата.

_____

Определение Приведенный автомат Мили именуется автоматом с конечной памятью, если есть такие число и Элементы теории конечных автоматов отображение , что

имеет место равенство . Меньшее число с

таким свойством именуется памятью автомата.

ЗАМЕЧАНИЕЕсли есть автомат с конечной памятью, то

будет

.

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

Аксиома 12.71)(Гилл)Если есть автомат с конечной

памятью, , то .

2) Автомат имеет конечную память и тогда только тогда, когда для

некого Элементы теории конечных автоматов не существует 2-ух равных вход-выходных путей

длины , оканчивающихся в различных состояниях: .

Из аксиомы следует таковой

Метод(вычисления памяти автомата)

Составим матрицу перехода автомата.

1) . Вычисляем , а по ней составляем огромного количества вход-

выходных путей длины : .

2) Если , то полагаем память . В неприятном

случае перебегаем к 3).

3) Если , то перебегаем к 1) и полагаем . В Элементы теории конечных автоматов случае

по аксиоме Гилла память автомата нескончаема.

_____

Разглядим одну разновидность автоматов Мили.

Определение Автомат Мили , у которого функция выходов задается в виде , где - отображение (называемое определяющим), именуется автоматом Мура. Другими словами функция выходов автомата Мура определяется только состоянием автомата, но не , как у автомата Мили, а состоянием , в которое он перебегает при подаче Элементы теории конечных автоматов буковкы .

Обозначение .

Определение Реакцией состояния автомата Мура именуется отображение , определяемое по правилу

ЗАМЕЧАНИЕКаждый автомат Мили порождает эквивалентный ему автомат Мура с числом состояний по правилу:

каждое состояние начального автомата заменяется на несколько

состояний в количестве, равном числу разных значений

функции выходов при переходе автомат в это состояние.

_____

Определение Автомат всегда находится в определенном состоянии Элементы теории конечных автоматов . Это состояние именуется исходным, а пара - инициальным автоматом.

ЗАМЕЧАНИЕКаждый автомат порождает

инициальных автоматов.

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

: A \ S : A \ S
(0,0) (0,0)
(0,1) (0,1)
(1,0) (1,0)
(1,1) (1,1)

При сложении Элементы теории конечных автоматов, к примеру, двоичных чисел и берем

поочередно пары одноименных разрядов

.

При помощи таблиц убеждаемся, что сумматор "перерабатывает" это слово побуквенно в слово .

Инициальные автоматы можно охарактеризовать одним

особым отображением.

ОпределениеПусть есть конечные алфавиты. Отображение именуется автоматным оператором, если оно обладает качествами:

1) ;

2) если у слов совпадают 1-ые букв: , и , то .

ЗАМЕЧАНИЕ 1Автоматный оператор Элементы теории конечных автоматов всегда реализуется в виде некого инициального автомата по правилу . Назад, каждый инициальный автомат порождает автоматный оператор по правилу

.

ЗАМЕЧАНИЕ 2Если автоматный оператор задан на одном слове , то при помощи метода покрывающего автомата строится

приведенный автомат, переводящий слово в слово .

ОпределениеСостояние инициального автомата именуется достижимым из , если .

СЛЕДСТВИЕ Состояние не достижимо из , если

.

Метод Элементы теории конечных автоматов (нахождения огромного количества достижимых состояний

инициального автомата)

1) Положим

.

По построению каждое следующее огромное количество содержит предыду

щее.

2) Потому что после первого совпадения все следующие множе

ства будут совпадать с и , то 1-ое совпа

дение произойдет при . Потому есть огромное количество

достижимых состояний.

ОпределениеИнициальные автоматы с ,

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

Для формулировки метода эквивалентности инициальных автоматов Элементы теории конечных автоматов нам пригодится

Определение Прямым произведением автоматов

именуется автомат , где

.

ЗАМЕЧАНИЕ Достижимость состояния из в

прямом произведении равносильна тому, что

.

Аксиома 12.8 (Мура) Инициальные автоматы

эквивалентны и тогда только тогда, когда для хоть какого достижимого

состояния инициального автомата имеет место равенство .

ЗАМЕЧАНИЕ Из определения достижимости следует, что если

из места состояний инициального автомата выкинуть все

недосягаемые состояния, то получится Элементы теории конечных автоматов инициальный автомат,

который будет эквивалентен начальному.

_____

Определение Параллельным соединением 2-ух автоматов с преобразователем инфы именуется автомат , функции которого определяются по правилу

,

.

Он имеет последующее схематическое обозначение

Пример Построим по ортогональным конгруэнциям автомата с таблицей (*) фактор-автоматы

.

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

,

преобразователем инфы

и функцией выходов

.

По условию . Отсюда и

.

В силу последнего равенства Элементы теории конечных автоматов приобретенное параллельное соединение эквивалентно автомату без выходов (*).

Определение Поочередным соединением (суперпозицией) 2-ух автоматов именуется автомат , функции которого определяются по правилу ,

.

ЗАМЕЧАНИЕПараллельное и последовательное соединения

автоматов являются личными вариантами каскадной композиции

2-ух и поболее автоматов.

Определение Декомпозицией автомата именуется представле ние его в виде композиции автоматов с более обычный структурой.

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

Определение Автомат с таблицей переходов

именуется триггером.

ЗАМЕЧАНИЕТриггер порождает три унарных отображения

места состояний : . Они

входят во огромное количество всех отображений вида , и это

огромное количество замкнуто относительно операции композиции отображе

ний. Оно именуется полугруппой триггера. Аналогично строится

полугруппа для случайного автомата без

выходов . Она именуется полугруппой автомата.

ОпределениеПодгруппа группы именуется обычной, если . Группа именуется обычной, если у нее Элементы теории конечных автоматов нет нетривиальных (= ) обычных подгрупп.

ОпределениеАвтомат именуется автоматом обычной группы, если его полугруппа является обычный группой.

Определение Группа разделяет полугруппу , если существует

гомоморфизм какой-нибудь полугруппы на : .

Имеет место

Аксиома 12.9(о декомпозиции конечного автомата)

1) Две ортогональные конгруэнции автомата без выходов

порождают параллельное соединения автоматов ,.

эквивалентное автомату .

2) Одна конгруэнция автомата без выхода Элементы теории конечных автоматов порождают

эквивалентный автомат, который является поочередным

соединением автоматов.

3) (аксиома Крона-Роудза) Конечный автомат можно представить в

виде каскадного соединения из триггеров и автоматов обычных

групп, которые делят полугруппу начального автомата.

ЗАМЕЧАНИЕ Для сотворения моделей событийно управляемых

систем (- конечных автоматов) и работы с ними в MATLAB есть пакет расширения Stateflow.

____

Преобразование инфы есть итог выполнения

некого метода Элементы теории конечных автоматов, при всем этом операционный автомат (ОА) реализует содержимое шагов метода, а управляющий автомат (УА) реализует порядок выполнения шагов.

Пример На этом принципе базирована работа микрокалькулятора.

ЗАМЕЧАНИЕ При проектировании автомата выделяют три

шага.

1) Начальной информацией на системном шаге являются совокуп

ность классов решаемых задач и характеристики грядущего автомата.

Строится композиция пар автоматов ОА и УА. Определяются их

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

2) На логическом шаге делается синтез ОА и УА в виде

логических схем. При всем этом для формализованного синтеза ОА

употребляется теория безграничных автоматов, для УА – теория

конечных автоматов. В последнем случае выделяются два шага:

а) шаг построения автоматного оператора (состоит из 3-х

подэтапов: а1) алгоритмический, а2) абстрактный, а3) кодирование

внутренних Элементы теории конечных автоматов состояний) и б) шаг структурного синтеза автомата

(реализация его в виде сети либо каскадного соединения элементар

ных автоматов).

3) На техническом шаге строится принципная монтажная схема

и готовится техно документация.


elementi-rinka-truda-tovar-spros-predlozhenie-cena.html
elementi-sfericheskoj-trigonometrii.html
elementi-sistemi-izmereniya-fizicheskih-velichin.html