Шпоры по теории автоматов

Билет №1

Определение ЦА. Основные понятия теории автоматов: ЦА конечные, синхронные, асинхронные, идеализированные, абстрактные, структурные. Абстрактная и структурная теория автоматов.

ЦА - устройство, предназначенное для преобразования цифровой информации, способное переходить под воздействием входных сигналов из одного состояния в другое и выдавать выходные сигналы.

ЦА конечны, когда множество входных и выходных сигналов, а также число входных и выходных каналов и множество состояний автомата конечны.

Синхронный ЦА – входные сигналы действуют в строго определенные моменты времени при Т=конст, определяемые генератором синхронизирующих импульсов, в которые возможен переход автомата из одного состояния в другое.

Асинхронный ЦА – Т <> конст и определяется моментами поступления входных сигналов, а переход автомата из одного состояния в другое осуществляется при неизменном состоянии входа.

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

Абстрактный ЦА - шестикомпонентный вектор S = {A,z,w,σ,λ,a1}, у которого: А- множество состояний автомата, Z – входные сигналы, W- выходные сигналы, σ- функция переходов, λ- функция выходов, а1 – начальное состояние автомата.

Структурный ЦА – учитывает структуру входных и выходных сигналов, а также его внутреннее устройство на уровне структурных схем.

Структурная теория ЦА изучает общие приемы построения структурных схем автоматов на основе элементарных автоматов.

Абстрактная теория ЦА – изучаются наиболее общие законы их поведения без учета конечной структуры автомата и физической природы информации.

Билет №2

Варианты ЦА: автоматы Мили и Мура, С-автомат, автомат без памяти, автономный автомат, автомат без выхода, управляющие и операционные автоматы, микропрограммные автоматы.

Автомат Мили – a(t+1) = σ (a(t), z(t)); w(t) = λ (a(t), z(t)); a(0) = a1, t= 0,1,2,...

Автомат Мура – a(t+1) = σ (a(t), z(t)); w(t) = λ (a(t)); a(0) = a1, t= 0,1,2,...

С-автомат: под абстрактным С-автоматом понимают математическую модель цифрового устройства, определяемую восьмикомпонентным вектором S = {A,Z,W,U,σ,λ1, λ2,a1}, где А- множество состояний, Z- входной алфавит, W- выходной алфавит автомата Мили, U- выходной алфавит автомата Мура, σ- функция переходов автомата, λ1- функция выходов автомата Мили, λ2- функция выходов автомата Мура, а1 – начальное состояние.

Автомат без памяти(КС): Алфавит состояний такого автомата содержит единственную букву, поэтому понятие функции переходов вырождается и становится ненужным для описания работы автомата, т.е. выходной сигнал в данном такте зависит только от входного сигнала того же такта и никак не зависит от ранее принятых сигналов.

Автономный автомат: В таком автомате входной алфавит состоит из одной буквы. Автомат задается четырьмя объектами: А, W, σ, λ с возможным выделением начального состояния а1. Если автомат конечен и число его состояний равно к, то среди значений а(1), А(2),…, а(к) найдутся повторяющиеся состояния. АА используются для построения генераторов периодических последовательностей, генераторов синхросерий и в других задающих устройствах.

Автомат без выхода: В таком автомате выходной алфавит содержит только одну букву. Автомат задается тремя объектами: А, Z, σ. Из функций, задающих поведение автомата, сохраняется лишь функция переходов.

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

Микропрограммные автоматы: Алгоритм записываемый с помощью микроопераций и логических условий, называется микропрограммой.

 

Билет №3

Автоматы Мили и Мура. С-автомат. Законы функционирования. Основные различия.

Автомат Мили – a(t+1) = σ (a(t), z(t)); w(t) = λ (a(t), z(t)); a(0) = a1, t= 0,1,2,...

Автомат Мура – a(t+1) = σ (a(t), z(t)); w(t) = λ (a(t)); a(0) = a1, t= 0,1,2,...

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

С-автомат: под абстрактным С-автоматом понимают математическую модель цифрового устройства, определяемую восьмикомпонентным вектором S = {A,Z,W,U,σ,λ1, λ2,a1}, где А- множество состояний, Z- входной алфавит, W- выходной алфавит автомата Мили, U- выходной алфавит автомата Мура, σ- функция переходов автомата, λ1- функция выходов автомата Мили, λ2- функция выходов автомата Мура, а1 – начальное состояние.

