Реферат: Шпоры по теории автоматов
Билет №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.