Студентам > Рефераты > Шпоры по теории автоматов
Шпоры по теории автоматовСтраница: 1/2
Билет
№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
Алгоритм минимизации ЦА Мили с помощью
таблицы пар. Задача минимизации. Алгоритм. Пример.
Алгоритм:
|
Главная
Документация
Файлы
Информация