a(t+1) = σ (a(t), z(t)); w(t) = λ 1(a(t), z(t)); u(t) = λ (a(t)); a(0) = a1, t= 0,1,2,...

Отличие С-автомата в том, что он одновременно реализует две функции выходов λ1 и λ2, каждая из которых характерна для модели Мили и модели Мура в отдельности. От С-автомата легко перейти к автоматам Мили и Мура с учетом возможных сдвигов выходных сигналов на такт, аналогично тому, как возможен переход от автомата Мили к автомату Мура и наоборот. Много реальных автоматов работает по модели С-автомата.

Билет №4

Системы канонических уравнений (СКУ) и системы выходных функций (СВФ). Построение СКУ И СВФ для автоматов Мили и Мура.

СКУ и СВФ являются аналитической интерпретацией таблиц переходов и выходов или графов ЦА. СКУ определяет функции переходов ЦА, а СВФ определяет функции выходов ЦА.

Каждое состояние ЦА интерпретируется как событие, соответствующее множеству переходов в это состояние: As(t+1) = v Zf(t)&Am(t). Для сокращения записи СКУ и СВФ опускают знаки конъюнкции и времени t в правой части уравнения.

Для автомата Мили: СКУ: a1(t+1) = a1z1 v a2z2 v a4z2; a2(t+1) = a1z2; a3(t+1) = a3z1 v a4z2; a4(t+1) = a2z1 v a3z2

CВФ: w1(t) = a1z1 v a1z2; w2(t) = a2z2; w3(t) = a3z1 v a4z2; w4(t) = a4z1; w5(t) = a4z1 v a3z2

Для автомата Мура: a1(t+1) = a2z1 v a3z1; a2(t+1) = a4z2; a3(t+1) = a6z1; a4(t+1) = a3z2 v a2z2 v a1z2; a5(t+1) = a5z1 v a6z2; a6(t+1)= a4z1 v a5z2

СВФ: w1(t) = a1 v a4; w2(t) = a1; w3(t) = a5; w4(t) = a3; w5(t) = a6

Билет №5

Задание ЦА на стандартных языках: таблицы, графы и их аналитическая интерпретация – СКУ и СВФ. Условия однозначности и полной определенности.

Стандартные (автоматные) языки задают функции переходов и выходов в явном виде. Для того, чтобы задать автомат, необходимо описать все компоненты вектора S = {A,z,w,σ,λ,a1}.

Табличный способ: автомат Мили описывается с помощью двух таблиц: таблицы переходов и таблицы выходов. Таблица переходов задает функцию σ, таблица выходов – λ. Каждому столбцу таблицы поставлено в соответствие одно состояние из множества А, каждой строке – один входной сигнал из множества Z. На пересечении строки и столбца в таблице переходов, записывается состояние as, в которое должен перейти автомат из состояния am, под действием входного сигнала zf, т.е. as = σ(am, zf). На пересечении строки и столбца в таблице выходов записывается выходной сигнал wg, выдаваемый автоматом в состоянии am при поступлении на его вход сигнала zf, т.е. wg = λ(am, zf). Автомат Мура задается одной отмеченной таблицей переходов, в которой каждому столбцу приписаны не только состояния am, но еще и выходной сигнал wg, соответствующий этому состоянию, где wg = λ(am).

Граф: Ориентированный граф, вершины которого соответствуют состояниям, а дуги – переходам между ними. Дуга, направленная из вершины am в вершину as, задает переход в автомате из состояния am в состояние as.

СКУ и СВФ являются аналитической интерпретацией таблиц переходов и выходов или графов ЦА. СКУ определяет функции переходов ЦА, а СВФ определяет функции выходов ЦА.

Каждое состояние ЦА интерпретируется как событие, соответствующее множеству переходов в это состояние: As(t+1) = v Zf(t)&Am(t). Для сокращения записи СКУ и СВФ опускают знаки конъюнкции и времени t в правой части уравнения.

Условие однозначности: означает, что для любой пары (am, zf) задано единственное состояние перехода as и единственный выходной сигнал wg, выдаваемый на переходе.

Условие полной определенности: означает, что для всех возможных пар (am, zf) всегда указано состояние перехода и выходной сигнал.

Билет №6

Задание ЦА на языке граф схем алгоритмов (ГСА) и построение на его основе СКУ и СВФ.

ГСА – ориентированный связный граф, содержащий одну начальную (А0), одну конечную (Ак) и произвольное конечное множество условных Х={x1,...,xl} и операторных А = {А1,…,Ам} вершин. Любой алгоритм должен начинаться и заканчиваться символами начальной и конечной вершин. Начальная вершина не имеет входов, конечная – выходов. Конечная, операторная и условная вершины имеют по одному входу, причем входящая линия может образовываться слиянием нескольких линий. Начальная и операторная вершины имеют по одному выходу, а условная – два выхода, помеченных символами 1 и 0. Операторной вершине сопоставляется вполне определенный оператор Ам, символизирующий некоторые действия Yt. Yt – подмножество множества Y={y1, y2,..., yn}, называемого множеством микроопераций. Разрешается в различных операторных вершинах запись одинаковых подмножеств множества Y. Внутри условных вершин записывается один из элементов множества X={x1, x2, ..., xl}, называемого множеством логических условий. Разрешается в различных условных вершинах запись одинаковых элементов множества Х.

 

Билет №7

Задание ЦА на языке логических схем алгоритмов (ЛСА) и построение на его основе СКУ и СВФ.

Язык ЛСА является аналитической интерпретацией языка ГСА и может быть использован для более компактной формы записи алгоритма функционирования ЦА. Запись алгоритма на языке ЛСА представляет собой конечную строку, состоящую из символов операторов А = {A0, A1,...,Ak}, логических условий X={x1,...,xl} и верхних и нижних стрелок, которым приписаны натуральные числа. В некоторых случаях используются логические, которые всегда принимают нулевое значение, т.е. тождественно ложные логические условия ω (оператор ω). После оператора ω всегда производится переход по стрелке, которая стоит справа от него. Если в ЛСА имеются циклы из логических условий, то вводится пустой оператор Ae(Ye), отмеченный пустым выходным сигналом. Этот оператор помещают в ЛСА путем замены стрелки i, стоящей в начале петли из логических условий на следующую группу символов ЛСА: ω↑k↓iAe(Ye)↓k.

Билет №12

Минимизация полностью определенных автоматов Мили методом Ауфенкампа и Хона. Задача минимизации. Алгоритм. Пример.

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

Состояния am и as являются эквивалентными, если λ(am, ξ) = λ(as, ξ) для всевозможных входных слов ξ.

Алгоритм: 1. Находим последовательные разбиения п1, п2, …, пк, п_к+1 множества А на классы одно-, двух-, К-, К+1- эквивалентных состояний до тех пор, пока в каком-то (К+1) шаге не окажется, что пк = п_к+1.

2. В каждом классе эквивалентности разбиения п выбирается по одному состоянию, в результате чего получаем множество А’ состояний минимального автомата S’ = {A’,z,w,σ’,λ’,a1’} эквивалентному автомату S.

3. Для определения функции переходов и выходов автомата S’ в таблице переходов и выходов вычеркиваются столбцы, соответствующие не вошедшим в А’ состояниям. В оставшихся столбцах не вошедшие в множество А состояния заменяются на эквивалентные.

4. В качестве начального состояния а1’ выбирается состояние из множества А’, эквивалентное состоянию а1. В частности, удобно за а1’ принимать само состояние а1.

Билет №13

Минимизация полностью определенных автоматов Мура методом Ауфенкампа и Хона. Задача минимизации. Алгоритм. Пример.

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

Состояния am и as являются эквивалентными, если λ(am, ξ) = λ(as, ξ) для всевозможных входных слов ξ.

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

1. Находим последовательные разбиения п1, п2, …, пк, пк+1 множества А на классы одно-, двух-, К-, К+1- эквивалентных состояний до тех пор, пока в каком-то (К+1) шаге не окажется, что пк = пк+1.

2. В каждом классе эквивалентности разбиения п выбирается по одному состоянию, в результате чего получаем множество А’ состояний минимального автомата S’ = {A’,z,w,?’,?’,a1’} эквивалентному автомату S.

3. Для определения функции переходов и выходов автомата S’ в таблице переходов и выходов вычеркиваются столбцы, соответствующие не вошедшим в А’ состояниям. В оставшихся столбцах не вошедшие в множество А состояния заменяются на эквивалентные.

4. В качестве начального состояния а1’ выбирается состояние из множества А’, эквивалентное состоянию а1. В частности, удобно за а1’ принимать само состояние а1.

Билет №14

Алгоритм минимизации ЦА Мили с помощью таблицы пар. Задача минимизации. Алгоритм. Пример.

Алгоритм: